Project Euler (answers)

Проект Эйлера: Ответ и решение 24 задачи (Словарные перестановки)

Проект Эйлера (24 задача) трудна пониманием самого порядка перестановки цифр. Для решения потребовалось вводить другую систему исчисления

Узнать больше в телеграм-канале: ProjectEuler++

Условия задачи

Перестановка – это упорядоченная выборка объектов. К примеру, 3124 является одной из возможных перестановок из цифр 1, 2, 3 и 4. Если все перестановки приведены в порядке возрастания или алфавитном порядке, то такой порядок будем называть словарным. Словарные перестановки из цифр 0, 1 и 2 представлены ниже:
012 021 102 120 201 210
Какова миллионная словарная перестановка из цифр 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9?

Содержание статьи

Решение задачи

Описание системы исчисления
Непосредственно решение
Измеряем время работы программы

Функции, использующиеся в программе

Функция для получения промежуточного числа по номеру перестановки
Функция для вычисления факториала
Функция, которая определяет превышение переменной своего предельного значения и выводит предупреждение
Функция, которая выводит на экран искомую перестановку

Ответ и скорость работы программы

Решение (проект Эйлера - 24 задача)

Описание системы исчисления

Меняем систему исчисления

Рассмотрим всего три цифры из примера в задании – 1, 2 и 3. Их можно переставить шестью различными способами:

123 -> 132 -> 213 ->231 -> 312 ->321

Однако как понять, почему цифры переставляются именно таком порядке?

Рассмотрим, как формируется первая (нулевая) выборка цифр – 123 (Рисунок 1):

Цифры в числе используются только один раз – не повторяются и как бы хранятся в отсортированном (!!!) по возрастанию массиве arr[] = {1,2,3}, уменьшающемся, когда из него забирают цифру:

[1,2,3] забираем 1 arr[0]

[2,3] забираем 2 arr[0] – не arr[1]!!!

[3] забираем 3 arr[0] – не arr[2]!!!

При этом по мере укорачивания массива индекс цифры (в массиве) может меняться и это важно!
Таким образом, чтобы получить число 123 требуется из массива [1,2,3] взять arr[0] == 1, из массива [2,3] взять arr[0] == 2, из массива [3] взять arr[0] == 3.
Вот это промежуточное число-из-массивов – 000 и нужно для дальнейших вычислений

Если остальные числа перестановки чисел 1 2 3 преобразовать подобным образом, вся перестановка обретает смысл и становится видна логика перестановки:

123 -> 000
132 -> 010
213 -> 100
231 -> 110
312 -> 200
321 -> 210

Получаем перестановку чисел по порядковому номеру

В итоге мы получаем шесть искомых перестановок в виде чисел-из-индексов. При этом нулевая перестановка будет 000, а последняя, пятая – 210 (Рисунок 2). Однако нужно понимать ряд особенностей такой системы:

В отличие от двоичной и десятичной систем исчисления цифры в каждом разряде числа-из-индексов не будут иметь одинаковое максимальное значение. Так происходит потому, что каждый разряд забирает числа из массивов разный длины. Потому для старшего разряда максимальным может быть индекс 2 (массив из трех элементов [1,2,3]), а для младшего – 0 (массив из одного элемента [2])
Чтобы получить значение перестановки, необходимо сложить номера индексов, умноженные на факториалы максимального значения для данного разряда.

Например, для 4-й перестановки цифр 123, мы получаем число-из-индексов 200 (смотрите рисунок 2). Далее чтобы получить искомое значение перестановки промежуточное число 200 трансформируется следующим образом:

2 00 -> [1,2,3] -> извлекаем arr[2] = 3
2 0 0 -> [1,2] -> извлекаем arr[0] = 1
20 0 -> [2] -> извлекаем arr[0] = 2

В итоге мы имеем следующую цепочку:

4-я перестановка -> число-из-индексов 200 -> искомая перестановка 312

Непосредственно решение (проект Эйлера - 24 задача)

Переставляемые цифры 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9 сохраним в массив.

int sort_arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

Данная перестановка будет иметь номер-из-индексов 0000000000 и, по сути, будет не первой, а нулевой. Потому будем искать не миллионную перестановку, а 999999-ю.

Промежуточный ответ, в виде числа-из-индексов будем сохранять в отдельном массиве:

int indx_arr[LEN_ARR] = {0};

Далее задача будет решаться буквально в два действия:

По номеру перестановки вычисляем промежуточный ответ
get_indx_arr(indx_arr, num);
Преобразуем промежуточный ответ в искомую перестановку и выводим на экран
show_permutation(sort_arr, indx_arr);

Измеряем время работы программы

Для измерения времени работы программы подключаем библиотеку time.h:

#include <time.h>

С помощью функции clock() измеряем время начала (begin) и окончания (end) работы программы. В итоге время работы будем находить как разность между ними.

* Примечания:

clock_t

clock_t это тип данных, определенный через typedef. По сути это обычный целочисленный long

(double)

(double) приводит число (в данном случае – результат вычислений end – begin) к вещественному типу данных double (числа с точкой)

CLOCKS_PER_SEC

CLOCKS_PER_SEC – это константа, сохраненная в библиотеке и зависящая от типа устройства, на котором запускается программа. В данном случае – это просто 1000

Функции, использующиеся в программе (проект Эйлера - 24 задача)

Функция для получения промежуточного числа по номеру перестановки

Поскольку нам многократно понадобятся значения факториалов чисел, потому вычислим их заранее. Сохранив их в массив по индексу, мы в итоге, сможем получать значение факториала просто обращаясь к нему:

factorial[3] = 6 (3!)

Далее функция делит число (номер перестановки) на факториал 9! (для старшего разряда) заносит в первую ячейку массива indx_arr[]. Остаток от деления делится на 8! и результат заносится в следующую. И так до конца массива.

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

Функция для вычисления факториала

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

Также, функция возвращает значение последнего вычисленного факториала.

Функция, которая определяет превышение переменной своего предельного значения и выводит предупреждение

Как ясно из названия, функция сравнивает два значения.

Если контролируемое значение превысит свой предел, то функция вернет true и выведет предупреждение.

Иначе вернет false.

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

Функция, которая выводит на экран искомую перестановку (проект Эйлера - 24 задача)

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

Функция работает следующим образом:

Берет из массива с промежуточным числом первый индекс – 2.
Выводит на экран число с этим индексом из массива:
sort_arr[2] = 2 ({0, 1, 2, 3, 4, 5, 6, 7, 8, 9})

Число 2 изымается из массива, цифры смещаются влево:
{0, 1, 3, 4, 5, 6, 7, 8, 9, 9}
Выводится следующее число:
sort_arr[6] = 7 ({0, 1, 3, 4, 5, 6, 7, 8, 9, 9})
Опять таки число изымается и цифры смещаются:
{0, 1, 3, 4, 5, 6, 8, 9, 9, 9}
И так далее, пока в итоге на экран не будет выведен ответ

В функции также предусмотрена проверка каждого числа на не превышение длинны массива.

Ответ и скорость работы программы (проект Эйлера - 24 задача)

В итоге ответ на 24 задачу проекта Эйлера составил 2783915460, программа считает ответ мгновенно – за 0.0000000 секунды.

По традиции хотелось бы выразить глубочайшую признательность Сергею Балакиреву за его титанический труд по созданию бесплатных курсов и в частности, за “Язык программирования C/C++ для начинающих“.

Есть вопросы, господа? Отвечаем спокойно, четко и только по делу))

Есть вопросы, господа?

Политика конфиденциальности

Конфиденциальность