Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Overmind024
99 / 99 / 27
Регистрация: 10.09.2010
Сообщений: 267
#1

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

07.04.2011, 04:46. Просмотров 656. Ответов 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
http://www.cyberforum.ru/cpp-beginners/thread1279751.html
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.04.2011, 04:46
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Купить торт (C++):

Задача про торт
/*Задача интересная и на самом деле не сложная, но в виду того что я кодю...

подскажите где можно купить хорошую методичку
по си++ в москве... желательно чтоб там были только таблицы и обазначения...

Сколько животных можно купить за 100 рублей?
Написать программу, которая выводит на экран все возможные варианты решения...

Сколькими способами можно купить 185 кг ящиками по 15, 17 и 21 кг
В магазине продается мастика в ящиках по 15 кг,17 кг,21 кг. Как купить ровно...

Вычислить сколько товара можно купить без сдачи
Задаётся произвольная цена товара (допустим 11,11) задается произвольное...

3
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1306 / 1221 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
07.04.2011, 07:20 #2
Не понимаю, что делает программа.
Номиналов монет нет.
Только стоимость торта есть и всё.
0
Mr.X
Эксперт С++
3178 / 1705 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
07.04.2011, 11:38 #3
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/////////////////////////////////////////////////////////////////////////////////////////
//Сколькими способами можно заплатить за торт стоимостью n. если можно использовать 
//монеты натуральным номиналом в любом количестве.
//(n <= 100)
//Примеры:
//1 -> 1
//2 -> 2
//3 -> 3
//4 -> 5
//5 -> 7
//6 -> 11
//7 -> 15 
/////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
/////////////////////////////////////////////////////////////////////////////////////////
const int  MIN_COST = 1;
const int  MAX_COST = 100;
/////////////////////////////////////////////////////////////////////////////////////////
int  get_coins_combinations_total(int  target_cost)
{
    const int  BAD_RESULT = -1;
    if(target_cost > MAX_COST)  return  BAD_RESULT;
    int  cost_combs_total_to_noms_is_not_less[MAX_COST + 2][MAX_COST + 2] = {0};    
 
    for(int  cost = 1; cost <= target_cost + 1; ++cost)
    {
        cost_combs_total_to_noms_is_not_less[cost][cost] = 1;
        for(int  nom = 1; nom < cost; ++nom)
        {
            int  old_cost = cost - nom;
            for(int  old_nom = nom; old_nom <= old_cost; ++old_nom)
            {
                cost_combs_total_to_noms_is_not_less[cost][nom] 
                    += cost_combs_total_to_noms_is_not_less[old_cost][old_nom];
            }
 
            if(   cost  == target_cost + 1
               && nom   == 1)
            {
                return  cost_combs_total_to_noms_is_not_less[target_cost + 1][1];
            }
        }        
    }
    return  BAD_RESULT;
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    for(;;)
    {
        int  cost = 0;
        do
        {
            std::cout << "Введите стоимость торта ("
                      << MIN_COST
                      << ".."
                      << MAX_COST
                      << "): ";
        
            std::cin >> cost;
        }while(   cost      < MIN_COST
               || MAX_COST  < cost);        
        
        std::cout << "За торт стоимостью "
                  << cost
                  << " можно заплатить "
                  << get_coins_combinations_total(cost)
                  << " способами."
                  << std::endl
                  << std::endl
                  << std::endl;    
    }
}
1
Overmind024
99 / 99 / 27
Регистрация: 10.09.2010
Сообщений: 267
07.04.2011, 19:57  [ТС] #4
спасибо буду разбираться.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.04.2011, 19:57
Привет! Вот еще темы с решениями:

Cколько можно купить быков, коров и телят на 100 рублей
Составить алгоритм решения задачи: сколько можно купить быков, коров и телят,...

Сколько быков, коров и телят можно купить на 100 рублей?
1.Имеется 100 рублей. Сколько быков, коров и телят можно купить на все эти...

Через сколько лет этот человек сможет купить машину?
Один человек имеет 100 тыс.руб., он хочет купить машину за 150 тыс.руб., для...

Через сколько лет этот человек сможет купить машину?
Один человек имеет 100 тыс.руб., он хочет купить машину за 150 тыс.руб., для...


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

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

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