Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

14.11.2012, 17:53. Просмотров 899. Ответов 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

Вопрос:
Каким образом мне найти количество различных способов выплаты?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.11.2012, 17:53
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Сколько есть способов выплатить сумму (C++):

Сколько различных способов есть у зайца добраться до вершины лестницы? - C++
В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему не было скучно, директор зоопарка распорядился поставить в его клетке...

Как наименьшим количеством купюр можно выплатить денежную сумму x - C++
надо ввести натуральное число x , и каким наименьшим количеством купюр можно выплатить денежную сумму в данном случае x, если есть купюры ...

Сколько существует способов составить отрезок длиной 1 метр? - C++
Сколько существует способов составить отрезок длиной 1 метр из отрезков длиной А и В см?

Определить, есть ли в заданном предложении цифры. И если есть, найти их сумму - C++
Определить, есть ли в заданном предложении цифры. И если есть, найти их сумму.

Сколько существует способов расставить между цифр знаки "+" и "-" - C++
Вот сама задача - {удалено} Не могу сделать норм перебор

Узнать, есть ли среди элементов массива элементы с нечетными номерами, которые кратны 17, и если есть, посчитать их сумму - C++
Проблема с заданием. Дан одномерный массив. Узнать, есть ли среди них элементы с нечетными номерами, которые кратны 17, и если есть,...

2
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 нулями.
Вот имеем линейную сложность алгоритма. Интуитивно понятно, что быстрее линейного вряд ли получится сделать, но я не могу доказать что тут не получится всё скрутить в одну явную формулу, не рекурсивную, как в данном случае. В эти дебри Вам лезть не стоит, у Вас олимпиада не с математики.
1
Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 270
15.11.2012, 01:45  [ТС] #3
33parrots, Спасибо за ваш огромный труд. Буду разбирать то что вы написали, потому что прочитав один раз понял, что нечего не понял.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.11.2012, 01:45
Привет! Вот еще темы с ответами:

Ввести двумерный массив 4*4, подсчитать кол-во (+) и (-) элементов и вывести статистику по строкам, сколько (+), сколько (-) и подсчитать общую сумму - C++
не получается никак сделать многомерный массив... помогите пожалуйста #include &lt;iostream&gt; #include &lt;ctime&gt; using namespace...

Подсчитать через какое минимальное количество месяцев пользователь сможет выплатить кредит - C++
Спросите у пользователя, какую зар.плату он получает и какой кредит он хочет взять. Подсчитать, через какое минимальное количество месяцев...

Сколько языков Cи есть?Какие у каждого особенности? - C++
Сколько языков Cи есть?Какие у каждого особенности?

Есть ли способ проверить, сколько указателей указывают на определённую область памяти? - C++
Привет народ. Такой вопрос: Есть ли способ проверить, сколько указателей указывают на определённую область памяти? Спасибо.


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

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