Задача 98. Проект Эйлера

Вкратце: да, все перестановки нужно перепробовать.

Допускаются любые присвоения цифр буквам. Таким образом, C=1, A=2, R=3, E=4 были бы возможным назначением... за исключением того, что 1234 не является квадратом, так что это было бы бесполезно.

Может быть, другой пример поможет прояснить ситуацию? Если мы присвоим A=6, E=5, T=2, то TEA = 256 = 16² и EAT = 625 = 25². Итак, (TEA=256, EAT=625) — это квадратная пара слов анаграммы.

(Тот факт, что разрешены все присваивания цифр буквам, не означает, что пробовать все такие присваивания — лучший способ решить проблему. Может быть какой-то другой, более умный способ сделать это.)

Если вы проверяете все замены букв на цифры, вы ищете пары квадратов со свойствами:

• иметь одинаковую длину
• иметь те же цифры с количеством вхождений, что и во входной строке.

Быстрее найти все эти пары квадратов. Есть 68 квадратов с длиной 4, 216 квадратов с длиной 5, ... Фильтрация всех квадратов одинаковой длины по верхним свойствам сгенерирует «небольшое» количество пар, которые являются решениями, которые вы ищете.

Эти данные являются «статическими» и не зависят от входных строк. Его можно вычислить один раз и использовать для всех входных строк.

Хм. Как это поставить. Люди, составившие проект «Эйлер», обещают, что для каждой проблемы существует решение менее одной минуты, и есть только одна проблема, которая, я думаю, может не выполнить это обещание, но это не так.

Да, вы можете переставить цифры и попробовать все перестановки со всеми квадратами, но это будет очень большое пространство для поиска, и вряд ли это будет (ТМ) правильно. В общем, когда вы видите, что ваш «взгляд» на проблему приведет к поиску, который займет слишком много времени, вам нужно искать что-то еще.

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

Существует множество новаторских решений, но первое, о котором вы думаете, особенно то, о котором вы думаете, когда Project Euler описывает проблему, скорее всего, будет неправильным.

Итак, как вы можете подойти к этой проблеме? Вероятно, слишком много перестановок, чтобы их рассматривать, но, может быть, вы сможете что-то понять с сопоставлениями и сравнением сопоставлений?

(Пытаясь не выдать все это.)