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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 26, средняя оценка - 5.00
алишка999
1 / 1 / 0
Регистрация: 01.09.2012
Сообщений: 30
07.09.2012, 16:08     составить алгоритм подсчета количества способов, которыми можно разменять рубль медными монетами(достоинством в1,2,3,5 копеек) #1
составить алгоритм подсчета количества способов, которыми можно разменять рубль медными монетами(достоинством в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++ Составить функцию для подсчета количества различных чисел в массиве
C++ Составить программу для подсчета набольшего количества одинаковых элементов, размещенных последовательно, в массиве для каждого одномерного массива...
C++ Сколькими способами можно отобрать команду в составе 5 человек из 8 кандидатов;из 10 кандидатов; из 11 кандидатов? Подсчет количества способов отбора
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Day
 Аватар для Day
1149 / 954 / 57
Регистрация: 29.10.2009
Сообщений: 1,384
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++
 Аватар для Thinker
4215 / 2189 / 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++
 Аватар для valeriikozlov
4660 / 2486 / 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++
 Аватар для Thinker
4215 / 2189 / 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++
Рекурсия (алгоритм подсчета числа способов, с помощью которых можно представить число М в виде суммы) C++
Составить программу для подсчета количества четных, нечетных и нулевых элементов матрицы C++

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

Или воспользуйтесь поиском по форуму:
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 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 копеек)
Ответ Создать тему
Опции темы

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