Блог

Главная - Вопросы по программированию - Использование перестановок в Java для решения уравнения

Использование перестановок в Java для решения уравнения

#java #permutation #equation #backtracking #brute-force

#java #перестановка #уравнение #отслеживание возврата #перебор

Вопрос:

Для данной задачи мне предоставляются два числа, которые таким образом приведут к определенному результату:

 num1   num2 = result

Однако эти числа будут «закодированы», так что, например, ввод может быть:

 ab   bc = acd

Числа могут иметь любую длину до 9 цифр.

Моя задача — создать эффективный метод, позволяющий определить, сколько возможных решений имеет каждый ввод, или если это невозможно.

Я решил эту проблему, создав класс с именем Number (в java), который имеет букву (тип char) и числовое значение (int), а затем я преобразовал каждое число в массив этого нового номера класса, чтобы я мог легко проверить их текущие значения.

Однако я не совсем уверен, как подойти к этой проблеме с возвратом.

Я знаю, что я должен начать сравнивать единицы из number1 и number2, затем десятки и так далее, на каждом «уровне» выбирая только те случаи, в которых сумма будет логичной, так, например, в приведенном выше примере для единиц b = 2 и c = 3 это будет толькоимеет смысл, если d = 5, и я мог бы отбросить все остальные случаи, в которых d!= 5 для этих двух ранее существовавших значений.

Мне сказали, что можно охватить все эти перестановки, используя только два цикла: один для циклического перебора возможных чисел [от 0 до 9] и один для охвата всех букв / переменных, но я не совсем понимаю, как это можно сделать!

Если бы мне пришлось это представить, я думаю, я мог бы думать об этом как

 for cycle ( through "columns" from the rightmost up to the leftmost column of the shortest number)
  for cycle( for numbers 0 to 9?)

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

Комментарии:

1. Каковы ваши входные данные? Каков ваш результат? ваша проблема не ясна. Вы говорите, что число может состоять из 9 цифр, значит a ли это, что может быть 1236548 ?? Или буква равна цифре?

2. @majid hajibaba: каждая буква представляет собой одну цифру. Уравнение может содержать до девяти букв в каждом операнде или сумме. Для OP: в прошлом я использовал грубую силу для решения проблем такого типа, потому что уравнение может содержать не более 10 разных букв, представляющих 0-9, и не более 27 полных букв (три целых числа 10 ^ 9). Вложенные циклы с крошечными числами выполняются быстро.

Ответ №1:

Вот один алгоритм, который должен работать.

Давайте возьмем ваш пример уравнения:

 ab   bc = acd

  1. Определите количество уникальных символов в уравнении. В вашем примере это будет четыре (a, b, c, d).

  2. Чтобы перебрать все возможности, мы собираемся создать цикл. Минимальное значение этого цикла равно 10 ^ 3 или 1000. Максимальное значение этого цикла равно 10 ^ 4 или 10000. Количество уникальных символов в уравнении определяет степени 10, которые вы будете использовать. Максимальный максимум равен 10 ^ 10, что больше, чем an int . A long будет работать.

  3. Внутри итерации разделите индекс на N цифр. В вашем примере это будет 4 цифры. Поскольку мы выполняем итерации от 1000 до 9999 включительно (10 000 исключаются), все значения индекса будут иметь 4 цифры.

  4. Убедитесь, что N цифр уникальны. Дубликатов нет. Это устранит большинство значений индекса в начале.

  5. Подставьте цифры в уравнение и проверьте, действительно ли уравнение. Если это так, сохраните уравнение в a List<String> .

  6. Выведите List значения или решение не найдено после завершения итерации.