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;  }

(adsbygoogle = window.adsbygoogle || []).push({});