피보나치 수 프로그램

위키백과 ― 우리 모두의 백과사전.

피보나치 수 프로그램피보나치 수프로그래밍 언어로 만든 것으로, 일반적으로 재귀적인 방법을 사용한다.

피보나치 수를 정의에 따라 재귀적으로 구하면 일반적으로 거듭제곱의 시간 복잡도가 소요된다. 하지만 한번 구한 값을 저장해서 여러 번 중복해서 계산하지 않는 메모이제이션을 사용하면 O(n)의 복잡도가 소요된다. 또한 수식을 통해 O(1)의 복잡도로 값을 구할 수도 있다.

아래는 다양한 프로그래밍 언어로 구현된 피보나치 수 프로그램의 예이다.

목차

[편집] 커먼 리스프

[편집] 루카스 식을 통한 피보나치 계산

(defun fib (n)
  (cond
   ((= n 0) 0)
   ((or (= n 1) (= n 2)) 1)
   ((= 0 (mod n 2)) (-
                     (expt (fib (+ (truncate n 2) 1)) 2)
                     (expt (fib (- (truncate n 2) 1)) 2)))
   (t (+ (expt (fib (truncate n 2)) 2)
         (expt (fib (+ (truncate n 2) 1)) 2)))))

(fib (parse-integer (second *posix-argv*))) ;

[편집] 하스켈

[편집] Lazy infinite list

module Main where
import System.Environment

fibo = 1 : 1 : zipWith (+) fibo (tail fibo)

main = do
    args <- getArgs
    print (fibo !! (read(args!!0)-1))

[편집] Perl

[편집] One example

#! /usr/bin/perl
use bigint;

my ($a, $b) = (0, 1);
for (;;) {
    print "$a\n";
    ($a, $b) = ($b, $a+$b);
}

[편집] Binary recursion, snippet

sub fibo;
sub fibo {$_ [0] < 2 ? $_ [0] : fibo ($_ [0] - 1) + fibo ($_ [0] - 2)}

Runs in Θ(F(n)) time, which is Ω(1.6n).

[편집] Binary recursion with special Perl "caching", snippet

use Memoize;
memoize 'fibo';
sub fibo;
sub fibo {$_ [0] < 2 ? $_ [0] : fibo ($_ [0] - 1) + fibo ($_ [0] - 2)}

[편집] Iterative, snippet

sub fibo {
    my ($n, $a, $b) = (shift, 0, 1);
    ($a, $b) = ($b, $a + $b) while $n -- > 0;
    $a
}

[편집] Command line iterative

perl -Mbigint -le '$a=1; print $a += $b while print $b += $a'

[편집] 포스트스크립트

[편집] Iterative

20 % how many Fibonacci numbers to print
                                                                               
1 dup
3 -1 roll
{
       dup
       3 -1 roll
       dup
       4 1 roll
       add
       3 -1 roll
       =
}
repeat

[편집] 스택 리커젼

This example uses recursion on the stack.

% the procedure
/fib
{
   dup dup 1 eq exch 0 eq or not
   {
      dup 1 sub fib
      exch 2 sub fib
      add
   } if
} def

% prints the first twenty fib numbers 
/ntimes 20 def
  
/i 0 def
ntimes {
   i fib =
   /i i 1 add def
} repeat

[편집] 파이썬

[편집] 재귀

def fib(n):
    if n < 2:
        return n
    else:
        return fib(n - 1) + fib(n - 2)

[편집] Generator

def fib():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

[편집] 행렬 방정식

def mul(A, B):
    a, b, c = A
    d, e, f = B
    return a*d + b*e, a*e + b*f, b*e + c*f

def pow(A, n):
    if n == 1:     return A
    if n & 1 == 0: return pow(mul(A, A), n/2)
    else:          return mul(A, pow(mul(A, A), (n-1)/2))

def fib(n):
    if n < 2: return n
    return pow((1,1,0), n-1)[0]

This calculates the nth Fibonacci number in O(log N) time, from the matrix equation

\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n =        \begin{bmatrix} F\left(n+1\right) & F \left(n\right) \\                        F\left(n\right)   & F \left(n-1\right) \end{bmatrix}

and by using exponentiating by squaring.

[편집] Scheme

[편집] Binary recursion, snippet

(define fibo
 (lambda (x)
   (if (< x 2)
     x
     (+ (fibo (- x 1)) (fibo (- x 2))))))

Θ(F(n)) 시간이 소요된다.

[편집] Tail-end recursive, snippet

(define (fibo x) 
  (define (fibo-iter x a b)
     (if (= x 0) 
            a 
           (fibo-iter (- x 1) b (+ a b))))
  (fibo-iter x 0 1))

Θ(n) 시간에 실행된다.

[편집] 모두 표시하는 코드 조각

(define (fibo-run a b) 
  (display a)
  (newline)
  (fibo-run b (+ a b)))

(define fibo-run-all (fibo-run 0 1))) 

[편집] C/C++/Java

[편집] 재귀적 코드 조각

int fib(int n) {
  if (n < 2)
    return n;
  else
    return fib(n-1) + fib(n-2);
}

Θ(F(n)) 실행 시간에 실행되며, Ω(1.6n)의 시간을 갖는다.

[편집] 루비

 def fib(num)
   i, j = 0, 1
   while i <= num
     yield i
     i, j = j, i + j
   end
 end

 fib(10) {|i| puts i}

[편집] 같이 보기

다른 언어