피보나치 수 프로그램 문서 원본 보기

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

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

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

== [[스킴 (프로그래밍 언어)|스킴]] ==
=== Binary recursion, snippet ===
<source lang="scheme">
 (define fibo
  (lambda (x)
    (if (< x 2)
      x
      (+ (fibo (- x 1)) (fibo (- x 2))))))
</source>
[[점근 표기법|&Theta;]](F(''n'')) 시간이 소요된다.

=== [[Tail recursion|Tail-end recursive]], snippet ===
<source lang="scheme">
 (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))
</source>
[[점근 표기법|&Theta;]](''n'') 시간에 실행된다.

=== 모두 표시한 코드 조각 ===
<source lang="scheme">
 (define (fibo-run a b) 
   (display a)
   (newline)
   (fibo-run b (+ a b)))
 
 (define fibo-run-all (fibo-run 0 1))) 
</source>

== [[커먼 리스프]] ==
=== 루카스 식을 통한 피보나치 계산 ===
<source lang="lisp">
(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*))) ;
</source>

== [[하스켈]] ==
=== Lazy infinite list ===
<source lang="haskell">
 module Main where
 import System.Environment
 
 fibo = 1 : 1 : zipWith (+) fibo (tail fibo)
 
 main = do
     args <- getArgs
     print (fibo !! (read(args!!0)-1))
</source>

== [[펄]] ==
=== 하나의 예 ===

<source lang="perl">
 use bigint;
 
 my ($a, $b) = (0, 1);
 for (;;) {
     print "$a\n";
     ($a, $b) = ($b, $a+$b);
 }
</source>

=== Binary recursion, snippet ===
<source lang="perl">
 sub fibo;
 sub fibo {$_ [0] < 2 ? $_ [0] : fibo ($_ [0] - 1) + fibo ($_ [0] - 2)}
</source>
Θ(F(n)) 실행 시간에 실행되며, Ω(1.6n)의 시간을 갖는다.

=== Binary recursion with special Perl "caching", snippet ===
<source lang="perl">
 use Memoize;
 memoize 'fibo';
 sub fibo;
 sub fibo {$_ [0] < 2 ? $_ [0] : fibo ($_ [0] - 1) + fibo ($_ [0] - 2)}
</source>
=== Iterative, snippet ===
<source lang="perl">
 sub fibo {
     my ($n, $a, $b) = (shift, 0, 1);
     ($a, $b) = ($b, $a + $b) while $n -- > 0;
     $a
 }
</source>

===Command line iterative===
<source lang="bash">
 perl -Mbigint -le '$a=1; print $a += $b while print $b += $a'
</source>

== [[포스트스크립트]] ==
=== 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

==[[파이썬]]==
=== 재귀함수 ===
<source lang="python">
def fibonacci(n):
	if 0 <= n <= 1:
		return n
	else:
		return fibonacci(n-1) + fibonacci(n-2)

def fibolist(n):
	list = []
	for i in range(n):
		list.append(fibonacci(i))
	return list
</source>

=== 개선된 재귀함수 버전 ([[메모이제이션]] 적용) ===
<source lang="python">
fibomemo = {0:0, 1:1}
def fibonacci(n):
	if not n in fibomemo:
		fibomemo[n] = fibonacci(n-1) + fibonacci(n-2)
	return fibomemo[n]

def fibolist(n):
	fibonacci(n-1)
	return list(fibomemo.values())
</source>

=== For문 ===
<source lang="python">
def fibonacci(n):
	a = 0
	b = 1
	for i in range(n):
		a, b = b, a+b
	return a

def fibolist(n):
	list = []
	a = 0
	b = 1
	for i in range(n):
		list.append(a)
		a, b = b, a+b
	return list
</source>

===Generator===
<source lang="python">
def fib():
   a, b = 0, 1
    while True:
        yield a
        a, b = b, a+b
</source>

===행렬 방정식===
<source lang="python">
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]
</source>
This calculates the ''n''th Fibonacci number in [[Big O notation|O]]([[logarithm|log]] N) time, from the [[matrix (mathematics)|matrix]] equation
:<math>\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}
</math>
and by using [[exponentiating by squaring]].


==[[스칼라]]==
=== 재귀함수 ===
<source lang="scala">
def fib(n:Int):Int = if (n <= 1) n else fib(n-1) + fib(n-2)                                
</source>

=== 메모이제이션 ===
<source lang="scala">
val memo = collection.mutable.Map[Int, Int](0->0, 1->1)

def fib(n:Int):Int = {
        if (memo.get(n) == None) memo += (n -> (fib(n-1) + fib(n-2)))
        memo.get(n).getOrElse(0) 
    }

</source>

== [[C언어 (프로그래밍 언어)|C언어]]/[[C++]]/[[자바 (프로그래밍 언어)|자바]]/[[자바스크립트]] ==
=== Binary Recursive ===

<source lang="c">
 long fib(long n) {
   if (n < 2)
     return n;
   else
     return fib(n-1) + fib(n-2);
 }
</source>
[[점근 표기법|&Theta;]](F(''n'')) 실행 시간에 실행되며, &Omega;(1.6<sup>''n''</sup>)의 시간을 갖는다.

=== Tail-end Recursive ===
<source lang="c">
 long fib(long n) {
  return fibo_iter(n, 0, 1);
 }

 long fibo_iter(long x, long a, long b) {
  if (x==0) return a;
  else return fibo_iter(x-1, b, a+b);
 }
</source>
[[점근 표기법|&Theta;]](''n'') 실행 시간에 실행된다.

== [[루비 (프로그래밍 언어)|루비]] ==
<source lang="ruby">
 def fib(num)
   i, j = 0, 1
   while i <= num
     yield i
     i, j = j, i + j
   end
 end

 fib(10) {|i| puts i}
</source>

== [[F 샤프|F#]] ==
=== 꼬리 재귀호출(tail recursive call) ===
<source lang="ocaml">
#light

let fibo n =
    let rec loop a b k =
        match k with
        | v when v <= 1 -> a
        | _ -> loop (a + b) a (k - 1)
    loop 1I 1I n

printfn "fibo(10) = %O" (fibo 10)
</source>

== [[OCaml]] ==
<source lang="ocaml">
 let rec fib n =
   if n > 2 then fib (n - 1) + fib (n - 2)
   else 1;;

 fib(10);;
</source>

== [[로고 (프로그래밍 언어)|로고]] ==
<pre>
to fib :n
  if :n < 2 [output :n]
  output sum fib :n-1 fib :n-2
end
</pre>

== 같이 보기 ==
* [[피보나치 수]]
* [[황금비]]
* [[Hello world 프로그램]]

[[분류:알고리즘]]