算法笔记 08_最优合并问题


★问题描述:

    给定 k 个排好序的序列 s1,s2,...,sk,用 2 路合并算法将这 k 个序列合并成一个序列。
    假设所采用的 2 路合并算法合并 2 个长度分别为 m 和 n 的序列需要 m + n - 1 次比较。
    试设计一个算法确定合并这个序列的最优合并顺序,使所需的总比较次数最少。
    为了进行比较,还需要确定合并这个序列的最差合并顺序,使所需的总比较次数最多。

★算法思想

1.给定的所有序列已经排好了顺序,无需再进行排列;
2.所采用的 2 路合并算法合并两个序列所需的比较次数已经给出,直接调用;
3.既然是求最优和最差,那也就是考虑两种极端情况,分析结果如下:
  ① 最差合并顺序:总是最长的两个序列先合并
  ② 最优合并顺序:总是最短的两个序列先合并

★ C++代码如下

//写得很麻烦,希望有改良版私信我。。。。谢谢

#include "stdafx.h"
#include<stdio.h>
#include<iostream>
using namespace std;

//最优合并方法次数
int min(int *a,int n) {
    int number = n, result_min = 0;    
    int *s = new int[n];
    s = a;    
    int i, j, temp;    
    while (number > 1) {    
        for (i = 0; i < number; i ++) {        
            for (j = i + 1; j < number; j ++) {            
                if (s[i] > s[j]) 
                {
                    temp = s[i]; 
                    s[i] = s[j]; 
                    s[j] = temp;
                }
            }
        }
        s[0] = s[0] + s[1];
        result_min += s[0] - 1; // m + n - 1
        number --;        
        for (i = 1; i < number; i ++)
            s[i] = s[i + 1];
    }   
    return result_min;  
}

//最差合并方法次数
int max(int *b,int n) {
    int number = n, result_max = 0;    
    int *s = new int[n];
    s = b;    
    int i, j, temp;    
    while (number > 1) {     
       for (i = 0; i < number; i ++) {         
          for (j = i + 1; j < number; j ++) {             
             if (s[i] < s[j])
                { 
                  temp = s[i]; 
                  s[i] = s[j]; 
                  s[j] = temp; 
                }
            }
        }
        s[0] = s[0] + s[1];
        result_max += s[0] - 1;
        number --;        
        for (i = 1; i < number; i ++)
            s[i] = s[i + 1];
    }    
    return result_max;
}

//主函数
void main() {
    while(1)
    {      
          int q;        
          cout << "Please input the number of sequences: " << endl;  // 请求用户输入序列的个数
        cin >> q;        
        cout << "Please input the size of each sequence: " << endl;        
        int *a = new int[q];  // 动态分配数组大小,存储用户输入的每个序列的大小数值
        for (int i = 0; i < q; i++)
        { cin >> a[i]; }    // 读取用户输入的每个序列的大小数值
        cout << "最优算法次数为: " << min(a,q) << endl;        
        cout << "_____________________________________________________________" << endl;        
        int p;        
        cout << "Please input the number of sequences: " << endl;  // 请求用户输入序列的个数
        cin >> p;        
        cout << "Please input the size of each sequence: " << endl;        
        int *b = new int[p];  // 动态分配数组大小,存储用户输入的每个序列的大小数值
        for (int j = 0; j < p; j++)
        { cin >> b[j]; }    // 读取用户输入的每个序列的大小数值
        cout << "最差算法次数为: " << max(b,p) << endl;        
        cout << "_____________________________________________________________" << endl;
    }    
    delete[] a;    
    delete[] b;
    system("pause");
}

happysneaker.com

Unity那些事儿
请先登录后发表评论
  • 最新评论
  • 总共0条评论