算法设计与分析2023秋-头歌实验-实验五 分治法

第1关：求一组数据中最大的两个数

任务描述

本关任务：利用分治法求一组数据中最大的两个数和最小的两个数。

编程要求

请在右侧编辑器Begin-End处补充代码，完成本关任务。

测试说明

平台会对你编写的代码进行测试，比对你输出的数值与实际正确数值，只有所有数据全部计算正确才能通过测试：
测试输入：

10    //数据的总个数
1     //此行及以下为具体的每个数据
3
5
7
9
10
8
6
4
2

预期输出：

max1=10 max2=9
min1=1 min2=2

参考答案

#include <stdio.h>
void max_min(int a[],int m,int n,int *min1,int *min2,int *max1,int *max2);
void main() {
	int num,i;
	scanf("%d",&num);
	int a[num];
	for (i=0;i<num;i++)
	        scanf("%d",&a[i]);
	/**********  Begin  **********/
	int min1,min2;
	int max1,max2;
	max_min(a,0,num-1,&min1,&min2,&max1,&max2);
	printf("max1=%d max2=%d\n",max1,max2);
	printf("min1=%d min2=%d",min1,min2);
	/**********  End  **********/
}
void max_min(int a[],int m,int n,int *min1,int *min2,int *max1,int *max2) {
	int lmin1,lmin2,lmax1,lmax2;
	int rmin1,rmin2,rmax1,rmax2;
	int mid;
	if(m==n)//分治子数组中只有一个数 {
		*min1=*min2=*max1=*max2=a[m];
	} else//分治子数组中不止一个数
	if(m==n-1)//分治子数组中仅有2个数 {
		if(a[m]<a[n]) {
			*min1=a[m];
			*min2=a[n];
			*max1=a[n];
			*max2=a[m];
		} else {
			*min1=a[n];
			*min2=a[m];
			*max1=a[m];
			*max2=a[n];
		}
	} else//分治子数组中有超过2个数 {
		mid=(m+n)/2;
		max_min(a,m,mid,&lmin1,&lmin2,&lmax1,&lmax2);
		max_min(a,mid+1,n,&rmin1,&rmin2,&rmax1,&rmax2);
		//**************************************************
		//确定出数组中最小的两个数
		//**************************************************
		if(lmin1<rmin1)//左子数组最小数<右子数组最小数 {
			if(lmin2<rmin1) {
				*min1=lmin1;
				*min2=lmin2;
			} else {
				*min1=lmin1;
				*min2=rmin1;
			}
		} else//右子数组最小数<左子数组最小数
		if(rmin2<lmin1) {
			*min1=rmin1;
			*min2=rmin2;
		} else {
			*min1=rmin1;
			*min2=lmin1;
		}
		//**************************************************
		//确定出数组中最大的两个数
		//**************************************************
		if(lmax1>rmax1)//左子数组最大数>右子数组最大数 {
			if(lmax2>rmax1) {
				*max1=lmax1;
				*max2=lmax2;
			} else {
				*max1=lmax1;
				*max2=rmax1;
			}
		} else//右子数组最大数>左子数组最大数
		if(rmax2>lmax1) {
			*max1=rmax1;
			*max2=rmax2;
		} else {
			*max1=rmax1;
			*max2=lmax1;
		}
	}
}

第2关：求一组数据的和

任务描述

本关任务：利用分治法求一组数据的和。

编程要求

请在右侧编辑器Begin-End处补充代码，完成本关任务，注意需要学生自己获取输入数据再进行操作。

测试说明

平台会对你编写的代码进行测试，比对你输出的数值与实际正确数值，只有所有数据全部计算正确才能通过测试：
测试输入：

10    //数据的总个数
-5    //此行及以下为具体的每个数据
5
10
99
100
30
60
98
-10
-1

预期输出：分治法求出数组元素的和为:386

参考答案

#include "stdio.h"
/**********  Begin  **********/
#include<stdlib.h> 
int add(int *a,int left,int right);
int main() {
	int i,num;
	scanf("%d", &num);
	int array[num];
	for (i = 0; i < num; i++) {
		scanf("%d", &array[i]);
	}
	int sum=add(array,0,num-1);
	printf("分治法求出数组元素的和为:%d",sum);
	return 0;
}
int add(int a[],int left,int right) {
	int mid;
	if(left==right) {
		return a[left];
	} else if (left == right-1) {
		return a[left]+a[right];
	} else {
		mid=(left+right)/2;
		return add(a,left,mid)+add(a,mid+1,right);
	}
}
/**********  End  **********/

第3关：找出数组中第 k 个小的元素

任务描述

本关任务：对于给定的 n 个元素的数组a[0:n-1]，要求从中找出第 k 小的元素。

编程要求

请在右侧编辑器Begin-End处补充代码，完成本关任务，注意需要学生自己获取输入数据再进行操作。

测试说明

平台会对你编写的代码进行测试，比对你输出的数值与实际正确数值，只有所有数据全部计算正确才能通过测试：
测试输入：

10 5    //表示给定10（n）个元素的数组，从中找出第5（k）小的元素
-34     //此行及以下为具体的每个数据
95
-50
67
73
81
-38
10
-11
70

预期输出：第5小的元素是10

参考答案

#include <stdio.h>
/**********  Begin  **********/
int Solve(int a[], int s, int t,int k) {
	//划分算法
	int i = s, j = t;
	int temp = a[s];
	if (s < t) {
		while (i != j) {
			while (j > i&&a[j] >= temp)
			                j--;
			a[i] = a[j];
			while (i < j&&a[i] <= temp)
			                i++;
			a[j] = a[i];
		}
		a[i] = temp;
		//求解
		if (k - 1 == i)
		            return a[i]; else if (k - 1 < i) {
			return Solve(a, s, i - 1, k);
		} else return Solve(a, i + 1, t, k);
	} else if (s == t && s == k - 1)
	        return a[k - 1];
}
int main() {
	int n,i,k;
	scanf("%d%d",&n,&k);
	int a[n];
	for (i = 0; i <= n; i++)
	        scanf("%d",&a[i]);
	printf("第%d小的元素是%d",k,Solve(a,0,n,k));
	return 0;
}
/**********  End  **********/