当前位置：首页 > ds >正文

《算法笔记》11.1小节——动态规划专题-＞动态规划的递归写法和递推写法问题 A: Fibonacci

ds 2025/9/7 11:32:59

题目描述

The Fibonacci Numbers{0,1,1,2,3,5,8,13,21,34,55...} are defined by the recurrence:
F0=0 F1=1 Fn=Fn-1+Fn-2,n>=2
Write a program to calculate the Fibonacci Numbers.

输入

Each case contains a number n and you are expected to calculate Fn.(0<=n<=30) 。

输出

For each case, print a number Fn on a separate line,which means the nth Fibonacci Number.

样例输入

样例输出

分析：给出一个 n，求第 n 个斐波那契数。最好是先打表计算出前 30 个斐波那契数，之后根据输入的 n 直接输出。

#include<algorithm>
#include <iostream>
#include  <cstdlib>
#include  <cstring>
#include   <string>
#include   <vector>
#include   <cstdio>
#include    <queue>
#include    <stack>
#include    <ctime>
#include    <cmath>
#include      <map>
#include      <set>
#define INF 0x3fffffff
#define db1(x) cout<<#x<<"="<<(x)<<endl
#define db2(x,y) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<endl
#define db3(x,y,z) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<endl
#define db4(x,y,z,r) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#r<<"="<<(r)<<endl
#define db5(x,y,z,r,w) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#r<<"="<<(r)<<", "<<#w<<"="<<(w)<<endl
using namespace std;void getnum(int fab[])
{fab[0]=0,fab[1]=1;for(int i=2;i<=30;++i)fab[i]=fab[i-1]+fab[i-2];return;
}int main(void)
{#ifdef testfreopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);clock_t start=clock();#endif //testint fab[36]={0};getnum(fab);int n;while(~scanf("%d",&n)){printf("%d\n",fab[n]);}#ifdef testclockid_t end=clock();double endtime=(double)(end-start)/CLOCKS_PER_SEC;printf("\n\n\n\n\n");cout<<"Total time:"<<endtime<<"s"<<endl;        //s为单位cout<<"Total time:"<<endtime*1000<<"ms"<<endl;    //ms为单位#endif //testreturn 0;
}

查看全文

http://www.xdnf.cn/news/7806.html