Проект Эйлера (41 задача). Самый быстрый способ решить эту задачу – сразу вычислять пан-цифровые числа, не перебирая весь числовой ряд.
Узнать больше в телеграм-канале: ProjectEuler++
Будем считать n-значное число пан-цифровым, если каждая из цифр от 1 до n используется в нем ровно один раз. К примеру, 2143 является 4-значным пан-цифровым числом, а также простым числом.
Какое существует наибольшее n-значное пан-цифровое простое число?
Измеряем время работы программы
Уже привычно разбил функцию main() на два скриншота.
Чтобы удовлетворять задаче, число в итоге должно соответствовать сразу двум условиям: быть пан-цифровым и простым.
Потому будем перебирать пан-цифровые числа от большему к меньшему и каждое из них проверять на то, простое ли оно. Первое же число, удовлетворившее обоим параметрам будет в итоге ответом.
Максимально возможное пан-цифровое число будет девятизначным: 987654321. Если перебирать девятизначные пан-цифровые числа от большего к меньшему, то в итоге минимальным будет 123456789.
После чего следует проверять восьмизначные числа: от 87654321 до 12345678, потом семизначные и так далее.
123 -> 132 -> 213 ->231 -> 312 ->321
Однако как понять, почему цифры переставляются именно таком порядке?
Рассмотрим, как формируется первая (нулевая) выборка цифр – 123 (Рисунок 1):
- [1,2,3] забираем 1 arr[0]
- [2,3] забираем 2 arr[0] – не arr[1]!!!
- [3] забираем 3 arr[0] – не arr[2]!!!
Если остальные числа перестановки чисел 1 2 3 преобразовать подобным образом, вся перестановка обретает смысл и становится видна логика перестановки:
В итоге мы получаем шесть искомых перестановок в виде чисел-из-индексов. При этом нулевая перестановка будет 000, а последняя, пятая – 210 (Рисунок 2). Однако нужно понимать ряд особенностей такой системы:
Например, для 4-й перестановки цифр 123, мы получаем число-из-индексов 200 (смотрите рисунок 2). Далее чтобы получить искомое значение перестановки промежуточное число 200 трансформируется следующим образом:
В итоге мы имеем следующую цепочку:
Для хранения пан-цифрового числа создадим структуру. В ней будет храниться:
Сначала данная структура инициализируется максимально возможным пан-цифровым числом (987654321). Числа перебираются от большему к меньшему и каждое проверяется на то, является ли оно простым.
Как конкретно инициализируется и декрементируется структура будет описано ниже, в описании соответствующих функций.
Если среди чисел нет простого, то при достижении минимально возможного (девятизначного!) пан-цифрового числа (123456789), функция pandig_decrement() вернет 0 и цикл while() прервется.
Для получения максимального восьмизначного пан-цифрового числа, вычисляется вспомогательный делитель div того же порядка, что и число. С его помощью старшая цифра отрезается.
Структура инициализируется данным восьмизначным числом и цикл идет заново.
Для измерения времени работы программы подключаем библиотеку time.h:
С помощью функции clock() измеряем время начала (begin) и окончания (end) работы программы. В итоге время работы будем находить как разность между ними.
(double) приводит число (в данном случае – результат вычислений end – begin) к вещественному типу данных double (числа с точкой)
CLOCKS_PER_SEC – это константа, сохраненная в библиотеке и зависящая от типа устройства, на котором запускается программа. В данном случае – это просто 1000
Поскольку при создании структуры ее поля заполнены случайными значениями, потому необходима данная функция.
Сначала поля структуры обнуляются, вносится значение пан-цифрового числа, вычисляется его длина и подбирается делитель div для отрезания старшей цифры числа.
Однако лучше пояснить на простом примере.
Вносим пан-цифровое число 213 в структуру.
Поскольку длина числа – 3 цифры, а длина массива для хранения индексов – 10, потому необходимо вычислить указатель на первый значащий индекс: 10 – 3 = 7.
Т.е. в массив индексы будут вноситься не с начала:
… а начиная с седьмого:
Отрезаем старшую цифру от вносимого числа:
Определяем индекс этой цифры в отсортированном массиве:
Заносим этот индекс в массив для хранения индексов чисел в структуре:
Удаляем использованную цифру в отсортированном массиве и смещаем следующие за ней влево:
Отрезаем следующую цифру от числа:
Ее индекс в отсортированном массиве будет 0:
[->1<-,3,4,5,6,7,8,9,9]
Заносим индекс (0) в массив структуры и убираем цифру (1) из отсортированного массива:
На следующей итерации заносим индекс последней цифры – 3:
Каждая занесенная цифра числа помечается в массиве fl_ar[] по индексу:
После занесения всех цифр функция проверяет, что все цифры от 1 до len (длина числа), были занесены и потому число является пан-цифровым.
Структура каждого пан-цифрового числа содержит массив с индексами, необходимых для получения этого числа из отсортированного массива.
Максимально возможное число 987654321 потому будет иметь массив с индексами [0,8,7,6,5,4,3,2,1,0].
Минимально возможное (девятизначное) 123456789: [0,0,0,0,0,0,0,0,0,0].
Для получения очередной перестановки цифр (следующего меньшего пан-цифрового числа) будем последовательно уменьшать значения индексов в массиве.
Потому для корректной работы необходимо определять индекс “последнего нуля”, после которого уже не нужно проводить операцию декрементирования.
Однако в итоге массив полностью заполнится нулями. И это значит, что достигнута минимально возможная перестановка. Функция в таком случае прервется и вернет ноль.
Значение которое могут принимать числа в массиве ограничено их максимальными значениями:
Так происходит, потому что при изъятии числа из отсортированного массива:
… он укорачивается.
При декрементировании цифр в массиве уменьшается значение предпоследней ячейки:
Если это невозможно, и ячейка имеет нулевое значение:
…декрементируется следующая (старшая) ячейка
…а младшая принимает максимально возможное для данной позиции значение:
После получения массива с индексами формируем следующее (меньшее) число.
Например, мы имеем массив [0,1,2,3,4,4,3,2,1,0].
Первый ноль – незначащий и служит лишь для ограничения алгоритма декрементирования, описанного выше.
Берем первую цифру из отсортированного массива по его индексу (1):
Берем цифру со следующим индексом:
Данная функция перебирает делители числа. Если число не делится нацело ни на один, то оно – простое.
Особенности функции:
По традиции хотелось бы выразить глубочайшую признательность Сергею Балакиреву за его титанический труд по созданию бесплатных курсов и в частности, за “Язык программирования C/C++ для начинающих“.
Есть вопросы, господа? Отвечаем спокойно, четко и только по делу))
Есть вопросы, господа?
© 2023-2024 | eulerproject.ru
