Форум программистов, компьютерный форум, киберфорум
Наши страницы
C++/CLI
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/12: Рейтинг темы: голосов - 12, средняя оценка - 4.50
KING1994
-18 / 6 / 0
Регистрация: 18.07.2011
Сообщений: 77
#1

Сколькома способами можно сложить 1 рубль из 1,2,5,10,25,50 копеек которые даные в неограниченом количестве?

26.08.2011, 20:17. Просмотров 2180. Ответов 10
Метки нет (Все метки)

Сколькома способами можно сложить 1 рубль из 1,2,5,10,25,50 копеек которые даные в неограниченом количестве?помогите написать код програмы.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.08.2011, 20:17
Ответы с готовыми решениями:

Сколькими способами можно разменять 10 копеек монетами по 1, 2, 3 и 5 копеек?
Помогите решить задачу пожалуйста "сколькими способами можно разменять 10...

Подсчет количества способов, которыми можно разменять рубль медными монетами (достоинством 1, 2, 3, 5 копеек)
составить алгоритм подсчета количества способов, которыми можно разменять рубль...

Сколькими способами можно разменять рубль?
сколькими способами можно разменять рубль на монеты достоинством в 10, 15, 20 и...

Сколькими способами можно разменять рубль?
сколькими способами можно разменять рубль(100 копеек) на монеты достоинством в...

Как наименьшим количеством монет можно выплатить N копеек?Предполагается,что в достаточном количестве имеются монеты достоинством 1,2.3.5.10,15,20,50
Дано натуральное число N.Как наименьшим количеством монет можно выплатить N...

10
magirus
26.08.2011, 20:38
  #2
 Комментарий модератора 
называйте темы информативно.
0
odip
Эксперт С++
7161 / 3220 / 76
Регистрация: 17.06.2009
Сообщений: 14,161
27.08.2011, 13:43 #3
Тема очень информативна !

Задача решается полным перебором
Или можно немного сократить перебор
0
KING1994
-18 / 6 / 0
Регистрация: 18.07.2011
Сообщений: 77
27.08.2011, 14:00  [ТС] #4
Немного втупил в теме)Должна была бить "Интересная задача"
Перебор я знаю:сначала может быть 1 2 5 10 25 50
1 2 5 10 25 50 1 2 5 10 25 50 1 2 5 10 25 50 1 2 5 10 25 50
ну и так далее но как етот перебор записать програмным кодом ето посложнее)помогите пожалуйста етот код сочинить)по етому дереву што я навел.

Добавлено через 6 минут
блин ненарисовало дерево как я сочинял ну моя идея такова: сначала может может быть один из видов монет предположим што ето монета номиналом 1 после могут идти 6 видов->1,2,5,10,25,50
у на уже есть 5 вариантов 1+1,1+2,1+5,1+10,1+25,1+50.
Потом из етих шести сочиняетса 36 вариантов типа 1+1+1,1+1+2,1+1+5,1+1+10,1+1+25,1+1+50,1+2+1.....
и так далее помогите мне ето дерево записать в програмном коде пожалуйста.Некоторые вариации повторяютса но потом число которое получитса надо поделить на 6 и будет точная цифра.
0
novikov.ea
944 / 736 / 261
Регистрация: 10.06.2011
Сообщений: 1,406
27.08.2011, 16:30 #5
Типичная задача на поиск в глубину. У меня программа сосчитала 1130 способов.
Разберёшься куда код вставить и как он работает?

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
#define Ruble 100
int Count;   //Количество способов
 
void Func(int Balance, int BiggestMoneta){
    if (BiggestMoneta >= 50) Proverka(Balance, 5);
    if (BiggestMoneta >= 25) Proverka(Balance, 3);
    if (BiggestMoneta >= 10) Proverka(Balance, 2);
    if (BiggestMoneta >= 5) Proverka(Balance, 5);
    if (BiggestMoneta >= 2) Proverka(Balance, 2);
    if (BiggestMoneta >= 1) Proverka(Balance, 1);
}
 
void Proverka(int Balance, int Moneta){
    Balance += Moneta;
    if (Balance == Ruble){
        Count++;
    }else if(Balance < Ruble){
        Func(Balance, Moneta);
    }
}
 
int SkolkoSposobov( void ){
    int Balance = 0;   //Текущий баланс при подсчёте
    int BiggestMoneta = 50;     //Наибольшая монета
    Func (Balance, BiggestMoneta);
    return Count;
}
 
 
System::Void button1_Click(System::Object^  sender, System::EventArgs^  e) {
    Count = 0;
    this->textBox1->Text = SkolkoSposobov().ToString();
}
Добавлено через 51 минуту
Функцию Func неправильно записал. После контрольной проверки забыл исправить)

C++
1
2
3
4
5
6
7
8
void Func(int Balance, int BiggestMoneta){
        if (BiggestMoneta >= 50) Proverka(Balance, 50);        //Здесь...
        if (BiggestMoneta >= 25) Proverka(Balance, 25);        //...здесь...
        if (BiggestMoneta >= 10) Proverka(Balance, 10);        //...и здесь
        if (BiggestMoneta >= 5) Proverka(Balance, 5);
        if (BiggestMoneta >= 2) Proverka(Balance, 2);
        if (BiggestMoneta >= 1) Proverka(Balance, 1);
}
1
KING1994
-18 / 6 / 0
Регистрация: 18.07.2011
Сообщений: 77
27.08.2011, 17:56  [ТС] #6
Теперь понятней) ото откуда цыфри 3 и 5 два раза)функциями я делал ето но хочу попробивать класами описать древообразную структуру)
0
KING1994
-18 / 6 / 0
Регистрация: 18.07.2011
Сообщений: 77
28.08.2011, 00:54  [ТС] #7
Кстати по вашему коду у меня получилось 3953 способа)
0
novikov.ea
944 / 736 / 261
Регистрация: 10.06.2011
Сообщений: 1,406
28.08.2011, 09:18 #8
Да, да, всё верно, 3953. Просто я говорю, что забыл исправить.
Я проверял алгоритм на простом примере при условиях Ruble=10, возможные монеты: 5, 3 и 2. В операторе if() затем значения поменял обратно, а в функции Proverka(int Balance, int Moneta) на радостях забыл.
0
KING1994
-18 / 6 / 0
Регистрация: 18.07.2011
Сообщений: 77
28.08.2011, 12:24  [ТС] #9
И все же я думаю ета цыфра слегка великовата.Ведь комбинации могут повторятса 50+25+25,25+50+25,25+25+50-ето не 3 разних а 1 способ.

Добавлено через 16 минут
Можно задать суму как динамический массив m[i]типа char m[]="1+2+5+...+25"и подщитать количество плюсов в каждой строке.на Count++ надо поставить еще одно условие:количество плюсов не совпадает с другими вариантами.
0
novikov.ea
944 / 736 / 261
Регистрация: 10.06.2011
Сообщений: 1,406
28.08.2011, 19:13 #10
KING1994, вот почему вы меня не спросили, что такое за серия условий
C++
1
2
3
4
5
6
if(BiggestMoneta >= 50)
if (BiggestMoneta >= 25)
if (BiggestMoneta >= 10)
if (BiggestMoneta >= 5)
if (BiggestMoneta >= 2)
if (BiggestMoneta >= 1)
?
Именно эти условия исключают повторения типа 50+25+25, 25+50+25 и 25+25+50. Если бы этих условий не было, то все три сочетания были бы сосчитаны. НО! Давайте брать только те из сочетаний, которые отсортированы по определённому условию, например по достоинству монеты. В этом случае будет сосчитано только одно из сочетаний. То есть, 50+25+25.
Алгоритм запрещает брать в каждом случае ту монету, номинал которой больше предыдущей взятой монеты. Например:
5 + 10 + 50 + 25 + 2 + 2 + 1 + 5 = 100
Алгоритм отберёт только
50 + 25 + 10 + 5 + 5 + 2 + 2 + 1 = 100
Потому что
50 ≥ 25 ≥ 10 ≥ 5 ≥ 5 ≥ 2 ≥ 2 ≥ 1
Понятно?

Цитата Сообщение от KING1994 Посмотреть сообщение
И все же я думаю ета цыфра слегка великовата.
Так есть же монета с номиналом 1 копейка. В любом случае она очень широко используется:
50 + 50*(1 копейка) = 100
10 + 5 + 2 + 83*(1 копейка) = 100
25 + 25 + 10 + 10 + 5 + 2 + 33*(1 копейка) = 100
... и так далее, короче ЦЕЛАЯ КУЧА случаев!

Цитата Сообщение от KING1994 Посмотреть сообщение
Можно задать суму как динамический массив m[i]типа char m[]="1+2+5+...+25"и подщитать количество плюсов в каждой строке.
Это зачем? Хотя можешь делать как хочешь!

А вы сами не знаете правильный ответ? Спросите у кого-нибудь.
1
KING1994
-18 / 6 / 0
Регистрация: 18.07.2011
Сообщений: 77
28.08.2011, 20:11  [ТС] #11
Да я етого незаметил.Ваша программа работает правильно.Убедился в етом используя 2 монеты 25 и 50.
0
28.08.2011, 20:11
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.08.2011, 20:11

Сколькими способами можно выдать один рубль, имея монеты разных номиналов
У Вас есть монеты номиналом 1, 2, 5, 10, 25 та 50 копеек в бесконечном...

Сколькими способами можно сложить 9 разных книг в 5 бандеролей, если 4 бандероли содержат по 2 книги
Сколькими способами можно сложить 9 разных книг в 5 бандеролей, если 4...

Сколькими способами можно выбрать 9 книг, которые не стояли рядом?
Помогите, пожалуйста, с задачей. Заранее спасибо. На полке 20 книг. Сколькими...


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

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

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