分治法设计技术

2023-04-24 146

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 设计一个程序，采用分治法求含n个实数序列中的最大元素和次大元素，并分析算法的时间复杂度1.算法设计2.程序清单3.运行结果

设计一个程序，采用分治法求含n个实数序列中的最大元素和次大元素，并分析算法的时间复杂度

1.算法设计

情况1：区间中只有一个值

最大值为该值

maxFirst = a[low];

次大值为无穷小

maxSecond = INT_MIN;

情况2：区间中只有两个值

最大值为两数中的较大数

maxFirst = max(a[low], a[high]);

次大值为另一个数

maxSecond=min(a[low], a[high]);

情况3：区间中有多个值

1计算区间中位数 mid

int mid = (low + high) / 2;

2递归求取左区间（[low, mid]）最大值及次打值

solve(a, low, mid, leftMaxFirst, leftMaxSecond);

3递归求取右区间（[mid + 1, high]）最大值及次大值

solve(a, mid + 1,high, rightMaxFirst, rightMaxSecond);

情况：4判断四个数中的最大值及次大值

左区间最大值 > 右区间最大值

最大值：必为左区间最大值

maxFirst = leftMaxFirst;

次大值：max(左区间次大值, 右区间最大值)

maxSecond = max(leftMaxSecond, rightMaxFirst);

左区间最大值 < 右区间最大值

最大值: 必为右区间最大值

maxFirst = rightMaxFirst;

次大值: max(右区间次大值, 左区间最大值)

maxSecond = max(leftMaxFirst, rightMaxSecond);

2.程序清单

在这里插入代码片//
// Created by xpc on 2023/3/18.
//
#include <iostream>
#include <limits.h>
#include <algorithm>
using namespace std;
/**
 * 查找最大和次大元素，分为3种情况
 * @param a
 * @param low
 * @param high
 * @param maxFirst
 * @param maxSecond
 */
void solve(int a[],int low,int high,int &maxFirst,int &maxSecond) {
    //1.区间中只有一个元素
    if (low==high) {
        maxFirst = a[low];
        //表示无穷小
        maxSecond = INT_MIN;
    }
        //2.区间中只有两个元素
    else if (low==high-1) {
        maxFirst = max(a[low], a[high]);
        maxSecond=min(a[low], a[high]);
    }
        //3.区间有两个以上元素
    else {
        int mid = (low + high) / 2;
        //左区间中求leftMaxFirst和leftMaxSecond
        int leftMaxFirst, leftMaxSecond;
        solve(a, low, mid, leftMaxFirst, leftMaxSecond);
        //右区间中求rightMaxFirst和rightMaxSecond
        int rightMaxFirst, rightMaxSecond;
        solve(a, mid + 1,high, rightMaxFirst, rightMaxSecond);
        if (leftMaxFirst> rightMaxFirst) {
            //leftMaxSecond、rightMaxFirst中求次大元素
            maxFirst = leftMaxFirst;
            maxSecond = max(leftMaxSecond, rightMaxFirst);
        }
        else {
            //leftMaxFirst、rightMaxSecond中求次大元素
            maxFirst = rightMaxFirst;
            maxSecond = max(leftMaxFirst, rightMaxSecond);
        }
    }
}
int main() {
    int n = 0;
    cout << "请输入元素个数" << endl;
    cin >> n;
    int *a = new int[n];
    cout << "请输入元素：" << endl;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int maxFirst, maxSecond;
    solve(a,0,n-1, maxFirst, maxSecond);
    cout << "最大值为：" << maxFirst<< " " << "次大值为:" << maxSecond << endl;
    system("exit");
}