首页 > 移动平台 > 详细

[华为oj]放苹果

时间:2015-09-03 13:59:09      阅读:554      评论:0      收藏:0      [点我收藏+]

标签:算法   class   style   log   si   la   sp   方法   for   

题目描述

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

 

输入

每个用例包含二个整数M和N。0<=m<=10,1<=n<=10。<=n<=10<=m<=10

 

样例输入

7 3

 

样例输出

8

    

/**

     * 计算放苹果方法数目


     * 输入值非法时返回-1

     * 1 <= m,n <= 10<><= m,n <= 10<>

     * @param m 苹果数目

     * @param n 盘子数目数

     * @return 放置方法总数

     * 

     */

    public static int count(int m, int n)

思路:

1.利用递归思想,假设已经得到后面一个盆子的摆放组合次数;

2.因为题目要的是组合,因此要把同样重复的组合去掉,有一种办法就是把盘子从左往右排一列,苹果的数量依次为降序,即可避免出现重复的情况,因此要有个判断。

3.结束条件要判断当前是否满足降序,满足即知道该组合成立,返回1;否则返回0.

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int count(int m,int n,int b)
 5 {
 6     //结束条件
 7     if(n==1)
 8     {
 9         if(m<=b)
10             return 1;
11         else
12             return 0;
13     }
14 
15     //递归
16     int num=0;
17     for(int i=m;i>=0;i--)
18     {
19         if(i<=b)
20             num=num+count(m-i,n-1,i);
21     }
22     return num;
23 }
24 
25 int main()
26 {
27     int m,n;
28     cin>>m>>n;
29     int num=count(m,n,m);
30     cout<<num<<endl;
31 }

 

在写该算法过程中,我开始的思路是先算出所有的排列次数,然后除掉重复的。但后来发现自己没找到如何去除重复的排列的方法。因为有些排列重复的次数和其它排列重复的次数不一样。下面是错误的算法。

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 int count(int m,int n)
 6 {
 7     if(n==1)
 8     {
 9         return 1;
10     }
11 
12     int num=0;
13     for(int i=m;i>=0;i--)
14     {
15         num=num+count(m-i,n-1);
16     }
17     return num;
18 }
19 
20 int mul(int n)
21 {
22 int result=1;
23 for(int i=n;i>=1;i--)
24 {
25     result=result*i;
26 }
27 return result;
28 }
29 
30 int main()
31 {
32     int m,n;
33     cin>>m>>n;
34     int num=count(m,n);
35     num=num/mul(n);
36      cout<<num;
37 }

 

[华为oj]放苹果

标签:算法   class   style   log   si   la   sp   方法   for   

原文:http://www.cnblogs.com/lsr-flying/p/4780103.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号