分治法设计技术

简介: 设计一个程序,采用分治法求含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");
}


3.运行结果

28.png


29.png



相关文章
|
算法 Java 内存技术
深入理解操作系统的内存管理:原理与实践
【4月更文挑战第8天】本文旨在深入探讨操作系统中内存管理的关键技术和实现细节。我们将从内存管理的基本原理出发,逐步解析操作系统如何通过各种策略和算法实现高效的内存分配、回收和保护。文章还将介绍一些常见的内存管理问题及其解决方案,帮助读者更好地理解和应对实际工作中可能遇到的挑战。
|
存储 数据采集 运维
阿里巴巴DevOps实践指南(二十四)| 智能运维
智能运维( AIOps )是依托于阿里巴巴 DevOps 经验沉淀而来的智能化运维平台,通过运维大数据的积累,以及算法团队多种算法的校对,我们将运维提升到新的高度,通过 AI 来帮我们查看数据、判断异常、决策运维操作,形成监、管、控一体化的运维平台。
阿里巴巴DevOps实践指南(二十四)| 智能运维
|
数据采集 缓存 安全
浅谈WAF产品如何来拦截攻击
浅谈WAF产品如何来拦截攻击
399 0
AC/DC电源模块电源给各种工业设备和系统。
AC/DC电源模块是一种将交流电转换为直流电的设备,广泛应用于工业领域。它具有稳定可靠、高效节能的特点,可以提供稳定的电源给各种工业设备和系统。
AC/DC电源模块电源给各种工业设备和系统。
|
SQL Oracle 关系型数据库
SqlAlchemy 2.0 中文文档(八十一)(2)
SqlAlchemy 2.0 中文文档(八十一)
87 1
|
Java 容器
Java集合类ArrayList应用 | 二维数组的集合类表示与杨辉三角实现
这是一个关于LeetCode第118题“杨辉三角”的问题解答摘要。题目要求生成一个杨辉三角的前n行,其中每一行都是由前一行的元素按规则生成的。杨辉三角的规律是:每一行的第一个和最后一个数是1,其他数是其上方两数之和。
171 4
|
C语言
c运算符
c运算符
95 0
|
Web App开发 存储 安全
手把手带你手撕一个shell
手把手带你手撕一个shell
|
网络架构
计算机网络基础知识总结(三)
传输时延和传播时延的比较
2767 1
计算机网络基础知识总结(三)
|
弹性计算 安全 Linux
阿里云服务器搭建宝塔面板(新手入门)
阿里云服务器搭建宝塔面板(新手入门)阿里云服务器网以CentOS操作系统为例,安装宝塔Linux面板,先远程连接到云服务器,然后执行宝塔面板安装命令,系统会自动安装宝塔面板,安装完成后会返回面板地址、账号和密码,然后在安全组开通宝塔面板端口号
768 0