3.航空母舰（aircraft.cpp）

【题目描述】

航空母舰（Aircraft Carrier）,是一种以舰载机为主要作战武器的大型水面舰艇。依靠航空母舰，一个国家可以在远离其国土的地方、不依靠当地机场情况施加军事压力和进行作战。航空母舰已经是现代海军不可或缺的利器。也成为一个国家综合国力的象征。

假如，某国家有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

【题目分析】

• 原题来自“放苹果”。

【参考代码1】

#include<bits/stdc++.h>
using namespace std;
//本题的算法思想为递归
int q(int n,int m)
{
    if(n==1||m==1)//当二者任意为1则就是一种
    {
        return 1;
    }
    if(n<m)  return q(n,n);//当m>n时没有意义便为q(n,n)
    /*n=m时可以分为两种情况，一个是使用n本身，只有一种情况。二个是使用不大于n-1的整数进行拆分。
    所以此时q(n,m)=1+q(n,n-1);*/
    if(n==m)
    {
        return q(n,m-1)+1;
    }
    /*
    n>m这时候有两种情况，一个是使用m对n进行拆分，一个是使用小于m的数对n进行拆分

对于第一个，使用m对n进行拆分，所以拆分出来的情况最大的数是m，剩下的所有数加起来为n-m，问题变成使用不大于m的整数对n-m进行拆分，所以此时为q(n-m,m)

对于第二个，使用小于m的数对n进行拆分，表示为q(n,m-1)
    */
    if(n>m)
        return q(n,m-1)+q(n-m,m);
}

int main()
{
    int n, m;
    int t;
    cin>>t;
    for(int i=0; i<t; i++)
    {
        cin>>n>>m;
        int k = q(n,m);
        cout<<k<<endl;
    }
    return 0;
}

【参考代码2】

#include<iostream>
#include<cstring>
using namespace std;
int a[20][20];
int f(int m,int n)
{
    int i,j;
    for(i=1;i<=n;i++)//0个苹果
        a[0][i]=1;
    for(i=1;i<=m;i++)//1个盘子
        a[i][1]=1;
    for(i=1;i<=m;i++)
        for(j=2;j<=n;j++)
            if(i<j)
                a[i][j]=a[i][i];
            else 
                a[i][j]=a[i][j-1]+a[i-j][j]; 
}
int main()
{
    int m,n,i,j,k;
    cin>>k;
    for(i=1;i<=k;i++)
    {
        cin>>m>>n;
        f(m,n);
        cout<<a[m][n]<<endl;
    }
    return 0;
}