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
←Ciąg Fibonacciego Ciąg Fibonacciego
Kod źródłowy
Program obliczający n–ty wyraz ciągu Fibonacciego.

Spis treści

[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
    elif n == 1 or n == 2: return 1
 
    n -= 2
 
    from math import log
    r = int(log(n, 2)+1)
    del log
 
    ca, cb, cc = 1, 1, 0
    sa, sb, sc = 1, 1, 0
 
    for i in xrange(r):
        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];
}
Źródło „http://pl.wikisource.org/wiki/Ci%C4%85g_Fibonacciego/kod”
Utwórz książkę