Algoritmdan nazorat savollariga javoblar Algoritm nima

28.dinamik dasturlash fibonachi ketma ketligi misolida.

• 
  Deyarli dinamik dasturlashga misol
  
• 
  Fib[0] = Fib[1] = 1;
  
• 
  Fib[n] = Fib[n-1] + Fib[n-2] agar n>1
  

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;
  
• 
  }