苏木三少
错的不是你,而是这个世界。

递归-放苹果

放苹果

题目:

把M个同样的苹果放在N个同样的盘子里,允许有盘子空着不放,问共有多少种不同的方法?5,1,1和1,5,1是同一种分法。

输入:

第一行是测试数据的数目t(0<=t<20)。以下每行均包含两个整数M和N,以空格分开。1<=M,N<=10;

输出

对输入的每组数据M和N,用同一行输出相应的K。

样例输入:

1

7 3

样例输出:

8

解题思路:

设i个苹果放在k个盘子里放法总数是f(i,k),则

当 k > i时,f(i,k) =f(i,i)

当k  < =i 时,总放法=+有盘子为空的放法+没盘子为空的放法

f(i,k)=f(i,k-1)+f(i-k,k)

边界条件:基线条件防止递归无限循环。

C++源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
using namespace std;
int f(int m,int n){//m个苹果 n个盘子
    if(n> m) //盘子多于苹果
        return f(m,m);
    if(m == 0)//苹果数为0
        return 1;
    if(n == 0)//盘子数为0
        return 0;
    return f(m,n-1)+f(m-n,n);
}
int main(){
    int t,m,n;
    cin>>t;
    while(t--){
        cin>>m>>n;
        cout <<f(m,n)<<endl;
    }
    return 0;
}

 

 

C++截图:

赞(4) 打赏
有问题的朋友随时留言,或者加我为好友。我的QQ是805375353. <<苏木三少博客 » 递归-放苹果

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

十年之约