ECIM list (Help!)
피보나치 수열 비재귀방법으로 풀기 - Fibonacci number without recursion
지그프리드
2015. 8. 30. 16:25
피보나치 수열 재귀함수 이용하지 않고
비재귀로 하는방법 좀 알려주세요~~
일단 재귀함수 이용하는건 했는데
비재귀는 어떻게 해야되는지 모르겠네요.. 더쉬울줄알았는데..
// 제가 작성한 피보나치 재귀함수 이용 버전입니다.
Stack을 사용하면 됩니다 |
○ 재귀함수를 없애는 가장 기본적인 방법은 Stack을 사용하는 것입니다. 재귀함수 자체가 실제로는 함수 Stack에 차곡차곡 결과값을 쌓고 있는 것입니다. 실제 Stack을 이용해서 값을 저장하면 그만입니다.
○ 특히 피보나치수열의 경우는 진짜 Stack을 쓸 필요도 없고, Stack 처럼 동작하는 Array면 됩니다. 제 코드에서도 Pop() 함수는 작성을 했지만, 막상 부르는 곳이 없습니다. 지우기도 귀찮아서 일단 남겨둡니다.
○ 참고로, 이 피보나치 수열은 0부터 시작하는 피보나치 수열입니다. 즉, 0, 1, 1, 2, 3, 5 순서로 진행됩니다. Wikipedia에 이것이 현대적인 형태라고 하더군요
https://en.wikipedia.org/wiki/Fibonacci_number
코드 예제 |
#includeusing namespace std; /* stack */ int stack[100]; int top = -1; int loop; int push(int inputV); int pop(void); int fibonacciOne(int x); int main() { //피보나치 수열 재귀 int n; cout << "몇번째 항의 값을 원합니까?"; cin >> n; cout << "\n" << n << "번째 항은 " << fibonacciOne(n) << "입니다."; cin >> n; return 0; } int push(int inputV) { if (top >= 99) //stack is full { return -1; //Error } else { stack[++top] = inputV; } } int pop(void) { if (top < 0) { return -1; //Error } else return stack[top--]; } int fibonacciOne(int x) { /* init stack */ for (loop = 0; loop < 100; loop++) { stack[loop] = 0; } top = -1; /* Set first two number of fibonacci array*/ stack[0] = 0; stack[1] = 1; /* calculate Nth number */ if (x <= 0) { return -1; //Error } else if ((x == 1) && (x == 2)) { return stack[x - 1]; } else if (x >= 100) //too big for demo { cout << "Error\n"; return -1; } else //Normal case { for (loop = 2; loop < x; loop++) { stack[loop] = stack[loop - 2] + stack[loop - 1]; } /* show all array */ for (int loop = 0; loop < x; loop++) { cout << stack[loop] << " "; } return stack[x - 1]; } }
실행 결과 |