动态规划专题之斐波那契数列1
需积分: 0 158 浏览量
2022-08-08
20:08:24
上传
评论
收藏 41KB DOCX 举报
动态规划系列专题讲义
专题一：斐波那契数列
/*
Name: 动态规划专题之斐波那契数列
Copyright: 巧若拙
Author:
Date: 22-03-17 08:56
Description: 1755_菲波那契数列
描述：斐波那契数列是指这样的数列: 数列的第一个和第二个数都为 1，接下来每个数都等
于前面 2 个数之和。给出一个正整数 a，要求斐波那契数列中第 a 个数是多少。
输入：第 1 行是测试数据的组数 n，后面跟着 n 行输入。每组测试数据占 1 行，包括一个正
整数 a(1 <= a <= 20)
输出：输出有 n 行，每行输出对应一个输入。输出应是一个正整数，为菲波那契数列中第 a
个数的大小
样例输入
4
5
2
19
1
样例输出
5
1
4181
1
*/
#include<iostream>
#include<cmath>
using namespace std;
const int MAXN = 50;
int F1[MAXN];//Fibonacci 数列
int F2[MAXN] = {0, 1};//Fibonacci 数列
int Fibonacci(int n); //递归算法
int Fibonacci_1(int n); //备忘录：自顶而下
int Fibonacci_2(int n);//动态规划：自底而上
int Fibonacci_3(int n);//动态规划：降维优化
int main()
{
评论0