피보나치 수열은
1 1 2 3 5 8 13 ..
전 수와 그 전전 수를 더한 값을 갖게 된다. 그래서 Fi ( num-1 ) + Fi ( num -2 ) 을 사용한 것이다.
재귀 함수를 이용해서 푼 문제
#include <iostream>
#include <vector>
using namespace std;
int Fi(int num)
{
if(num == 1)
return 1;
else if( num ==2 )
return 1;
else
return Fi(num-1)+Fi(num-2);
}
int main() {
int num;
cin >>num;
cout<< Fi(num)<<endl;
return 0;
}
#include <stdio.h>
//***** 일반 재귀 *****//
int Fibo(int n){
if (n == 1)
return 0;
else if (n == 2)
return 1;
else
return Fibo(n - 1) + Fibo(n - 2);
}
//***** 꼬리 재귀 *****//
int FiboTail(int n){
return FiboTailRec(n, 0, 1);
}
int FiboTailRec(int n, int before, int next){
if (n == 0)
return before;
else
return FiboTailRec(n - 1, next, before + next);
}
//***** 반복문 *****//
int FiboLoop(int n){
int before=0, cur=1, i, temp;
if (n == 0)
return 0;
else if (n == 1)
return 1;
else{
for (i = 1; i < n; i++){
temp = cur;
cur = before + cur;
before = temp;
}
return cur;
}
}
int main(int arc, char** argv){
int num = 10;
int i = 1;
for (; i <= num; i++){
printf("%d ", Fibo(i));
}
printf("\n");
for (i=0; i < num; i++){
printf("%d ", FiboTail(i));
}
printf("\n");
for (i = 0; i < num; i++){
printf("%d ", FiboLoop(i));
}
}
출처: http://ledgku.tistory.com/38 [견우와 직녀]
댓글