#!/usr/bin/perl # 使用遞迴方法 (recursive) - 速度慢 # 輸入 : 整數 n # 輸出 : 費波那契數 sub fibonacci { my $n = shift; return 0 if ($n==0); return 1 if ($n==1); return fibonacci($n+2) - fibonacci($n+1) if ($n<0); return fibonacci($n-1) + fibonacci($n-2); } # 使用疊代方法 (iterative) - 速度快 # 輸入 : 整數 n # 輸出 : 費波那契數 sub fibonacci_i { my $n = shift; my (@fib, $i, $neg); $neg = 0; if ($n<0) { $n = abs($n); $neg = 1; } $fib[0] = 0; $fib[1] = 1; for ($i=2;$i<=$n;$i++) { $fib[$i] = $fib[$i-1] + $fib[$i-2]; } return (-1)**($n+1)*$fib[$n] if ($neg); return $fib[$n]; }
# 上面程式以自家電腦執行發現
# F74 之後以科學記號顯示
# F1477 之後溢位無法計算
# 使用大數模組 (package) # 輸入 : 整數 n # 輸出 : 費波那契數 use Math::BigInt; sub fibonacci_p { my $n = shift; my (@fib, $i, $neg, $temp); $neg = 0; if ($n<0) { $n = abs($n); $neg = 1; } $fib[0] = 0; $fib[1] = 1; for ($i=2;$i<=$n;$i++) { $temp = Math::BigInt->new($fib[$i-1]); $temp = $temp->badd($fib[$i-2]); $fib[$i] = $temp; } if ($neg) { $temp = Math::BigInt->new(-1); $temp = $temp->bpow($n+1); return $temp*$fib[$n]; } return $fib[$n]; }
全站熱搜
留言列表