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

Question

Проблема заключается в следующем:

Путем замены каждой из букв в слове CARE с 1, 2, 9 и 6, соответственно, мы образуют квадрат числа: 1296 = 36^(2). Примечательно то, что, используя те же цифровые подстановки, анаграмма RACE также образует квадратное число: 9216 = 96^(2). Мы будем называть CARE (и RACE) квадратной парной параграмм и дополнительно указывать, что ведущие нули не разрешены, и другая буква не может иметь то же цифровое значение, что и другая буква.

Использование слова.txt (правый щелчок и «Сохранить ссылку/цель как ...»), текстовый файл размером 16 КБ, содержащий почти две тысячи общих английских слов, найти все квадратные пары анаграмм (палиндромное слово НЕ считается анаграммой самой).

Что представляет собой наибольшее квадратное число, образованное любым членом такой пары?

ПРИМЕЧАНИЕ. Все сформированные анаграммы должны содержаться в данном текстовом файле.

Я не понимаю карту CARE до 1296? Как это работает? или все перестановочные сопоставления, предназначенные для судебного разбирательства, т. е. все буквы в 1-9?

Answer 1

Одним словом: да, все перестановки необходимо судить.

Answer 2

Все присвоения цифр буквам разрешены. Таким образом, 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) представляет собой квадратную пару параграмм.

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

Answer 3

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

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

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

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

Answer 4

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

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

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

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

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

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