データ構造_3_fibnacci再帰と非再帰

個人総括:1、コードはいつも手で書きます.
2、先生が授业で私たちに再帰と非再帰を要求したので、fibnacciは私がすべて试みます
その後、ツリーの再帰と非再帰の2つの方法を試みます.

//Chapter3_fibnacci.cpp:コンソールアプリケーションのエントリポイントを定義します.//#include "stdafx.h"#include #include using namespace std; long fib(long n) {if (n <= 1) return n;else {return fib(n - 1) + fib(n - 2);} }//再帰//********************************************************************************************************************************************************************************************************************************************************************************************************************************************long fib2(long n) {stack s;Node* w=new Node();long sum = 0;do {while (n > 1) {w->n = n;w->tag = 1;s.push(*w);n--;}sum = sum + n;while (!s.empty()) {w = &s.top();s.pop();if (w->tag == 1) {w->tag = 2;s.push(*w);n = w->n - 2;break;}}} while (!s.empty());return sum; };//非再帰1//********************************************************//画図再帰理解long fib 3(int n){if(n<=1)returnn;///f(0)またはf(1)の場合long twoback=0,oneback=1,current;///n>=2の場合for(int i=2;i<=n;i+){current=twoback+oneback;//計算f(n)=f(n-2)+f(n-1)twoback=oneback;////////////計算f(n)=f(n-1)twoback=oneback;//////////////////計算f(計算f(n=f(n-1)twoback f(n-1)、次のf(n-2)oneback = current;//計算f(n),次のf(n-1)}return current;}//****************************************************************************************************************************************************************************************************************************************************************************int main() {long ans1 = fib(10);cout << "ans1:"<< ans1 << endl;cout << "***********************"<< endl;ans1 = fib2(10);cout << "ans2:"<< ans1 << endl;cout << "***********************"<< endl;ans1 = fib3(10);cout << "ans3:"<< ans1 << endl;return 0; }