Навигация: [Вверх] [Индекс] Эта страница:/serious/r_fibonacci.html
Автор страницы Сергей Зубков
Страница написана на ISO 15445:2000 HTML
Последнее обновление: $Date: 2003/09/30 04:12:47 $
Используются следующие шесть алгоритмов:fib(0) = 1
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2)
-- Mathematical Handbook 2nd ed., G. Korn, T. Korn, 1968. параграф 8.7-2
(да, я знаю что в первом томе Кнута приведено другое определение. Преобразование тривиально)
Точная запись вышеприведённого определения. Для данного n, рекурсивно вычислить fib(n-1), рекурсивно вычислить fib(n-2), сложить. Рекурсия заканчивается если n равно нулю или единице.Сложность: O(2N) по скорости, O(2N) по памяти.
n-ный элемент списка вычисляется как сумма двух предыдущих элементов. Используются отложенные (ленивые) вычисления где возможно (Hope, Haskell), или используются исключения для эмуляции отложенных вычислений (Caml, Java). Если ничего этого язык не поддерживает, используется простой связный список или массив изменяемого размера.Сложность: O(N) по скорости, O(N) по памяти.
fib(n) вызывает lambda(1,1,n) lambda(n1,n2,n) рекурсивно вызывает lambda(n1+n2,n1,n-1), если N>1 lambda(n1,n2,n) возвращает n1, if N<2Сложность: O(N) по скорости, O(1) по памяти (если компилятор понимает хвостовую рекурсию)
шаг 1: присвоить n1 значение 1, и n2 значение 1 шаг 2: присвоить n1 значение n1+n2, и n2 старое значение n1 шаг 3: повторить шаг 2 n раз шаг 4. вернуть значение n1Сложность: O(N) по скорости, O(1) по памяти.
Рассмотрим функцию F(n+m) (F - то же, что и fib, для краткости). По
определению, F(n+m)=F(n)F(m) + F(n-1)F(m-1).
Теперь вычислим F(n) через F(n/2):
Так как мы работаем в целых числах, получаем
F(n) = F(n/2)^2 + F(n/2-1)^2 если n делится на 2
F(n) = F(n-1/2)*F(n-1/2+1) + F(n-1/2)*F(n-1/2-1) если n не делится на 2
Алгоритмизуем:
Функция lambda(n) принимает одно число n и возвращает два - F(n-1) и F(n).
lambda(n) рекурсивно вызывает lambda(n/2-1), если n чётно
lambda(n) рекурсивно вызывает lambda((n-1)/2), если n нечётно
lambda(n) вычисляет F(n) и F(n-1) по вышеприведённым формулам, используя
полученные после рекурсивного вызова числа.
Рекурсия заканчивается когда n равно 0, 1 или 2.
Функция fib(n) просто вызывает функцию lambda(n) и возвращает F(n).
Сложность: O(log(N)) по скорости и памяти
| F(2n) | | 1 | | 1 1 | | | = A^n * | |, где A = | | | F(2n+1) | | 1 | | 1 2 |Сложность: O(log(N)) по скорости и памяти (сложность взятия целой степени от целочисленной матрицы)
| Дважды рекурсивные (медленные) алгоритмы для 35-го числа Фибоначчи | ||
| Язык | Транслятор [*] | Время в секундах |
|---|---|---|
| Ассемблер | GNU as 2.9.1 [c] | 0.63 |
| Caml | Objective Caml 2.99 [c] | 0.74 |
| C | GCC 2.95.1 [c] | 0.92 |
| C++ | G++ 2.95.1 [c] | 0.99 |
| Scheme | MIT Scheme 7.5.0 [b] | 1.94 |
| Java | JDK 1.1.7B [b] | 10.17 |
| Forth | ThisForth 1.0.0d [i] | 14.57 |
| Haskell | NHC98 1.0 pre-prelease 14 [c] | 36.05 |
| PostScript | GhostScript 5.10 [i] | 42.98 |
| Joy | Joy0 by Manfred von Thun [i] | 50.41 |
| Perl | perl 5.005_003 [i] | 114.05 |
| Prolog | SWI-Prolog 3.3.10 [b] | 120.44 |
| AWK | by Brian Kernighan [i] | 212.30 |
| Hope | by Ross Paterson [i] | 512.46 |
| Tcl | TCL 8.2 [i] | 1468.49 |
| sh | GNU bash 1.14 [i] | 8792.43 |
| Быстрые алгоритмы для вычисления 50000-го числа Фибоначчи (10451 десятичных разрядов) | |||||
| Язык | Бесконечный список | Однажды рекурсивный | Нерекурсивный | Быстрый рекурсивный | Матричное уравнение |
|---|---|---|---|---|---|
| Haskell | 2.83 | 2.68 | n/a | 1.48 | 1.51 |
| Scheme | mem | 4.79 | 4.82 | 0.19 | 0.53 |
| Java | 10.0 | 10.7 | 7.88 | 0.44 | 0.77 |
| perl | mem | mem | 1859.42 | 24.99 | 119.25 |
| Представленные языки программирования | ||||
| Конкатенативные | Логические | Функциональные | Объектные | Императивные |
|---|---|---|---|---|
|
Форт PostScript MUF Joy | Пролог |
Hope Scheme Caml Haskell |
Java C++ |
Фортран C AWK perl Tcl sh Языки ассемблера |
Проблемы:
Форт - мой любимый язык!
Дважды рекурсивная функция:: fib ( n -- n ) DUP 2 < IF DROP 1 EXIT THEN 1- DUP 1- RECURSE SWAP RECURSE + ; : fib35 ( -- ) ." 35th Fibonacci number is " 35 fib . CR ;Бесконечный список:
: flist_put ( a i -- )
OVER 1 CELLS + @ 0= IF
2 CELLS ALLOCATE THROW TUCK !
DUP ROT 1 CELLS + !
0 SWAP 1 CELLS + !
ELSE SWAP 1 CELLS + @ SWAP RECURSE THEN
;
: flist_get ( a i -- n )
1+ OVER SWAP
0 DO DUP 1 CELLS + @
0= IF I 1- ROT TUCK SWAP RECURSE
SWAP DUP DUP I 2 - RECURSE
2SWAP SWAP ROT + flist_put SWAP
THEN 1 CELLS + @
LOOP @ NIP
;
: fib ( n -- n )
2 CELLS ALLOCATE THROW 1 OVER ! 0 OVER 1 CELLS + !
DUP 1 flist_put DUP 1 flist_put
SWAP flist_get
;
: fib35 ( -- )
." 35th Fibonacci number is " 35 fib . CR
;
Однажды рекурсивная функция:
: fib-lambda ( n1 n2 ni -- n ) ROT 1- DUP 0 U> INVERT IF 2DROP EXIT THEN OVER 2SWAP + RECURSE ; : fib ( n -- n ) 1 2 fib-lambda ; : fib35 ( -- ) ." 35th Fibonacci number is " 35 fib U. CR ;Нерекурсивный цикл:
: fib ( n -- n ) 1 1 ROT 1 DO SWAP OVER + LOOP SWAP DROP ; : fib35 ( -- ) ." 35th Fibonacci number is " 35 fib U. CR ;Быстрая рекурсивная функция:
: fib-lambda ( n -- n1 n2 )
DUP 2 U< IF DROP 1 1 ELSE
DUP 2 = IF DROP 2 1 ELSE
2 /MOD SWAP IF RECURSE
2DUP OVER * 2OVER + ROT * +
ROT DUP * ROT DUP * +
ELSE 1- RECURSE
2DUP OVER + TUCK * 2SWAP OVER * ROT +
ROT DUP * ROT DUP * + SWAP
THEN THEN THEN
;
: fib ( n -- n )
fib-lambda DROP
;
: fib35 ( -- )
." 35th Fibonacci number is " 35 fib U. CR
;
Матричное уравнение
: mmult ( A B -- C ) OVER 7 PICK * 8 PICK 5 PICK * + OVER 8 ROLL * 4 PICK 9 ROLL * + 3 ROLL 6 PICK * 7 PICK 6 ROLL * + 3 ROLL 5 ROLL * 4 ROLL 5 ROLL * + ; : mswap ( A B -- B A ) 7 ROLL 7 ROLL 7 ROLL 7 ROLL ; : mover ( A B -- A B A ) 7 PICK 7 PICK 7 PICK 7 PICK ; : fib ( n -- n ) 2 /MOD 1 2 1 1 1 1 0 0 1 9 PICK 9 PICK AND 0<> IF 2DROP 2DROP 2OVER 2OVER THEN BEGIN 8 PICK 10 PICK < WHILE mswap 2OVER 2OVER mmult mswap 8 ROLL 2* 9 1 DO 8 ROLL LOOP 9 PICK 9 PICK AND 0<> IF mover mswap mmult THEN REPEAT mswap 2DROP 2DROP 2DROP 2SWAP 2DROP ROT 0= IF DROP ELSE + THEN ; : fib35 ( -- ) ." 35th Fibonacci number is " 35 fib U. CR ;
/fib {dup 1 le {pop 1} {1 sub dup 1 sub fib exch fib add} ifelse} def
/Times-Roman findfont
20 scalefont setfont newpath 72 72 moveto (35th Fibonacci number is ) show
35 fib 10 string cvs show
showpage
Бесконечный список:
/fib {dup 0 ne
{ dup 1 add array dup 0 1 put dup 1 1 put exch 2 exch 1 sub
{ dup 3 2 roll dup 3 2 roll 1 sub get 1 index 3 index 2 sub get
add 1 index exch 3 index exch put exch 1 add
} repeat 1 sub get
} {pop 1} ifelse
} def
/Times-Roman findfont
20 scalefont setfont newpath 72 72 moveto (35th Fibonacci number is ) show
35 fib 10 string cvs show
showpage
Однажды рекурсивная функция:
/fib-lambda {3 -1 roll 1 sub dup 0 le {pop pop}
{3 1 roll dup 3 2 roll add fib-lambda} ifelse
} def
/fib {1 2 fib-lambda} def
/Times-Roman findfont
20 scalefont setfont newpath 72 72 moveto (35th Fibonacci number is ) show
35 fib 10 string cvs show
showpage
Нерекурсивный цикл:
/fib {dup 0 gt {1 sub} if 1 1 3 2 roll {dup 3 2 roll add} repeat exch pop} def
/Times-Roman findfont
20 scalefont setfont newpath 72 72 moveto (35th Fibonacci number is ) show
35 fib 10 string cvs show
showpage
Быстрая рекурсивная функция:
/fib-lambda { dup 1 le {pop 1 1} {
dup 2 eq {pop 2 1} {
dup 2 mod 1 eq {
1 sub -1 bitshift fib-lambda
dup dup dup mul 4 -1 roll
dup dup dup dup mul 5 -1 roll
add exch 5 -1 roll add 3 -1 roll
mul 4 -2 roll mul add exch
} {
-1 bitshift 1 sub fib-lambda
dup 3 -1 roll dup dup dup dup
6 -1 roll add dup dup mul
4 -2 roll mul add 5 -2 roll mul
4 -2 roll mul add
} ifelse
} ifelse
} ifelse
} def
/fib {fib-lambda pop} def
/Times-Roman findfont
20 scalefont setfont newpath 72 72 moveto (35th Fibonacci number is ) show
35 fib 10 string cvs show
showpage
Матричное уравнение:
/mmult {
1 index 7 index mul 8 index 5 index mul add
1 index 9 -1 roll mul 4 index 10 -1 roll mul add
4 -1 roll 6 index mul 7 index 7 -1 roll mul add
4 -1 roll 6 -1 roll mul 5 -1 roll 6 -1 roll mul add
} def
/mswap { 8 -1 roll 8 -1 roll 8 -1 roll 8 -1 roll } def
/mover { 7 index 7 index 7 index 7 index } def
/mdup { 3 index 3 index 3 index 3 index } def
/fib {
dup 2 mod exch -1 bitshift 1 2 1 1 1 1 0 0 1
9 index 9 index and 0 ne { pop pop pop pop mdup } if
{ 8 index 10 index ge {exit} if mswap mdup mmult mswap
9 -1 roll 1 bitshift 9 1 roll
9 index 9 index and 0 ne {mover mswap mmult} if
} loop
mswap pop pop pop pop pop pop 3 -1 roll pop 3 -1 roll pop
3 -1 roll 0 eq {pop} {add} ifelse
} def
/Times-Roman findfont
20 scalefont setfont newpath 72 72 moveto (35th Fibonacci number is ) show
35 fib 10 string cvs show
showpage
: fib ( n -- n ) dup 2 < if pop 1 exit then 1 - dup 1 - fib swap fib + ; : fib35 ( -- ) me @ "35th Fibonacci number is " 35 fib intostr strcat notify ;Бесконечный список:
: fib-get ( n -- n )
dup intostr "fib/" swap strcat me @ swap getpropval
dup 0 = if
pop dup 1 - dup fib-get swap 1 - fib-get +
"fib/" rot intostr strcat me @ swap "" 4 pick addprop
else swap pop then
;
: fib ( n -- n )
me @ "fib/0" "" 1 addprop
me @ "fib/1" "" 1 addprop
fib-get
;
: fib35 ( -- )
me @ "35th Fibonacci number is " 35 fib intostr strcat notify
;
Однажды рекурсивная функция:
: fib-lambda ( ni n2 n1 -- n ) rot 1 - dup 0 > not if pop pop exit then swap rot over + fib-lambda ; : fib ( n -- n ) 1 2 fib-lambda ; : fib35 ( -- ) me @ "35th Fibonacci number is " 35 fib intostr strcat notify ;Нерекурсивный цикл:
: fib ( n -- n )
1 1 rot begin
1 - dup 0 > while
swap rot over + rot
repeat pop swap pop
;
: fib35 ( -- )
me @ "35th Fibonacci number is " 35 fib intostr strcat notify
;
Быстрая рекурсивная функция:
: fib-lambda ( n -- n1 n2 )
dup 2 < if pop 1 1 else
dup 2 = if pop 2 1 else
dup 2 / swap 2 % if fib-lambda
dup 3 pick + 3 pick * over 4 pick * +
swap dup * rot dup * +
else 1 - fib-lambda
dup 3 pick + dup 4 pick * rot 4 pick * +
swap dup * rot dup * + swap
then then then
;
: fib ( n -- n )
fib-lambda pop
;
: fib35 ( -- )
me @ "35th Fibonacci number is " 35 fib intostr strcat notify
;
Матричное уравнение:
: mmult ( A B -- C ) over 8 pick * 9 pick 6 pick * + over 9 rotate * 5 pick 10 rotate * + 4 rotate 7 pick * 8 pick 7 rotate * + 4 rotate 6 rotate * 5 rotate 6 rotate * + ; : mswap ( A B -- B A ) 8 rotate 8 rotate 8 rotate 8 rotate ; : mover ( A B -- A B A ) 8 pick 8 pick 8 pick 8 pick ; : mpop ( A -- ) pop pop pop pop ; : mdup ( A -- A A ) 4 pick 4 pick 4 pick 4 pick ; : fib ( n -- n ) dup 2 % swap 2 / 1 2 1 1 1 1 0 0 1 10 pick 10 pick bitand 0 = not if mpop mdup then begin 10 pick 10 pick < not while mswap mdup mmult mswap 9 rotate 2 * 8 begin dup while 10 rotate swap 1 - repeat pop 10 pick 10 pick bitand 0 = not if mover mswap mmult then repeat mswap mpop pop pop rot pop rot pop rot 0 = if pop else + then ; : fib35 ( -- ) me @ "35th Fibonacci number is " 35 fib intostr strcat notify ;
"35th Fibonacci number is " [putch] step 35 [small] [pop 1] [pred dup pred] [+] binrec .Бесконечный список:
"35th Fibonacci number is " [putch] step 35 [1 1] [size >=] [dup dup size pred dupd dup swapd at [pred at] dip + [] cons concat] while of .Однажды рекурсивная функция:
"35th Fibonacci number is " [putch] step 35 [1 1] dip [small] [pop swap pop] [pred [dup [swap] dip +] dip] tailrec .Нерекурсивный цикл:
"35th Fibonacci number is " [putch] step 35 [1 1] dip [dup [+] dip swap] times pop .Быстрая рекурсивная функция:
LIBRA
fib == [[[2 <][pop 1 1]] [[2 =][pop 2 1]]
[[2 rem 1 =] [pred 2 /] [
dupd dupd dupd dup [+ *] dip swapd dup
[* +] dip dup * rolldown dup * + ]]
[[2 rem 0 =] [2 / pred] [
dupd dupd dup [+ dup dup * rolldown dup * + rotate] dip
dupd * rollup * + ]]
[[]] ] condlinrec pop.
"35th Fibonacci number is " [putch] step 35 fib .
Матричное уравнение:
LIBRA
fourth == rest rest rest first;
bitandnezero == [[[2 rem swap 2 rem + 2 =] [pop2 true]]
[[0 = swap 0 = and] [pop2 false]]
[[true] [2 / swap 2 /] []] [[]]] condlinrec;
a1 == [dup dup first swap second] dip;
a2 == [dup dup third swap fourth] dip;
b1 == dup dup [first swap third] dip;
b2 == dup dup [second swap fourth] dip;
c == [swapd * [*] dip +] dip swapd;
mmult == a1 b1 c a1 b2 c a2 b1 c a2 b2 c pop2 pair cons cons;
fib == dup 2 rem swap 2 / 1 [2 1 1 1] [1 0 0 1]
[pop2 bitandnezero] [pop dup] [] ifte
[pop2 <] [ [pop2 pop] dip swap
[1 =] [pop dup first swap second +] [pop first] ifte ]
[ [dup mmult] dip [2 *] dip2 [pop2 bitandnezero] [dupd mmult] [] ifte ]
tailrec.
"35th Fibonacci number is " [putch] step 35 fib .
fib(0,1).
fib(1,1).
fib(N,F) :-
N>1, N1 is N-1, N2 is N-2, fib(N1,F1), fib(N2,F2), F is F1+F2.
fibb :-
write('35th Fibonacci number is '), fib(35,X), write(X), nl.
fibb.
Бесконечный список:
flist(_,N,[1,1]) :- N<2.
flist(L1,N,[T|L1]) :-
length(L1,FLL), N =:= FLL, N1 is FLL-N+1, nth1(N1,L1,T1),
N2 is FLL-N+2, nth1(N2,L1,T2), T is T1+T2.
flist(L1,N,L2) :-
length(L1,FLL), N>FLL, N3 is N-1, flist(L1,N3,L3), flist(L3,N,L2).
fib(N,F) :-
flist([1,1],N,FL), length(FL,FLL), N1 is FLL-N, nth1(N1,FL,F).
fibb :-
write('35th Fibonacci number is '), fib(35,X), write(X), nl.
fibb.
Однажды рекурсивная функция:
fib(N,F) :- fib_lambda(1,1,N,F).
fib_lambda(F1,F2,N,F):-
N1>1, F3 is F1+F2, N2 is N-1, fib_lambda(F3,F1,N2,F);
N1<2, F is F1.
fibb :-
write('35th Fibonacci number is '), fib(35,X), write(X), nl.
fibb.
Нерекурсивный цикл:
Не может быть реализован.Быстрая рекурсивная функция:
fib(N,F) :- fl(N,[F|_]).
fl(N,[F1|F2]) :-
N < 2, F1 is 1, F2 is 1;
N =:= 2, F1 is 2, F2 is 1;
Z1 is N mod 2, Z1 =:= 1, A1 is (N-1)/2, fl(A1,[K1|K2]),
F1 is K1*(K1+K2)+K1*K2, F2 is K1*K1+K2*K2;
Z1 is N mod 2, Z1 =:= 0, A2 is (N/2)-1, fl(A2,[L1|L2]),
F1 is (L1+L2)*(L1+L2)+L1*L1, F2 is (L1+L2)*L1+L1*L2.
fibb :-
write('35th Fibonacci number is '), fib(35,X), write(X), nl.
fibb.
Матричное уравнение:
fib(N,F) :-
Z1 is N mod 2, Z1 =:= 0, mpow(N,[2,1,1,1],[1,0,0,1],_,C), nth1(1,C,F);
Z1 is N mod 2, Z1 =:= 1, mpow(N,[2,1,1,1],[1,0,0,1],_,C),
nth1(1,C,F1), nth1(2,C,F2), F is F1+F2.
mpow(N,A1,C1,A2,C2) :-
NH is N//2, T is NH /\ 1, T =:= 0, mpow(NH,1,A1,C1,A2,C2);
NH is N//2, T is NH /\ 1, T =\= 0, mpow(NH,1,A1,A1,A2,C2).
mpow(NH,BIT,A1,C1,A1,C1) :- BIT >= NH.
mpow(NH,BIT,A1,C1,A2,C2) :-
BIT < NH, mmult(A1,A1,AN), BIT2 is BIT*2, T is NH /\ BIT2,
T =\= 0, mmult(AN,C1,CN), mpow(NH,BIT2,AN,CN,A2,C2);
BIT < NH, mmult(A1,A1,AN), BIT2 is BIT*2, T is NH /\ BIT2,
T =:= 0, mpow(NH,BIT2,AN,C1,A2,C2).
mmult([A11,A12,A21,A22],[B11,B12,B21,B22],[C11,C12,C21,C22]) :-
C11 is A11*B11+A12*B21, C12 is A11*B12+A12*B22,
C21 is A21*B11+A22*B21, C22 is A21*B12+A22*B22.
fibb :-
write('35th Fibonacci number is '), fib(35,X), write(X), nl.
fibb.
dec fib : num -> num; --- fib 0 <= 1; --- fib 1 <= 1; --- fib(n+2) <= fib n + fib(n+1); write "35th Fibonacci number is "; write [fib 35];Бесконечный список:
uses lists; dec fibs : list num; --- fibs <= fs whererec fs == 1::1::map (+) (tail fs||fs); write "35th Fibonacci number is "; write [fibs@35];Однажды рекурсивная функция:
dec fib : num -> num;
--- fib n <= fl(1,1,n)
whererec fl == \(a,b,c) => if c<2 then a else fl(a+b,a,c-1);
write "35th Fibonacci number is ";
write [fib 35];
Нерекурсивный цикл:
Не может быть реализован.Быстрая рекурсивная функция:
dec fib : num -> num;
--- fib n <= a where (a,b) == fl(n)
whererec fl == \(n) => if n<2 then (1,1) else
if n=2 then (2,1) else
if n mod 2 = 1 then
(k1*(k1+k2)+k1*k2,k1*k1+k2*k2)
else
((l1+l2)*(l1+l2)+l1*l1,(l1+l2)*l1+l1*l2)
where (k1,k2) == fl((n-1)/2)
where (l1,l2) == fl((n/2)-1);
write "35th Fibonacci number is ";
write [fib 35];
Матричное уравнение:
uses lists;
dec bitandnotzero : num # num -> bool;
--- bitandnotzero (a,b) <=
if (a mod 2) + (b mod 2) = 2 then true
else if a=0 and b=0 then false
else bitandnotzero(a div 2,b div 2);
dec mmult : list(num) # list(num) -> list(num);
--- mmult([a11,a12,a21,a22],[b11,b12,b21,b22]) <=
[a11*b11+a12*b21 ,a11*b12+a12*b22 ,a21*b11+a22*b21 ,a21*b12+a22*b22];
dec mpow : num # list(num) # list(num) -> list(num) # list(num);
--- mpow(n,A,C) <= if bitandnotzero(n div 2,1) then mpow_l(n div 2,1,A,A)
else mpow_l(n div 2,1,A,C)
whererec mpow_l == \(nh,bit,A,C) =>
if bit >= nh then (A,C) else
if bitandnotzero(nh,(bit*2)) then
mpow_l(nh,bit*2,mmult(A,A),mmult(mmult(A,A),C))
else mpow_l(nh,bit*2,mmult(A,A),C);
dec fib : num -> num;
--- fib n <= if (n mod 2) = 0 then l@0 else l@0 + l@1
where (a,l) == mpow(n,[2,1,1,1],[1,0,0,1]) ;
write "35th Fibonacci number is ";
write [fib 35];
(define (fib n) (if (< n 2) 1 (+ (fib (- n 1)) (fib(- n 2))))) (write-string "35th Fibonacci number is ") (write-line (fib 35))Бесконечный список
(define (z-incr k)
(append k (list (+ (list-ref k (- (length k) 1))
(list-ref k (- (length k) 2))))))
(define (fibl n l)
(if (< n (length l))
(list-ref l n)
(fibl n (z-incr l))))
(define (fib n)
(fibl n '(1 1)))
(write-string "35th Fibonacci number is ")
(write-line (fib 35))
Однажды рекурсивная функция
(define (fib n) (define (fl a b c) (if (< c 2) a (fl (+ a b) a (- c 1)))) (fl 1 1 n)) (write-string "35th Fibonacci number is ") (write-line (fib 35))Нерекурсивный цикл
(define (fib n)
(do ((x1 1) (x2 1) (tmp 1) (i 1 (+ i 1))) ((> i n) x1)
(set! tmp (+ x1 x2))
(set! x1 x2)
(set! x2 tmp)))
(write-string "35th Fibonacci number is ")
(write-line (fib 35))
Быстрая рекурсивная функция
(define (fib n)
(define (fl n)
(if (< n 2) (cons 1 1)
(if (= n 2) (cons 2 1)
(if (= (modulo n 2) 1)
(let ((k (fl (/ (- n 1) 2))))
(let ((k1 (car k)) (k2 (cdr k)))
(cons (+ (* k1 (+ k1 k2)) (* k1 k2))
(+ (* k1 k1) (* k2 k2)))))
(let ((k (fl (- (/ n 2) 1))))
(let ((k1 (car k)) (k2 (cdr k)))
(cons (+ (* (+ k1 k2) (+ k1 k2)) (* k1 k1))
(+ (* k1 (+ k2 k1)) (* k1 k2)))))))))
(car (fl n)))
(write-string "35th Fibonacci number is ")
(write-line (fib 35))
Матричное уравнение
(define (mmult l1 l2)
(cons (cons (+ (* (car (car l1)) (car (car l2)))
(* (cdr (car l1)) (car (cdr l2))))
(+ (* (car (car l1)) (cdr (car l2)))
(* (cdr (car l1)) (cdr (cdr l2)))))
(cons (+ (* (car (cdr l1)) (car (car l2)))
(* (cdr (cdr l1)) (car (cdr l2))))
(+ (* (car (cdr l1)) (cdr (car l2)))
(* (cdr (cdr l1)) (cdr (cdr l1)))))))
(define (fib n)
(define (mpow_l nh bit l1 l2)
(if (>= bit nh)
(cons l1 l2)
(if (zero? (fix:and nh (* 2 bit)))
(mpow_l nh (* 2 bit) (mmult l1 l1) l2)
(mpow_l nh (* 2 bit) (mmult l1 l1) (mmult (mmult l1 l1) l2)))))
(define (mpow n l1 l2)
(if (zero? (fix:and 1 (quotient n 2)))
(mpow_l (quotient n 2) 1 l1 l2)
(mpow_l (quotient n 2) 1 l1 l1)))
(define l1 (cdr (mpow n '((2 . 1) 1 . 1)
'((1 . 0) 0 . 1))))
(if (zero? (modulo n 2)) (car (car l1))
(+ (car (car l1)) (car (cdr l1)))))
(write-string "35th Fibonacci number is ")
(write-line (fib 35))
let rec fib = function 0 -> 1 | 1 -> 1 | x -> fib(x-1) + fib(x-2);;
let main () = print_string("35th Fibonacci number is ");
print_int(fib 35);
print_newline();
exit 0;;
main ();;
Бесконечный список:
let rec fib ?(:l=[1;1]) n =
try List.nth l n with Failure "nth" ->
fib l:(l@[(fib l:l (List.length(l)-1))
+ (fib l:l (List.length(l)-2))]) n;;
let main () = print_string("35th Fibonacci number is ");
print_int(fib 35);
print_newline();
exit 0;;
main ();;
Однажды рекурсивная функция:
let rec fib ?(:a=1) ?(:b=1) n =
if n<2 then a else fib a:(a+b) b:a (n-1);;
let main () = print_string("35th Fibonacci number is ");
print_int(fib 35);
print_newline();
exit 0;;
main ();;
Нерекурсивный цикл:
let fib n =
let x1 = ref 1 in
let x2 = ref 1 in
let tmp = ref 0 in
for i = 1 to n do
tmp := !x1 + !x2;
x1 := !x2;
x2 := !tmp;
done;
!x1;;
let main () = print_string("35th Fibonacci number is ");
print_int(fib 35);
print_newline();
exit 0;;
main ();;
Быстрая рекурсивная функция:
let fib n = let rec fl n =
if n<2 then (1,1) else
if n=2 then (2,1) else
if (n mod 2) = 1 then
let (k1,k2) = fl((n-1)/2) in (k1*(k1+k2)+k1*k2,k1*k1+k2*k2)
else
let (l1,l2) = fl((n/2)-1) in ((l1+l2)*(l1+l2)+l1*l1,(l1+l2)*l1+l1*l2)
in fst (fl n);;
let main () = print_string("35th Fibonacci number is ");
print_int(fib 35);
print_newline();
exit 0;;
main ();;
Матричное уравнение:
let fib n =
let mmult = function
[a11;a12;a21;a22],[b11;b12;b21;b22] ->
[a11*b11+a12*b21;a11*b12+a12*b22;a21*b11+a22*b21;a21*b12+a22*b22]
| _,_ -> [] in
let rec mpow_l(nh,bit,l1,l2) =
if bit >= nh then (l1,l2) else
let l11 = mmult(l1,l1) in
if ((bit*2) land nh)<>0
then mpow_l(nh,bit*2,l11,mmult(l11,l2))
else mpow_l(nh,bit*2,l11,l2) in
let mpow(n,l1,l2) =
if ((n/2) land 1)<>0 then mpow_l(n/2,1,l1,l1)
else mpow_l(n/2,1,l1,l2) in
let (_,l) = mpow(n,[2;1;1;1],[1;0;0;1]) in
if (n mod 2) = 0 then List.hd l
else List.hd l + List.hd (List.tl l);;
let main () = print_string("35th Fibonacci number is ");
print_int(fib 35);
print_newline();
exit 0;;
main ();;
module Main where
fib :: Int -> Int
fib x | x < 2 = 1
| x >= 2 = fib (x-1) + fib (x-2)
main = print ("35th Fibonacci number is " ++ show (fib 35))
Бесконечный список:
module Main where
fib :: [Integer]
fib = 1 : 1 : zipWith (+) fib (tail fib)
main = print ("35th Fibonacci number is " ++ show (fib!!35))
Однажды рекурсивная функция:
module Main where
fib :: Int -> Integer
fib n = fl 1 1 n where
fl :: Integer -> Integer -> Int -> Integer
fl a b c = if c<2 then a else fl (a+b) a (c-1)
main = print ("35th Fibonacci number is " ++ show (fib 35))
Нерекурсивный цикл:
Не может быть реализован.Быстрая рекурсивная функция:
module Main where
fib :: Int -> Integer
fib n = fst (fl n) where
fl :: Int -> (Integer,Integer)
fl n | n<2 = (1,1)
| n==2 = (2,1)
| n>2 = if (rem n 2)==1 then (k1*(k1+k2)+k1*k2, k1*k1+k2*k2)
else ((l1+l2)*(l1+l2)+l1*l1, (l1+l2)*l1+l1*l2)
where (k1,k2) = fl (div (n-1) 2)
(l1,l2) = fl ((div n 2)-1)
main = print ("35th Fibonacci number is " ++ show (fib 35))
Матричное уравнение:
module Main where
fib :: Int -> Integer
fib n = if (mod n 2)==0 then head l else head l + head (tail l)
where (_,l) = mpow n [2,1,1,1] [1,0,0,1]
mpow :: Int -> [Integer] -> [Integer] -> ([Integer],[Integer])
mpow n l1 l2 = if bitandnz (div n 2) 1 then mpow_l (div n 2) 1 l1 l1
else mpow_l (div n 2) 1 l1 l2
mpow_l :: Int -> Int -> [Integer] -> [Integer] -> ([Integer],[Integer])
mpow_l nh bit a c = if bit >= nh then (a,c)
else if bitandnz nh (bit*2) then
mpow_l nh (bit*2) ama (mmult ama c)
else mpow_l nh (bit*2) ama c
where ama = mmult a a
bitandnz :: Int -> Int -> Bool
bitandnz a b = if (mod a 2)+(mod b 2)==2 then True
else if (a==0) && (b==0) then False
else bitandnz (div a 2) (div b 2)
mmult :: [Integer] -> [Integer] -> [Integer]
mmult [a11,a12,a21,a22] [b11,b12,b21,b22] =
[a11*b11+a12*b21, a11*b12+a12*b22, a21*b11+a22*b21, a21*b12+a22*b22]
main = print ("35th Fibonacci number is " ++ show (fib 35))
class fib {
private static long fib(long n) {
return n<2 ? 1 : fib(n-2)+fib(n-1);
}
public static void main(String argv[]) {
System.out.println("35th Fibonacci number is " + fib(35));
}
}
Бесконечный список:
import java.math.BigInteger;
import java.util.Vector;
class FibArray {
private static Vector numbers;
public FibArray() {
numbers=new Vector();
numbers.addElement(new BigInteger("1"));
numbers.addElement(new BigInteger("1"));
}
public static BigInteger elementAt(int index) {
try {
return (BigInteger)numbers.elementAt(index);
} catch (ArrayIndexOutOfBoundsException r) {
numbers.addElement(
((BigInteger)numbers.elementAt(numbers.size()-2)).add(
(BigInteger)numbers.elementAt(numbers.size()-1))
);
return (elementAt(index-1).add(elementAt(index-2)));
}
}
}
class fib {
private static BigInteger fib(int n) {
return (new FibArray()).elementAt(n);
}
public static void main(String argv[]) {
System.out.println("35th Fibonacci number is " + fib(35));
}
}
Однажды рекурсивная функция:
import java.math.BigInteger;
class fib {
private static BigInteger fib_lambda(BigInteger x1, BigInteger x2, long c) {
return c<2 ? x1 : fib_lambda(x1.add(x2), x1, c-1);
}
private static BigInteger fib(long n) {
return fib_lambda(new BigInteger("1"),new BigInteger("1"),n);
}
public static void main(String argv[]) {
System.out.println("35th Fibonacci number is " + fib(35));
}
}
Нерекурсивный цикл:
import java.math.BigInteger;
class fib {
private static BigInteger fib(long n) {
BigInteger x1 = new BigInteger("1");
BigInteger x2 = new BigInteger("1");
BigInteger tmp;
for(long i=1;i<=n;i++) {
tmp=x1.add(x2);
x1=x2; x2=tmp;
}
return x1;
}
public static void main(String argv[]) {
System.out.println("35th Fibonacci number is " + fib(35));
}
}
Быстрая рекурсивная функция
import java.math.BigInteger;
class fib {
private static BigInteger[] fl(long n) {
BigInteger[] k = new BigInteger[2];
BigInteger[] l = new BigInteger[2];
if(n<2) { k[0]=new BigInteger("1"); k[1]=new BigInteger("1"); return k; }
if(n==2) { k[0]=new BigInteger("2"); k[1]=new BigInteger("1"); return k; }
if((n%2)==1) {
k = fl((n-1)/2);
l[0]=k[0].multiply((k[0].add(k[1]))).add(k[0].multiply(k[1]));
l[1]=k[0].multiply(k[0]).add(k[1].multiply(k[1]));
} else {
k = fl((n/2)-1);
l[0]=(k[0].add(k[1])).multiply((k[0].add(k[1]))).add(k[0].multiply(k[0]));
l[1]=(k[0].add(k[1])).multiply(k[0]).add(k[0].multiply(k[1]));
}
return l;
}
private static BigInteger fib(long n) { return fl(n)[0]; }
public static void main(String argv[]) {
System.out.println("35th Fibonacci number is " + fib(35));
}
}
Матричное уравнение
import java.math.BigInteger;
class fib {
private static BigInteger[][] matrix_mult(BigInteger[][] a,BigInteger[][] b)
{
BigInteger[][] c = new BigInteger[a.length][b[0].length];
for(int i=0;i<a.length;i++)
for(int j=0;j<b[0].length;j++) {
c[i][j] = new BigInteger("0");
for(int k=0;k<b.length;k++)
c[i][j] = c[i][j].add(a[i][k].multiply(b[k][j]));
}
return c;
}
private static BigInteger fib(int n) {
BigInteger[][] a = {{new BigInteger("2"),new BigInteger("1")},
{new BigInteger("1"),new BigInteger("1")}};
BigInteger[][] c = {{new BigInteger("1"),new BigInteger("0")},
{new BigInteger("0"),new BigInteger("1")}};
int nh=n/2; int bit=1;
if ((nh&bit)!=0) c=a;
while(bit<nh) {
a=matrix_mult(a,a);
bit<<=1;
if((nh&bit)!=0)
c=matrix_mult(a,c);
}
return (n%2)==0 ? c[0][0] : c[0][0].add(c[1][0]);
}
public static void main(String argv[]) {
System.out.println("35th Fibonacci number is " + fib(35));
}
}
#include <iostream>
using namespace std;
long fib(int x)
{
return x<2 ? 1 : fib(x-1) + fib(x-2);
}
int main()
{
cout << "35th Fibonacci number is " << fib(35) << endl;
return 0;
}
Бесконечный список:
#include <iostream>
#include <stl.h>
using namespace std;
long fib(int x)
{
vector<long> fib(2);
fib[0]=1;
fib[1]=1;
fib.reserve(x);
while(x>=fib.size())
fib.push_back(*(fib.end()-2) + *(fib.end()-1));
return fib[x];
}
int main()
{
cout << "35th Fibonacci number is " << fib(35) << endl;
return 0;
}
Однажды рекурсивная функция:
#include <iostream>
using namespace std;
long fib(int x, long n1 = 1, long n2 = 1)
{
return x<2 ? n1 : fib(x-1,n2+n1,n1);
}
int main()
{
cout << "35th Fibonacci number is " << fib(35) << endl;
return 0;
}
Нерекурсивный цикл:
#include <iostream>
#include <stl.h>
using namespace std;
long fib(int x)
{
long x1=1;
for(long i=1,x2=1;i<=x;i++) {
x1+=x2;
swap(x1,x2);
}
return x1;
}
int main()
{
cout << "35th Fibonacci number is " << fib(35) << endl;
return 0;
}
Быстрая рекурсивная функция:
#include <iostream>
using namespace std;
struct fib_pair {
long n1,n2;
fib_pair(long a = 1, long b = 1) { n1=a; n2=b; }
};
fib_pair* fl(int x)
{
if(x<=1) return new fib_pair;
if(x==2) return new fib_pair(2,1);
if(x%2) {
fib_pair* k = fl((x-1)/2);
return new fib_pair(k->n1*(k->n1+k->n2) + k->n1*k->n2
,k->n1*k->n1 + k->n2*k->n2);
} else {
fib_pair* k = fl((x/2)-1);
return new fib_pair( (k->n1+k->n2)*(k->n1+k->n2) + k->n1*k->n1
,(k->n1+k->n2)*k->n1 + k->n1*k->n2);
}
}
long fib(int x)
{
return fl(x)->n1;
}
int main()
{
cout << "35th Fibonacci number is " << fib(35) << endl;
return 0;
}
Матричное уравнение:
#include <iostream>
#include <vector>
using namespace std;
template<class T>
class Matrix {
private:
vector<vector<T> > data;
public:
Matrix(int size) : data(vector<vector<T> >(size,vector<T>(size,0))) {}
size_t size(void) const { return data.size(); }
vector<T> & operator[] (int i) { return data[i]; }
const vector<T> & operator[] (int i) const { return data[i]; }
const Matrix operator*(const Matrix& b) const {
Matrix c(data.size());
for(int i=0; i<data.size(); i++)
for(int j=0; j<data.size(); j++)
for(int k=0; k<data.size(); k++)
c[i][j]+=data[i][k]*b[k][j];
return c;
}
};
long fib(int x)
{
Matrix<int> a(2); Matrix<int> b(2);
a[0][0]=2; a[0][1]=a[1][0]=a[1][1]=1;
b[0][0]=b[1][1]=1; b[0][1]=b[1][0]=0;
int nh = x/2; int bit=1;
if(nh&bit) b=a;
while(bit<nh) {
a=a*a; bit<<=1;
if(nh&bit) b=a*b;
}
return x%2 ? b[0][0]+b[0][1] : b[0][0];
}
int main()
{
cout << "35th Fibonacci number is " << fib(35) << endl;
return 0;
}
PROGRAM FIB19
INTEGER*4 I
I=19
CALL FIB (I)
PRINT *,'19th Fibonacci number is',I
STOP
END PROGRAM
C
SUBROUTINE FIB(I)
DIMENSION A(2**I), B(2**I)
DO1J=1,2**I
A(J)=0; B(J)=0
1 CONTINUE
A(1)=I+1;
IP=0;
4 J2=1
DO2J=1,2**IP
B(J2)=A(J)-1
B(J2+1)=A(J)-2
J2=J2+2
2 CONTINUE
DO3J=1,2**I
A(J)=B(J)
3 CONTINUE
IP=IP+1
IF(A(1).GT.1) GO TO 4
9 IP=IP-1
J2=1
DO5J=1,2**(IP-1)
IF(A(J2+1)-0)10,10,12
10 B(J)=A(J2)+1
GO TO 7
12 B(J)=A(J2)+A(J2+1)
7 J2=J2+2
5 CONTINUE
DO8J=1,2**(I-1)
A(J)=B(J)
8 CONTINUE
IF(IP.GT.1) GO TO 9
I=A(1)
RETURN
END SUBROUTINE
Бесконечный список:
PROGRAM FIB35
I=35
CALL FIB (I)
PRINT *,'35th Fibonacci number is',I
STOP
END PROGRAM
C
SUBROUTINE FIB(I)
DIMENSION A(I+1)
A(1)=1; A(2)=1
DO1J=3,I+1
A(J)=A(J-1)+A(J-2)
1 CONTINUE
I=A(I+1)
RETURN
END SUBROUTINE
Однажды рекурсивная функция
PROGRAM FIB35
I=35
CALL FIB (I)
PRINT *, '35th Fibonacchi number is ', I
STOP
END PROGRAM
C
SUBROUTINE FIB(I)
I1=1; I2=1
DO 2 J=2,I
I3=I1+I2
I2=I1
I1=I3
2 I=I1
RETURN
END SUBROUTINE
Быстрая рекурсивная функция
PROGRAM FIB35
I=35
CALL FIB (I)
PRINT *,'35th Fibonacci number is',I
STOP
END PROGRAM
C
SUBROUTINE FIB(I)
J1=LOG(I+1.)/LOG(2.)
JL=2**J1-2
JR=2**(J1+1)-2
JM=(JL+JR)/2
IF(I-JM)2,2,1
1 JL=JM
I1=2; I2=1; N=2
GO TO 3
2 JR=JM
I1=1; I2=1; N=1
3 IF(N-I)11,7,7
11 JM=(JL+JR)/2
IF(I-JM)5,5,4
4 JL=JM
N=(N+1)*2
ITMP=(I1+I2)**2+I1**2
I2=(I1+I2)*I1+I1*I2
I1=ITMP
GO TO 6
5 JR=JM
N=2*N+1
ITMP=I1*(I1+I2)+I1*I2
I2=I1**2+I2**2
I1=ITMP
6 IF(N-I)11,7,7
7 I=I1
RETURN
END SUBROUTINE
Матричное уравнение
PROGRAM FIB35
I=35
CALL FIB (I)
PRINT *,'35th Fibonacci number is',I
STOP
END PROGRAM
C
SUBROUTINE FIB(I)
DIMENSION A(2,2),B(2,2),C(2,2)
INTEGER L
A(1,1)=2; A(1,2)=1; A(2,1)=1; A(2,2)=1
B(1,1)=1; B(1,2)=0; B(2,1)=0; B(2,2)=1
J=I/2; J1=1
IF(AND(J,J1).NE.0) CALL MCOPY(A,B)
4 IF(J1.GE.J) GO TO 3
CALL MMULT (A,A,C)
CALL MCOPY (C,A)
J=J/2
IF(AND(J,J1).EQ.0) GO TO 4
CALL MMULT(A,B,C)
CALL MCOPY(C,B)
GO TO 4
3 IF(MOD(I,2).NE.0) GO TO 2
I=B(1,1)
RETURN
2 I=B(1,1)+B(1,2)
RETURN
END SUBROUTINE
C
SUBROUTINE MMULT(D,E,C)
DIMENSION D(2,2),E(2,2),C(2,2)
C(1,1)=D(1,1)*E(1,1)+D(1,2)*E(2,1);
C(1,2)=D(1,1)*E(1,2)+D(1,2)*E(2,2);
C(2,1)=D(2,1)*E(1,1)+D(2,2)*E(2,1);
C(2,2)=D(2,1)*E(1,2)+D(2,2)*E(2,2);
RETURN
END SUBROUTINE
C
SUBROUTINE MCOPY(D,E)
DIMENSION D(2,2),E(2,2)
E(1,1)=D(1,1); E(1,2)=D(1,2)
E(2,1)=D(2,1); E(2,2)=D(2,2)
RETURN
END SUBROUTINE
#include <stdio.h>
long fib(long x)
{
return x<2 ? 1 : fib(x-1)+fib(x-2);
}
int main(void)
{
printf("35th Fibonacci number is %ld\n",fib(35));
return 0;
}
Бесконечный список:
#include <stdio.h>
#include <stdlib.h>
struct FL {
long i;
struct FL* next;
};
long flist_get(struct FL* flist, int n)
{
int i;
struct FL* flist_head;
long tmp_l;
flist_head=flist;
for(i=0; flist->next!=NULL; i++)
if (i==n) return flist->i; else flist=flist->next;
if(i==n) return flist->i;
tmp_l=flist_get(flist_head,i-1)+flist_get(flist_head,i);
flist->next=(struct FL*)calloc(1,sizeof(struct FL));
flist->next->i=tmp_l;
return flist_get(flist_head,n);
}
int main(void)
{
struct FL* flist;
flist = (struct FL*)calloc(1,sizeof(struct FL));
flist->i=1;
flist->next=(struct FL*)calloc(1,sizeof(struct FL));
flist->next->i=1;
printf("35th number is %ld\n",flist_get(flist,35));
return 0;
}
Однажды рекурсивная функция:
#include <stdio.h>
long fib_lambda(long x1,long x2,long c)
{
return c<2 ? x1 : fib_lambda(x1+x2,x1,c-1);
}
long fib(long x)
{
fib_lambda(1,1,x);
}
int main(void)
{
printf("35th Fibonacci number is %ld\n",fib(35));
return 0;
}
Нерекурсивный цикл:
#include <stdio.h>
long fib(long x)
{
long i,x1=1,x2=1;
for(i=1;i<=x;i++) {
x1+=x2;
x1^=x2^=x1^=x2;
}
return(x1);
}
int main(void)
{
printf("35th Fibonacci number is %ld\n",fib(35));
return 0;
}
Быстрая рекурсивная функция:
#include <stdio.h>
void fib_lambda(long* n1,long* n2,long n)
{
long k1,k2;
if(n<=1) { *n1 = *n2 = 1; return; }
if(n==2) { *n1 = 2; *n2 = 1; return; }
if(n%2) {
fib_lambda(&k1,&k2,(n-1)/2);
*n1 = k1*(k1+k2) + k1*k2;
*n2 = k1*k1 + k2*k2;
} else {
fib_lambda(&k1,&k2,(n/2)-1);
*n1 = (k1+k2)*(k1+k2) + k1*k1;
*n2 = (k1+k2)*k1 + k1*k2;
}
}
long fib(long x)
{
long n1,n2;
fib_lambda(&n1,&n2,x);
return n1;
}
int main(void)
{
printf("35th Fibonacci number is %ld\n",fib(35));
return 0;
}
Матричное уравнение
#include <stdio.h>
void matrix_mult(long** mat1, long** mat2, long** result,long n)
{
long i,j,k;
for(i=0;i<n;i++)
for(j=0;j<n;j++) {
result[i][j] = 0;
for(k=0;k<n;k++)
result[i][j] += mat1[i][k] * mat2[k][j];
}
}
void matrix_copy(long** src, long** dest,long n)
{
long i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
dest[i][j]=src[i][j];
}
long** matrix_new(long n)
{
long i,**a;
a=(long**)malloc(n*sizeof(long*));
for(i=0;i<n;i++)
a[i]=(long*)malloc(n*sizeof(long));
return a;
}
long fib(long n)
{
register bit=1,nh;
long **a,**b,**c,**d;
a=matrix_new(2); b=matrix_new(2);
c=matrix_new(2); d=matrix_new(2);
a[0][0]=2; a[0][1]=1;
a[1][0]=1; a[1][1]=1;
c[0][0]=1; c[0][1]=0;
c[1][0]=0; c[1][1]=1;
nh=n/2;
if(nh&bit) matrix_copy(a,c,2);
while(bit<nh) {
matrix_mult(a,a,b,2);
bit<<=1; if(nh&bit) {
matrix_mult(b,c,d,2);
matrix_copy(d,c,2);
}
matrix_copy(b,a,2);
}
return (n%2) ? c[0][0]+c[0][1] : c[0][0];
}
int main(void)
{
printf("35th Fibonacci number is %ld\n",fib(35));
return 0;
}
BEGIN { print "35th Fibonacci number is " fib(35) }
function fib(n) { return n<2 ? 1 : fib(n-1)+fib(n-2) }
Бесконечный список:
BEGIN { flist[0]=1 flist[1]=1
print "35th Fibonacci number is " fib(35) }
function fib(n) {
if(flist[n]==0) flist[n]=fib(n-1)+fib(n-2)
return flist[n]
}
Однажды рекурсивная функция:
BEGIN { print "35th Fibonacci number is " fib(35) }
function fib(n) { return fl(1,1,n) }
function fl(x1,x2,c) { return c<2 ? x1 : fl(x1+x2,x1,c-1) }
Нерекурсивный цикл:
BEGIN { print "35th Fibonacci number is " fib(35) }
function fib(n) {
x1=x2=1
for(i=1;i<=n;i++) {
tmp=x1+x2
x1=x2; x2=tmp
}
return x1
}
Быстрая рекурсивная функция:
BEGIN { print "35th Fibonacci number is " fib(35) }
function fib(n, k1, k2) {
if(n<2) return 1
if(n==2) return 2
if((n%2)==1) {
k1=fib((n-1)/2)
k2=fl_snd((n-1)/2)
return k1*(k1+2*k2)
} else {
k1=fib((n/2)-1)
k2=fl_snd((n/2)-1)
return (k1+k2)^2 + k1^2
}
}
function fl_snd(n, k1, k2) {
if(n<=2) return 1
if((n%2)==1) {
k1=fib((n-1)/2)
k2=fl_snd((n-1)/2)
return k1^2 + k2^2
} else {
k1=fib((n/2)-1)
k2=fl_snd((n/2)-1)
return k1*(k1+2*k2)
}
}
Матричное уравнение:
BEGIN { print "35th Fibonacci number is " fib(35) }
function mmultabb() {
c[1]=a[1]*b[1]+a[2]*b[3]
c[2]=a[1]*b[2]+a[2]*b[4]
c[3]=a[3]*b[1]+a[4]*b[3]
c[4]=a[3]*b[2]+a[4]*b[4]
for(i in c) b[i]=c[i]
}
function mmultaaa() {
c[1]=a[2]*a[3]+a[1]^2
c[2]=a[1]*a[2]+a[2]*a[4]
c[3]=a[3]*a[1]+a[4]*a[3]
c[4]=a[3]*a[2]+a[4]^2
for(i in c) a[i]=c[i]
}
function bitandnz(n1,n2) {
if (((n1%2)+(n2%2))==2) return 1
if ((n1==0) && (n2==0)) return 0
return bitandnz(int(n1/2),int(n2/2))
}
function fib(n) {
a[1]=2; a[2]=1; a[3]=1; a[4]=1
b[1]=1; b[2]=0; b[3]=0; b[4]=1
nh=int(n/2); bit=1
if (bitandnz(nh,bit))
for(i in a) b[i]=a[i]
while(bit<nh) {
mmultaaa()
bit=bit*2
if(bitandnz(nh,bit)) mmultabb()
}
if(n%2) return b[1]+b[2]
else return b[1]
}
#!/usr/bin/perl
use Math::BigInt;
print "35th Fibonacci number is ", fib(35), "\n";
sub fib {
return @_[0] < 2 ? new Math::BigInt("1") : fib(@_[0]-1) + fib(@_[0]-2)
}
Бесконечный список:
#!/usr/bin/perl
use Math::BigInt;
print "35th Fibonacci number is ", fib(35), "\n";
sub fib {
@fl=(new Math::BigInt("1"),new Math::BigInt("1"));
$fl[$i+1]=$fl[$i-1]+$fl[$i] until $i++==@_[0];
return $fl[@_[0]]
}
Однажды рекурсивная функция:
#!/usr/bin/perl
use Math::BigInt;
print "35th Fibonacci number is ", fib(35), "\n";
sub fib {
return fl(new Math::BigInt("1"), new Math::BigInt("1"), @_[0])
}
sub fl {
return @_[2] < 2 ? @_[0] : fl(@_[0]+@_[1], @_[0], @_[2]-1);
}
Нерекурсивный цикл:
#!/usr/bin/perl
use Math::BigInt;
print "35th Fibonacci number is ", fib(35), "\n";
sub fib {
$x1=new Math::BigInt "1";
$x2=new Math::BigInt "1";
$tmp=new Math::BigInt "0";
for(;$i < @_[0]; $i++) {
$tmp=$x1+$x2; $x1=$x2; $x2=$tmp;
}
return $x1;
}
Быстрая рекурсивная функция:
#!/usr/bin/perl
use Math::BigInt;
print "35th Fibonacci number is ", fib(35), "\n";
sub fib {
my @a=fl(@_[0]);
return $a[0];
}
sub fl {
return (new Math::BigInt("1"),new Math::BigInt("1")) if @_[0]<=1;
return (new Math::BigInt("2"),new Math::BigInt("1")) if @_[0]==2;
if (@_[0] % 2) {
my @k = fl((@_[0]-1)/2);
return ($k[0]*($k[0]+$k[1]) + $k[0]*$k[1],
$k[0]*$k[0] + $k[1]*$k[1]);
} else {
my @k = fl((@_[0]/2)-1);
return (($k[0]+$k[1])*($k[0]+$k[1]) + $k[0]*$k[0],
($k[0]+$k[1])*$k[0] + $k[0]*$k[1]);
}
}
Матричное уравнение:
#!/usr/bin/perl
use Math::BigInt;
print "35th Fibonacci number is ", fib(35), "\n";
sub fib {
@a=(new Math::BigInt("2"),new Math::BigInt("1"),
new Math::BigInt("1"),new Math::BigInt("1"));
@b=(new Math::BigInt("1"),new Math::BigInt("0"),
new Math::BigInt("0"),new Math::BigInt("1"));
my $nh=@_[0]/2; my $bit=1;
@b=@a if ($nh & $bit);
while ($bit < $nh) {
@a=mmult(@a,@a); $bit<<=1;
@b=mmult(@a,@b) if $nh & $bit;
}
return @_[0] % 2 ? $b[0]+$b[1] : $b[0];
}
sub mmult {
my @a = (@_[0], @_[1], @_[2], @_[3]);
my @b = (@_[4], @_[5], @_[6], @_[7]);
$d[0]=$a[0]*$b[0]+$a[1]*$b[2];
$d[1]=$a[0]*$b[1]+$a[1]*$b[3];
$d[2]=$a[2]*$b[0]+$a[3]*$b[2];
$d[3]=$a[2]*$b[1]+$a[3]*$b[3];
return @d;
}
proc fib {n} {
if { $n < 2 } {return 1} else {
return [expr [fib [expr $n-1]] + [fib [expr $n-2]]]
}
}
puts [concat "35th Fibonacci number is " [fib 35]]
Бесконечный список:
proc fib {n l} {
set len [llength $l]
if {[expr $n>=$len]} {
set l [lappend l [expr [lindex $l [expr $len - 2]] + [lindex $l [expr $len - 1]]]]
return [fib $n $l]
}
return [lindex $l $n]
}
puts [concat "35th Fibonacci number is " [fib 35 [list 1 1]]]
Однажды рекурсивная функция:
proc fl {x1 x2 c} {
if { $c < 2 } {return $x1} else {
return [fl [expr $x1+$x2] $x1 [expr $c-1]]
}
}
proc fib {n} { return [fl 1 1 $n] }
puts [concat "35th Fibonacci number is " [fib 35]]
Нерекурсивный цикл:
proc fib {n} {
set x1 1
set x2 1
for {set i 1} {$i <= $n} {incr i} {
set tmp [expr $x1+$x2]
set x1 $x2; set x2 $tmp
}
return $x1
}
puts [concat "35th Fibonacci number is " [fib 35]]
Быстрая рекурсивная функция:
proc fl {n} {
if {$n<2} {return [list 1 1]}
if {$n==2} {return [list 2 1]}
if {[expr $n % 2]} {
set kl [fl [expr ($n-1)/2]]
set k1 [lindex $kl 0]
set k2 [lindex $kl 1]
return [list [expr $k1*($k1+$k2)+$k1*$k2] [expr $k1*$k1+$k2*$k2]]
} else {
set kl [fl [expr ($n/2)-1]]
set k1 [lindex $kl 0]
set k2 [lindex $kl 1]
return [list [expr ($k1+$k2)*($k1+$k2)+$k1*$k1] [expr ($k1+$k2)*$k1+$k1*$k2]]
}
}
proc fib {n} { return [lindex [fl $n] 0] }
puts [concat "35th Fibonacci number is " [fib 35]]
Матричное уравнение:
proc mmult {a b} {
set c1 [expr [lindex $a 0]*[lindex $b 0]+[lindex $a 1]*[lindex $b 2]]
set c2 [expr [lindex $a 0]*[lindex $b 1]+[lindex $a 1]*[lindex $b 3]]
set c3 [expr [lindex $a 2]*[lindex $b 0]+[lindex $a 3]*[lindex $b 1]]
set c4 [expr [lindex $a 2]*[lindex $b 1]+[lindex $a 3]*[lindex $b 3]]
return [list $c1 $c2 $c3 $c4]
}
proc fib {n} {
set a {2 1 1 1}
set b {1 0 0 1}
set nh [expr $n/2]
set bit 1
if {[expr $nh & $bit]!=0} { set b $a }
while {$bit < $nh} {
set a [mmult $a $a]
set bit [expr $bit*2]
if {[expr $nh & $bit]!=0} { set b [mmult $a $b] }
}
if {[expr $n % 2]} {
return [expr [lindex $b 0] + [lindex $b 1]]
} else {
return [lindex $b 0] }
}
puts [concat "35th Fibonacci number is " [fib 35]]
#!/bin/sh
fib () {
if test $1 -lt 2; then
return 1
else
return $(($(fib $(($1-2));echo $?)+$(fib $(($1-1));echo $?)))
fi
}
fib 35
echo "35th Fibonacci number is" $?
Бесконечный список:
#!/bin/sh
fib () {
eval A='$'F$1
if test x$A != x; then
return $A
else
eval A='$'F$(($FL-1))
eval B='$'F$(($FL))
FL=$(($FL+1))
eval F$FL=$(($A+$B))
fib $1
fi
}
F0=1
F1=1
FL=1
fib 35
echo "35th Fibonacci number is" $?
Однажды рекурсивная функция:
#!/bin/sh
fib () {
if test $1 -le 1; then
return $2
else
fib $(($1-1)) $(($2+$3)) $2
fi
}
fib 35 1 1
echo "35th Fibonacci number is" $?
Нерекурсивный цикл:
#!/bin/sh
fib () {
N1=1
N2=1
I=1
while test $I -lt $1; do
I=$(($I+1))
TMP=$(($N1+$N2))
N2=$N1
N1=$TMP
done
return $N1
}
fib 35
echo "35th Fibonacci number is" $?
Быстрая рекурсивная функция:
#!/bin/sh
fib () {
if test $1 -lt 2; then
return 1
elif test $1 -eq 2; then
return 2
elif test $(($1%2)) -eq 1; then
return $(($(fib $((($1-1)/2));echo $?)*($(fib $((($1-1)/2));echo $?)
+2*$(fl $((($1-1)/2));echo $?))))
else
return $((($(fib $(($1/2-1));echo $?)+$(fl $(($1/2-1));echo $?))
*($(fib $(($1/2-1));echo $?)+$(fl $(($1/2-1));echo $?))
+$(fib $(($1/2-1));echo $?)*$(fib $(($1/2-1));echo $?)))
fi
}
fl () {
if test $1 -le 2; then
return 1
elif test $(($1%2)) -eq 1; then
return $(($(fib $((($1-1)/2));echo $?)*$(fib $((($1-1)/2));echo $?)
+$(fl $((($1-1)/2));echo $?)*$(fl $((($1-1)/2));echo $?)))
else
return $(($(fib $(($1/2-1));echo $?)*($(fib $(($1/2-1));echo $?)
+2*$(fl $(($1/2-1));echo $?))))
fi
}
fib 35
echo "35th Fibonacci number is" $?
Матричное уравнение:
#!/bin/sh
fib () {
A11=2; A12=1; A21=1; A22=1
B11=1; B12=0; B21=0; B22=1
NH=$(($1/2))
BIT=1
if test $(($BIT & $NH)) -ne 0; then
B11=$A11; B12=$A12; B21=$A21; B22=$A22
fi
while test $BIT -lt $NH; do
BIT=$((2*$BIT))
mmultaaa
if test $(($BIT & $NH)) -ne 0; then
mmultabb
fi
done
if test $(($1%2)) -ne 0; then
return $(($B11+$B12))
else
return $B11
fi
}
mmultaaa () {
C11=$(($A12*$A21+$A11*$A11))
C12=$(($A11*$A12+$A12*$A22))
C21=$(($A21*$A11+$A22*$A21))
C22=$(($A21*$A12+$A22*$A22))
A11=$C11; A12=$C12; A21=$C21; A22=$C22
}
mmultabb () {
C11=$(($A12*$B21+$A11*$B11))
C12=$(($A11*$B12+$A12*$B22))
C21=$(($A21*$B11+$A22*$B21))
C22=$(($A21*$B12+$B22*$A22))
B11=$C11; B12=$C12; B21=$C21; B22=$C22
}
fib 35
echo "35th Fibonacci number is" $?
.globl _start
_start:
pushl $35
call fib
call print_eax
xorl %ebx,%ebx
movl $1,%eax
int $0x80
fib:
movl 4(%esp),%eax
cmpl $2,%eax
jl quitrec
decl %eax
pushl %eax
call fib
popl %edx
movl 4(%esp),%eax
movl %edx,4(%esp)
subl $2,%eax
pushl %eax
call fib
popl %eax
addl %eax,4(%esp)
ret
quitrec:
movl $1,4(%esp)
ret
print_eax:
movl $outbyte,%edi
movl 4(%esp),%eax
movl $10,%ebx
xorl %ecx,%ecx
divlp:
xorl %edx,%edx
divl %ebx
addb $48,%dl
pushl %edx
incl %ecx
testl %eax,%eax
jnz divlp
store:
popl %eax
stosb
loop store
movb $012,(%edi)
subl $outbyte,%edi
movl %edi,%edx
addl $outtxt_l,%edx
movl $outtxt,%ecx
movl $1,%ebx
movl $4,%eax
int $0x80
ret
.data
outtxt:
.ascii "35th Fibonacci number is "
outtxt_l = .-outtxt+1
outbyte:
.ascii "0000000000"
Бесконечный список.model tiny .code org 100h _start: mov ax,cs mov ds,ax mov es,ax cld push 23 call fib call print_eax ret fib: push bp mov bp,sp mov di,offset fib_array+2 mov cx,[bp+4] fib_loop: mov ax,[di-1] add ax,[di-2] inc di mov [di],ax loop fib_loop mov bx,[bp+4] mov ax,word ptr [bx+fib_array] mov [bp+4],ax pop bp ret print_eax: mov bp,sp mov di,offset outbyte mov ax,[bp+2] mov bx,10 xor cx,cx divlp: xor dx,dx div bx add dl,48 push dx inc cx test ax,ax jnz divlp store: pop ax stosb loop store mov byte ptr [di],'$' mov dx, offset outtxt mov ah,9 int 21h ret 2 outtxt db "23rd Fibonacci number is " outtxt_l = $-outtxt+1 outbyte db "00000000" fib_array db 1,1 end _startОднажды рекурсивная функция:
.section ".text"
.global _start
_start:
save %sp,-112,%sp
mov 35,%o2
mov 1,%o1
call fib_lambda,1
mov 1,%o0
call print_o0
nop
mov 1,%g1
ta 8
fib_lambda:
save %sp,-112,%sp
st %i2,[%fp+68]
ld [%fp+68],%o2
cmp %o2,2
bl lambda_ends
nop
st %i0,[%fp+68]
ld [%fp+68],%o1
add %o1,%i1,%o0
call fib_lambda,1
dec %o2
st %o0,[%fp+68]
ld [%fp+68],%i0
lambda_ends:
ret
restore
print_o0:
save %sp,-112,%sp
st %i0,[%fp+68]
ld [%fp+68],%o0
sethi %hi(outbyte_end),%l2
or %l2,%lo(outbyte_end),%l2
print_o0_loop:
clr %l1
o0_div_10_loop:
sub %o0,10,%o0
cmp %o0,0
bge o0_div_10_loop
inc %l1
add %o0,10+'0',%o0
stb %o0,[%l2]
dec %l1
mov %l1,%o0
cmp %l1,0
bne print_o0_loop
dec %l2
mov 1,%o0
sethi %hi(outtext),%o1
or %o1,%lo(outtext),%o1
mov outtext_l,%o2
mov 4,%g1
ta 8
mov 1,%o0
sethi %hi(outbyte),%o1
or %o1,%lo(outbyte),%o1
mov outbyte_l,%o2
mov 4,%g1
ta 8
ret
restore %g0,0,%o0
.section ".data"
outtext:
.ascii "35th Fibonacchi number is "
outtext_l = .-outtext
outbyte:
.ascii "0000000000"
.byte 012
outbyte_end = .-1
outbyte_l = .-outbyte
Нерекурсивный цикл:.toc outtext_a: .tc outtext[TC],outtext outbyte_a: .tc outbyte_l[TC],outbyte_l .csect __start[DS] .globl __start __start: .long .__start, TOC[tc0], 0 .csect .text[PR] .__start: li 3,35 li 7,1 li 8,1 fib_loop: add 11,7,8 mr 7,8 mr 8,11 subi 3,3,1 cmpwi 3,0 bgt fib_loop lwz 9,outbyte_a(2) lwz 9,0(9) li 10,10 div_loop: divwu 3,7,10 mr 6,3 mullw 3,3,10 subf 3,3,7 mr 7,6 addi 3,3,'0' stb 3,0(9) subi 9,9,1 cmpwi 6,0 bgt div_loop li 3,1 lwz 4,outtext_a(2) li 5,outtext_l li 0,26 sc li 3,7 li 0,9 sc .csect .data[RW] outtext: .byte "35th Fibonacci number is " .byte "00000000" outbyte: .byte 10 outtext_l = .-outtext outbyte_l: .long outbyte-1Быстрая рекурсивная функция:
.globl start .text start: mov $0,(sp) mov $27,-(sp) jsr pc, lambda print_r1: mov $outbyte,r3 div_loop: sxt r0 div $12,r0 add $60,r1 movb r1,-(r3) mov r0,r1 tst r1 jne div_loop mov $1,r0 sys 4; outtext; 37 mov $1,r0 sys 1 lambda: mov 2(sp),r1 cmp $2,r1 beq gottwo bgt gotone sxt r0 div $2,r0 tst r1 beq even odd: mov 2(sp),r1 dec r1 sxt r0 div $2,r0 mov r0,-(sp) jsr pc,lambda add $2,sp mov r0,r3 mov r1,r2 mov r3,r4 mul r2,r4 mov r5,r1 mov r3,r4 add r2,r4 mul r2,r4 add r5,r1 mul r3,r3 mov r3,r0 mul r2,r2 add r3,r0 rts pc even: mov 2(sp),r1 sxt r0 div $2,r0 dec r0 mov r0,-(sp) jsr pc,lambda add $2,sp mov r0,r3 mov r1,r2 mov r2,r4 mul r2,r4 mov r5,r1 mov r2,r4 add r3,r4 mul r4,r4 add r5,r1 mov r2,r4 add r3,r4 mul r2,r4 mov r5,r0 mul r2,r3 add r3,r0 rts pc gotone: mov $1,r0 mov $1,r1 rts pc gottwo: mov $1,r0 mov $2,r1 rts pc .data outtext: .byte 62,63,162,144,40,106,151,142,157,156 .byte 141,143,143,151,40,156,165,155 .byte 142,145,162,40,151,163,40 .byte 60,60,60,60,60 outbyte: .byte 12Матричное уравнение: