C++减治法查找范围整数VIP专享

实验二 减治法查找范围整数学院： 计算机科学与技术 专业：计算机科学与技术学号： 班级： 姓名： 一、实验内容：从包含 n 个整数的无序列表中输出第 k1 小到第 k2 小之间的所有整数，其中 k1<=k2。分析时间复杂度。二、算法思想： 减治法的基本思想：规模为 n 的原问题的解与较小规模（通常是 n/2）的子问题的解之间具有关系：（1）原问题的解只存在于其中一个较小规模的子问题中；（2）原问题的解与其中一个较小规模的解之间存在某种对应关系。 由于原问题的解与较小规模的子问题的解之间存在这种关系，所以，只需求解其中一个较小规模的子问题就可以得到原问题的解。一旦建立了这种关系，就可以从顶至下（递归）也可以从底至上（非递归）的来运用。减治法查找范围整数的思想：先把输入的无序列表中的每个整数都标记为 1，用 f1 和 f2 存储每次查找的最大和最小的整数，并标记为 0，作为删除。接着循环递归，直到将范围缩小到 k1->k2.时就得到了所要的结果。三、实验过程：#includeusing namespace std;#define max 100typedef struct Data{int data;bool flag;}Data,Mat[max];Mat a;void Found_k1_k2(Mat &a,int n,int k1,int k2)//用减治法查找无序列表中第 k1 到第 k2 小的整数{int x=0;int y=n-1;while(xk2-1){int temp;int f1,f2;//存储最小和最大数的下标f1=x;f2=y;for(int i=x; i<=y; i++){if(a[f1].data>a[i].data)f1=i;if(a[f2].datak2-1){ temp=a[y].data; a[y].data=a[f2].data; a[f2].data=temp; a[y].flag=0; y--;}}}void Show(Mat &a,int n,int k1,int k2){cout<<"第"<>choice;switch(choice){ case 1:{int n; int k1,k2; cout<<"请输入无序列表 n 的大小:"; cin>>n; cout<<"请输入无序列表中的所有整数:"; for(int i=0; i>a[i].data;} cout<<"请输入 k1，k2 的值:"; cin>>k1>>k2; if(k1>k2){ int temp=k1; k1=k2; k2=temp;} if(k1<0||k2>n||n<0){ cout<<"输入不和法!!请重新输入!!"<