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

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

Войти
Регистрация
Восстановить пароль
 
Leonman
 Аватар для Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
14.11.2012, 17:53     Сколько есть способов выплатить сумму #1
В Эстонии в обращении находятся 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и есть?Какие у каждого особенности? C++
Определить, есть ли в заданном предложении цифры. И если есть, найти их сумму C++
C++ Нужно написать программу на С/С++ (дано слово. определить сколько в нем различных букв), есть алгоритм
Ввести двумерный массив 4*4, подсчитать кол-во (+) и (-) элементов и вывести статистику по строкам, сколько (+), сколько (-) и подсчитать общую сумму C++
C++ Узнать, есть ли среди элементов массива элементы с нечетными номерами, которые кратны 17, и если есть, посчитать их сумму
C++ Сколько существует способов составить отрезок длиной 1 метр?
Есть ли способ проверить, сколько указателей указывают на определённую область памяти? C++
Дана строка. Определить, сколько в ней символов *, ;, : [Есть код на Pascal] C++
C++ Как наименьшим количеством купюр можно выплатить денежную сумму x
Сколько различных способов есть у зайца добраться до вершины лестницы? 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
 Аватар для Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
15.11.2012, 01:45  [ТС]     Сколько есть способов выплатить сумму #3
33parrots, Спасибо за ваш огромный труд. Буду разбирать то что вы написали, потому что прочитав один раз понял, что нечего не понял.
Yandex
Объявления
15.11.2012, 01:45     Сколько есть способов выплатить сумму
Ответ Создать тему
Опции темы

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