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

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

Войти
Регистрация
Восстановить пароль
 
Overmind024
99 / 99 / 6
Регистрация: 10.09.2010
Сообщений: 267
#1

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

07.04.2011, 04:46. Просмотров 606. Ответов 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
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.04.2011, 04:46
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Купить торт (C++):

Три толстяка едят торт. Сколько времени потребуется, чтобы съесть весь торт вместе? - C++
Доброго времени суток! :) Я вот решаю задачки, но столкнулся с целом рядом проблем: некоторые не засчитываются до конца (70-90 %),...

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

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

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

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

Вычислить сколько товара можно купить без сдачи - C++
Задаётся произвольная цена товара (допустим 11,11) задается произвольное количество монет (10р 5р 2р 1р 50к 10к 5к) допустим каждой по 5 ...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
07.04.2011, 07:20 #2
Не понимаю, что делает программа.
Номиналов монет нет.
Только стоимость торта есть и всё.
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 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;    
    }
}
Overmind024
99 / 99 / 6
Регистрация: 10.09.2010
Сообщений: 267
07.04.2011, 19:57  [ТС] #4
спасибо буду разбираться.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.04.2011, 19:57
Привет! Вот еще темы с ответами:

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

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

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

Сколько быков, коров и телят можно купить на 100 рублей? - C++
1.Имеется 100 рублей. Сколько быков, коров и телят можно купить на все эти деньги, если плата за быка – 10 рублей, за корову – 5 рублей,...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
07.04.2011, 19:57
Ответ Создать тему
Опции темы

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