采用分治法求含n个实数序列中的最大元素和次大元素（C语言）

本文主要是介绍采用分治法求含n个实数序列中的最大元素和次大元素（C语言），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

实验内容：

实验过程：

1.算法设计

2.程序清单

3.复杂度分析

4.运行结果

---

实验内容：

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

实验过程：

1.算法设计

该程序采用递归分治策略,以下是算法设计思路的详细描述：

核心函数solve()：

• 基本情况：当数组只有一个元素（low == high）时，直接将该元素赋值给max1，将一个较小常数（如-1000）赋值给max2作为初始次大值。若只有两个元素（low == high - 1），则直接比较并返回两元素的最大值和最小值作为最大值和次大值。
• 递归分割：对于包含三个或更多元素的数组，计算中间下标mid，将数组分为左右两个子区间：a[low..mid]和a[mid+1..high]。
• 递归调用：对左右子区间分别调用solve()函数，分别得到左右区间的最大值lmax1和rmax1以及次大值lmax2和rmax2。
• 合并结果：比较左右子区间的最大值lmax1和rmax1，将较大者赋值给全局最大值max1。接着，从剩余元素（包括左右区间的次大值及未被选为最大值的另一区间最大值）中找出最大值，将其赋值给全局次大值max2。

辅助函数：

1. max(int m, int n)：比较两个整数，返回较大的值。
2. min(int m, int n)：比较两个整数，返回较小的值。

主函数main()：

1. 获取用户输入：首先提示用户输入整数数组的元素个数n，然后根据n读取相应的整数元素，依次存入数组a中。
2. 调用solve()函数：传入数组a、起始下标low（设为0）、结束下标high（设为n-1）以及两个引用变量max1和max2用于接收最大值和次大值。
3. 输出结果：在solve()函数执行完毕后，输出最大值max1和次大值max2。

 2.程序清单

#include<stdio.h>
#include <climits>
int max(int m, int n) {return (m > n) ? m : n;
}int min(int m, int n) {return (m < n) ? m : n;
}
void solve(int a[],int low,int high,int &max1,int &max2){if(low==high){max1=a[low];max2=-1000;}else if(low==high-1){max1=max(a[low],a[high]);max2=min(a[low],a[high]);}else{int mid=(low+high)/2;int lmax1,lmax2;solve(a,low,mid,lmax1,lmax2);//左区间求lmax1,lmax2int rmax1,rmax2;solve(a,mid+1,high,rmax1,rmax2);//右区间求rmax1,rmax2if(lmax1>rmax1){max1=lmax1;max2=max(lmax2,rmax1);}else{max1=rmax1;max2=max(lmax1,rmax2);}}
}int main(){int n;printf("请输入元素的个数：");scanf("%d",&n);int a[100];printf("请输入元素：\n");for(int i=0;i<n;i++){scanf("%d",&a[i]);}int max1,max2;solve(a,0,n-1,max1,max2);printf("最大元素为：%d\n",max1);printf("次大元素为：%d\n",max2);return 0;
}

3.复杂度分析

(1)时间复杂度

时间复杂度主要是调用solve函数

(2)空间复杂度

实验查找最大值和次大值是在一个一维数组的存储并得出出结果，故采用分治法求含n个实数序列中的最大元素和次大元素的算法空间复杂度为O(n)。

4.运行结果

这篇关于采用分治法求含n个实数序列中的最大元素和次大元素（C语言）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---