關於菲波那契數列的一個低級問題?

四、矩陣快速冪

若題主想了解效率更高的演算法來處理數據量更大的情況，可以看看以下這個編程題目：

#include &

struct Mat {
int val[matSize][matSize];
void init() {
memset(val, 0, sizeof(val));
}
void set1() { // 把矩陣置為單位矩陣
for(int i = 0; i &< matSize; ++i) for(int j = 0; j &< matSize; ++j) val[i][j] = (i == j); } friend Mat operator * (Mat a, Mat b) { // 重載*號進行矩陣乘法 Mat res; res.init(); for(int i = 0; i &< matSize; ++i) { for(int k = 0; k &< matSize; ++k) { if(a.val[i][k]) { for(int j = 0; j &< matSize; ++j) { res.val[i][j] += a.val[i][k] * b.val[k][j]; res.val[i][j] %= mod; } } } } return res; } friend Mat operator ^ (Mat a, int x) { // 重載^號進行快速冪運算 Mat res; res.set1(); while(x) { if(x 1) res = res * a; a = a * a; x &>&>= 1;
}
return res;
}
};


import Data.List
import Data.Bits

fib :: Int -&> Integer
fib n = snd . foldl" fib" (1, 0) . dropWhile not $
[testBit n k | k &<- let s = bitSize n in [s-1,s-2..0]] where fib" (f, g) p | p = (f*(f+2*g), ss) | otherwise = (ss, g*(2*f-g)) where ss = f*f+g*g fibonMod n d = mod (fib n) d

ghci&> fibonMod 10000000 10007
28
(0.20 secs, 20298700 bytes)
ghci&> fibonMod 100000000 10007
6193
(2.89 secs, 230900212 bytes)
ghci&> fibonMod 100000 10007
5675
(0.00 secs, 0 bytes)
ghci&> fibonMod 1000000 10007
114
(0.02 secs, 1209368 bytes)
ghci&> fibonMod 10000000 10007
28
(0.20 secs, 20298740 bytes)
ghci&> fibonMod 100000000 10007
6193
(2.89 secs, 230953920 bytes)
ghci&> fibonMod 1000000000 10007
7300
(34.43 secs, 2283929676 bytes)
ghci&> fibonMod 10000000000 10007
6734
(46.36 secs, 3231113156 bytes)
ghci&> fibonMod 100000000000 10007
9877
(41.68 secs, 2785967264 bytes)


看到上面有人寫了 Haskell 的代碼, 一看時間覺得怪怪的, 怎麼會那麼慢呢. 於是我試著寫了一個:

fib n m = fst $ fib" n m

fib" n m
| n == 0 = (0, 1)
| mod n 2 == 1 = (p, q)
| otherwise = (r, p)
where
(a, b) = fib" (div n 2) m
p = mod (b * b + a * a) m
q = mod (b * (2 * a + b)) m
r = mod (a * (2 * b - a)) m


測試了一下, 證明 Haskell 還是可以很快的.

*Main&> map (flip fib 10007) [1..20]
[1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765]
(0.01 secs, 2077504 bytes)
*Main&> fib 1000000 10007
114
(0.01 secs, 1553336 bytes)
*Main&> fib 10000000 10007
28
(0.00 secs, 1556312 bytes)
*Main&> fib 100000000 10007
6193
(0.01 secs, 1556220 bytes)
*Main&> fib 1000000000000000000000000000000000000000000000000000000 10007
6193
(0.01 secs, 1555316 bytes)
*Main&> fib 1000000000000000000000000000000000000000000000000000000 10007
6193
(0.01 secs, 1554428 bytes)
*Main&> fib 10000000000000000000000000000000000000000000000000000000 10007
7300
(0.01 secs, 2098484 bytes)


def recfib(n,m):
if n == 0: return (0, 1)
a, b = recfib(n / 2,m)
return ((b*b+a*a)%m, b*(2*a+b)%m) if n%2 else (a*((2*b)-a)%m, ((b*b+a*a))%m)


對 @沈周 的答案做個筆記。

3. 可以二分且每層的計算複雜度為常量的問題，總複雜度為O(logn)

#include &
#include &
const int MaxN = 1000000;
int fib[MaxN + 1];

int main(){
for (int i = 1; i &<= MaxN; i++) fib[i] = -1; static int stack[MaxN * 5], bak; asm __volatile__ ( "movl %%esp, %0 " "movl %1, %%esp ": "=g"(bak): "g"(stack + MaxN * 5 - 1): ); printf("%d ", f(MaxN)); asm __volatile__ ( "movl %0, %%esp " : : "g"(bak) ); return 0; }

for(int i=3;i&<=n;i++) { int c=a+b; c=c%10007 a=b; b=c; }

int f(int n)
{
if(n&<3) return 1; int a=1; int b=1; for(int i=3;i&<=n;i++) { int c=a+b; a=b; b=c; } return b; }

uint64_t fib_helper(uint64_t n,uint64_t a,uint64_t b)
{
if(n &< 3) return b; return fib_helper(n-1,b,a+b); }

a = sqrt(5);

#include &
#include &

沒太留心運行時間，不過應該還不至於讓樓主拿1000000測試就直接跪。

之所以拿出來獻醜，只是想說明這個問題可以用遞歸。

#include &
using namespace std;
long long a[1000000];
void fib()
{
a[0] = 0;
a[1] = a[2] = 1;
for (int i = 3; i &< 1000000; i++) { a[i] = a[i-1] + a[i-2] ;//全部都存在了a這個數組中，待會直接取 //如果求餘數，這句改為a[i]=(a[i-1] + a[i-2])%10007 //此時你基本可AC了。 } } int main() { int n; fib(); cin &>&> n;
cout &<&< a[n] &<&< endl; return 0; }

• return f(n-1)+f(n-2);//不推薦

• 

  這裡會考慮到有沒有叫做尾遞歸優化的東西~~Python自帶沒有。

• 利用fib的公式求解
• 迭代。上面那些回答的人中就有迭代。
• 呵呵~~~

扯一句沒用的

#include &
#include &
#include &
#define DIV_N 10007
int
fib_div(int n)
{
int f1 = 1,f2 = 1;
int i;
int res = 0;
int tmp;
if (n &< 3) { return 1; } for(i = 2;i &< n; i++) { res = f1 + f2; f1 = f2; f2 = res; if(f1 &> DIV_N) {
f1 -= DIV_N;
}
if(f2 &> DIV_N) {
f2 -= DIV_N;
}
if (f1 == 1 f2 == 1) {
tmp = n % (i - 1);
return fib_div(tmp);// can be optimized
}
}
return f2;
}
int main()
{
int n = 1000000000;
int rv;
clock_t f_s,f_e;
f_s=clock();
rv = fib_div(n);
f_e=clock();
printf("So n is %d, and the result is %d, time %ums
",n, rv, f_e-f_s);
return 0;
}


結果

So n is 1000000000, and the result is 7300, time 0ms