|
dinamik dasturlash fibonachi ketma ketligi misolida
|
bet | 35/61 | Sana | 31.12.2021 | Hajmi | 4,28 Mb. | | #254919 |
| Bog'liq 2 5355268973329911567
28.dinamik dasturlash fibonachi ketma ketligi misolida.
Oddiy hisoblash usuli
long long fib(int n) {
if (n < 2)
return 1;
return fib(n-1) + fib(n-2);
}
int main() {
cout << fib(n);
} n ≤ 36
Hisoblash daraxti
Javoblarni yodda saqlash metodi
Qandaydir nomerli Fibonatchi soni hisoblangach uni saqlab qo’yish lozim va qayta hisoblamaslik kerak.
calculated mantiqiy massivida joriy indeksdagi qiymat hisoblangan yoki hisoblanmaganligi haqida ma’lumot saqlanadi.
F massivida hisoblangan sonlarni saqlaymiz
Tezroq hisoblash
bool calculated[1000001];
long long F[1000001];
long long fib(int n) {
if (n < 2)
return 1;
if (calculated[n])
return F[n];
long long res = fib(n-1) + fib(n-2);
F[n] = res;
calculated[n] = 1;
return res;
}
Do'stlaringiz bilan baham: |
|
|