Project Euler (answers)

Проект Эйлера: Ответ и решение 20 задачи (Сумма цифр факториала)

Проект Эйлера (20 задача) продолжит знакомить Вас с длинной арифметикой. В данном случае – с перемножением очень больших чисел

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

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

n! означает n × (n − 1) × … × 3 × 2 × 1
Например, 10! = 10 × 9 × … × 3 × 2 × 1 = 3628800,
и сумма цифр в числе 10! равна 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.
Найдите сумму цифр в числе 100!.

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

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

Хранение числа в массиве в виде отдельных цифр
Алгоритм работы программы
Измеряем время работы программы

Функции необходимые для решения

Функция для умножения длинного числа на обычное
Функция для подсчета суммы цифр в массиве (числе)
Контролируем корректность работы функций

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

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

Хранение числа в массиве в виде отдельных цифр

Поскольку число из задания (100!) будет длиной 100 – 200 цифр, то в обычные типы данных оно не поместится. Потому для хранения числа будем использовать массив, в ячейках которого будут храниться отдельные его цифры.

1234567 -> [7,6,5,4,3,2,1]

Однако обратите внимание, что цифры в массиве идут в обратном порядке, чем в числе. Слева находятся младшие разряды (7), а справа – старшие (1).

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

Потому будем записывать количество занесенных цифр в массив (длину числа) в нулевую ячейку массива (num_arr[0]).

В итоге число 1234567 в массиве будет сохранено в виде:

[7,7,6,5,4,3,2,1,0,0,0,0,0,0…], где:
первое число (7) – это длина занесенного числа 1234567
а нули после числа (0) – это незанятые ячейки массива.

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

#define LEN_ARR 200

Это необходимо, потому что иначе при изменениях в программе придется вручную менять это значение в нескольких местах.

Алгоритм работы программы

Алгоритм очень простой. Перебираются числа до ста включительно и с помощью функции multiply() перемножаются между собой.

При этом первое число (1) сразу заносим в массив при его инициализации:

int num_arr[LEN_ARR] = {1, 1};

При этом, однако, напомню, что первое число (1) в массиве – это количество занесенных в массив цифр.

После перемножения ряда чисел (от 1 до 100) между собой. Ответ с начала будет сохранен в массиве в виде ряда цифр. И в итоге он будет получен сложением цифр в массиве посредством функции get_sum_dig().

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

Для измерения времени работы программы подключаем библиотеку 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

Функции необходимые для решения (проект Эйлера - 20 задача)

Функция для умножения длинного числа на обычное

Функция принимает два числа (num_ar1[] и num2), причем одно из них в виде массива цифр.

Работает она так:

функция проходит указателем по массиву num_ar1[] и умножает каждый его элемент на число num2;
допустим [7,6,5,4,3,2,1] умножаем на 12;
при этом полученное произведение может быть больше 9 (7*12 = 84);
в таком случае в массив записывается только младший регистр числа (84%10 = 4);
[4,6,5,4,3,2,1]
после чего он сам “отрезается”(84/10 = 8) от числа и оно добавляется в остаток (residue);
указатель переходит на следующий элемент массива;
перемножаются числа 6*12 = 72 и к их произведению добавляется предыдущий остаток 72 + 8 = 80;
в массив записывается младший регистр (0), а старший заносится в остаток (8);
[4,0,5,4,3,2,1]
таким образом указатель проходит по массиву и заменяет значения цифр первого числа (1234567) на значения результата произведения (1234567 * 12 = 14814804);

В итоге движение указателя по массиву продолжается до тех пор, пока не пройдена длина первого числа num_ar1[] или существует (не равен нулю) остаток – residue

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

Работа функции очень проста. Указатель просто проходит по массиву и в итоге суммирует числа в ячейках.

Контролируем корректность работы функций

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

if (num2>=LEN_ARR||num2<1)

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

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

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

В итоге ответ на 20 задачу проекта Эйлера составил 648, программа считает ответ мгновенно.

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

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

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

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

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