【c++递推递归算法】放苹果（详细代码+图解+解题思路） |
您所在的位置：网站首页 › 把12个桃子平均放在3个盘子里 › 【c++递推递归算法】放苹果（详细代码+图解+解题思路） |
|
递推递归算法解决放苹果问题：把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。
1.【题目描述】2.【解题思路】3.【地推代码】4.【递归代码】
1.【题目描述】
把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。 【输入】 第一行是测试数据的数目t（0≤t≤20）。以下每行均包含二个整数M和N，以空格分开。1≤M，N≤10。 【输出】 对输入的每组数据M和N，用一行输出相应的K。 【输入样例】 1 7 3 【输出样例】 8 2.【解题思路】 盘子1盘子2盘子30070160250341151241332231.分两种情况 如果盘子比苹果多，即m>n，那么肯定有m-n个空盘子，空盘子没用，直接不要就行了： 递推公式：f[n][m] = f[n][n] 2.如果盘子小于等于苹果数量 f[n][m] 应该等于少去一个盘子的数量加上先把每一个盘子放一个苹果（n-m）剩下的苹果在放m个盘子 递推公式：f[n][m]=f[n][m-1]+f[n-m][m] 3.【地推代码】 #include using namespace std; int main() { int n,m,t,a[10][10]={0}; cin>>t; for(int i=0;i a[i][1]=1; //只有一个盘子的时候放法只有1种 a[1][i]=1; //只有一个苹果的时候放法只有1种 a[0][i]=1; //没有苹果的时候方法只有1种 } for(int i=2;i if(i a[i][k]=a[i][k-1]+a[i-k][k]; } } } cout return 1; } if(n>m) { return f(m,m); } else { return f(m,n-1)+f(m-n,n); } } int main() { int m,n,c; cin>>c; while(c--) { cin>>m>>n; cout |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |