l12

Динамично оптимиране - числа на Фибоначи и биномни коефициенти [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) = F²(n/2) + F²(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).
Да се реализира рекурсивен вариант, основан на динамичното програмиране.