피보나치 수 프로그램
위키백과 ― 우리 모두의 백과사전.
피보나치 수 프로그램은 피보나치 수를 프로그래밍 언어로 만든 것으로, 일반적으로 재귀적인 방법을 사용한다.
피보나치 수를 정의에 따라 재귀적으로 구하면 일반적으로 거듭제곱의 시간 복잡도가 소요된다. 하지만 한번 구한 값을 저장해서 여러 번 중복해서 계산하지 않는 메모이제이션을 사용하면 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 (s[[그림:Example.jpg]][[Media:Example.ogg]][[Media:Example.ogg]]<math>여기에 수식을 쓰세요</math>여기에 위키 문법을 사용하지 않을 글을 적어 주세요--~~~~
----'''굵은 글씨'''
econd *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))
[편집] 펄
[편집] 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 examples
[편집] 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}


