放苹果问题解题报告的软件_小学数学解决问题教案[通俗易懂]

把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

分析：
一、递归法
显然当苹果数m或盘子数n为1时，只有一种放法。
当m或n不等于1时
分两种情况讨论：
一.苹果数m<盘子数n，必然有空盘出现。例如3个苹果放入7个盘子即使每盘放一个还会空出4个盘子。此时把m个苹果放入n个盘子和把m个苹果放入m个盘子是一致的。即f(m,n)=f(m,m)
二.苹果数m>=盘子数n
这种情况下又分为2种情况
1.有空盘
如果有空盘，那么可以有很多个空盘，至少是空一个。方法总数f(m,n)=f(m,n-1),为什么是n-1呢，先空一个。f(m,n-1)可以再讨论看其能不能再空一个出来，能即继续f(m,n-1)=f(m,n-2);不能，说明盘子数为已经减少到1了。
2.无空盘
无空盘说明盘子里肯定有苹果。至少有一个，也可以有很多个只要满足盘子都有苹果。
此时苹果数m必然>=盘子数n(不然肯定有空盘出现)，举例把7 个苹果放入3 个盘子，我们来思考既然不允许有空盘每盘至少有一个，我们把每盘先放入一个苹果（目的是符合题意使得盘子都在用，不空盘）。这时，还剩7-3=4个苹果。关键点来了！由于苹果都一样，盘子都一样（题意），这时放入盘子那个苹果和盘子本身已经融为一体（可以看成一个无差别整体）即把7个苹果放入3个盘子的方法数f(7,3)=有空盘f(7,2）与无空盘f(4,3)的方法数之和。此时还剩的4个苹果仍然多于盘子数。按此思路可以每盘再放入这1个苹果，还剩1个苹果。即f(4,3)=有空盘f(4,2)与无空盘f(1,3)的和。至于现在的f(1,3)由于m为1,所以f(1,3)方法数为1，即f(1,3)=1,对f(1,3)不必继续讨论。
因此f(7,3)=f(7,2)+f(4,3)=f(7,2)+f(4,2)+f(1,3)
下面对这个式子中m或n不为1的情况继续讨论。
按照上面的思路把这式子展开：
f(7,2)=f(7,1)+f(5,2) f(5,2)=f(5,1)+f(3,2) f(3,2)=f(3,1)+f(1,2)
f(4,2)=f(4,1)+f(2,2) f(2,2)=f(2,1)+f(0,2)(说明：苹果数和盘子数一致时。我们讨论2个苹果放入2个盘子，方法数等于2种情况的和。即有空盘（空一个盘子）f(2,1)+无空盘此时m=0时（已经每盘放一个），方法数为1,所以f(0,2)=1

用画图来表示：

通过上面图我们可以得到:
f(7,3)=f(7,1)+f(5,1)+f(3,1)+f(1,2) +f(4,1)+f(2,1)+f(0,2)+f(1,1)=1+1+1+1+1+1+1+1=8种。

综上：通过上面的讨论：m与n的关系为：
if(m等于1||m等于0||n==1) f(m,n)=1;
if(m<n) f(m,n)=f(m,m);
if(m>=n) f(m,n)=f(m,n-1)+f(m-n,n);
将上述过程继续重复分解最终使得f(m,n)的展开式中所有的m都为0或1，或n为1为止。

下面写出递归代码：
#include<bits/stdc++.h>
using namespace std;
int f(int m,int n)
{

if(m等于1||m等于0||n==1) return 1;
if(m<n) return f(m,m);
return f(m,n-1)+f(m-n,n);
}
int main()
{

int t,m,n;
cin>>t;
for(int i=1;i<=t;i++)
{

cin>>m>>n;
cout<<f(m,n)<<endl;
}
return 0;
}

二、递归变递推
若我们把上述递归算法变递推该如何思考：
用递推来讨论，初始条件（边界）0个或1个苹果，或1个盘子其结果都只有1种方法。目标是求出m个苹果n个盘子时有多少种方法。对子问题的划分，当苹果数或盘子数增加时，都会影响后续决策的判断，最终得到结果。
对每个子问题（当前苹果数和盘子数对应的方法）可用二维数组f[m][n]保存当前子问题的结果随时更新或调用可避免重复计算。
状态转移方程：
if(m<n) f[m][n]=f[m][m];
if(m>=n) f[m][n]=f[m][n-1]+f[m-n][n];

这其实完全符合动态规划的特征。即：能确定边界，能划分子问题，且子问题结果影响后续决策结果符合最优子结构性质，存在子问题重叠能写出状态转移方程解决重复计算，无后效性（只向前、不后退）。用的算法思想就是dp动态规划(记忆化搜索)。

动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著《Dynamic Programming》，这是该领域的第一本著作。——百度百科

下面写出递推算法（dp算法）
#include<bits/stdc++.h>
using namespace std;
int f[11][11];
int main()
{

int k,t,m,n;
for(int i=0;i<=10;i++)
{

f[0][i]=1; //确定边界
f[1][i]=1;
f[i][1]=1;
}
for(int i=2;i<=10;i++)
for(int j=2;j<=10;j++)
if(i<j) f[i][j]=f[i][i];//状态转移方程，递推式
else f[i][j]=f[i][j-1]+f[i-j][j];
cin>>t;
for(int i=1;i<=t;i++)
{

cin>>m>>n;
cout<<f[m][n]<<endl;
}
return 0;
}

三、回溯法

这道题也可以用回溯法来解决，回溯法属于递归形式的dfs深搜。
回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法（选优其实就是先定下某种策略，如每次都按上下左右顺序进行试探），按选优条件向前搜索，以达到目标或无解。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。由于走不通即回溯一步的特点其时间复杂度把枚举法的n的n次方降为n!而被广泛使用。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美誉。

用回溯算法解决问题的一般步骤：
1、 针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解。
2 、确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间 。
3 、以深度优先的方式搜索解空间，并且在搜索过程中用利用剪枝避免无效搜索。（关于剪枝视情况而用，这道题无需剪枝，也不能剪枝。因为题目并没有限定特别条件）

#include<bits/stdc++.h>
using namespace std;
int m,n,a[11],ans;
打印验证输出结果
//void print(int k) 这里的k表示全部放完苹果共用了k个盘子
//{

// for(int p=1;p<=k;p++)
// cout<<a[p]<<’ ‘;
// cout<<endl;
// return;//return也可以不写。
//}
void dfs(int s,int k)
{
/* 每盘中苹果数可从a[0]—a[s]中进行选择，
且下一个盘选择的数都不小于前面已选的数
（目的避免出现类似1 1 5和1 5 1 这样的重复数据)
如果不能选了，即表示苹果已放完，出现空盘。
无论是否出现空盘只要苹果数放完即一次成功结果。
*/
for(int i=a[k-1];i<=s;i++)
if(i<=m)
{

a[k]=i;
s-=a[k];
if(s==0&&k<=n){

// print(k);//用于输出验证结果
ans++;
}
dfs(s,k+1);
s+=a[k];//回溯到上一步继续搜索其他结果
}
}
int main()
{

int t;
cin>>t;
for(int i=1;i<=t;i++)
{

ans=0;
a[0]=1;//取1表示，开始放苹果时第一个盘子至少放1个，
//把空盘情况放在后面。
cin>>m>>n;
dfs(m,1);//意思是搜索第一个盘子里放的苹果数。
cout<<ans<<endl;
}
}
这道题用回溯法的优势在于：把问题对是否空盘的情况讨论变得很容易，你只管放苹果直到放完m个即可，放完苹果还有盘子不就是空盘吗？虽然时间效率不如dp算法，但是在解题思路变得简单。即每个盘子从1开始放苹果直到m个苹果放完搜索出有多少种可能。唯一的难点就是要把回溯算法写熟练

今天的文章放苹果问题解题报告的软件_小学数学解决问题教案[通俗易懂]分享到此就结束了，感谢您的阅读。