POJ-1664-放苹果

发布于 2019-07-20  1.03k 次阅读


问题传送门:

题意:

有n个苹果,放入m个盘子。一共有多少种方法。
盘子可以空,如果3个苹果2个盘子,1  2 和 2  1 是同一种方法。

分析:

(1)首先我们知道,当只有一个苹果,或者没有苹果,或只有一个盘子时,
只有一种方法。

(2)当盘子的数量比苹果的多时(m > n), 那么就算是所有的盘子都放一个
苹果,还是会有空的盘子。这种情况等价于把 n 个苹果放入 n 个盘子。

(3)当盘子的数量<=苹果的数量时(m <= n), 分两种情况考虑
           <1>每个盘子都有,那么每个盘子至少有一个苹果,剩余的n-m个苹果
                  随便放。
           <2>至少空一个盘子,即把n个苹果放入m-1个盘子中
很入门的一道联系递归思想的题目

当然,所有的递归都能转换成递推,下面给出两种方法的代码

递归代码:

#include <iostream>

using namespace std;

// 把n个苹果分到m个盘子

int solve(int n, int m)
{

    if (n==0||m==1||n==1)
        return 1;
    if (n < m)
        return solve(n, n);
    else
        return solve(n-m, m) + solve(n, m-1);
}

int main()
{
    int T, m , n;
    cin >> T;
    while(T--)
    {
        cin >> n >> m;
        cout << solve(n,m) << endl;
    }
    return 0;
}

递推代码:

#include <iostream>

using namespace std;
// ans[i][j]表示i个苹果,j个盘子的答案 
int ans[11][11];

void init()
{
    for (int j = 0;j < 11; j++)
        ans[0][j] = 1, ans[1][j] = 1, ans[j][1] = 1;
    
    for (int i = 1; i < 11; i++)
    {
        for (int j = 1; j < 11; j++)
        {
            if (i==1||j==1) continue;

            if (j > i) ans[i][j] = ans[i][i];
            else       ans[i][j] = ans[i-j][j]+ans[i][j-1];
        }
    }
}

int main()
{
    init();
    int T, m , n;
    cin >> T;
    while(T--)
    {
        cin >> n >> m;
        cout << ans[n][m] << endl;
    }
    return 0;
}

Simple And Clear