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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.76
~GiPeRPrOgEr~
0 / 0 / 0
Регистрация: 21.12.2010
Сообщений: 85
#1

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

15.05.2011, 18:07. Просмотров 2474. Ответов 5
Метки нет (Все метки)

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

Комбинаторика - C++
Помогите написать алгоритм для вычисления количество непустых последовательностей из ряда чисел. Или кинте ссылочку, где почитать. Что я...

Комбинаторика - C++
Доброго всем времени суток!Помогите пожалуйста с решением такой задачи.Дана последовательность вещественных чисел.Пользователь вводит...

Комбинаторика на С++ - C++
Нужно составить программу, или скорее функцию, которая для заданного натурального числа k выводит все возможные произведения k чисел с...

комбинаторика - C++
Здравствуйте! Я решаю задачи по дискретной математике на языке С.В интернете масса примеров задач на тему комбинаторики, но на языке...

Комбинаторика - C++
От пользователя требуется ввести n. Результат должен быть таким:

Комбинаторика. Сочетания - C++
Добрый день! Прошу помочь со следующей задачкой: генерация сочетания по номеру(порядок лексикографический). Толковое объяснение нашел...

Перестановка.(Комбинаторика) - C++
Прошу помощи. Объясните пожалуйста тугодуму этот код. Какой день его пытаюсь понять. Не как не могу в нём разобраться. Вроде знаю как...

Комбинаторика в программировании - C++
есть алфавит длинны Х; длинна слова Y; написать код(лучше на с++) который будет составлять и выводить все возможные варианты слов. ...

Комбинаторика style - C++
Здравствуйте, помогите разобраться с задачей по комбинаторике. Условие: http://codeforces.com/problemset/problem/630/F Решение: ...

Покерная комбинаторика - C++
Добрый день, форумчане. Рад возможности стать членом общества программистов. Я чайник на все 234%. Болею задачей создания покерной...

Рекурсия. Комбинаторика. Размещения - C++
Дана задача: вывести все размещения из n по k, где n - это число элементов конечного множества (например, задаваемого из файла). Комбинации...

Комбинаторика и теория вероятностей - C++
Для заданных m и n найти все сочетания по m из чисел 1, 2, ..., n


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
4669 / 2495 / 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
1473 / 840 / 73
Регистрация: 26.03.2010
Сообщений: 2,881
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++
4669 / 2495 / 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     Комбинаторика
Ответ Создать тему
Опции темы

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