Проект Эйлера (40 задача). Подсказка! Вычислять огромное число из задания нет никакого смысла, потому что Вам не хватит ни времени, ни памяти
Узнать больше в телеграм-канале: ProjectEuler++
Дана иррациональная десятичная дробь, образованная объединением натуральных чисел:
0.123456789101112131415161718192021…
Видно, что 12-я цифра дробной части – 1.
Также дано, что dn представляет собой n-ю цифру дробной части. Найдите значение следующего выражения:
d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000
Уже привычно разбил функцию main() на два скриншота.
Вариант решения “в лоб”, т.е. создать строку или массив длиной в миллион, как в задании, и искать в них искомые цифры, даже не стал пробовать. Потому что перерасход памяти и времени, мне кажется, очевиден.
Вместо этого будем перебирать натуральные числа, из которых составляется дробь, и вычислять ее длину. Как только в итоге длина дроби достигнет одной из искомых (1, 10, 100 и т.д.) уже и будем определять необходимую цифру.
При этом, однако, очевидно, что длины чисел постепенно увеличиваться:
Для удобства создадим свою структуру данных “большое число”. Число в нем будет храниться в массиве, разложенным на отдельные цифры.
При необходимости получить отдельную цифру числа, в итоге достаточно просто обратиться к нему по индексу.
Кроме того, в структуре будет храниться длина числа.
Для работы с числами используется две функции:
При этом инициализируется, по сути, только первое число – единица. Все последующие будут инкрементироваться.
Это позволит не раскладывать каждое число:
А работать сразу с массивами:
…что в итоге сократит количество операций.
Сделаем программу более универсальной и потому занесем номера искомых цифр в массив, а количество его членов для цикла for() будем определять с помощью операции sizeof().
Числа, составляющие дробь, будут инкрементироваться пока ее длина не достигнет одной из искомых величин. Номер цифры в массиве (структуре “большое число”) определим как разность между действительной и искомой длиной дроби.
Например, длина дроби 1003. Нам необходимо определить 1000-ую цифру.
Все найденные цифры в итоге перемножаются и образуют ответ.
Для измерения времени работы программы подключаем библиотеку time.h:
С помощью функции clock() измеряем время начала (begin) и окончания (end) работы программы. В итоге время работы будем находить как разность между ними.
(double) приводит число (в данном случае – результат вычислений end – begin) к вещественному типу данных double (числа с точкой)
CLOCKS_PER_SEC – это константа, сохраненная в библиотеке и зависящая от типа устройства, на котором запускается программа. В данном случае – это просто 1000
Поскольку при создании структуры ее поля заполнены случайными значениями, потому необходима функция для инициализации начальных значений.
Данная функция:
Данная функция прибавляет единицу к цифре в младшем регистре числа. При переполнении регистра (значение более 9), в ячейка обнуляется и значение переносится на старший регистр.
Если длина числа в итоге изменилась – корректируем ее.
Кроме того, с помощью функции more_input(), контролируем невыход за пределы массива.
Поскольку многие функции кочуют из одной задачи в другую, потому часто возникают трудно уловимые ошибки. Вроде бы и функция правильная и работает вроде верно, однако контекст задачи изменился и ответ выходит некорректный. Потому, везде где это возможно, делаются проверки ввода.
Для данной проверки и придумана функция more_limit(). Если функция принимает не те значения, на которые она рассчитана, она прекратит ее работу (вернет true – должно дальше обрабатываться) и выведет предупреждение.
По традиции хотелось бы выразить глубочайшую признательность Сергею Балакиреву за его титанический труд по созданию бесплатных курсов и в частности, за “Язык программирования C/C++ для начинающих“.
Есть вопросы, господа? Отвечаем спокойно, четко и только по делу))
Есть вопросы, господа?
© 2023-2024 | eulerproject.ru
