第四章算法实践

时间:2024-01-22 08:23:23

第四章算法实践

1.实践题目

 

7-1 最优合并问题 (100 分)

题目来源:王晓东《算法设计与分析》

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

输入样例:

4

5 12 11 2

输出样例:

78 52

2.问题描述

将几个序列合并成一个序列,序列的比较次数的计算方式是序列长度分别为m和n的序列为m+n-1 次。计算最多比较次数时,从待选序列中选取最长的两个序列合并成新的序列,继续比较合并直至合并成最终序列,同理于最少比较次数的方法,只是合并最短序列。

代码如下:

#include<iostream>

using namespace std;

 

int getmax(int a[],int n){

    int number=n,result=0,s[n];

    int i,j,temp;

    for(i=0;i<n;i++){

        s[i]=a[i];

    }

    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+=s[0]-1;

        number--;

        for(i=1;i<number;i++)

            s[i]=s[i+1];

    }

    return result;

}

 

int getmin(int a[],int n){

    int number = n,result=0,s[n];

    int i,j,temp;

 

    for(i=0; i<n; i++){

        s[i]=a[i];

    }

    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+=s[0]-1;

        number--;

        for(i=1;i<number;i++)

            s[i]=s[i+1];

    }

    return result;

}

 

int main()

{

    int n;

    cin >> n;

    int *a = new int[n];

    for(int i=0;i<n;i++)

    {

             cin >> a[i];

    }

         cout << getmax(a,n) << " " <<getmin(a,n);

    return 0;

}

3.

时间复杂度:O(nlongn)

空间复杂度:O(n) 

4.心得:感觉这道,题跟之前几道实践题类似,在最开始写算法时,编写了冒泡算法,虽然可以计算正确,算法的操作时间和代码数都不少,较为冗余。自己编写的算法缺点很明显,在编写算法代码这方面较为薄弱,下次还要继续改进

 

posted on 2018-12-02 19:54 宏嚯嚯桦 阅读(...) 评论(...) 编辑 收藏