Форум программистов, компьютерный форум, киберфорум
Thinker
Войти
Регистрация
Восстановить пароль
Рейтинг: 4.00. Голосов: 1.

Рекурсивные комбинаторные алгоритмы

Запись от Thinker размещена 10.07.2013 в 10:27
Обновил(-а) Thinker 10.07.2013 в 19:12

Задача о бандероли
За пересылку бандероли надо уплатить 100 рублей. Сколькими способами можно оплатить ее марками стоимостью 1,2,3,5 рублей, если два способа, отличающиеся порядком марок, считаются различными (запас марок различного достоинства считаем неограниченным).
Используем рекурсивную функцию
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;
}


с помощью динамического программирования задача решается более элегантно и быстро:
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
#include<iostream>
const long N = 101;
 
int main()
{
   long long count[N] = {1, 1, 2, 4, 7, 14};
   for(int i = 5; i < N; ++i)
      count[i] = count[i-1] + count[i-2] + count[i-3] + count[i-5];
   std::cout << (unsigned long long)count[100] << std::endl;
   return 0;
}

Размен рубля
Требуется составить алгоритм подсчета количества способов, которыми можно разменять рубль медными монетами(достоинством в 1,2,3,5 копеек).
Данная задача решается несколько другим способом, так как здесь последовательности должны быть упорядочены
Кликните здесь для просмотра всего текста
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 способов.
Размещено в Без категории
Просмотров 1289 Комментарии 2
Всего комментариев 2
Комментарии
  1. Старый комментарий
    Thinker, а можешь написать динамику по этой рекурсии?
    Запись от Dani размещена 10.07.2013 в 17:01 Dani вне форума
  2. Старый комментарий
    Аватар для Thinker
    да, алгоритм привел
    Запись от Thinker размещена 10.07.2013 в 18:28 Thinker вне форума
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.