黑马程序员技术交流社区

标题: 算法题目，大家可以挑战一下 [打印本页]
作者: vipzh    时间: 2012-12-5 15:34
标题: 算法题目，大家可以挑战一下
给你一个小于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]}
作者: 马金池    时间: 2012-12-5 17:56
  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]}
不会上传截图
作者: 马金池    时间: 2012-12-5 17:58
标题: 结果截图如下：
file:///C:/1.jpg

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

1.jpg
作者: 马金池    时间: 2012-12-5 18:03
这类问题统称背包问题，即求容量为a的背包，完全装满的方案。  代码中的n应该改成a的。忘记改了，不影响结果。
我们老师带我们参加软件大赛，辅导课时讲了这类问题的解法，分0/1背包和完全背包讲的，所以此类题对我来说毫无压力，呵呵！
解法思路就是：递归，从大到小选数，若选出来的数和正好为a，则输出一种方案。



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2