A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© vipzh 中级黑马   /  2012-12-5 15:34  /  1562 人查看  /  3 人回复  /   1 人收藏 转载请遵从CC协议 禁止商业使用本文

给你一个小于50的数字 a ,请写出一个算法得到所有可能的数字集合,每个数字集合满足以下条件:
1. 集合中所有数字的和等于a;
2. 集合中的所有数字均大于1;
3. 集合中可以出现重复数字;
例如:
2 -> {2},
3->{3},
4->{[4], [2, 2]},
5->{[5], [3, 2]},
6->{[6], [4, 2], [3, 3], [2, 2, 2]}
7->{[7], [5, 2], [4, 3], [3, 2, 2]}
8->{[8], [6, 2], [5, 3], [4, 4], [4, 2, 2], [3, 3, 2], [2, 2, 2, 2]}

评分

参与人数 1技术分 +1 收起 理由
古银平 + 1 神马都是浮云

查看全部评分

3 个回复

倒序浏览
  1. import java.util.Scanner;
  2. public class bp
  3. {
  4.         static int n;
  5.         static int count=0;//count为统计集合元素的个数
  6.         static int []d=new int[25];//存放集合中的每个元素
  7.         static void divide(int number,int idx)
  8.         {
  9.                 if(number==0)
  10.                 {               
  11.                         if(count==0)
  12.                         {
  13.                                 System.out.print(n+"->");
  14.                                 System.out.print("{");
  15.                         }
  16.                         for(int i=0;i<idx;i++)
  17.                         {
  18.                                 if(i==0&&(n/2>1))
  19.                                         System.out.print("[");
  20.                                 if(i>0)
  21.                                         System.out.print(",");
  22.                                 System.out.print(d[i]);
  23.                         }
  24.                         if(n/2>1) System.out.print("]");
  25.                         if(idx<n/2)
  26.                                 System.out.print(",");
  27.                         else
  28.                                 System.out.println("}");
  29.                         count++;//元素个数自增
  30.                         return;
  31.                 }
  32.                 for(int i=number;i>=2;i--)//从大到小开始选数
  33.                 {
  34.                         if(idx==0||i<=d[idx-1])//用来保证右边的数不大于左边的
  35.                         {
  36.                                 d[idx]=i;
  37.                                 divide(number-i,idx+1);//递归
  38.                         }
  39.                 }
  40.         }
  41.         public static void main(String[] args)
  42.         {
  43.                 Scanner sc=new Scanner(System.in);
  44.                 while(sc.hasNextInt())
  45.                 {
  46.                         count=0;
  47.                         n=sc.nextInt();
  48.                         divide(n,0);//递归
  49.                 }       
  50.         }
  51. }
复制代码
运行结果如下:2
2->{2}
3
3->{3}
4
4->{[4],[2,2]}
5
5->{[5],[3,2]}
6
6->{[6],[4,2],[3,3],[2,2,2]}
7
7->{[7],[5,2],[4,3],[3,2,2]}
8
8->{[8],[6,2],[5,3],[4,4],[4,2,2],[3,3,2],[2,2,2,2]}
不会上传截图

评分

参与人数 1技术分 +1 收起 理由
冯海霞 + 1

查看全部评分

回复 使用道具 举报

结果截图如下:

file:///C:/1.jpg

1.jpg (47.94 KB, 下载次数: 19)

1.jpg
回复 使用道具 举报
这类问题统称背包问题,即求容量为a的背包,完全装满的方案。  代码中的n应该改成a的。忘记改了,不影响结果。
我们老师带我们参加软件大赛,辅导课时讲了这类问题的解法,分0/1背包和完全背包讲的,所以此类题对我来说毫无压力,呵呵!
解法思路就是:递归,从大到小选数,若选出来的数和正好为a,则输出一种方案。
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马