Задать вопрос
SmerxDimas
@SmerxDimas
Начинающий разработчик на Java
java

Как реализовать алгоритм комбинаторики в программе?

Здравствуйте, недавно наткнулся на такую задачу, подумал, что она очень лёгкая, но ошибся. Задача по комбинаторике. Прикладываю текст в приложение. Суть кратко говоря в том, чтобы подобрать 9 чисел в диапазоне от 1..20 не повторяя. Чтобы сумма определённых номеров чисел равнялась сумме других. То есть цикл
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 10
1 2 3 4 5 6 7 8 11
1 2 3 4 5 6 7 8 12
И такие проверки далее и далее, пока мы не найдём совпадение.
Пытался сделать цикл для подбора, но он повторяет значение: 
for (int a = 1; a < 21; a++) {
            for (int b = 1; b < 21; b++) {
                for (int c = 1; c < 21; c++) {
                    for (int d = 1; d < 21; d++) {
                        for (int e = 1; e < 21; e++) {
                            for (int f = 1; f < 21; f++) {
                                for (int g = 1; g < 21; g++) {
                                    for (int h = 1; h < 21; h++) {
                                        for (int y = 1; y < 21; y++) {
                                            circle[1].value = a;
                                            circle[2].value = b;
                                            circle[3].value = c;
                                            circle[4].value = d;
                                            circle[5].value = e;
                                            circle[6].value = f;
                                            circle[7].value = g;
                                            circle[8].value = h;
                                            circle[9].value = y;

Задача ОООЧЕНЬ зацепила, а опыта, к сожалению, не хватает. Надеюсь выручите5c4875cec9596366747703.jpeg
  • Вопрос задан
  • 424 просмотра
3 комментария
Подписаться 2 Средний 3 комментария
Пригласить эксперта
Ответы на вопрос 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Сначала переведите картинку из залачи в числа. Вот есть у вас 20 точек, пронумерованные от 1 до 20, как-то. Выпишите все 12 групп (9 окружностей и 3 диаметра). Будет у вас 12 наборов по 5-6 номеров. Запишите их в программе константными массивами.

Затем делайте перебор рекурсией: У вас в глобальном массиве или списком в параметре будет набор пока не поставленных чисел. Сначала проверьте, что вы не сделали уже 2 группы с разной суммой. Пройдитесь по всем 9+3 группам, если какая-то целиком уже заполнена, то записываете ее сумму в переменную для окружности или диаметра, соответственно. Если перед записью там уже была другая сумма -то вы нашили противоречие. В этом случае надо просто вернуться из текущей рекурсии назад.

Если противоречий нет и вы все 20 чисел поставили - выводите ответ.

Иначе - перебираете, какое число ставите в первую незаполненую точку циклом. Ставите туда число и вызываетесь рекурсивно.

Надо только аккуратно уже поставленные на картинке числа в нужные места поставить. Для этого их, во первых, не включйте в список непоставленных чисел, во вторых на заполенные позиции ставьте уже записанное там число.

Просто перебирать все перестановки (наборы массивов из чисел без повторений) и в конце проверять суммы, как вы хотите сделать - будет слишком долго. Их 21! (факториал) - это дофига слишком.
Ответ написан
2 комментария
2 комментария
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Вакансии с Хабр Карьеры
Lead Java
Bell Integrator • Ульяновск
До 400 000 ₽
Lead Java
Bell Integrator • Хабаровск
До 400 000 ₽
Java-разработчик
ДАЛЕЕ
от 200 000 ₽
Ещё вакансии
Заказы с Хабр Фриланса
Нужен аудит и настройка Яндекс.Директ и вебаналитики в Метрике
16 апр. 2024, в 12:04
7000 руб./за проект
Разработать фронтенд для небольшого веб приложения
16 апр. 2024, в 12:04
20000 руб./за проект
Поправить flutter приложение и загрузить в PlayMarket
16 апр. 2024, в 11:52
1000 руб./в час
Ещё заказы