【题解】【记忆化递归】——Function
Function
题目描述
对于一个递归函数 w ( a , b , c ) w(a,b,c) w(a,b,c)
- 如果 a ≤ 0 a \le 0 a≤0 或 b ≤ 0 b \le 0 b≤0 或 c ≤ 0 c \le 0 c≤0 就返回值$ 1$。
- 如果 a > 20 a>20 a>20 或 b > 20 b>20 b>20 或 c > 20 c>20 c>20 就返回 w ( 20 , 20 , 20 ) w(20,20,20) w(20,20,20)
- 如果 a < b a<b a<b 并且 b < c b<c b<c 就返回$ w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c)$。
- 其它的情况就返回 w ( a − 1 , b , c ) + w ( a − 1 , b − 1 , c ) + w ( a − 1 , b , c − 1 ) − w ( a − 1 , b − 1 , c − 1 ) w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1) w(a−1,b,c)+w(a−1,b−1,c)+w(a−1,b,c−1)−w(a−1,b−1,c−1)
这是个简单的递归函数，但实现起来可能会有些问题。当 a , b , c a,b,c a,b,c 均为 15 15 15 时，调用的次数将非常的多。你要想个办法才行。
注意：例如 w ( 30 , − 1 , 0 ) w(30,-1,0) w(30,−1,0) 又满足条件 1 1 1 又满足条件 2 2 2，请按照最上面的条件来算，答案为 1 1 1。
输入格式
会有若干行。
并以 − 1 , − 1 , − 1 -1,-1,-1 −1,−1,−1 结束。
输出格式
输出若干行，每一行格式：
w(a, b, c) = ans
注意空格。
输入输出样例
输入 #1
1 1 1
2 2 2
-1 -1 -1
输出 #1
w(1, 1, 1) = 2
w(2, 2, 2) = 4
提示
数据规模与约定
保证输入的数在 [ − 9223372036854775808 , 9223372036854775807 ] [-9223372036854775808,9223372036854775807] [−9223372036854775808,9223372036854775807] 之间，并且是整数。
保证不包括 − 1 , − 1 , − 1 -1, -1, -1 −1,−1,−1 的输入行数 T T T 满足 1 ≤ T ≤ 1 0 5 1 \leq T \leq 10 ^ 5 1≤T≤105。
1.思路解析
读完题目，很容易就可以根据题意模拟出递归函数，如下：（记得要开long long）。
long long w(long long a,long long b,long long c)//定义递归函数
{
if(a<=0||b<=0||c<=0)return 1;//递归边界
if(a>20||b>20||c>20)return w(20,20,20);
if(a<b&&b<c)return w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);//缓存答案
else return w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1);
}
但是很荣幸地打了零分。
这是因为，这个递归函数存在大量重复调用。我们可以在一个递归函数计算完成之后，将答案缓存下来，后续只要发现这个答案计算过就直接返回。这就是记忆化递归。改动后的递归函数如下：
long long a,b,c,f[25][25][25];//用数组f缓存答案
long long w(long long a,long long b,long long c)//定义递归函数
{
if(a<=0||b<=0||c<=0)return 1;//递归边界
if(a>20||b>20||c>20)return w(20,20,20);
if(f[a][b][c])return f[a][b][c];
if(a<b&&b<c)f[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);//缓存答案
else f[a][b][c]=w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1);
return f[a][b][c];
}
注意，由于w函数的返回值永远大于
1
1
1，所以并不需要将f数组初始化为-1，直接判断是否为0就行了。
2.AC代码
#include<bits/stdc++.h>
using namespace std;
long long a,b,c,f[25][25][25];//用数组f缓存答案
long long w(long long a,long long b,long long c)//定义递归函数
{
if(a<=0||b<=0||c<=0)return 1;//递归边界
if(a>20||b>20||c>20)return w(20,20,20);
if(f[a][b][c])return f[a][b][c];
if(a<b&&b<c)f[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);//缓存答案
else f[a][b][c]=w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1);
return f[a][b][c];
}
int main()
{
while(true)//循环输入
{
scanf("%lld%lld%lld",&a,&b,&c);
if(a==-1&&b==-1&&c==-1)break;//结束
printf("w(%lld, %lld, %lld) = %lld\n",a,b,c,w(a,b,c));
}
return 0;
}
喜欢就订阅此专辑吧！
【蓝胖子编程教育简介】
蓝胖子编程教育，是一家面向青少年的编程教育平台。平台为全国青少年提供最专业的编程教育服务，包括提供最新最详细的编程相关资讯、最专业的竞赛指导、最合理的课程规划等。本平台利用趣味性和互动性强的教学方式，旨在激发孩子们对编程的兴趣，培养他们的逻辑思维能力和创造力，让孩子们在轻松愉快的氛围中掌握编程知识，为未来科技人才的培养奠定坚实基础。
欢迎扫码关注蓝胖子编程教育
