ybt1192放苹果后续:正解

ybt1192放苹果后续:正解ybt1192放苹果注:本篇为"此篇"后续真正的正解找规律上次的想法只是一时灵机一动,但小聪明是不能解决问题的,所以要理性地分析,在复杂的问题,经过分解都会变得简单。|·|·|·|·|·|·||::

大家好,欢迎来到IT知识分享网。ybt1192放苹果后续:正解"

ybt1192放苹果

注:本篇为此篇后续

真正的正解

找规律

上次的想法只是一时灵机一动,但小聪明是不能解决问题的,所以要理性地分析,在复杂的问题,经过分解都会变得简单。

· · · · · ·
盘子\苹果 1 2 3 4 5
1 1 1 1 1 1
2 1 2 2 3 3
3 1 2 3 4 5
4 1 2 3 5 6
5 1 2 3 5 7

设i果j盘的方案数是fi,j

在列表后可以发现,表格的第一行和第一列都是1,并且易知m或n为零时的方案数,这便是我们递推的边界条件。

写出初始化代码:

f[0][0]=1;
for(int i=1;i<=10;i++) {
	f[1][i]=1;
	f[i][1]=1;
	f[0][i]=1;
	f[i][0]=0;
}

另外,在盘子比苹果多的时候,方案数不再随盘子的增多而增多。

所以当i<j时,fi,j=fi,i

要想进行递推,找清状态关系是关键,在列上文的表时,我是先将所有苹果放在第一个盘子里,然后一个一个往后拿,直到在保证苹果数量递减的前提下无法往后拿为止。一开始就会出现在后面的盘子里大量出现零的情况,那么我们就可以这样分类。

\[总方案=有空盘方案+无空盘方案 \]

当有空盘时​,至少但不仅仅有一个盘子没放苹果,所以这时的问题就简化成j-1个盘子放i个苹果的情况;

当没有空盘时,每个盘子有至少但不仅仅一个苹果,所以这时将每个盘子的第一个苹果去掉,问题就简化成将i-j个苹果放进j个盘子的情况。

写出方程: fi,j=fi,j-1+fi-j,j

/*完整代码*/
#include<iostream>
using namespace std;
int f[15][15],t,m,n;
int main() {
	f[0][0]=1;
	for(int i=1;i<=10;i++) {
		f[1][i]=1;
		f[i][1]=1;
		f[0][i]=1;
		f[i][0]=0;
	}
	for(int j=2; j<=10; j++) {//枚举盘子数
		for(int i=2;i<=j;i++){//苹果比盘子少 
			f[i][j]=f[i][i]; 
		}
		for(int i=j; i<=10; i++) {//枚举苹果数 
			f[i][j]=f[i][j-1]+f[i-j][j];
			//cout<<i<<"	"<<j<<"	"<<f[i][j]<<endl; //测试,重要,勿动!!!
		}
	}
	cin>>t;
	for(int k=1;k<=t;k++) {
		cin>>m>>n;
		cout<<f[m][n]<<endl;
	}
	return 0;
}

思路来自这里,感谢

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/32573.html

(0)

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注微信