피보나치 수 프로그램
위키백과 ― 우리 모두의 백과사전.
피보나치 수 프로그램은 피보나치 수를 프로그래밍 언어로 만든 것으로, 일반적으로 재귀적인 방법을 사용한다.
피보나치 수를 정의에 따라 재귀적으로 구하면 일반적으로 거듭제곱의 시간 복잡도가 소요된다. 하지만 한번 구한 값을 저장해서 여러 번 중복해서 계산하지 않는 메모이제이션을 사용하면 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
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}