Ciąg Fibonacciego/kod
Z Wikiźródeł, repozytorium wolnych materiałów źródłowych
| ←Ciąg Fibonacciego | Ciąg Fibonacciego Kod źródłowy |
||
| Program obliczający n–ty wyraz ciągu Fibonacciego. |
[edytuj] MatLAB
%Ciag Fibonacciego cfibonacciego.m % program główny % n=input('Podaj liczbe wyrazow ciagu: '); fibonacci(n); function y=fibonacci(n) %fibonacci.m - funkcja if n==1 y(1)=1; disp(['a(1)=',num2str(y(1))]); elseif n==2 y(1)=1; y(2)=1; for i=1:n disp(['a(',num2str(i),')=',num2str(y(i))]); end elseif n>2 y(1)=1; y(2)=1; disp('a(1)=1'); disp('a(2)=1'); for i=3:n y(i)=y(i-2)+y(i-1); disp(['a(',num2str(i),')=',num2str(y(i))]); end else disp('zle n!'); end z=1:n; plot(z,y);
[edytuj] C/C++
[edytuj] Rekurencyjnie
unsigned int fib(unsigned int n) { if(n == 0) return 0; if(n == 1) return 1; return fib(n-1)+fib(n-2); }
[edytuj] Iteracyjnie
unsigned int fib(unsigned int n) { if(n == 0) return 0; unsigned int a, b; a = 0; b = 1; for(unsigned int i=0; i<(n-1); i++) { b += a; a = b-a; } return b; }
[edytuj] Ze wzoru Bineta
Należy dołączyć dodatkowo plik nagłówkowy biblioteki matematycznej.
#include <math.h> unsigned int fib(unsigned int n) { return 1.0/sqrt(5.0) * ( pow( (1.0+sqrt(5.0))/2.0 , (double)(n) ) - pow( (1.0-sqrt(5.0))/2.0 , (double)(n) ) ); }
[edytuj] Pascal
[edytuj] Iteracyjnie
program fibonacci; var a, b, c, i, liczba: integer; begin writeln('Podaj ktora liczbe z ciagu Fibonacciego chcesz zobaczyc: '); readln(liczba); a:=1; b:=1; if liczba<=2 then writeln('Wynik: ', a) else begin for i:=3 to liczba do begin c:=a+b; a:=b; b:=c; end; writeln('Wynik: ', c); end; end.
[edytuj] Rekurencyjnie
program ciagFib; uses crt; var liczba: integer; function fib(n:integer):integer; begin if (n=1) or (n=0) then fib:=n else if n>1 then fib:=fib(n-1)+fib(n-2); end; begin writeln('Podaj n: '); readln(liczba); writeln('Wynik: ', fib(liczba)); repeat until keypressed; end.
[edytuj] Python
[edytuj] Iteracyjnie
def fib(n): a, b = 0, 1 for i in xrange(n): a, b = b, a+b return a
[edytuj] Rekurencyjnie
def fib(n): if n == 0 or n == 1: return n else: return fib(n-1)+fib(n-2)
[edytuj] Potęgując macierze
Metoda szerzej opisana na wikipedii
def fib(n): if n == 0: return 0 n -= 2 ca, cb, cc = sa, sb, sc = 1, 1, 0 while n>0: if n & 1: sa, sb, sc = (sa*ca + sb*cb), (sa*cb + sb*cc), (sb*cb + sc*cc) n >>= 1 t = cb**2 ca, cb, cc = (ca**2+t), (cb*(ca+cc)), (cc**2+t) return sa
[edytuj] Common Lisp / Emacs Lisp
[edytuj] Iteracyjnie
defun fib(n) (let ((a 0) (b 1) (tmp 0)) (dotimes (x n a) (setq tmp a) (setq a b) (setq b (+ tmp b)))))
[edytuj] Prolog
fib(N, N) :- N < 2, !. fib(N, Wynik) :- fib(N-1, W1), fib(N-2, W2), Wynik is W1 + W2.
[edytuj] Haskell
fib :: Integer -> Integer fib 0 = 1 fib 1 = 1 fib n = fib (n-1) + fib (n-2)
Poprzedni algorytm wymaga kilku sekund do policzenia 30 liczby ciągu Fibonacciego. Następujący algorytm oblicza 50000 liczbę w czasie poniżej 1s.
listFib :: [Integer] listFib = 1:1:( zipWith (+) listFib (tail listFib) ) fib :: Int -> Integer fib n = listFib !! (n+1)
[edytuj] C#
[edytuj] Rekurencyjnie
public static uint Fibonacci(uint n) { if (n <= 1) { return 1; } else { return Fibonacci(n - 2) + Fibonacci(n - 1); } }
[edytuj] Iteracyjnie
public static uint Fibonacci(uint n) { if (n <= 1) { return 1; } else { uint a = 1; uint b = 1; uint c = 0; for (int i = 0; i < n-1; i++) { c = a + b; a = b; b = c; } return c; } }
[edytuj] Potęgowanie macierzy
Metoda obliczająca n–ty wyraz ciągu Fibonacciego ze złożonością O(n) w języku C# (złożoność może zostać zredukowana do O(lg n) przez zastosowanie binarnego algorytmu potęgowania macierzy)
public static int Fibonacci(int n) { if (n == 0) return 0; if (n == 1 || n == 2) return 1; int[,] A = new int[2, 2] { { 0, 1 }, { 1, 1 } }; int[,] B = (int[,])A.Clone(); int[,] C = new int[2, 2]; n -= 2; for (int i = 1; i <= n; i++) { C[0, 0] = B[0, 0] * A[0, 0] + B[0, 1] * A[1, 0]; C[0, 1] = B[0, 0] * A[0, 1] + B[0, 1] * A[1, 1]; C[1, 0] = B[1, 0] * A[0, 0] + B[1, 1] * A[1, 0]; C[1, 1] = B[1, 0] * A[0, 1] + B[1, 1] * A[1, 1]; B = (int[,])C.Clone(); } return C[1, 1]; }
