两种斐波那契数列非递归算法(堆栈模拟、循环)

发布于 / C语言 / Comments Off on 两种斐波那契数列非递归算法(堆栈模拟、循环)
//堆栈模拟

#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;

int main(){
  int num;
  cout << "计算几项呢?\n"; 
  cin >> num;
  stack<int> St;  //定义栈 
  for(int i = num; i > 0; i--)
    St.push(i);  //从大到小将数字压入栈
 
  int s = 0, b = 0, ans = 0;
  while(!St.empty()){  //栈非空的时候 
    int front = St.top();  //front是栈顶元素 
    if(front == 1) //栈顶为1,给s赋值,此时ans为1 
      ans = s = 1;
    else if(front == 2)//栈顶为2,给b复制,ans为2 
      ans = b = 2;
    else{    //栈顶大于2,可以按照递推公式进行计算 
      ans = b + s;
      s = b, b = ans;
    }
    cout << ans << ' ';  //输出该项的计算结果 
    St.pop();    //弹栈 
  }
  return 0;
}

//顺序计算
#include <bits/stdc++.h>
using namespace std;

int f(int n){
  if(n <= 0) return 0;
  else if(n == 1 || n == 2) return 1;
  else{
    int a = 0, b = 1;
    for(int i = 2; i <= n; i++){
      int t = a;
      a = b;
      b = a + t;
    }
    return b;
  }
} 

int main(){
  for(int i = 0; i < 10; i++) cout << f(i) << endl;
  
  return 0;
}

转载原创文章请注明,转载自: 斐斐のBlog » 两种斐波那契数列非递归算法(堆栈模拟、循环)
评论已关闭