【算法】整数集合分解

  1.问题描述

S为一个n个正整数的集合,n为偶数。请设计一个有效算法将S分成两个子集S1S2,使每个子集中含有n/2个元素,而且S1中所有元素的和与S2中所有元素的和的差最大。这个算法的时间复杂性是什么?

 2. 具体要求

输入的第一行是一个正整数m,表示测试例个数。接下来几行是m个测试例的数据,每个测试例的数据由两行组成,其中第一行为一个正整数n (n<=500),表示原整数集合的长度,第二行给出这n个整数序列,整数之间用一个空格隔开。

输出:对于每个测试例输出两行,分别表示新生成的整数集合。其中,第一行是元素和比较小的整数集合,第二行是元素和比较大的整数集合,整数之间用一个空格隔开。两个测试例的输出数据之间用一个空行隔开。

限于平台,输出的两个新整数集合中的数要求按照从小到大排序后输出。这对算法时间复杂性有一定影响。

3. 测试数据

输入:

2

22

68 25 34 16 2 37 3 95 76 57 21 13 4 78 29 6 17 39 51 20 43 12

26

28 3 48 59 14 32 47 51 42 61 9 24 52 78 65 2 37 78 51 73 29 7 26 95 37 2

输出:

    2 3 4 6 12 13 16 17 20 21 25

    29 34 37 39 43 51 57 68 76 78 95

   

    2 2 3 7 9 14 24 26 28 29 32 37 37

    42 47 48 51 51 52 59 61 62 65 73 78 95

4. 设计与实现的提示

本题可以有多种方法算法时间复杂性是选取算法的重要依据。限于平台,输出的两个新整数集合要求按照从小到大排序后输出。这对算法时间复杂性可能有所影响。

5、程序实现(java)
 1import java.io.*;
 2public class Intrl2
 3{
 4    public static void main(String[] args) throws Exception
 5    {
 6        Intrl2 yeyunce=new Intrl2();
 7        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
 8        System.out.println("请输入测试例个数:");
 9        String str=br.readLine();
10        int m=Integer.parseInt(str);
11        yeyunce.Test(m);
12    }

13    
14    public static int SPLIT(int[] A,int low,int high)
15    {
16        int w;
17        int i=low;
18        int x=A[low];
19        for(int j=low+1;j<=high;j++)
20        {
21            if(A[j]<=x)
22            {
23                i=i+1;
24                
25                if(i!=j)
26                {
27                    int a;
28                    a=A[i];
29                    A[i]=A[j];
30                    A[j]=a;
31                }

32            }

33        }

34        int a2;
35        a2=A[low];
36        A[low]=A[i];
37        A[i]=a2;
38        w=i;
39        return w;
40    }

41    
42    public static void quicksort(int[] A,int low,int high)
43    {
44         int w;
45        if(low<high)
46        {  
47            w=SPLIT(A,low,high);
48            quicksort(A,low,w-1);
49            quicksort(A,w+1,high);
50        }

51    }

52
53    public void Test(int m)
54    {
55        String[][] ss=new String[m][2];
56        for(int i=0;i<m;i++)
57        {
58            try
59            {
60                BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
61                System.out.println("总测试例个数为"+m+",现请输入第"+(i+1)+"个用例数组的元素个数,并在下一行列出:");
62                String str=br.readLine();
63                int d=Integer.parseInt(str);
64                String str2=br.readLine();
65                String[] str3=str2.split(" ");
66                int[] ii=new int[d];
67                for(int j=0;j<d;j++)
68                {
69                    ii[j]=Integer.parseInt(str3[j]);
70                }

71                quicksort(ii,0,d-1);
72                String sf1="";
73                String sf2="";
74                for(int f1=0;f1<d/2;f1++)
75                {
76                    sf1+=ii[f1]+" ";
77                }

78                for(int f2=d/2;f2<d;f2++)
79                {
80                    sf2+=ii[f2]+" ";
81                }

82                ss[i][0]=sf1;
83                ss[i][1]=sf2;
84            }

85            catch(IOException e)
86            {
87                System.out.println(e);
88            }

89        }

90        for(int i=0;i<m;i++)
91        {
92            System.out.println();
93            for(int j=0;j<2;j++)
94            {
95                System.out.println(ss[i][j]);
96            }

97        }

98    }

99}

6、运行结果
运行结果

posted on 2009-04-11 18:42 intrl 阅读(964) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法

只有注册用户登录后才能发表评论。
<2009年4月>
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

导航

统计

随笔分类(55)

随笔档案(34)

网址收藏

资源下载

随笔导航

搜索

最新评论

阅读排行榜

评论排行榜