Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
#1

Сколько есть способов выплатить сумму - C++

14.11.2012, 17:53. Просмотров 831. Ответов 2
Метки нет (Все метки)

В Эстонии в обращении находятся 1,2,5,10,25,50,100 и 500 - кроновые купюры.
Написать программу, которая сможет найти сколько есть различных способов выплатить данную сумму.
На единственной строке текстового файла raha.sis.txt дано целое число S(0 < S < 250).
На единственной строке текстового файла raha.val.txt вывести количество различных способов выплаты.

Пример:
Файл raha.sis.txt содержит число: 6 (то есть S = 6)
Файл raha.val.txt содержит число различных способов выплаты: 5 (то есть есть 5 способов выплаты)

Вот какие есть варианты выплаты:
6 = 1 + 1 + 1 + 1 + 1 + 1
6 = 2 + 1 + 1 + 1 + 1
6 = 2 + 2 + 1 + 1
6 = 2 + 2 + 2
6 = 5 + 1

Вопрос:
Каким образом мне найти количество различных способов выплаты?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.11.2012, 17:53     Сколько есть способов выплатить сумму
Посмотрите здесь:
Сколько различных способов есть у зайца добраться до вершины лестницы? C++
C++ Как наименьшим количеством купюр можно выплатить денежную сумму x
C++ Сколько существует способов составить отрезок длиной 1 метр?
Определить, есть ли в заданном предложении цифры. И если есть, найти их сумму C++
C++ Сколько существует способов расставить между цифр знаки "+" и "-"
C++ Узнать, есть ли среди элементов массива элементы с нечетными номерами, которые кратны 17, и если есть, посчитать их сумму
Ввести двумерный массив 4*4, подсчитать кол-во (+) и (-) элементов и вывести статистику по строкам, сколько (+), сколько (-) и подсчитать общую сумму C++
Подсчитать через какое минимальное количество месяцев пользователь сможет выплатить кредит C++
Сколько языков Cи есть?Какие у каждого особенности? C++
Есть ли способ проверить, сколько указателей указывают на определённую область памяти? C++
Дана строка. Определить, сколько в ней символов *, ;, : [Есть код на Pascal] C++
Есть ли в символах строки соседние одинаковые пары символов Сколько таких пар в строке C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
33parrots
3 / 3 / 0
Регистрация: 25.05.2012
Сообщений: 23
15.11.2012, 01:15     Сколько есть способов выплатить сумму #2
Будем выплачивать по 1 монете.
Для того чтобы не различать выплаты типа (2+1+1) и (1 + 2 + 1), где достоинства монет те же, но монеты выданы в другом порядке, введём некое правило, которое гласит "Если уже была выдана монета номиналом Р, то следующая монета может быть номиналом не более чем Р". Под это правило попадают все выписанные ТС варианты выплат для числа 6.

Теперь введём понятие "состояние системы", которое содержит в себе информацию сколько монет уже выдано и каков минимальный номинал у уже выданных монет (что равно номиналу последней выданной монеты). Пример:
Уже выдали 100+50+50+25, значит состояние системы определяется парой (225, 25)

Всего у нас может быть (к-во необходимых монет в конце) * (к-во возможных минимальных номиналов уже выданных монет) состояний системы. Второе из этих чисел - это к-во разных номиналов монет в наличии, их 8.
Перенумеруем возможные номиналы монет в порядке возрастания, нумерация от 0 до 7.

Создаём двумерный массив (М+1)*8, м - к-во необходимых монет. В ячейке (А, Б) будем сохранять к-во вариантов выдать А монет соблюдая правило и так, чтобы последняя выданная монета была номинала Ф(Б). Где Ф(Х) - порядковый номер номинала Х.

Изначально в массиве везде нули, а элемент М(0,7) = 1. У нас ровно 1 вариант выдать 0 монет, не наложив ограничений. Заполняем массив двумя вложенными циклами. Внешний цикл бежит от 1 до нужного итогового к-ва денег, внутренний цикл бегает в обратном порядке, от 7 до 0. В каждое состояние мы можем попасть лишь добавлением к уже имеющемуся набору монеты номиналом, указанным в "состоянием системы", и лишь из состояний, в которых ограничение на используемые далее монеты позволяет нам такую монету добавить. К примеру в состояние (7, ограничение монетой 1) мы можем попасть из состояний
(6, ограничение 500), (6, ограничение 100), ..., (6, ограничение 1), и всё. Ибо если идти туда из состояния 5 монет, то ограничение 1 не наложится, наложится двоечка.

Если мы пытаемся обратиться к состоянию с минусовым номиналом, то, естественно, мы должны получать 0. Точнее не обращаться туда вовсе ))

Итого заполнение одного состояния требует обращения к не более чем 8 ячейкам памяти (в среднем 4.5) и не более 7ми операция "+" ( в среднем 4 при большом числе в файле инпут). Для каждого к-ва монет у нас 8 состояний, имеем
Для нахождения к-ва вариантов выдать М монет необходимо М*28 обращений к ячейкам массива и М*21 операций сложения. Также в начале работы программы заполнение массива М*8 нулями.
Вот имеем линейную сложность алгоритма. Интуитивно понятно, что быстрее линейного вряд ли получится сделать, но я не могу доказать что тут не получится всё скрутить в одну явную формулу, не рекурсивную, как в данном случае. В эти дебри Вам лезть не стоит, у Вас олимпиада не с математики.
Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
15.11.2012, 01:45  [ТС]     Сколько есть способов выплатить сумму #3
33parrots, Спасибо за ваш огромный труд. Буду разбирать то что вы написали, потому что прочитав один раз понял, что нечего не понял.
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru