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

Комбинаторика - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.76
~GiPeRPrOgEr~
0 / 0 / 0
Регистрация: 21.12.2010
Сообщений: 85
15.05.2011, 18:07     Комбинаторика #1
Здравствуйте все. В данный момент дпополнительно решил заняться комбинаторикой, столкнулся с задачей, и никак не могу её решить.Суть такова.
Сколько существует вариантов размена 1 рубля, копеечными монетами, достоинством 1,2,3,4,5 копеек.
Подскажите пожалуйста формулу, или дайте совет. Код я сам смогу написать, а вот с алгоритмном затрудняюсь.
Буду очень благодарен всем неравнодушным.
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.05.2011, 18:07     Комбинаторика
Посмотрите здесь:

комбинаторика C++
C++ Комбинаторика на С++
комбинаторика в программировании C++
C++ Комбинаторика и переборные алгоритмы
C++ Комбинаторика
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
15.05.2011, 20:02     Комбинаторика #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Вроде так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;
int col=0;
void rec(int a, int max)
{
    if(a<0)
        return;
    if(a==0)
    {
        col++; return;
    }
    for(int i=max; i>0; i--)
        rec(a-i, i);
}
int main()
{   
    rec(100, 5);
    cout<<col<<endl;
    return 0;
}
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,694
15.05.2011, 20:38     Комбинаторика #3
valeriikozlov, а за что у вас отвечает второй парамент в функции?
~GiPeRPrOgEr~
0 / 0 / 0
Регистрация: 21.12.2010
Сообщений: 85
15.05.2011, 20:44  [ТС]     Комбинаторика #4
Спасибо большое, если не сложно то вы не могли бы немного пояснить, код простейший, а вот как вычисляется не могу понять...(

Добавлено через 1 минуту
100 это копеек в рубле, 5 это количество монет, а вычисление не доходит.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
15.05.2011, 20:52     Комбинаторика #5
neske, Попробую пояснить на примере разложения 5 копеек теми же монетами.
Если раскладывать любыми комбинациями то получится что некоторые комбинации будут повторяться.
Например:
1 1 1 1 1
2 1 1 1
1 2 1 1
1 1 2 1
и т.д.
т.е. последние 3 варианта это одна и таже комбинация. Поэтому я начинаю с максимального значения монеты и у меня получается так:
5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1
т.е. последующие значения не могут быть больше предыдущих.

Цитата Сообщение от ~GiPeRPrOgEr~ Посмотреть сообщение
а вычисление не доходит.
Не доходит куда?
~GiPeRPrOgEr~
0 / 0 / 0
Регистрация: 21.12.2010
Сообщений: 85
15.05.2011, 21:27  [ТС]     Комбинаторика #6
Не доходит куда?
Не доходит до моей головы, алгоритм вычисления я имел ввиду.

Добавлено через 1 минуту
Теперь кажется дошло, на примере 5 копеек. Еще раз спасибо огромное.
Yandex
Объявления
15.05.2011, 21:27     Комбинаторика
Ответ Создать тему
Опции темы

Текущее время: 12:30. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru