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;

3、voidFound_k1_k2(Mat&a,intn,intk1,intk2)//用减治法查找无序列表中第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].data

6、=a[f1].data;a[f1].data=temp;a[x].flag=0;x++;}if(y>k2-1){temp=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;i

8、f(k1>k2){inttemp=k1;k1=k2;k2=temp;}if(k1<0

9、

10、k2>n

11、

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

13、况是K1、K2恰好在输入的无序列表的两端，此时不做运算，直接输出，时间复杂度为O(0)。最坏情况是K1=K2=n/2时，此时做n/2次运算，时间复杂度为O(n/2)。