文档介绍：宁夏师范学院数学与计算机科学学院《算法分析与设计》实验报告实验序号: 5实验项目名称: 线性时间选择问题算法设计学号23姓名专业、班 10 信科实验地点 323 指导教师惠云时间 一、实验目的及要求(1)掌握使用分治策略解决线性时间选择问题的方法; 二、实验设备(环境)及要求 1 、环境要求: 硬件: PC (P II 以上, 128M 以上内存) 、因特网接入; 软件: Windows XP 操作系统、 VC++ 编程环境。三、实验内容与步骤(1) 使用分治策略编写程序,求 n个数据中第 k个最小的数。(2) #include <> int partition(int s[], int low, int high){ if (low >high ) return 0; if(low==high) return low; s[0]=s[low]; while (low < high){ while (low < high && s[high] >s[0]) high--; if (low < high) s[low++] = s[high]; while (low < high && s[low] <s[0]) low++; if (low < high) s[high--] = s[low];} s[low] = s[0]; return low;} //分治找 K-th Number int Select(int s[], int low, int high, int k){ //得到中间数的下标 inti= partition(s, low, high); //j为左区间长度 intj=i- low +1; //位置大就在左区间找,否则就在右区间找 if (j == k) return s[i]; else if (k<j) return Select(s, low, i, k); else return Select(s, i+1, high, k-j);} int main(){ int n;int i; int low, high, k; int a[20]; printf(" 请问有多少个数要输入?\n"); scanf("%d",&n); printf(" 请输入数据:\n"); for (i=1;i <= n; i++) scanf("%d",&a[i]); printf("\n"); printf(" 请输入第几个最小值:\n"); scanf("%d",&k); printf(" 第%d 个最小的数为:%d",k,Select(a, 1,n, k)); (3) 使用分治策略编写程序,求 n个数据中第 k个最大的数。#include <> int partition(int s[], int low, int high){ if (low >high ) return 0; if(low==high) return low; s[0]=s[low]; while (low < high){ while (low < high && s[high] >s[0]) high--; if (low < high) s[low++] = s[high]; while (low < hig