Wikibooks

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

< Kody źródłowe
Ciąg Fibonacciego • Kod źródłowy
Ciąg Fibonacciego
Kod źródłowy
Program obliczający n–ty wyraz ciągu Fibonacciego.
Spis treści

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;
};
Spis treści

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

Bash

edytuj 
#!/bin/bash

a=1;
echo $a;
b=1;
echo $b;

for i in {90..1}
    do
        c=$[a+b];
        a=$b;
        b=$c;
        echo $c
    done

ANSI C - wzór Bineta

edytuj

Funkcja zwraca zaokrąglone - dokładne wyniki, powyższe funkcje dot. wzoru Bineta zwracają przybliżenie 

int binet(int n) {
	double fi = (sqrt(5) + 1) / 2;
	
	return (int)round((pow(fi, n) - pow((fi - 1), n)) * sqrt(5) / 5);
}

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

ANSI C

edytuj

Rozszerzona wersja iteracyjna. Coded by MS 

#include <stdio.h>

#define DIGITS 2090
#define NUMBER 10000

void writenum(short[], int);

int main(void) {
    short a[DIGITS], b[DIGITS], c[DIGITS];
    int ten = 0, counter = 1;
    
    for(int i = 0; i < DIGITS; i++) {
        a[i] = 0;
        b[i] = 0;
        c[i] = 0;
    }
    
    a[DIGITS - 1] = 1;
    b[DIGITS - 1] = 1;
    
    writenum(a, counter);
    counter++;
    writenum(b, counter);
    counter++;
    
    while(counter <= NUMBER) {
        if(a[0] + b[0] + ten > 9) break;
        
        for(int j = DIGITS - 1; j >= 0; j--) {
            c[j] = a[j] + b[j] + ten;
            if(c[j] > 9) { 
                ten = 1;
                c[j] -= 10;
            }
            else ten = 0;
        }
        
        writenum(c, counter);
        counter++;
        
        for(int move = 0; move < DIGITS; move++) {
            a[move] = b[move];
            b[move] = c[move];
        }
    }
    
    printf("\n\n");
    
    return 0;
}

void writenum(short num[], int cnt) {
    int zerocnt = 0, digitscnt = 0;
    
    for(int j = 0; j < DIGITS; j++) {
        if(num[j] == 0) zerocnt++;
        else break;
    }
    
    printf("\n-------------------------------------------");
    printf("\n%d Fibonacci Sequence number: \n\n", cnt);
    
    for(int k = zerocnt; k < DIGITS; k++) {
        digitscnt++;
        printf("%d", num[k]);
    }
    
    printf("\n\nDigits Count: %d", digitscnt);
    printf("\n-------------------------------------------");
}
Źródło: „https://pl.wikibooks.org/w/index.php?title=Kody_źródłowe/Ciąg_Fibonacciego&oldid=488166”