简约好看的网站模板免费下载,教育网站 网页赏析,网页报价表,网站建设相关网站题目链接#xff1a;斐波那契数列 - 题目 - 青藤 OJ题目来源#xff1a;经典题题目大意输入 #xff0c;输出 0#xff0c;1 开头的斐波那契数列的第 n 项。这里我们不讨论递推方法#xff0c;我们采用这道简单的题目简单说一下记忆化搜索相关内容。解法首先#xff0c;基…题目链接斐波那契数列 - 题目 - 青藤 OJ题目来源经典题题目大意输入 输出 01 开头的斐波那契数列的第 n 项。这里我们不讨论递推方法我们采用这道简单的题目简单说一下记忆化搜索相关内容。解法首先基础的递归解决的程序非常好写对于 f(n) 来说边界情况 递归方程 所以代码就很自然#include bits/stdc.h
using namespace std;
long long f(int n) {if (n 1)return 0;if (n 2)return 1;return f(n - 1) f(n - 2);
}
int main() {int n;cin n;cout f(n) endl;return 0;
}
然而这样的做法在 n 为 40 时便达到了 500ms在 45 时无法通过为什么呢我们会发现求解 f(6) 时 用到的 f(4) 会在求解 f(5) 用到时重新求解再往上看的话重复计算所花的时间时非常恐怖的导致我们做了很多多余的计算。解决的方法也很简单算过了的我们就拿个小本本出来记下来下次要用上直接拿出上次的结果就好。 #include bits/stdc.h
using namespace std;
long long book[50]; //小本本
long long f(int n) {//如果算过了直接返回结果if (book[n] ! -1)return book[n];if (n 1) {//返回之前记下来book[n] 0;return book[n];}if (n 2) {//返回之前记下来book[n] 1;return 1;}//返回之前记下来book[n] f(n - 1) f(n - 2);return book[n];
}
int main() {//没算过的就用-1表示memset(book, -1, sizeof(book));int n;cin n;cout f(n) endl;return 0;
}
这便是所谓的记忆化递归。如果有两个参数的递归我们可以开一个二维数组来记录就好。比如下面这道阿克曼(Ackmann)函数 - 题目 - 青藤 OJ虽然这道题的数据范围不需要记忆化普通递归也能过但是大家可以试一下用记忆化递归实现~当然斐波那契数列的求解还会有更多方式递推的方式就可以和记忆化递归一样达到 的时间复杂度采用矩阵快速幂来做的话可以达到 也会有数学的方法利用公式快速得出更大数据范围的项。
