Решение 13 задачи проекта Эйлера: Большая сумма

В программе округлил все числа до первых 17 знаков, их сложил и из полученной суммы выделил первые 10 цифр.

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

Найдите первые десять цифр суммы следующих ста 50-значных чисел.

Задача Эйлера #13 (задание)

Полностью ряд чисел приводить не буду - он огромен. Само задание можно найти на сайте.

Преобразовал ряд чисел в удобный формат

Для удобства работы преобразовал ряд чисел в строку.

Задача Эйлера #13 - решение

Алгоритм действий пояснялся подробно в задаче Эйлера #8. По итогу получил массив символов длиной 5001, где последний символ - символ окончания строки.

Ищу первые десять цифр искомой суммы

Задача Эйлера #13 - продолжение решения

Задумка программы

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

Максимальная длина числа типа unsigned long long: 19 - 20 знаков, сумма ста чисел больше самих чисел максимум на два порядка. Поэтому беру первые 17 знаков из каждого числа, их складываю и из полученной суммы выделяю число, содержащее первые 10 цифр.

Выделяю первые 17 цифр числа

Как уже описывалось ранее, каждый символ в массиве имеет свой код и хранится в виде числа. Чтобы из "символа-цифры" получить искомое число необходимо вычесть 48 из кода символа. Например:

'5' имеет код - 53 -> 53 - 48 = 5

В массив num_str[] числа записаны один за другим:

num_str[0] - начало первого 50-значного числа

num_str[50] - начало второго и т.д.

По индексу indx перебираю символы в массиве и формирую число, состоящее из первых 17 цифр 50-значного числа:

for(unsigned long long i = 10000000000000000; i > 0; i /= 10)

num += (num_str[indx++] - 48)*i;

Происходят следующие преобразования:

• ['3','7','1','0','7','2','8','7','5','3','3','9','0','2','1','0','2','7','9','8','7',...] ->
• 3*10000000000000000 = 30000000000000000 ->
• 30000000000000000 + 7*1000000000000000 = 37000000000000000 ->
• ...
• 37107287533902102 - искомое 17-значное число

Складываю первые 17 цифр суммы 50-значных чисел

sum += num;

Вычисленные числа суммирую.

for(indx = 0; indx < 5000; indx += 33)

Перемещаю indx начало следующего числа.

Обрезаю лишние цифры

sum /= 1000000000;

Т.к сумма ста 17-значных чисел - 19-значное число, то обрезал лишние цифры с помощью целочисленного деления.

Ответ на задачу:

Программа вычисляет ответ за 0.5 секунды.

Что можно улучшить

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

P.S. Изначальная цель блога - получить "фидбек" в комментариях, чтобы более опытные "кодеры" указывали мне на ошибки, советовали и всячески помогали в саморазвитии.

Также приглашаю всех на мой сайт)

На нем Вы можете посмотреть ответ на задачу Эйлера #13 (когда необходима лишь небольшая подсказка) и последний, самый быстрый вариант решения.

Нам тут одним долго не продержаться! Подписывайтесь скорее)

В общем, добро пожаловать на канал))