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

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

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

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

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

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

Сколькими способами можно отобрать команду в составе 5 человек из 8 кандидатов;из 10 кандидатов; из 11 кандидатов? Подсчет количества способов отбора - C++
Нужна помощь, есть код на Pascal нужно в C. Вот программа: function fact(x: longint): longint; begin if x=0 then fact:=1 ...

Подсчет количества способов создания команды из 6 человек - C++
Нужен алгоритм создания программы, которая подсчитывает количество способов создания команды из 6 человек, в которой не менее 2 девочек,...

Требуется определить количество способов выплаты n рублей монетами по 1, 2, 5 и 10 рублей - C++
Формат входных данных На вход программе дается одно натуральное число n (n ≤ 99). Формат выходных данных Требуется вывести одно...

например 317 должно вывести 3 гривны 17 копеек, 1 гривна 00 копеек - C++
Помогите подумать над алгоритмом, вот сама задача: Дано натуральное число, равное выраженной в копейках цене некоторого товара, например...

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

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

7
Day
1158 / 963 / 57
Регистрация: 29.10.2009
Сообщений: 1,385
07.09.2012, 16:35 #2
Цитата Сообщение от алишка999 Посмотреть сообщение
разменять рубль медными монетами(достоинством в1,2,3,5 копеек)
Видать, задачка-то еще со времен СССР
0
алишка999
1 / 1 / 0
Регистрация: 01.09.2012
Сообщений: 30
07.09.2012, 16:36  [ТС] #3
а что делать раз задали
0
Thinker
Эксперт С++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
07.09.2012, 21:39 #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;
}
1
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
08.09.2012, 02:26 #5
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от Thinker Посмотреть сообщение
получается 117372865913707249 способов.
многовато )
У меня получается всего 6518.
Все дело в том что например варианты для набора 3-х копеек: (1 2) и (2 1) Вы считаете разными, хотя это одно и тоже.
3
Thinker
Эксперт С++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
08.09.2012, 12:34 #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 руб, так как последовательности неупорядочены.
1
Dantes48
0 / 0 / 0
Регистрация: 04.04.2013
Сообщений: 16
09.07.2013, 14:59 #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?
0
Thinker
Эксперт С++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
09.07.2013, 15:02 #8
Цитата Сообщение от Dantes48 Посмотреть сообщение
Почему у вас в функции F, вторая переменная равна 3?
это индекс последнего элемента массива a
2
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.07.2013, 15:02
Привет! Вот еще темы с ответами:

Определить, можно ли разменять сумму в N копеек данными монетами - Pascal ABC
Задача 12. Имеются монеты достоинством 10,15,20,50 копеек. Определить, можно ли разменять сумму в N копеек данными монетами.

Рекурсивно определить, мржно ли заданную сумму денег разменять монетами по 3, 10, 15 копеек - C (СИ)
Добрый день. Подскажите, пожалуйста, где ошибка в решении следующей задачи: написать программу, которая рекурсивно позволяет определить,...

Найдите число способов наклейки марок достоинством в 3, 5 и 10 копеек так, чтобы общая сумма была равна 16 коп - Комбинаторика
Найдите число способов наклейки марок достоинством в 3, 5 и 10 копеек так, чтобы общая сумма была равна 16 копейкам.

Можно ли разменять 25 рублей десятью купюрами достоинством в 1,3,5 - Pascal ABC
можно ли разменять 25 рублей при помощи десяти купюр достоинством в 1,3,5 паскальABC


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

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

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