C++减治法查找范围整数.doc

《C++减治法查找范围整数.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验二减治法查找范围整数学院：计算机科学与技术专业：计算机科学与技术学号：班级：姓名：一、实验内容：从包含n个整数的无序列表中输出第k1小到第k2小之间的所有整数，其中k1<=k2。分析时间复杂度。二、算法思想：减治法的基本思想：规模为n的原问题的解与较小规模（通常是n/2）的子问题的解之间具有关系：（1）原问题的解只存在于其中一个较小规模的子问题中；（2）原问题的解与其中一个较小规模的解之间存在某种对应关系。由于原问题的解与较小规模的子问题的解之间存在这种关系，所以，只需求解其中一个较小规模的子问题就可以得到原问题的解。一旦建立了这种关系，就可以

2、从顶至下（递归），也可以从底至上（非递归）的来运用。减治法查找范围整数的思想：先把输入的无序列表中的每个整数都标记为1，用f1和f2存储每次查找的最大和最小的整数，并标记为0，作为删除。接着循环递归，直到将范围缩小到k1->k2.时就得到了所要的结果。三、实验过程：#includeusingnamespacestd;#definemax100typedefstructData{intdata;boolflag;}Data,Mat[max];Mata;voidFound_k1_k2(Mat&a,intn,intk1,intk2)/

3、/用减治法查找无序列表中第k1到第k2小的整数{intx=0;inty=n-1;while(x

4、

5、y>k2-1){inttemp;intf1,f2;//存储最小和最大数的下标f1=x;f2=y;for(inti=x;i<=y;i++){if(a[f1].data>a[i].data)f1=i;if(a[f2].datak2-1){temp

6、=a[y].data;a[y].data=a[f2].data;a[f2].data=temp;a[y].flag=0;y--;}}}voidShow(Mat&a,intn,intk1,intk2){cout<<"第"<

7、>>choice;switch(choice){case1:{intn;intk1,k2;cout<<"请输入无序列表n的大小:";cin>>n;cout<<"请输入无序列表中的所有整数:";for(inti=0;i>a[i].data;}cout<<"请输入k1，k2的值:";cin>>k1>>k2;if(k1>k2){inttemp=k1;k1=k2;k2=temp;}if(k1<0

8、

9、k2>n

10、

11、n<0){cout<<"输入不和法!!请重新输入!!"<

12、k2(a,n,k1,k2);Show(a,n,k1,k2);break;}case2:{cout<<"退出程序！";break;}default:cout<<"选择不合理，请重选！"<