黑马程序员技术交流社区
标题:
算法题目,大家可以挑战一下
[打印本页]
作者:
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
import java.util.Scanner;
public class bp
{
static int n;
static int count=0;//count为统计集合元素的个数
static int []d=new int[25];//存放集合中的每个元素
static void divide(int number,int idx)
{
if(number==0)
{
if(count==0)
{
System.out.print(n+"->");
System.out.print("{");
}
for(int i=0;i<idx;i++)
{
if(i==0&&(n/2>1))
System.out.print("[");
if(i>0)
System.out.print(",");
System.out.print(d[i]);
}
if(n/2>1) System.out.print("]");
if(idx<n/2)
System.out.print(",");
else
System.out.println("}");
count++;//元素个数自增
return;
}
for(int i=number;i>=2;i--)//从大到小开始选数
{
if(idx==0||i<=d[idx-1])//用来保证右边的数不大于左边的
{
d[idx]=i;
divide(number-i,idx+1);//递归
}
}
}
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
while(sc.hasNextInt())
{
count=0;
n=sc.nextInt();
divide(n,0);//递归
}
}
}
复制代码
运行结果如下: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, 下载次数: 19)
下载附件
2012-12-5 17:58 上传
作者:
马金池
时间:
2012-12-5 18:03
这类问题统称背包问题,即求容量为a的背包,完全装满的方案。 代码中的n应该改成a的。忘记改了,不影响结果。
我们老师带我们参加软件大赛,辅导课时讲了这类问题的解法,分0/1背包和完全背包讲的,所以此类题对我来说毫无压力,呵呵!
解法思路就是:递归,从大到小选数,若选出来的数和正好为a,则输出一种方案。
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2