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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 26, средняя оценка - 5.00
алишка999
1 / 1 / 0
Регистрация: 01.09.2012
Сообщений: 30
#1

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

07.09.2012, 16:08. Просмотров 3443. Ответов 7
Метки нет (Все метки)

составить алгоритм подсчета количества способов, которыми можно разменять рубль медными монетами(достоинством в1,2,3,5 копеек)
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.09.2012, 16:08     Подсчет количества способов, которыми можно разменять рубль медными монетами (достоинством 1, 2, 3, 5 копеек)
Посмотрите здесь:

Проверить, можно ли набрать заданную сумму монетами заданных номиналов C++
C++ Подсчет количества символов
C++ Сколькими способами можно отобрать команду в составе 5 человек из 8 кандидатов;из 10 кандидатов; из 11 кандидатов? Подсчет количества способов отбора
C++ Подсчет количества бит
C++ например 317 должно вывести 3 гривны 17 копеек, 1 гривна 00 копеек
C++ Задача на циклы: Можно ли разменять m рублей
C++ 6. Можно ли разменять m руб. на рублёвые, трёхрублёвые, пятирублёвые купюры так, чтобы получить всего 10 купюр. (10<m<50)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Day
1154 / 959 / 57
Регистрация: 29.10.2009
Сообщений: 1,385
07.09.2012, 16:35     Подсчет количества способов, которыми можно разменять рубль медными монетами (достоинством 1, 2, 3, 5 копеек) #2
Цитата Сообщение от алишка999 Посмотреть сообщение
разменять рубль медными монетами(достоинством в1,2,3,5 копеек)
Видать, задачка-то еще со времен СССР
алишка999
1 / 1 / 0
Регистрация: 01.09.2012
Сообщений: 30
07.09.2012, 16:36  [ТС]     Подсчет количества способов, которыми можно разменять рубль медными монетами (достоинством 1, 2, 3, 5 копеек) #3
а что делать раз задали
Thinker
Эксперт C++
4220 / 2194 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
07.09.2012, 21:39     Подсчет количества способов, которыми можно разменять рубль медными монетами (достоинством 1, 2, 3, 5 копеек) #4
Цитата Сообщение от алишка999 Посмотреть сообщение
а что делать раз задали
Используйте рекурсивную функцию
F(n) = F(n-1) + F(n-2) + F(n-3) + F(n-5)
с начальными условиями
F(0) = 1,
F(x) = 0 при x < 0

получается 117372865913707249 способов. обычной рекурсией его не получить. Только с сохранением уже подсчитанного.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
const long N = 101;
 
long long F(long n)
{
   static long long count[N];
   if (n < 0)
      return 0;
   else if (count[n] != 0)
      return count[n];
   else if (n == 0)
      return (count[n] = 1);
   else
      return (count[n] = F(n-1) + F(n-2) + F(n-3) + F(n-5));
}
 
int main()
{
   std::cout << F(100);
   return 0;
}
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
08.09.2012, 02:26     Подсчет количества способов, которыми можно разменять рубль медными монетами (достоинством 1, 2, 3, 5 копеек) #5
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от Thinker Посмотреть сообщение
получается 117372865913707249 способов.
многовато )
У меня получается всего 6518.
Все дело в том что например варианты для набора 3-х копеек: (1 2) и (2 1) Вы считаете разными, хотя это одно и тоже.
Thinker
Эксперт C++
4220 / 2194 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
08.09.2012, 12:34     Подсчет количества способов, которыми можно разменять рубль медными монетами (достоинством 1, 2, 3, 5 копеек) #6
Да, действительно, я учел порядок, а он не важен, спасибо. Так задачу о наклейке марок надо решать, тут другая рекурсия
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
 
long F(long *a, long i, long n)
{
   if (n < 0)
      return 0;
   else if (n == 0)
      return 1;
   return i < 0 ? 0 : F(a, i - 1, n) + F(a, i, n - a[i]);
}
 
int main()
{
   long a[4] = {1, 2, 3, 5};
   std::cout << F(a, 3, 100);
   return 0;
}
Ответ: 6518. Здесь последовательности упорядочены.
При этом существует 117372865913707249 способов наклеить марки на конверт стоимостью в 1,2,3 и 5 коп., чтобы в сумме получился 1 руб, так как последовательности неупорядочены.
Dantes48
0 / 0 / 0
Регистрация: 04.04.2013
Сообщений: 16
09.07.2013, 14:59     Подсчет количества способов, которыми можно разменять рубль медными монетами (достоинством 1, 2, 3, 5 копеек) #7
Цитата Сообщение от Thinker Посмотреть сообщение
Да, действительно, я учел порядок, а он не важен, спасибо. Так задачу о наклейке марок надо решать, тут другая рекурсия
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
 
long F(long *a, long i, long n)
{
   if (n < 0)
      return 0;
   else if (n == 0)
      return 1;
   return i < 0 ? 0 : F(a, i - 1, n) + F(a, i, n - a[i]);
}
 
int main()
{
   long a[4] = {1, 2, 3, 5};
   std::cout << F(a, 3, 100);
   return 0;
}
Ответ: 6518. Здесь последовательности упорядочены.
При этом существует 117372865913707249 способов наклеить марки на конверт стоимостью в 1,2,3 и 5 коп., чтобы в сумме получился 1 руб, так как последовательности неупорядочены.
Цитата Сообщение от Thinker Посмотреть сообщение
int main()
{
* *long a[4] = {1, 2, 3, 5};
* *std::cout << F(a, 3, 100);
* *return 0;
}
Почему у вас в функции F, вторая переменная равна 3?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.07.2013, 15:02     Подсчет количества способов, которыми можно разменять рубль медными монетами (достоинством 1, 2, 3, 5 копеек)
Еще ссылки по теме:

C++ Наименьшее количество купюр, которыми можно выдать n гривен
C++ Можно ли разменять m руб. на рублёвые, трёхрублёвые, пятирублёвые купюры так, чтобы получить всего 10 купюр
C++ Какими из приведенных способов можно задавать функцию main
Подсчет количества способов создания команды из 6 человек C++
C++ Требуется определить количество способов выплаты n рублей монетами по 1, 2, 5 и 10 рублей

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

Или воспользуйтесь поиском по форуму:
Thinker
Эксперт C++
4220 / 2194 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
09.07.2013, 15:02     Подсчет количества способов, которыми можно разменять рубль медными монетами (достоинством 1, 2, 3, 5 копеек) #8
Цитата Сообщение от Dantes48 Посмотреть сообщение
Почему у вас в функции F, вторая переменная равна 3?
это индекс последнего элемента массива a
Yandex
Объявления
09.07.2013, 15:02     Подсчет количества способов, которыми можно разменять рубль медными монетами (достоинством 1, 2, 3, 5 копеек)
Ответ Создать тему
Опции темы

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