Algoritmdan nazorat savollariga javoblar Algoritm nima

32. N-fibonachi sonini tezkor hisoblash.

Matematik nuqtai nazardan Fibonachchi ketma-ketligi deganda quyidagi shartlarni bajaruvchi ketma-ketlikka aytiladi:

F(n) = F(n-1) + F(n-2) va F(0) = 0, F(1) = 1

Ta’rif: Har bir hadi o’zidan oldingi ikkita hadning yig’indisiga teng bo’lgan ketma-ketlik Fibonachchi ketma-ketligi deyiladi. Bunda boshlang’ish ikkita had ko’pincha 0 va 1 deb olinadi. Lekin, ixtiyoriy ikkita son boshlang’ish had sifatida olinishi ham mumkin.

(0), 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … sonlari Fibonachchi ketma-ketligining dastlabki hadlari hisoblanadi.

Fibonachchi raqamlari (ba'zan ular Fibonachchi [2] deb yozadilar) raqamli ketma-ketlikning elementlari unda birinchi ikkita raqam 1 yoki 1 yoki 0 va 1 bo'ladi va har bir keyingi raqam oldingi ikkita raqamlarning yig'indisiga teng bo'ladi. O'rta asrlardagi matematik Leonardo Pizaning nomi (Fibonachchi sifatida tanilgan).

Ba'zan Fibonachchi raqamlari n manfiy qiymatlari uchun ham bir xil takrorlanish munosabatlarini qondiradigan ikki tomonlama cheksiz ketma-ketlik sifatida qabul qilinadi. Bundan tashqari, salbiy indekslarga ega bo'lgan a'zolarni ekvivalent ekstremal formuladan foydalanib osongina olish mumkin:

#include

using namespace std;

int fibonachi(int n)

{

if (n<=1)

return n;

else

return fibonachi(n-2)+fibonachi(n-1);

}

int main()

{

int n;

cin>>n;

cout<

}
Fibonatchi sonlarini uchta usul bo’yicha hisoblashni ko’rib chiqaylik.

3. 
   To’g’ri tartib
   

fib[1] = 1; // boshlang’ich holat

fib[2] = 1; // boshlang’ich holat

for (int i = 3; i ≤ n; i++) {

fib[i]:=fib[i-1]+fib[i-2] // i holatini qayta hisoblash

}

4. 
   Teskari tartib
   

fib[1] = 1; // boshlang’ich holar

for (int i = 3; i ≤ n; i++) {

fib[i+1]:=fib[i] // i+1 holatini yangilash

fib[i+2]:=fib[i] // i+2 holatini yangilash

}

5. 
   Erinchoq dinamika
   

int fib[] = {-1}; // dastlab -1 ga to’ldiramiz, bu uning qiymati hali hisoblanmaganligini bildiradi.

int get_fib(int i) {

if (i ≤ 2) {

fib[i] = 1; //boshlang’ich holar

return 1;

}

if (fib[i] != -1) {// Avval hisoblanganmi

return fib[i]; // erinchoqlik qilib hisoblangan qiymatni qaytaradi

}

fib[i] = get_fib(i-1)+get_fib(i-2);

return fib[i];

}

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