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

Купить торт - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Описание протокола, заголовка и тела функции (Язык Pelles C) http://www.cyberforum.ru/cpp-beginners/thread271588.html
Описать функцию IsIdent целого типа, проверяющую, является ли строка S (переданная в качестве параметра) допустимым идентификатором языка «С». При утвердительном ответе возвращается 0. Если ...
C++ Структуры, перечисления ( Язык Pelles C) 1.Разработать программу. Вывести список сообщений на экран, упорядочив по адресу отправителя, а внутри каждого адреса управителя по дате пересылки. СООБЩЕНИЕ: - адреса отправителя и получателя... http://www.cyberforum.ru/cpp-beginners/thread271585.html
C++ Не работает random() для динамического массива
здравствуйте. имеется квадратная матрица, созданная в динамической памяти. нужно заполнить ее случайными числами в интервале (-5;5). использую rand(), толку никакого: матрица выводится на экран, но...
C++ Вывести все числа, которые встречаются в этом массиве несколько раз
Дан массив, состоящий из 100 целых чисел. а) Вывести все числа, которые встречаются в этом массиве несколько раз. б) Вывести все числа, которые встречаются в массиве только по одному разу....
C++ Строки (Язык Pelles C) http://www.cyberforum.ru/cpp-beginners/thread271579.html
/************************************************ Дана строка предложение. Определить в предложении слова максимальной и минимальной длины и поменять их местами....
C++ ИЗ PACKAL в C++ Задача реализованная на PACKALЕ Program zapic; Uses Crt; type AEROFLOT =record Nazvanie:string; Nomer:byte; pynktpributya:string; sovpadenie:byte; End; var Poletu:array... подробнее

Показать сообщение отдельно
Overmind024
99 / 99 / 6
Регистрация: 10.09.2010
Сообщений: 267

Купить торт - C++

07.04.2011, 04:46. Просмотров 626. Ответов 3
Метки (Все метки)

Задание:
Сколькими способами можно заплатить за торт стоимостью n. если можно использовать монеты натуральным номиналом в любом количестве.
(n <= 100)
Я примерно написал:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
 
using namespace std;
 
int count=1;
 
void cake(int a,int limit)
{
    for(int i=2;i<=limit && i<=a ;i++)
    {
        count++;    
        cake(a-i,i);
    }
}
 
int main()
{
    int a;
    cin >> a;
    cake(a,a);
    cout << count;
    return 0;
}
Но при n>96 не проходит по времени((
Помогите улучшить или предложите свой алгоритм.

Примеры:
1 -> 1
2 -> 2
3 -> 3
4 -> 5
5 -> 7
6 -> 11
7 -> 15
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru