算法实现/数学/斐波那契数程序
斐波那契类似于许多函数式编程语言的“hello world”，因为它可能涉及模式匹配、备忘录和普通的尾递归（等效于迭代）等范式。然而，线性时间的迭代或尾递归只是第一步：更巧妙的求幂以对数时间运行。
虽然比奈/卢卡斯公式从技术上讲也是求幂，但它使用浮点数使其不如基于矩阵的解决方案有吸引力。此外，上面关于复杂性的讨论，以及这里的大多数代码，都假设加法和乘法都在一步内完成，但这对于通过斐波那契计算轻松创建的大型、指数增长的数字来说并非如此。
以下大部分内容的解释可以在 nayuki 的文章 中找到。
unsigned int fib(unsigned int n) {
// This is exactly the same as a ternary expression
if (n < 2)
return n;
else
return fib(n - 1) + fib(n - 2);
}
// C++ default arguments used. If implemented in C, call with fib(n, 0, 1) instead.
unsigned int fib(unsigned int n, unsigned int acc = 0, unsigned int prev = 1) {
if (n < 1)
return acc;
else
return fib(n - 1, prev + acc, acc);
}
#include <math.h>
const static double phi = (1 + sqrt(5)) / 2;
long fib(unsigned int n) {
return (pow(phi, n) - pow(1 - phi, n)) / sqrt(5);
}
unsigned int fib(unsigned int n) {
unsigned int i = 0, j = 1, t;
if (n == 0)
return 0;
for (k = 1; k < n; ++k) {
t = i + j;
i = j;
j = t;
}
return j;
}
// This version is more "parallel" in the sense of a more unrolled loop.
unsigned int fib(int n) {
unsigned int i = 0, j = 1, k = 1;
for (; n >= 3; n -= 3) {
i = j + k;
j = i + k;
k = i + j;
}
return n == 0 ? i :
n == 1 ? j :
k;
}
// A 2x2 matrix: m00, m01; m10, m11.
typedef struct mat22_s {
unsigned int m00, m01, m10, m11;
} mat22_t;
// Matrix multiplication.
inline static mat22_t mat22_mul(mat22_t a, mat22_t b) {
return (mat22_t){
a.m00 * b.m00 + a.m01 * b.m10, a.m00 * b.m01 + a.m01 * b.m11,
a.m10 * b.m00 + a.m11 * b.m10, a.m10 * b.m01 + a.m11 * b.m11};
}
// This is a less concise version written for clarity. The compiler should be able to optimize the boilerplate out.
unsigned int fib(unsigned int n) {
// Matrix holds F(N-1), F(N); F(N), F(N+1).
// This is an identity matrix, also the 0th power of matrix.
mat22_t result = {1, 0, 0, 1};
mat22_t matrix = {1, 1, 1, 0};
for (; n > 0; n /= 2) {
if (n % 2 == 1) {
result = mat22_mul(matrix, result);
}
matrix = mat22_mul(matrix, matrix);
}
return result.m10;
}
// A moderately compact version of the matrix calculation.
unsigned int fib(unsigned int n) {
// [a b] is "result"; [c d] is "matrix".
unsigned int a = 1, b = 0, c = 0, d = 1, t;
if (n == 0)
return 0;
n = n - 1;
while (n > 0) {
if (n % 2 == 1) {
t = d * (b + a) + c * b;
a = d * b + c * a;
b = t;
}
t = d * (2 * c + d);
c = c * c + d * d;
d = t;
n = n / 2;
}
return a + b;
}
一个类似的替代方案是 基于卢卡斯数。
// Nayuki's fast doubling code. Runs from high to low bits.
#include <limits.h>
static inline unsigned int log2i(unsigned int n) {
#if defined(__has_builtin) && __has_builtin(__builtin_clz)
return sizeof (unsigned int) * CHAR_BIT - __builtin_clz(n) - 1;
#else
return sizeof (unsigned int) * CHAR_BIT - 1; // pessimistic guess
#endif
}
unsigned int fib(unsigned int n) {
// Two numbers for iteration. At the end, a = F(N) and b = F(N+1).
unsigned int a = 0, b = 1;
// log2i is not reliable for n = 0. We know better.
unsigned int mask = n == 0 ? 0 : 1 << log2i(n);
for (; mask > 0; mask /= 2) {
// F(2k) = F(k) * (2 * F(k+1) + F(k))
unsigned int new_a = a * (b * 2 - a);
// F(2k+1) = F(k+1)**2 + F(k)**2
unsigned int new_b = a * a + b * b;
a = new_a;
b = new_b;
if (n & mask) {
new_b = a + b;
a = b;
b = new_b;
}
}
return a;
}
C# 代码与 C 代码基本相同，只是有一些静态方法说明符。
static int fib(int n) {
int fib0 = 0, fib1 = 1;
for (int i = 2; i <= n; i++) {
int tmp = fib0;
fib0 = fib1;
fib1 = tmp + fib1;
}
return (n > 0 ? fib1 : 0);
}
static int fibBINET(int n) {
double sqrt5 = Math.Sqrt(5.0);
double phi = (1 + sqrt5 ) / 2;
return (int)((Math.Pow(phi, n) - Math.Pow(-phi, -n)) / sqrt5);
}
static Num FibonacciNumber(int n) {
Num n1 = new Num(0);
Num n2 = new Num(1);
Num n3 = new Num(1);
for (int i = 2; i <= n; i++) {
n3 = n2 + n1;
n1 = n2;
n2 = n3;
}
return n3;
}
struct Num {
const int digit_base = 0x40000000; // 2^30
List<int> digits;
public int Length { get { return digits.Count; } }
public int this[int index] { get { return digits[index]; } private set { digits[index] = value; } }
public Num(int i) {
digits = new List<int>();
while (i > 0) {
digits.Add(i % digit_base);
i /= digit_base;
}
}
public static Num operator +(Num a, Num b) {
Num n = new Num();
n.digits = new List<int>();
int l = Math.Min(a.Length,b.Length);
int remainder = 0;
for (int i = 0; i < l; i++) {
n.digits.Add((a[i] + b[i] + remainder) % digit_base);
remainder = (a[i] + b[i] + remainder) / digit_base;
}
Num longer = a.Length > b.Length ? a : b;
for (; l < longer.Length; l++) {
n.digits.Add((longer[l] + remainder) % digit_base);
remainder = (longer[l] + remainder) / digit_base;
}
if (remainder > 0) n.digits.Add(remainder);
return n;
}
public override string ToString() {
StringBuilder sb = new StringBuilder();
for (int i = Length - 1; i >= 0; i--) {
sb.AppendFormat("{0:D" + (digit_base.ToString().Length-1) + "}", this[i]);
}
return sb.ToString();
}
}
ulong fib(uint n){
return (n < 2) ? n : fib(n - 1) + fib(n - 2);
}
ulong fib(uint n) {
ulong fib0 = 0;
ulong fib1 = 1;
for (auto i = 2; i <= n; i++) {
auto tmp = fib0;
fib0 = fib1;
fib1 = tmp + fib1;
}
return (n > 0 ? fib1 : 0);
}
ulong fib(uint n){
static ulong[] memo;
if (n < 0)
return n;
if (n < memo.length)
return memo[n];
auto result = (n < 2) ? n : fib(n - 1) + fib(n - 2);
memo.length = n + 1;
memo[n] = result;
return result;
}
fib(0) -> 0;
fib(1) -> 1;
fib(N) -> fib(N-1) + fib(N-2).
fib(N) ->
S = math:sqrt(5),
round(math:pow(((1 + S) / 2), N) / S).
算法取自下面的 Pascal “更有效” 版本
let rec fib x = if x < 2I then x else fib(x - 1I) + fib(x - 2I)
此版本使用 F# System.Numerics.BigInteger 类型
open System.Collections.Generic
let rec fib n =
let memo = Dictionary<_, _>()
let rec fibInner = function
| n when n = 0I -> 0I
| n when n = 1I -> 1I
| n -> fib(n - 1I) + fib(n - 2I)
if memo.ContainsKey(n) then memo.[n]
else
let res = fibInner n
memo.[n] <- res
res
let fib n =
let rec fibInner (n, a, b) =
if (n = 0I) then a
else fibInner ((n - 1I), b, (a + b))
fibInner (n, 0I, 1I)
let fib n =
if n < 2I then
n
else
let mutable fib1 = 0I
let mutable fib2 = 1I
let mutable i = 2I
let mutable tmp = 0I
while (i <= n) do
i <- i + 1I
tmp <- fib1
fib1 <- fib2
fib2 <- tmp + fib2
fib2
let fibSeq =
Seq.unfold (fun (a, b) -> Some(a, (b, a + b))) (0I, 1I)
let fib n =
fibSeq |> (Seq.skip n) |> Seq.head
: fib ( n -- fib ) 0 1 rot 0 ?do over + swap loop drop ;
func fib(n int) int {
if n < 2 {
return n;
}
return fib(n-1) + fib(n-2);
}
func fib(n int) int {
if n == 0 {
return 0
}
a, b := 0, 1
for i := 1; i < n; i++ {
a, b = b, a+b
}
return b
}
fib n = fibs 0 1 !! n
where
fibs a b = a : fibs b (a + b)
fib n | n < 0 = undefined
| otherwise = fib' n 0 1
where
fib' 0 a _ = a
fib' n a b = fib' (n - 1) b (a + b)
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
fibs = 0 : 1 : [ a + b | (a, b) <- zip fibs (tail fibs)]
或者
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
或者
fibs = map fst $ iterate (\(a,b)->(b,a+b)) (0,1)
定义自定义数据类型的算术运算，然后使用它来运行显式公式，无需通过浮点数 - 无需舍入或截断。在几秒钟内计算出第千万个斐波那契数（它大约有 200 万位数字）。
module Fib where
-- A type for representing a + b * sqrt n
-- The n is encoded in the type.
data PlusRoot n a = a :+/ a
deriving (Eq, Read, Show)
infix 6 :+/
-- Fetch the n in the root.
class WithRoot n where
getRoot :: Num b => PlusRoot n a -> b
instance (WithRoot n, Num a) => Num (PlusRoot n a) where
(a :+/ b) + (c :+/ d) = (a + c) :+/ (b + d)
x@(a :+/ b) * (c :+/ d) = (a * c + getRoot x * b * d) :+/ (a * d + b * c)
negate (a :+/ b) = negate a :+/ negate b
fromInteger = (:+/ 0) . fromInteger
-- I could implement these with (Ord a) but then we can't use the type
-- with e.g. complex numbers.
abs _ = error "PlusRoot.abs: unimplemented"
signum _ = error "PlusRoot.signum: unimplemented"
instance (WithRoot n, Fractional a) => Fractional (PlusRoot n a) where
fromRational = (:+/ 0) . fromRational
recip x@(a :+/ b) = (a / r) :+/ (negate b / r)
where
r = a*a - getRoot x * b*b
-- Type parameter to PlusRoot. It would be easy to declare similar
-- types for Two or whatever, and get all the above arithmetic for free.
newtype Five = Five Five
instance WithRoot Five where
getRoot _ = 5
-- The formula is phi^n - xi^n / sqrt 5
-- but it's always an integer, i.e. phi^n - xi^n is always a multiple
-- of sqrt 5, so the division isn't strictly necessary - just grab the
-- relevant coefficient.
fib :: Integer -> Integer
fib n = case phi^n - xi^n of
-- The 'round' here is to make the types match; as discussed previously
-- n must be an integer so no actual rounding is done.
_ :+/ n -> round n
where
phi :: PlusRoot Five Rational
phi = (1 :+/ 1) / 2
xi = (1 :+/ negate 1) / 2
有关其他版本，请参见
fibonacci?{
??0 1
?=0:???
(1??,+/?)? ?-1
}
fibonacci?{+/{?!??}(??)-?IO}
fib := method(n,
if(n < 4,
(n + n % 2) / 2,
(n % 2 * 2 - 1) * fib((n + n % 3) / 2 - 1) ** 2 + fib((n - n % 3) / 2 + 1) ** 3
)
)
Number fibonacci := method((self - 1) fibonacci + (self -2) fibonacci)
1 fibonacci = 1
0 fibonacci = 0
public void run(int n) {
if (n <= 0) {
return;
}
run(n, 1, 0);
}
private void run(int n, int eax, int ebx) {
n--;
if (n == 0) {
System.out.println(eax + ebx);
return;
}
run(n, ebx, eax + ebx);
}
/* Recursive versions. Horribly inefficient. Use iterative/memoized versions instead */
public long fib(long n) {
if (n < 2) {
return 1;
}
return fib(n - 1) + fib(n - 2);
}
public long fib2(long n) {
return (n < 2) ? n : getValue(n - 1) + getValue(n - 2);
}
/**
* Source based on
* http://20bits.com/2007/05/08/introduction-to-dynamic-programming/
* as at 9-May-2007
*/
private long fibonacci(int n) {
long n2 = 0;
long n1 = 1;
long tmp;
for (int i = n; i >= 2; i--) {
tmp = n2;
n2 = n1;
n1 = n1 + tmp;
}
return n2 + n1;
}
/**
* returns the Nth number in the Fibonacci sequence
*/
public int fibonacci(int N) {
int lo = 0;
int hi = 1;
for (int i = 0; i < N; i++) {
hi = lo + hi;
lo = hi - lo;
}
return lo;
}
private int[] fibs; // array for memoized fibonacci numbers
public int fib(int n) {
if (n < 2) {
return n;
}
if (fibs == null) { // initialise array to first size asked for
fibs = new int[n + 1];
}
else if (fibs.length < n) { // expand array
int[] newfibs = new int[n + 1]; // inefficient if looping through values of n
System.arraycopy(fibs, 0, newfibs, 0, fibs.length);
fibs = newfibs;
}
if (fibs[n] == 0) {
fibs[n] = fib(n - 1) + fib(n - 2);
}
return fibs[n];
}
public int fib(int n) {
if (n < 2) {
return n;
}
int[] f = new int[n + 1];
f[0] = 0;
f[1] = 1;
for (int i = 2; i <= n; i++) {
f[i] = f[i - 1] + f[i - 2];
}
return f[n];
}
Fibonacci: Principal : Rôles : n :: nombre Actions : "Entrez un nombre :" ! n ? fibo(n) ! Fibo : Rôles : * n :: nombre Actions : si n < 2 alors retourne n retourne fibo(n-1) + fibo(n-2)
clase Fib
publicos:
mensajes:
Fib nop
Fibonacci(deme n es una cantidad) es_funcion cantidad
{
los objetos uno, dos, tres, i, respuesta son cantidades
copie 0 en uno
copie 1 en dos
variando i desde 1 hasta n haga:
{
copie uno en respuesta
copie uno + dos en tres
copie dos en uno
copie tres en dos
}
retornar uno
}
/**********************************/
tarea
{
el objeto f es un Fib
muestre "el 5: ", f.Fibonacci(doy 5)
}
function fib(n)
local a, b = 0, 1
while n > 0 do
a, b = b, a + b
n = n - 1
end
return a
end
function fib(n)
if n > 1 then n = fib(n - 1) + fib(n - 2) end
return n
end
function F = fibonacci_recursive(n)
if n < 2
F = n;
else
F = fibonacci_recursive(n-1) + fibonacci_recursive(n-2);
end
function F = fibonacci_iterative(n)
first = 0;
second = 1;
third = 0;
for q = 1:n,
third = first + second;
first = second;
second = third;
end
F = first;
fib(n):=
if n < 2 then
n
else
fib(n - 1) + fib(n - 2)
$
fib(n):=(%phi^n-(-%phi)^-n)/sqrt(5);
fib(n) := block(
[i,j,k],
i : 1,
j : 0,
for k from 1 thru n do
[i,j] : [j,i + j],
return(j)
)$
fib(n) := block(
[i,F,A],
if n <= 0 then
return(0),
i : n - 1,
F : matrix([1,0],[0,1]),
A : matrix([0,1],[1,1]),
while i > 0 do block(
if oddp(i) then
F : F.A,
A : A^^2,
i : quotient(i,2)
),
return(F[2,2])
)$
let fib n =
let rec fibonacci n =
match n with
| 0 -> (0, 0)
| 1 -> (0, 1)
| m ->
let (a, b) = fibonacci (m-1) in
(b, a+b)
in
let (_, k) = fibonacci n in
k;;
function F(n: integer): integer;
begin
case n of
1,2: Result:=1
else Result:=F(n-1)+F(n-2) end;
end;
function F(n: integer): integer;
begin
Result:=Round(Power((1+sqrt(5))/2, n)/sqrt(5));
end;
请注意，Power 通常在 Math 中定义，默认情况下不包含。
对于大多数编译器来说，可以使用 Math.IntPower 来代替 Math.Power，以提高性能。
function fib(n:integer):extended;
var i:integer;
fib0,fib1:extended;
begin
fib0:=0;
fib1:=1;
for i:=1 to abs(n) do
begin
fib0:=fib0+fib1;
fib1:=fib0-fib1;
end;
if (n<0)and(not odd(n)) then fib0:=-fib0;
fib:=fib0;
end:
sub fib {
my ($n, $a, $b) = (shift, 0, 1);
($a, $b) = ($b, $a + $b) while $n-- > 0;
$a;
}
sub fib {
my $n = shift;
return $n if $n < 2;
return fib($n - 1) + fib($n - 2);
}
# returns F_n in a scalar context
# returns all elements in the sequence up to F_n in a list context
# only one recursive call
sub fib {
my ($n) = @_;
return (0) if ($n == 0);
return (0, 1) if ($n == 1);
my @fib = fib($n - 1);
return (@fib, $fib[-1] + $fib[-2]);
}
sub fibo;
sub fibo {$_ [0] < 2 ? $_ [0] : fibo ($_ [0] - 1) + fibo ($_ [0] - 2)}
运行时间为 Θ(F(n))，也就是 Ω(1.6n)。
use Memoize;
memoize 'fibo';
sub fibo;
sub fibo {$_ [0] < 2 ? $_ [0] : fibo ($_ [0] - 1) + fibo ($_ [0] - 2)}
sub fibo
{
my ($n, $a, $b) = (shift, 0, 1);
($a, $b) = ($b, $a + $b) while $n-- > 0;
$a;
}
function generate_fibonacci_sequence($length)
{
for($l = [0, 1], $i = 2, $x = 0; $i < $length; $i++) {
$l[] = $l[$x++] + $l[$x];
}
return $l;
}
function fib($n)
{
if ($n < 2) {
return $n;
}
return fib($n - 1) + fib($n - 2);
}
function fib($n)
{
return ($n < 2) ? $n : fib( $n-1 )+fib( $n-2 );
}
class Fibonacci
{
public $Begin = 0;
public $Next;
public $Amount;
public $i;
public function __construct( $Begin, $Amount ) {
$this->Begin = 0;
$this->Next = 1;
$this->Amount = $Amount;
}
public function _do() {
for( $this->i = 0; $this->i < $this->Amount; $this->i++ ) {
$Value = ( $this->Begin + $this->Next );
echo $this->Begin . ' + ' . $this->Next . ' = ' . $Value . '<br />';
$this->Begin = $this->Next;
$this->Next = $Value;
}
}
}
$Fib = new fibonacci( 0, 6 );
echo $Fib->_do();
function fib($n) {
return round(pow(1.6180339887498948482, $n) / 2.2360679774998);
}
def fib(n):
if n < 2: return n
return fib(n - 1) + fib(n - 2)
或者
def fib( n ):
return n if n < 2 else fib( n - 1 ) + fib( n - 2 )
m = {0: 1, 1: 1}
def fib(n):
#assert n >= 0
if n not in m:
m[n] = fib(n-1) + fib(n-2)
return m[n]
def fib(n):
phi = (1 + sqrt(5))/2
return int((phi**n - (-phi)**-n)/sqrt(5))
def fib(n):
i,j = 1,0
for k in range(1,n + 1):
i,j = j, i + j
return j
def fib(n):
a,b = 1,0
for i in range(n):
yield b
a, b = b, a+b
def fib(n):
if n <= 0:
return 0
i = n - 1
a,b = 1,0
c,d = 0,1
while i > 0:
if i % 2 == 1:
a,b = d*b + c*a, d*(b + a) + c*b
c,d = c**2 + d**2, d*(2*c + d)
i = i >> 1
return a + b
def fib(n):
if n <= 0:
return 0
# n = 2**r*s where s is odd
s, r = n, 0
while s & 1 == 0:
r, s = r+1, s/2
# calculate the bit reversal t of (odd) s
# e.g. 19 (10011) <=> 25 (11001)
t = 0
while s > 0:
if s & 1 == 1:
t, s = t+1, s-1
else:
t, s = t*2, s/2
# use the same bit reversal process
# to calculate the sth Fibonacci number
# using Lucas sequence identities
u, v, q = 0, 2, 2
while t > 0:
if t & 1 == 1:
# u, v of x+1
u, v = (u + v) / 2, (5*u + v) / 2
q, t = -q, t-1
else:
# u, v of 2*x
u, v = u * v, v * v - q
q, t = 2, t/2
# double s until we have
# the 2**r*sth Fibonacci number
while r > 0:
u, v = u * v, v * v - q
q, r = 2, r-1
return u
与迭代版本一样，此解决方案在任意精度下也是O(log n)。
def fib(n):
def fib_inner(n):
if n == 0:
return 0, 2
m = n >> 1
# q = 2*(-1)**m
q = -2 if (m & 1) == 1 else 2
u, v = fib_inner(m)
u, v = u * v, v * v - q
if n & 1 == 1:
# u, v of 2m+1
u1 = (u + v) >> 1
return u1, 2*u + u1
else:
# u, v of 2m
return u, v
if n <= 0:
return 0
# the outermost loop is unrolled
# to avoid calculating an unnecessary v
m = n >> 1
u, v = fib_inner(m)
if n & 1 == 1:
# u of m+1
u1 = (u + v) >> 1
# u of 2m+1
return u*u + u1*u1
else:
# u of 2m
return u * v
fib: func [n [integer!]] [
either n < 2 [n] [(fib n - 1) + (fib n - 2)]
]
class Integer
def fib
@n = self.abs
if @n < 2
return @n
else
return (@n-1).fib + (@n-2).fib
end
end
end
备用
class Integer
def fib
@n = self.abs
(@n<2)?(return @n):(return (@n-1).fib+(@n-2).fib)
end
end
# you run it like this
puts 10.fib # output: 55
puts 15.fib # output: 610
def fib n
return n if n < 2
fib(n - 1) + fib(n - 2)
end
class FibGenerator
def initialize(n)
@n = n
end
def each
a, b = 1, 1
@n.times do
yield a
a, b = b, a+b
end
end
include Enumerable
end
def fibs(n)
FibGenerator.new(n)
end
#use like this
fibs(6).each do |x|
puts x
end
def f(n)
((((1+Math.sqrt(5))/2)**n)/Math.sqrt(5)+0.5).floor
end
fibmemo=Hash.new{|h,k| h[k-1]+h[k-2]}
fibmemo[0]=1
fibmemo[1]=1
def fib n
fibmemo[n]
end
(define (fib n)
(if (<= n 1)
n
(+ (fib (- n 1)) (fib (- n 2)))))
(define (fib n)
(define (iter a b count)
(if (<= count 0)
a
(iter b (+ a b) (- count 1))))
(iter 0 1 n))
(define (fib n)
(let loop ((a 0) (b 1)
(count n))
(if (<= count 0) a
(loop b (+ a b) (- count 1))))))
(define fib
(let* ((sqrt5 (inexact->exact (sqrt 5)))
(fi (/ (+ sqrt5 1) 2)))
(lambda (n)
(round (/ (- (expt fi n) (expt (- fi 1) n)) sqrt5)))))
此版本对斐波那契变换进行平方，允许在 log2(n) 时间内进行计算
(define (fib-log n)
"Fibonacci, in logarithmic time."
(define (fib-iter a b p q count)
(cond ((= count 0) b)
((even? count)
(fib-iter a b
(+ (* p p) (* q q))
(+ (* 2 p q) (* q q))
(/ count 2)))
(else (fib-iter (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p q
(- count 1)))))
(fib-iter 1 0 0 1 n))
to fib :n output (cascade :n [?1+?2] 1 [?1] 0) end
to fib :n if :n<2 [output 1] output (fib :n-1)+(fib :n-2) end
Dim i As Integer = 2
Dim sequencelength As Integer = 50
Dim fibonacci(sequencelength) As Integer
fibonacci(0) = 0
fibonacci(1) = 1
While i <> sequencelength
fibonacci(i) = fibonacci(i - 1) + fibonacci(i - 2)
i += 1
End While
Private Function fibonacci(ByVal i as integer) As Integer
If i < 1 Then
Return -1
ElseIf i < 2 Then
Return i
Else
Return fibonacci(i-1) + fibonacci(i-2)
End If
End Function
function fib(n) {
return n < 2 ? n : fib(n - 1) + fib(n - 2);
}
function fib(n, prev, cur) {
if (prev == null) prev = 0;
if (cur == null) cur = 1;
if (n < 2) return cur;
return fib(n--, cur, cur + prev);
}
Prev 和 cur 是可选参数。
function fibonacci(n) {
var i = 1, j = 0, k, t;
for (k = 1; k <= Math.abs(n); k++) {
t = i + j;
i = j;
j = t;
}
if (n < 0 && n % 2 === 0) j = -j;
return j;
}
此示例支持负参数。
function fibonacci(n) {
var sqrt5 = Math.sqrt(5);
var fi = (1 + sqrt5) / 2;
return Math.round((Math.pow(fi, n) - Math.pow(-fi, -n)) / sqrt5);
}
function fibonacci(n) {
var sqrt5 = Math.sqrt(5);
var fi = (1 + sqrt5) / 2;
return Math.round((Math.pow(fi, n + 1) - Math.pow(1 - fi, n + 1)) / sqrt5);
}
function fibonacci(n) {
var sqrt5 = Math.sqrt(5);
return Math.round(Math.pow(((1 + sqrt5) / 2), n) / sqrt5);
}
(defun fib (n)
(cond
((= n 0) 0)
((or (= n 1) (= n 2)) 1)
((= 0 (mod n 2)) (-
(expt (fib (+ (truncate n 2) 1)) 2)
(expt (fib (- (truncate n 2) 1)) 2)))
(t (+ (expt (fib (truncate n 2)) 2)
(expt (fib (+ (truncate n 2) 1)) 2)))))
(fib (parse-integer (second *posix-argv*))) ;
(defun fib (x)
(if (or (zerop x) (= x 1)) 1
(+ (fib (- x 1)) (fib (- x 2)))))
(print (fib 10))
20 % how many Fibonacci numbers to print
1 dup
3 -1 roll
{
dup
3 -1 roll
dup
4 1 roll
add
3 -1 roll
=
}
repeat
这个示例使用栈递归。
% the procedure
/fib
{
dup dup 1 eq exch 0 eq or not
{
dup 1 sub fib
exch 2 sub fib
add
} if
} def
% prints the first twenty fib numbers
/ntimes 20 def
/i 0 def
ntimes {
i fib =
/i i 1 add def
} repeat
CREATE OR REPLACE PROCEDURE fibonacci(lim NUMBER) AS
fibupper NUMBER(38);
fiblower NUMBER(38);
fibnum NUMBER(38);
i NUMBER(38);
BEGIN
fiblower := 0;
fibupper := 1;
fibnum := 1;
FOR i IN 1 .. lim
LOOP
fibnum := fiblower + fibupper;
fiblower := fibupper;
fibupper := fibnum;
DBMS_OUTPUT.PUT_LINE(fibnum);
END LOOP;
END;