黑马程序员技术交流社区

标题: 这个算法怎么设计？ [打印本页]

---

作者: 孤影卓尔    时间: 2014-2-24 16:03
标题: 这个算法怎么设计？
给定k 个排好序的序列s1 , s2 ,... , sk  , 用 2 路合并算法将这k 个序列合并成一个序列。
假设所采用的 2 路合并算法合并 2 个长度分别为m和n的序列需要m + n -1次比较。试设
计一个算法确定合并这个序列的最优合并顺序，使所需的总比较次数最少。
数据的输入：
由文件input.txt给出输入数据。第一行有1 个正整数k，表示有k个待合并序列。接下
来的1 行中，有k个正整数，表示k个待合并序列的长度。
输入文件示例 输出文件示例
input.txt                                                                         output.txt
4                                                                                   78 52
5 12 11 2

---

作者: 丶小天    时间: 2014-2-24 16:18
是个贪心算法啊。下面的代码能运行，你导入自己运行下：

1. 
   
2. import java.util.PriorityQueue;
   
3. import java.util.Queue;
   
4. 
   
5. class Node implements Comparable<Node> {
   
6. 
   
7.     public int number;
   
8.    
   
9.     public Node(int number) {
   
10.         this.number = number;
    
11.     }
    
12.    
    
13.     @Override
    
14.     public int compareTo(Node other) {
    
15.         // TODO Auto-generated method stub
    
16.         if(this.number > other.number)
    
17.             return 1;
    
18.         else if(this.number < other.number)
    
19.             return -1;
    
20.         
    
21.         return 0;
    
22.     }
    
23. }
    
24. 
    
25. public class Main {
    
26. 
    
27.     public static void main(String[] args) {
    
28.         
    
29.         Queue<Node> queue = new PriorityQueue<Node>();
    
30.         queue.add(new Node(5));
    
31.         queue.add(new Node(12));
    
32.         queue.add(new Node(11));
    
33.         queue.add(new Node(2));
    
34.         
    
35.         while(queue.size() > 1) {
    
36.             Node node1 = queue.remove()();
    
37.             Node node2 = queue.remove()();
    
38.             queue.add(new Node(node1.number + node2.number - 1));
    
39.         }
    
40.         
    
41.         System.out.println(queue.remove()().number);
    
42.     }
    
43. }

复制代码

---

作者: syw02014    时间: 2014-2-24 16:36
这个问题不是很麻烦，我之前做ACM试题遇到过考察哈夫曼树，这类题目都差不多，直接给你C代码吧！思路：
求最小值：每取2个当前数组中的最小，申请2个变保证每次2个变量中的值值是当前的最小值便可,将2个数合并之后必有一个数取消在数组中的位置，可以将该数改成一个较大的数，将此空间和谐掉,最后按照题意m和n的序列需要m+n-1次比较这样便求出了最小值。
求最大值：将数组从大到小排列,依次相加前两位便可.
#include<stdio.h>
#include<stdlib.h>
void main()
{
    int num,min,max,*arrmax,*arrmin,i,j,a,b,k,temp;
    scanf("%d",&num);
    arrmax=(int *)malloc(num * sizeof(int));
    arrmin=(int *)malloc(num * sizeof (int));
    for(i=0;i<num;i++)
    {
        scanf("%d",&arrmax[i]);
        arrmin[i]=arrmax[i];
    }
    for(min=0,i=0;i<num-1;i++
    {
        a=0,b=1;//数组编号
        for(j=2;j<num;j++)
        {
            if(arrmin[j]<arrmin[a]||arrmin[j]<arrmin[b])
            {
                if(arrmin[a]>arrmin[b])
                    a=j;
                else
                    b=j;
            }
        }
        min+=(arrmin[a]+arrmin[b]);
        arrmin[a]+=arrmin[b];
        arrmin[b]=888888888;
    }
    min-=(num--);
    for(i=0;i<num;i++)
    {
        for(k=i,j=i+1;j<num;j++)
        if(arrmax[k]<arrmax[j])
            k=j;
        temp=arrmax[k];
        arrmax[k]=arrmax[i];
        arrmax[i]=temp;
    }

    for(max=0,i=0;i<num-1;i++)
    {
        max+=(arrmax[i]+arrmax[i++]);
        arrmax[i++]+=arrmax[i];
    }
    max-=(num--);
    printf("%d %d\n",max,min);
}

---

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

黑马程序员IT技术论坛 X3.2