Проект Эйлера (43 задача). Среди миллиардов чисел найти пан-цифровые и к тому же удовлетворяющие условиям делимости подстрок… Легко.
Узнать больше в телеграм-канале: ProjectEuler++
Число 1406357289, является пан-цифровым, поскольку оно состоит из цифр от 0 до 9 в определенном порядке. Помимо этого, оно также обладает интересным свойством делимости подстрок.
Пусть d1 будет 1-й цифрой, d2 будет 2-й цифрой, и т.д. В таком случае, можно заметить следующее:
- d2d3d4=406 делится на 2 без остатка
- d3d4d5=063 делится на 3 без остатка
- d4d5d6=635 делится на 5 без остатка
- d5d6d7=357 делится на 7 без остатка
- d6d7d8=572 делится на 11 без остатка
- d7d8d9=728 делится на 13 без остатка
- d8d9d10=289 делится на 17 без остатка
Найдите сумму всех пан-цифровых чисел из цифр от 0 до 9, обладающих данным свойством.
Измеряем время работы программы
Первый способ, приходящий на ум – это «брут-форс»:
Делать все это мы не будем. Достаточно лишь понимать, что таким способом понадобится перебрать(и дважды проверить!) около десяти миллиардов чисел.
Второй способ – сразу формировать пан-цифровые числа и проверять только их. Описание генератора пан-цифровых чисел приводилось ранее, потому не буду повторяться.
Для того чтобы можно было сравнить трудоемкость расчета с предыдущим вариантом, уточню, что количество перестановок из десяти цифр (от 0 до 9) равно 10!, т.е. 3628800. Потому и пан-цифровых чисел нужно будет перебрать около трех миллионов, что уже на три порядка меньше. К тому же и проверка понадобится только одна (потому что числа уже пан-цифровые).
Данным способом ответ задачи находится примерно за 0.5 секунды (решение можно посмотреть здесь).
Можно ли еще сократить вычисления? Можно.
Идея алгоритма в том, чтобы получать числа, удовлетворяющие условиям делимости сразу.
Подстрока d8d9d10 согласно заданию делится на 17. Три числа подстроки образуют число 999 максимум. Потому существует только 999 / 17 = 58 вариантов чисел, удовлетворяющих этому условию делимости.
Кроме того, часть из этих чисел тоже нужно будет исключить. К примеру, 119 делится на 17 нацело, однако не удовлетворяет условию о пан-цифровом числе, потому что в нем повторяются две цифры.
По каждому числу подстроки далее считаем следующую подстроку (d7d8d9) по ее делимости (на 13). При этом подставляться будут только те числа, что еще не использованы – т.е. семь чисел вместо десяти.
Например, d8d9d10 = 289 – делится на 17. Проверяем следующую подстроку. Имея d8d9 = 28, мы перебираем d7 – числа 0, 1, 3, 4 ,5 ,6 ,7 (d10 = 9 уже использовали). Если среди шести вариантов найдено подходящее, то переходим далее влево.
Поскольку при каждой найденной цифре, количество оставшихся (из которых можно выбирать) уменьшается. Потому общее количество чисел, которые необходимо проверить, будет равно:
В итоге видно, что количество проверяемых цифр сократилось еще на порядок. К тому же их нет необходимости подвергать каким либо дополнительным проверкам. Числа сразу будут обладать необходимыми свойствами делимости и будут пан-цифровыми.
Для удобства работы и читаемости кода создаем необходимые структуры данных.
Перечисление name содержит в себе названия подстрок от d1d2d3 до d8d9d10. На самом деле это будут просто числа от 0 до 7, что очень удобно, потому что это позволит обращаться к массивам чисел, не засоряя себе мозг их индексами.
Структура «подстрока» включает в себя:
Структура «пан-цифровое число» содержит массив из 8 подстрок. Кроме того есть два массива для цифр самого числа. В одном цифры заносятся по порядку, в котором число «набирается» с конца к началу, другой служит для того, чтобы цифры не повторялись.
Цифры в него записываются по своему индексу:
Уже привычно разбил функцию main() на два скриншота.
Как было описано выше в описании алгоритма, подбор подстрок начинается справа.
Число в подстроке d8d9d10 увеличивается до тех пор пока не удовлетворится условие делимости (в данном случае – на 17). После этого подбор переходит влево и начинается подбор цифры d7 в подстроке d7d8d9.
Каждый раз когда подстрока удовлетворяет условию делимости, цифра заносится в массивы пан-цифрового числа, а подбор переходит влево – к следующей подстроке.
Если перебрав все возможные варианты подстрока не проходит проверку на делимость, поиск переходит вправо – к предыдущей подстроке. Цифра в массивах пан-цифрового числа обнуляется, как и сама подстрока. Начинается подбор следующей подстроки, начиная с того места, где закончился подбор в предыдущий раз.
Подбор подстрок пан-цифрового числа, заканчивается когда, крайне левая подстрока d2d3d4 удовлетворила условию делимости (на 2).
После этого цифры пан-цифрового числа преобразуются в число ответа. При этом множитель fact определяет регистр каждой цифры.
Цифра, не занесенная в массив (d1) является самой старшей и определяется по массиву занятости цифр. Например:
Единственная незанятая цифра имеет индекс в этом массиве – 4 и будет самой старшей цифрой пан-цифрового числа.
Перебор вариантов подстрок прекращается окончательно, когда крайне правая подстрока превысит максимально возможное значение – 999.
Для измерения времени работы программы подключаем библиотеку time.h:
С помощью функции clock() измеряем время начала (begin) и окончания (end) работы программы. В итоге время работы будем находить как разность между ними.
(double) приводит число (в данном случае – результат вычислений end – begin) к вещественному типу данных double (числа с точкой)
CLOCKS_PER_SEC – это константа, сохраненная в библиотеке и зависящая от типа устройства, на котором запускается программа. В данном случае – это просто 1000
Как следует из названия, функция заносит необходимые значения в данную структуру.
Поскольку имя подстроки (d2d3d4, например) на самом деле является числом (1, в данном случае), потому делитель легко заносится из массива делителей по индексу.
Также значение числа, сразу раскладывается на цифры и заносится в массив.
В случае, если необходимо ее значения «обнулить», то в качестве параметра передается ноль в соответствующее поле.
Поскольку при создании структур их поля заполнены случайными «мусорными» значениями, потому и необходима эта функция. Она «обнуляет» часть полей и заносит необходимые данные в структуры подстрок.
Перед началом поиска следующего значения, подстрока сохраняет текущее состояние.
Если подстрока является крайней правой (d8d9d10), то необходимо перебирать все три цифры. Потому число увеличится пока не удовлетворит условию деления и при этом в нем не будет повторяющихся цифр.
Как только это произошло, из массивов пан-цифрового числа удаляются цифры, использованные в предыдущем состоянии подстроки (например, 017). Подстрока инициализируется новым значением (034) и эти цифры заносятся массивы пан-цифрового числа.
В случае, если подбор следующего значения прошел удачно, оно возвращается функцией. Если все числа до 1000 перебраны и нет больше новых значений – вернется ноль.
Если подстрока не является крайне правой, то перебирается только одна цифра. К примеру, строка d8d9d10 имеет значение 289, тогда при определении строки d7d8d9 перебирается только d7 (d8d9 = 28).
При этом это может быть уже не первый подбор и d7 уже имеет значение (отличное от нуля). Потому перебор начнется не с нуля, а с последнего значения (d7). При этом, поскольку цифра, занесенная в d7 уже отмечена как использованная, это значение также будет пропущено.
Как только будет найдено значение подстроки, удовлетворяющее условиям, структуры пан-цифрового числа и подстроки обновляются точно также как и при подборе трех цифр.
Данная функция просто переносит цифры из массива подстроки в массив пан-цифрового числа. При этом отмечает каждую цифру как занятую.
Как видно из названия, выполняются действия обратные предыдущей функции. Все цифры, которые есть в подстроке обнуляются в массивах пан-цифрового числа.
По традиции хотелось бы выразить глубочайшую признательность Сергею Балакиреву за его титанический труд по созданию бесплатных курсов и в частности, за “Язык программирования C/C++ для начинающих“.
Есть вопросы, господа? Отвечаем спокойно, четко и только по делу))
Есть вопросы, господа?
© 2023-2024 | eulerproject.ru
