Проект Эйлера (31 задача) может быть решена и перебором. Однако применение динамического программирования многократно ускорит вычисления.
Узнать больше в телеграм-канале: ProjectEuler++
В Англии валютой являются фунты стерлингов £ и пенсы p, и в обращении есть восемь монет:
1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) и £2 (200p).
£2 возможно составить следующим образом:
1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
Сколькими разными способами можно составить £2, используя любое количество монет?
Поскольку функция main() получилась довольно-таки объемной, потому решил не “мельчить” и разбить ее на два скриншота.
Вариант с перебором комбинаций монет, указанный в задании рассматривать не будем, потому что никакого секрета в этом нет. Вместо этого рассмотрим прием динамического программирования, примененный в программе.
Сутью динамического программирования является разбитие задачи большой вычислительной сложности на меньшие подзадачи. Эти подзадачи должны иметь меньшую сложность, что в итоге и даст выигрыш в производительности и скорости программы.
В данном случае мы посчитаем количество вариантов для каждой суммы монет от 1 до 200 пенни, для разных вариантов сочетаний монет. Звучит сложно, однако, это не так.
Например, сколько вариантов получить сумму в 50 пенни из монет номиналом 1 пенни? Один! Более того, какую бы сумму нам не было бы нужно получить, количество вариантов останется одним.
Для других сочетаний номиналов монет (1p + 2p, 1p + 2p + 5p и т.д. смотрите задание) количество вариантов будет изменяться, однако вычисляться они будут:
Заносим coins_arr[] в массив все номиналы монет, из которых будет составляться сумма отсортированные в порядке возрастания.
Для записи количества способов составить данную сумму из данного набора монет создаем массив sum_arr[ ][ ]. Он будет состоять из 8 подмассивов (количество монет) длиной 201 (максимальная сумма монет – 200). Поскольку в процессе написания программы менялись как номиналы монет, так и искомые суммы, потому размеры массива и константы в циклах сделал:
При внесении новых номиналов монет или изменения длины массива в начале программе, в итоге изменения происходят по всему коду.
Массив при инициализации заполняется нулями, потому для старта вычислений внесем в него первоначальные данные.
Нулевой подмассив служит для подсчета вариантов составления сумм монет, используя номинал только 1 пенни. Потому, как и было описано
выше, его сразу заполняем единицами (один вариант).
В последующих подмассивах будут добавляться номиналы монет:
В нулевые ячейки каждого подмассива также занесем единицы. Этот вспомогательный “столбик” в массиве вставляем, потому что всегда есть хотя бы один вариант получить искомую сумму монет.
Возьмем для примера небольшую сумму монет (10) и начнем заполнять массив пока вручную.
Поскольку из монет номиналом один пенни можно получить любую сумму только одним способом, потому нулевой массив мы уже заполнили единицами заранее.
Посчитаем для монет номиналом в один и два пенни.
Сумму в 1 пенни можно получить единственным способом, потому пишем в подмассив 1.
Два пенни можно получить уже двумя способами: либо монетой в 2 пенни, либо двумя монетами в один пенни. В итоге пишем в ячейку 2.
Пропустим часть подсчетов.
Десять пенни можно получить следующими сочетаниями монет:
Полученные 5 вариантов заносим в подмассив:
Для заполнения следующего подмассива (с монетами 1p, 2p и 5p) уже не будем вручную подсчитывать все варианты, а порассуждаем.
Для получения 10 пенни мы можем взять:
В итоге мы получим 5 + 3 + 1 = 8 возможных комбинаций для суммы в 10 пенни трех номиналов (1p, 2p, 5p).
Применив данный алгоритм ко всем ячейкам (кроме начальных данных), мы в итоге сведем решение задачи к проходу по массиву и заполнению его ячеек. При этом – на основании массивных же значений.
Для измерения времени работы программы подключаем библиотеку time.h:
С помощью функции clock() измеряем время начала (begin) и окончания (end) работы программы. В итоге время работы будем находить как разность между ними.
(double) приводит число (в данном случае – результат вычислений end – begin) к вещественному типу данных double (числа с точкой)
CLOCKS_PER_SEC – это константа, сохраненная в библиотеке и зависящая от типа устройства, на котором запускается программа. В данном случае – это просто 1000
По традиции хотелось бы выразить глубочайшую признательность Сергею Балакиреву за его титанический труд по созданию бесплатных курсов и в частности, за “Язык программирования C/C++ для начинающих“.
Есть вопросы, господа? Отвечаем спокойно, четко и только по делу))
Есть вопросы, господа?
© 2023-2024 | eulerproject.ru
