每日编程一刷之记忆化递归（结合两道基础题目带你理解记忆化）

每日编程一刷之记忆化递归（结合两道基础题目带你理解记忆化） 每日编程一刷之记忆化递归（结合两道基础题目带你理解记忆化）

目录侠在此‍

文章目录

每日编程一刷之记忆化递归（结合两道基础题目带你理解记忆化）

前言‍

例题结语

前言‍

小伙伴们肯定首先对递归很熟悉，相信学习过c语言的同学们，肯定是很多时候被这个递归搞得很难受，今天我是给大家说一下记忆化递归的思想是如何实现的，首先，我们肯定是知道如何求一个斐波那契数列

f(n)=f(n-1)+f(n-2);//这个是如何实现的

相信大家很快就能说出这个的实现过程 简单的一个递推公式就可以轻松解决

但是我们在计算的过程中会出现大量的计算，

就比如说我们在求解6的时候 我们计算了好多次f（3） 如果我们可以将这些重复的数据保存起来 就不用每次都去计算了

这样也可以大大加快我们的运算的效率 这样是我们的记忆化数组出现的原因

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

我们的实现思路 就是我们定义一个数组 用来存放我们每一次计算的数据 然后如果我们需要那个数据我们就可以直接去前面取那个数据

下面我写两个形式的代码 一个是递归类型的 一个是循环类型的

#include//循环的写法
using namespace std;
int arr[100000];
int f(int n){
	
      int i;
	if(n==1||n==2){
		return 1;
	}
	for(i=3;i<=n;i++){
		arr[i]=arr[i-1]+arr[i-2];
	}
	return arr[n];

	
}
int main(){
	int n;
	arr[1]=1;
	arr[2]=1;
	cin>>n;
	cout< 
记忆化的写法
#include
using namespace std;
int arr[100000]={0};
int f(int n){
    if(n==1||n==2){
        return 1;
    }
    if(arr[n]!=0){//这个是判断这个位置有没有被更新 只要是被更新的话就不是0 不然的话就是0 只要不是0我们就直接返回 不要再去递归
        return arr[n];
    }
    
    return arr[n]=f(n-1)+f(n-2);
}
int main(){
    int n;
    arr[1]=1;
    arr[2]=1;
    cin>>n;
    f(n);    
    cout< 
例题 
 
大同小异 直接递归上手 不过需要注意一点就是我们如何判断已经计算过了 这个不同于斐波那契数列 我们可以定义一个
 
bool数组 如果能够是true的话代表这个已经被赋予值，下次直接使用就可以了 如果不是的话 那么我们就 继续求值
 
下面代码演示
 
#include 
using namespace std;

#define MAX_SIZE 2001
 
int res[MAX_SIZE];       //res[x] = x - g(g(x - 1)), 即为res[x] == g(x)
bool visited[MAX_SIZE];
 
int g(int x)
{
    //递归结束条件
    if (x == 0)
	{
		return 0;
	}  
    
    //记忆化搜索
	if (visited[x])//这个步骤其实和上边判断是否计算过是一样的逻辑
	{
		return res[x];
	}
    
    //标记g(x)已被计算，res[x] 已存储了 g(x) 的值
	visited[x] = true;//能够走到这一步说明可以进行计算出来res[x]
	
	return res[x] = x - g(g(x - 1));
}
 
int main()
{
	int n;
	scanf("%d", &n);
	printf("%d", g(n));
	return 0;
}
 
//循环写法
#include 
using namespace std;

#define MAX_SIZE 2001
 
int res[MAX_SIZE];       //res[x] = x - g(g(x - 1)), 即为res[x] == g(x)
bool visited[MAX_SIZE];
 int f(int n){
 	if(n==0){
 		return 0;
 		
	 }
	 if(n==1){
	 	return 1;
	 }
	 int i;
	 res[0]=0;
	 res[1]=1;
	for(i=2;i<=n;i++){
		res[i]=i-res[res[i-1]];
	}
	return res[n];
 }
 
结语 
对于这些算法类的题目大家还是多做 多积累 见的多啦 自然就会了
 
加油
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5702558.html