Динамично оптимиране - числа на Фибоначи и биномни коефициенти [8.3.1, 8.3.2]

Числа на Фибоначи
* Числа на Фибоначи: F(0) = F(1) = 1 и F(i) = F(i-1) + F(i-2) за i > 1.

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
* Класически рекурсивен неефективен алгоритъм:
unsigned long fib(unsigned n)
{ if (n < 2) return 1;
  return fib(n - 1) + fib(n - 2);
}
    Експоненциална сложност - многократно извикване на функцията с един и същи аргумент!

* Динамично програмиране - със запомняне на вече пресметнатите стойности:

#include <stdio.h>
#define MAX 256
unsigned n = 10;
unsigned long m[MAX + 1];

unsigned long fibMemo(unsigned n)
{ if (n < 2) m[n] = 1;
  else if (0 == m[n]) m[n] = fibMemo(n - 1) + fibMemo(n - 2);
  return m[n];
}

int main()
{ memset(m, 0, MAX*sizeof(*m));
  scanf("%u", &n);
  printf("\n%u-тото число на Фибоначи е: %lu", n, fibMemo(n));
  return 0;
}
    Линейна сложност - всяка стойност се пресмята само веднаж.

* Друга формула за пресмянате на n-тото число на Фибоначи - със запомняне на вече пресметнате стойност.

F(n) = F2(n/2) + F2(n/2 - 1), за n четно;
F(n) = F(n - 1) + F(n - 2), за n нечетно.
#include <stdio.h>
#define MAX 250
#define SQR(X) ((X)*(X))

unsigned n = 10;
unsigned long m[MAX + 1];

unsigned long fMemo(unsigned n)
{ if (n < 2) m[n] = 1;
  else if (0 == m[n])
     if (1 == n%2) m[n] = fMemo(n - 1) + fMemo(n - 2);
     else m[n] = SQR(fMemo(n/2) + fMemo(n/2 - 1));
  return m[n];
}
int main()
{ memset(m, 0, MAX*sizeof(*m));
  scanf("%u", &n);
  printf("\n%u-тото число на Фибоначи е: %lu", n, fibMemo(n));
  return 0;
}
    Логаритмична сложност.

Биномни коефициенти

    Нека C(n, k) е биномният коефициент "n над k" или комбинации без повторения от n елемента k-ти клас.  Общата формула е: C(n, k) = n!/((n - k)! k!), а от триъгълника на Паскал имаме и рекурентна формула:

C(n, k) = 1,  за k = 0 или k = n;
C(n, k) = C(n - 1, k - 1) + C(n - 1, k),  за 0 < k < n;
C(n, k) = 0,  за k > n.
* Рекурсивен неефективен алгоритъм:
unsigned long binom(unsigned n, unsigned k)
{ if (k > n) return 0;
  if (k == 0 || k == n) return 1;
  return binom(n - 1, k - 1) + binom(n - 1, k);
}

* Динамично програмиране - със запомняне на вече пресметнатите стойности.
    Не е необходимо да се пази цялата таблица  C(n, k), а само един ред от таблицата - предишния.
#define MAX 200
unsigned long m[MAX];
unsigned long binomDynam(unsigned n, unsigned k)
{ unsigned i, j;
  for (i = 0; i <= n; i++)
  { m[i] = 1;
    if (i > 1)
    { if (k < i - 1) j = k; else j = i - 1;
      for (; j >= 1; j--) m[j] += m[j - 1];
    }
  }
  return m[k];
}
    Пример: n = 4, k = 3; C(4,3) = 4.

i j m
0 1 2 3 4
0 - 1 1 1 1 1
1 - 1 1 1 1 1
2 1 1 2 1 1 1
3 2 1 3 3 1 1
4 3 1 4 6 4 1 
    Този алгоритъм има сложност O(nk).
    Да се реализира рекурсивен вариант, основан на динамичното програмиране.
    Задача: (ЗИМНИ МАТЕМАТИЧЕСКИ ПРАЗНИЦИ, БУРГАС, 29 януари 2005, ТЕМА ЗА ГРУПА А (12 КЛАС)) Дадени са N дъски с правоъгълна форма, номерирани с числата от 1 до N (N < 2000). Дъските са с еднаква ширина, но с различна височина, като K-тата дъска е висока K дециметра. Подреждаме вертикално N-те дъски една до друга, така че да образуваме ограда. В зависимост от начина на подреждането се образуват участъци с последователно намаляващи дължини на дъските. Тези участъците обикновенно са повече от един, но може и цялата преграда да образува само един участък. Възможно е някои участъци да се състоят само от една дъска. Например, ако подредим 9 дъски, така че височините им да образуват последователността 6, 4, 2, 5, 3, 9, 7, 2, 1, 8, имаме 4 такива участъка 6, 4, 2; 5, 3; 9, 7, 2, 1 и 8. Колко от всичките възможни наредби на дъските ще образуват преграда, съдържаща точно P участъка (0 < P < N + 1).
    Напишете програма, която решава тази задача. Програмата трябва да прочете от стандартния вход стойностите на N и P, разделени с един интервал и да изведе на стандартния изход търсения брой прегради по модул 1020847 (т.е. остатъка на търсения брой при деление на 1020847).

ПРИМЕР 1
Вход
4 3
Изход
11
 ПРИМЕР 2
Вход
20 2
Изход
27708

Решение:
    Решаваме задачата по метода на динамичното оптимиране. Нека е дефинирана функция T(P,Q), която връща колко са пермутациите на P елемента, в които има точно Q намаляващи подредици. Тогава T(N,K) е отговорът на задачата. Допускаме, че когато искаме да изчислим T(P,Q), сме изчислили всички стойности T(R,S), за R  < P и S <= Q. 
    Да разсъждаваме по следния начин. Нека имаме една пермутация на P-1 елемента и започнем да добавяме числото P на всички възможни места. Тогава ако го добавим някъде във вече обособена намаляваща подредица, тя ще се разцепи на две, а ако го добавим точно преди началото на намаляваща подредица, броят на намаляващите редици в пермутацията ще се запази. Освен това поради начина на добавяме няма да повторим пермутации на P елемента. Понеже имаме изискването редиците да бъдат точно Q на брой, а местата, на които няма промяна в броя редици, са точно Q, то за T(P,Q) получаваме следната рекурентна формула:

T(P,Q) = Q*T(P-1,Q) + (P+1-Q)*T(P-1,Q-1).

Освен това Т(1,1) = 1, понеже ако имаме един единствен елемент, броят начини да образуваме една редица е точно 1.
    Сложността на описаното решение и от гледна точка на време, и от гледна точка на памет, е O(N2).

Примерна реализация: 

#include <stdio.h>
#define MOD 1020847
#define MAXN 2048

int t[MAXN][MAXN];
int main() 
{  int N, P, i, j; 
   scanf("%d%d", &N, &P); 
   t[1][1] = 1; 
   for (i = 2; i <= N;i++) 
      for (j = 1; j <= i; j++) 
          t[i][j] = ((j * t[i - 1][j])%MOD + 
                    ((i + 1 - j)*t[i - 1][j - 1])%MOD)%MOD; 
   printf("%d\n", t[N][P]); 
   return 0;
}
Автор: Слави Маринов (http://infoman.musala.com/)