دنباله n ام فیبوناچی

Question

سلام

فرض کنید Fib(n) نشان دهنده جمله n ام این دنباله باشد.آنگاه سریع ترین الگوریتم برای محاسبه (Fib )n^2 چیست؟

جواب درنظرگرفته شده logn

به نظر میرسه n^2 هزینه باشه :

for(i=0;i<n^2;i++)
q[i]=-1;
Fib(n) {
if(n<3){q[n]=1; return 1; }
if(q[n]>=0) return q[n];
q[n]=Fib(n-1)+Fib(n-2);
return q[n];
}

 

Answer 1

http://kukuruku.co/hub/algorithms/the-nth-fibonacci-number-in-olog-n

این جا توضیح داده که کلن چطوری جمله ی n ام دنباله ی فیبوناچی رو با هزینه ی لاگ ان به دست بیاریم

اردر دو به توان اِن دیگه انصافن خیلی ضایس، نزن همچین کدی رو هیچ وقت

+ توضیح اضافه:

اگر این ماتریس رو به توان n برسونید، درایه ی بالا و چپش جمله ی n ام دنباله ی فیبوناچی خواهد بود. لازم به ذکره که تابع به توان رسوندن یه ماتریس با اندازه ی معین رو از اردر لاگ ان میشه نوشت.

Answer 2

لینکی که گذاشتید دوباره چک کنید ، کد رو قرار میدم،با زمان lgn :

#include <stdio.h>
 
void multiply(int F[2][2], int M[2][2]);
 
void power(int F[2][2], int n);
 
/* function that returns nth Fibonacci number */
int fib(int n)
{
  int F[2][2] = {{1,1},{1,0}};
  if (n == 0)
    return 0;
  power(F, n-1);
  return F[0][0];
}
 
void power(int F[2][2], int n)
{
  if( n == 0 || n == 1)
      return;
  int M[2][2] = {{1,1},{1,0}};
 
  power(F, n/2);
  multiply(F, F);
 
  if (n%2 != 0)
     multiply(F, M);
}
 
void multiply(int F[2][2], int M[2][2])
{
  int x =  F[0][0]*M[0][0] + F[0][1]*M[1][0];
  int y =  F[0][0]*M[0][1] + F[0][1]*M[1][1];
  int z =  F[1][0]*M[0][0] + F[1][1]*M[1][0];
  int w =  F[1][0]*M[0][1] + F[1][1]*M[1][1];
 
  F[0][0] = x;
  F[0][1] = y;
  F[1][0] = z;
  F[1][1] = w;
}
 
/* Driver program to test above function */
int main()
{
  int n = 9;
  printf("%d", fib(9));
  getchar();
  return 0;
}

در واقع جواب به شکل زیر بدست میاد: