Kody źródłowe/Ciąg Fibonacciego

Z Wikibooks, biblioteki wolnych podręczników.
Przejdź do nawigacji Przejdź do wyszukiwania
Ciąg Fibonacciego
Kod źródłowy
Ciąg Fibonacciego
Program obliczający n–ty wyraz ciągu Fibonacciego.

MatLAB[edytuj]

%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);

Potęgując macierz[edytuj]

function f = fibonacci(n)
  f = ([1 1; 1 0]^n)(1,2)
endfunction

Autoit3[edytuj]

Iteracyjnie[edytuj]

Local $a = 1 , $b = 1
Local $num = InputBox("Ciąg Fibonacciego", "Podaj którą liczbę z ciągu Fibonacciego chcesz zobaczyć:")
If $num > 92 OR $num < 1 Then
	MsgBox(0,'Błąd','Przekroczono zakres.')
	exit
EndIf
If $num = 1 OR $num = 2 Then
	MsgBox(0,'Wynik','1')
	exit
EndIf
For $x = 1 to $num-2
	$c = $a + $b
	$a = $b
	$b = $c
Next
MsgBox(0,'Wynik',$b)

C/C++[edytuj]

Rekurencyjnie[edytuj]

unsigned int fib(unsigned int n) {
    if(n == 0) return 0;
    if(n == 1) return 1;
    return fib(n-1)+fib(n-2);
}

Poniższa implementacja wykorzystuje rekurencję ogonową, dzięki czemu kompilator potrafi przekształcić ją w iterację.

static unsigned int fib_(const unsigned int f2, const unsigned int f1, const unsigned int i, const unsigned int n)
{
    if (i == n)
        return f1;
    return fib_(f1, f2+f1, i+1, n);
}

unsigned int fib(const unsigned int n)
{
    if (n < 2)
        return n;
    return fib_(0, 1, 1, n);
}

Tu z kolei wykorzystujemy tożsamości pozwalające zredukować n o połowę w każdym kroku rekurencji, co prowadzi do logarytmicznej złożoności czasowej.

void fib_(unsigned int &pp, unsigned int &ff, const unsigned int n)
{
    if (n < 2) {
        pp = 0; ff = n;
    } else {
        unsigned int p, f;
        fib_(p, f, n / 2);      // dzielenie całkowite z odrzuceniem reszty

        if (n % 2 == 0)         // n = 2k
        {
            pp = p*p + f*f;     // F(n-1) = F(2k-1) = F(k-1)^2 + F(k)^2
            ff = 2*p*f + f*f;   // F(n)   = F(2k)   = (2F(k-1) + F(k))*F(k)
        }
        else                    // n == 2k+1,  n/2 = k
        {
            ff = p*p + f*f;     // F(n-2) = F(2k-1) = F(k-1)^2 + F(k)^2
            pp = 2*p*f + f*f;   // F(n-1) = F(2k)   = (2F(k-1) + F(k))*F(k)
            ff += pp;           // F(n)   = F(2k+1) = F(n-2) + F(n-1)
        }
    }
}

unsigned int fib(const unsigned int n)
{
    unsigned int p, f;  // p: F(n-1), f: F(n)
    fib_(p, f, n);
    return f;
}

Iteracyjnie[edytuj]

unsigned int fib(unsigned int n) {
    if( (n == 0) || (n == 1) ) return n;
    unsigned int a, b;
    a = 1; b = 1;
    for(unsigned int i=0; i < n-2; i++) {
        std::swap(a, b);
        b += a;
    }
    return b;
}

Ze wzoru Bineta[edytuj]

Należy dołączyć dodatkowo plik nagłówkowy biblioteki matematycznej.

#include <math.h> // #include <cmath> w C++
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) ) );
}

Metaprogramowanie[edytuj]

Działa tylko w C++ z racji braku szablonów w C, przy czym ilość elemetów ciągu jest ograniczona do 46 elementów, z powodu maksymalnej wartości dla typu int, która jest przekroczona przy próbie obliczenia 47 elemencie - tzw. "overflow" (próba obliczenia tego elementu skończy się błędem kompilacji w przypadku nowszych kompilatorów).

template <unsigned int n>
struct Fib {
    static const unsigned int value = Fib<n - 1>::value + Fib<n - 2>::value;
};

template <>
struct Fib<0> {
    static const unsigned int value = 0;
};

template <>
struct Fib<1> {
    static const unsigned int value = 1;
};

Pascal[edytuj]

Iteracyjnie[edytuj]

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=0 then
     writeln('wynik: 0')
  else
  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.

Rekurencyjnie[edytuj]

program ciagFib;

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));
end.

Python[edytuj]

Iteracyjnie[edytuj]

def fib(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a+b
    return a

Rekurencyjnie[edytuj]

def fib(n):
    if n == 0 or n == 1:
        return n
    else:
        return fib(n-1)+fib(n-2)

Potęgując macierze[edytuj]

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

PHP[edytuj]

Rekurencyjnie[edytuj]

function fib_rek($n)
{
	if($n==0)
	{
		return 0;
	}
	if($n==1)
	{
		return 1;
	}
	return fib_rek($n-2) + fib_rek($n-1);
}

Iteracyjnie[edytuj]

function fib_iter($n)
{
	if($n <= 2)
	{
		return 1;
	}
	else
	{
		$a = 1;
		$b = 1;
		$c = 0;
		for($i=0; $i<$n-2; $i++)
		{
			$c = $a + $b;
			$a = $b;
			$b = $c;
		}
		return $c;
	}
}

Ze wzoru Bineta[edytuj]

function fib_binet($n)
{
	$fi = (sqrt(5)+1)/2;
	$binet = (pow($fi,$n) - pow(($fi-1),$n)) * sqrt(5)/5;
	return $binet;
}

Ruby[edytuj]

Iteracyjnie[edytuj]

def fib(n)
    a, b = 0, 1
    for i in 0..n
        a, b = b, a+b
    end
    return a
end

Rekurencyjnie[edytuj]

def fib(n)
    if n == 0 or n == 1:
        return n
    else
        return fib(n-1)+fib(n-2)
    end
end

Ze wzoru Bineta[edytuj]

Korzystamy z tego, że φ - 1 = 1/φ

def fib(n)
    fi = (Math.sqrt(5)+1)/2
    (fi**n - (fi-1)**n) * Math.sqrt(5)/5
end

Potęgowanie macierzy[edytuj]

require 'matrix'

def fib(n)
    (Matrix.rows([[1,1],[1,0]]) ** n)[1,1]
end

Common Lisp / Emacs Lisp[edytuj]

Iteracyjnie[edytuj]

(defun fib (n)
  (do ((a 0 b)
       (b 1 (+ a b)))
    ((minusp (decf n)) a)))

Potęgując macierze[edytuj]

(defun matrix-multiply (A B)
  (let* ((sA (array-dimensions A))
         (sB (array-dimensions B))
         (res (make-array (list (first sA) (second sB)))))
    (loop for i from 0 below (first sA) do
      (loop for j from 0 below (second sB) do
        (setf (aref res i j)
          (loop for k from 0 below (first sB) sum (* (aref A i k) (aref B k j))))))
    res))

(defun binarize (n)
  (loop while (plusp n) collect (mod n 2) do (setf n (/ (- n (mod n 2)) 2))))

(defun fast-expt (x n &key (e 1) (op #'*))
  (let ((w e))
    (loop for i in (nreverse (binarize n)) do
      (setf w (reduce op (if (zerop i) (list w w) (list w w x)))))
    w))

(defun fib-matrix (n)
  (aref (fast-expt #2A((1 1)(1 0)) n :e #2A((1 0)(0 1)) :op #'matrix-multiply) 0 1))

Ze wzoru Bineta[edytuj]

(defun fib-bin (n)
  (let* ((a (/ (+ (sqrt 5) 1) 2))
         (b (- 1 a)))
    (truncate (/ (- (expt a n) (expt b n)) (sqrt 5)))))

Prolog[edytuj]

fib(N,0):-
	N =:= 0,
	!.
fib(N,1):-
	N>0,
	N<3,
	!.
fib(N, R):-
	fib(N-1, R2),
	fib(N-2, R3),
	R is R2+R3.

Erlang[edytuj]

fib(N)               -> fib(N, 0, 1).
fib(0, Result, _)    -> Result;
fib(N, Result, Next) -> fib(N - 1, Next, Result + Next).

Haskell[edytuj]

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 = 0 : 1 : (zipWith (+) listFib $ tail listFib)

fib :: Int -> Integer
fib n = listFib !! (n+1)

C#[edytuj]

Rekurencyjnie[edytuj]

public static uint Fibonacci(uint n)
        {
            if (n <= 2)
            {
                return 1;
            }
            else
            {
                return Fibonacci(n - 2) + Fibonacci(n - 1);
            }
        }

Iteracyjnie[edytuj]

public static uint Fibonacci(uint n)
        {
            if (n <= 2)
            {
               if (n=0) {
                  return 0;
               } else {
                return 1;
               }
            }
            else
            {
                uint a = 1;
                uint b = 1;
                uint c = 0;
                for (int i = 0; i < n-2; i++)
                {
                    c = a + b;
                    a = b;
                    b = c;
                }
                return c;
            }
        }

Potęgowanie macierzy[edytuj]

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];
}

Javascript[edytuj]

Rekurencyjnie[edytuj]

/**
 * Funkcja ciągu Fibonacciego rekurencyjnie
 * @param n
 * @returns {*}
 */
function fibonacci(n) {
    if (n === 0) return 0;
    else if (n === 1) return 1;
    else if (n > 1) {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

Iteracyjnie[edytuj]

/**
 * Funkcja ciągu Fibonacciego iteracyjnie
 * @param n
 * @returns {number}
 */
function fibonacci(n) {
    if (n === 0) return 0;
    else if (n === 1 || n === 2) return 1;
    else if (n > 2) {
        var a = 1;
        var b = 1;
        var c = 0;
        for (var i = 0; i < n - 2; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
}

NASM[edytuj]

Coded by MS

global _start

extern printf

section .text

_start:
    mov rax, 1
    mov rbx, 1
    
    push rax
    push rbx
    
    mov rcx, 2
    startsequencevals:
        pop rax
        push rax
        
        push rcx
        
        mov rdi, prntfib
        mov rsi, rax
        mov rax, 0
        call printf
        
        pop rcx
    loop startsequencevals
    
    mov rcx, 90
    countsequence:
        pop rax
        pop rbx
        
        add rax, rbx
        
        push rax
        push rbx
        
        push rcx
        
        mov rdi, prntfib
        mov rsi, rax
        mov rax, 0
        call printf
        
        pop rcx
    loop countsequence
    
    mov ebx, 0
    mov eax, 1
    int 0x80
    
section .data
    prntfib db '%ld', 10, 0

Python[edytuj]

Interacyjnie w Pythonie. Coded by MS

a = 1
b = 1

print a,"\n",b

for i in xrange(0, 90):
    c = a + b
    a = b
    b = c
    print(c)