Acwing-考研机试题

---

放苹果(北京大学机试题)

一、题目描述
Acwing-3428.放苹果

二、分析与代码
分析
采用DFS：
因为5，1，1与1，5，1属于同一种分法，故我们需要避免对类似情况的重复计数，可采用数量不减或数量不增两种分法，我们采用数量不减分法，具体而言就是后面的盘子所分得的苹果数量不小于前面盘子所分得的。
1、定义int型变量all，表示已经分配的苹果的数量；
2、定义一void dfs(int x,int y)函数，表示对第x个盘子进行操作，上个盘子放了y个苹果。当对最后一个盘子进行操作即x==n时，判断剩余苹果数量是否大于等于y（采用数量不减原则），若是则分法加1，否则不加；
3、若不是对最后一个盘子进行操作，则采用循环for(int i=y;i<=m;i++)调用dfs函数，因为采用数量不减原则，故可直接从y开始。
具体代码如代码1：

采用dp：
1、定义数组int dp[m+1][n+1]，dp[i][j]表示i个苹果放进j个盘子的分法数；
2、初始化dp数组，当盘子数为1时分法数为1，当苹果数为0时分法数为1；
3、找出dp[i][j]的表达式，当i<j，即苹果数量大于盘子数量时，dp[i][j]=dp[i][i]，因为多的盘子一定为空；当i>=j时，dp[i][j]=dp[i-j][j]+dp[i][j-1]，即一个盘子不放（dp[i][j-1]）加上每个盘子至少放一个（dp[i-j][j]，每个盘子至少放一个后还有i-j个苹果，即分法等于dp[i-j][j]）。
具体代码如代码2：

具体代码

代码1：

#include <iostream>
#include <cstring>

using namespace std;

//ans记录满足条件的答案数，all代表已经分配的苹果数量
int n,m,ans,all;

//对第x个盘子进行操作，上个盘子放了y个苹果
void dfs(int x,int y)
{
    
    if(x==n)
    {
    
        if(m-all>=y)
            ans++;
        return;
    }
    for(int i=y;i<=m;i++)
    {
    
        all+=i;
        dfs(x+1,i);
        all-=i;
    }
}

int main()
{
    
    while(cin>>m>>n)
    {
    
        ans=0;
        all=0;
        dfs(1,0);
        cout<<ans<<endl;
    }
    return 0;
}

代码2：

#include <iostream>
#include <cstring>

using namespace std;

int main()
{
    
    int m,n;
    while(cin>>m>>n)
    {
    
        int dp[m+1][n+1];   //dp[i][j]表示i个苹果放进j个盘子的分法
        for(int i=0;i<=m;i++)
            dp[i][1]=1;
        for(int i=0;i<=n;i++)
            dp[0][i]=1;
        for(int i=2;i<=n;i++)
            for(int j=1;j<=m;j++)
                if(j<i)
                    dp[j][i]=dp[j][j];
                else
                    dp[j][i]=dp[j][i-1]+dp[j-i][i];
        cout<<dp[m][n]<<endl;
    }
    return 0;
} 

(大学机试题)

一、题目描述
Acwing-

二、分析与代码
分析

具体代码

代码：