Java教程

记忆化搜索+递归与递推

本文主要是介绍记忆化搜索+递归与递推,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

记忆化搜索,顾名思义吗,搜索一次记忆一次,功能

题目描述

楼梯有 NN 阶,上楼可以一步上一阶,也可以一步上二阶。

编一个程序,计算共有多少种不同的走法。

就是提高效率呗。

 很容易看出就是个递推呗,斐波那契数列。那这道题数据很大,一次一次的递推会超限

没啥好说的就是高精的斐波那契,前面也有写到。



P1002 [NOIP2002 普及组] 过河卒 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P1002

 定义一个二维数组f(i,j)表示走到(i,j)的方案数,显然f(i,j)=f(i-1,j)+f(i,j-1)。

当卒从起点开始笔直地向下或笔直地向右,无论走多远都只有一种方法,所以当k>=0,f(0,k)=f(k,0)=1;这里值得注意的是f(0,0)=1,(自己想一想为什么),不要问我,因为我也不是很清楚。。。。。这儿就是递归的初始条件。

定义二维数组搜索马周围的控制点,赋值为1.

#include<bits/stdc++.h>
using namespace std;
int d[9][2] = { -2,-1,0,0,1,2,1,-2,-1,2,-1,-2,2,1,2,-1,-2,1 };
int cc[22][22];
long long f[22][22];
int main()
{
	int x, y, n, m;
	cin >> x >> y >> n >> m;
	for (int i = 0; i < 9; i++)
	{
		int tempx = n + d[i][0], tempy = m + d[i][1];
		if (tempx >= 0 && tempx <= x && tempy >= 0 && tempy <= y)
			cc[tempx][tempy] = 1;
	}
	f[0][0] = 1 - cc[0][0];
	for(int i=0;i<=x;i++)
		for (int j = 0; j <= y; j++)
		{
			if (cc[i][j] == 1)
				continue;
			if (i)//如果不在横轴上
				f[i][j] += f[i - 1][j];
			if (j)//如果不在纵轴上
				f[i][j] += f[i][j - 1];
	}
	cout << f[x][y];
		return 0;
}

P1044 [NOIP2003 普及组] 栈 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P1044

递推思想:假设i个元素有f(i)种方法,要求n个元素的出管方式,依题意,每个元素都有可能最后一个出去,那我们假设第k个小球最后一个出去有h(k)种方法,那么比k早入管且早出去的有k-1个数,则有f(k-1)种,比k晚出管且早出去的有f(n-k)种。独立性,所以h(k)=f(k-1)*f(n-k)

 那么每个元素都有机会最后一次出管,所以f(n)=h(1)+h(2)+   +h(n-1)+h(n)=f(0)*f(n-1)+f(1)*f(n-2)+ 

    +f(n-2)*f(1)+f(0)*f(n-1).

代码实现起来就很简单了。如下。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{//i个元素有f【i】钟出管方式
	int n;
	cin >> n;
	int  f[20] = { 1,1,2 };
	
	for (int i = 3; i <= n; i++)
	{
		for (int j = 0; j < n; j++)
			f[i] += f[j] * f[i - j - 1];
	}
	cout << f[n];
	return 0;
}

                                               接下来就是递归和记忆化搜索了


题目描述

我们要求找出具有下列性质数的个数(包含输入的正整数 nn)。

先输入一个正整数 nn(n \le 1000n≤1000),然后对此正整数按照如下方法进行处理:

  1. 不作任何处理;

  2. 在它的左边加上一个正整数,但该正整数不能超过原数的一半;

  3. 加上数后,继续按此规则进行处理,直到不能再加正整数为止。

思路很简单,把一个数一直分下去,加不加左边跟这题没关系,函数递归地结束条件为分到1不能再分了。

我们很容易写下下面的函数:

int ss(int x)
{
	int ans = 1;
	if (x==-1)
		return 1;
	for (int i = 1; i <= x / 2; i++)
		ans += ss(i);
	return ans;
}

当然并没有什么问题,但是只能通过数据小的,运行效率低会时间超限,举个例子,比如说我们递归ss(2),它可能也会被ss(8),ss(4)调用,但是ss(2)的值是一只不变的,在这却被重复计算了很多次。既然它的值是不变的,我们算一个保存一个,下次直接调用,不用再一直递归下去了。

这就是记忆化搜索。

将数组初始化为-1,代表没被搜索保存过。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int d[1005];
int ss(int x)
{
	int ans = 1;
	if (d[x]!=-1)
		return d[x];
	for (int i = 1; i <= x / 2; i++)
	{
		ans += ss(i);
	}
	return d[x]=ans;
}
int main()
{
	int n;
	cin >> n;
	memset(d, -1, sizeof(d));
	d[1] = 1;
	int ans = ss(n);
	cout << ans;
	return 0;
}

P1928 外星密码 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)icon-default.png?t=LA92https://www.luogu.com.cn/problem/P1928这题很容易想到用函数来实现递归,但是能不能实现就是另一回事了,,,,

我们直接输入一个字符串不好查找后面,那就一个一个输,又是一个小技巧。

举个例子:AC[3FUN]

首先,我们找到了被压缩的字符串:3FUN

3FUN进行解压,得到FUNFUNFUN

再把原来的字符串AC后面添上FUNFUNFUN即可。

由于这个只有一重「压缩」,可能递归思想体现的不太明显,这里再举一个多重「压缩」的例子:

SAD[4MLE[2TLE[2RE[2WA]]]

首先找到被「压缩」的部分:

[2MLE[2TLE[2RE[2WA]]]]

(从此处开始剩下的部分就是递归的内容了,全部由程序自主实现)

对这个部分进行解压,找到被「压缩」的部分:

[2TLE[2RE[2WA]]]

再对这个部分进行解压,找到被「压缩」的部分:

[2RE[2WA]]

再对这个部分进行解压,找到被「压缩」的部分:

[2WA]

(开始一层一层跳出递归)

对这个部分进行解压并加到前一个字符串的末尾:

[2REWAWA]

再对这个部分进行解压并加到前一个字符串的末尾:

[2TLEREWAWAREWAWA]

再对这个部分进行解压并加到前一个字符串的末尾:

[2MLETLEREWAWAREWAWATLEREWAWAREWAWA]

再对这个部分进行解压并加到前一个字符串的末尾:

SADMLETLEREWAWAREWAWATLEREWAWAREWAWAMLETLEREWAWAREWAWATLEREWAWAREWAWA

至此,递归结束,「密码」破译完毕。

所以,我们只需要找到被「压缩」的子串,并把这个字符串扔给「解压缩」程序即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
string xx()
{
	string s="",x;
	char c;
	int d;
	while (cin >> c)
	{
		if (c == '[')//发现一个压缩区
		{
			cin >> d;
			x = xx();
			while (d--)
				s += x;
		}
		else if (c == ']')
			return s;
		else
			s += c;
	}
	return s;
}
int main()
{
	cout << xx();
	return 0;
}

这篇关于记忆化搜索+递归与递推的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!