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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Конструктор копирования в c++ http://www.cyberforum.ru/cpp-beginners/thread697586.html
Добрый день, такая задача по с++ Какая ошибка в следующей реализации конструктора копирования по умолчанию и деструктора?? Какой еще оператор необходимо перегрузить для данного класса?? typedef unsigned int dlina; const dlina n=30; class Mouse { dlina rost; protected:
C++ Не работает код Дан файл zzz.txt В нем подсчитать кол-во букв «а»(латинская) с разбивкой по строчкам. В другом файле (qqq.txt) вывести результаты Всего вхождений: 3 (т.е. общее количествол букв а) Строка 1: 2(т.е. количество букв в этой строке) В данном коде не подсчитывает количество букв "а" как в строке так и в файле #include "stdafx.h" #include <iostream> #include <stdlib.h> http://www.cyberforum.ru/cpp-beginners/thread697578.html
Необходимо перевести из паскаля в с++ C++
Имеется программа на Паскале: uses crt; var a: array of string; i,j,k,l: byte; s,sl: string; begin write('s='); readln(s); s:=s+' '; sl:=''; j:=0; for i:=1 to length(s) do if not (s in )
Выставить цифры в числе 1234567890 таким образом, чтобы новое число делилось без остатка на все числа от 2 до 18 включительно. C++
Дана задача. Выставить цифры в числе 1234567890 таким образом, чтобы новое число делилось без остатка на все числа от 2 до 18 включительно. Я написал нижеследующее, но программа выводит почему то такие числа как 12252240, 24504480 и т.д. Что я тут неправильно написал? /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////...
C++ Массив: Учащиеся участвовали в посадке деревьев. Сколько деревьев было посажено http://www.cyberforum.ru/cpp-beginners/thread697558.html
1)Учащиеся 8-х классов участвовали в посадке деревьев. 8-а посадил 100 деревьев, 8-б —122 дерева, 8-в — 98 деревьев, 8-г — 104 дерева, 8-д — 121 дерево. Определить, сколько посажено деревьев.
C++ проверьте программу,пожжалуйста;) Сначала нужно ввести таблицу, в которой первое поле название, второе- группа, третье- место обитания, четвертое- численность..))) А потом сортировка по первому столбцу по алфавиту, с чем собственно и проблема( #include <stdio.h> #include <stdlib.h> const int n=7; int i,j; struct a1{ //объявляем структуру char name; char grup; char mesto; int chisl; подробнее

Показать сообщение отдельно
33parrots
3 / 3 / 0
Регистрация: 25.05.2012
Сообщений: 23
15.11.2012, 01:15     Сколько есть способов выплатить сумму
Будем выплачивать по 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 нулями.
Вот имеем линейную сложность алгоритма. Интуитивно понятно, что быстрее линейного вряд ли получится сделать, но я не могу доказать что тут не получится всё скрутить в одну явную формулу, не рекурсивную, как в данном случае. В эти дебри Вам лезть не стоит, у Вас олимпиада не с математики.
 
Текущее время: 07:10. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru