C++減治法查找范圍整數(shù)(共7頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上實(shí)驗(yàn)二 減治法查找范圍整數(shù)學(xué)院： 計(jì)算機(jī)科學(xué)與技術(shù) 專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)號(hào)： 班級(jí)： 姓名： 一、實(shí)驗(yàn)內(nèi)容：從包含n個(gè)整數(shù)的無(wú)序列表中輸出第k1小到第k2小之間的所有整數(shù)，其中k1<=k2。分析時(shí)間復(fù)雜度。二、算法思想： 減治法的基本思想：規(guī)模為n的原問(wèn)題的解與較小規(guī)模（通常是n/2）的子問(wèn)題的解之間具有關(guān)系：（1） 原問(wèn)題的解只存在于其中一個(gè)較小規(guī)模的子問(wèn)題中；（2） 原問(wèn)題的解與其中一個(gè)較小規(guī)模的解之間存在某種對(duì)應(yīng)關(guān)系。 由于原問(wèn)題的解與較小規(guī)模的子問(wèn)題的解之間存在這種關(guān)系，所以，只需求解其中一個(gè)較小規(guī)模的子問(wèn)題就可以得到原問(wèn)題的解。一旦建立了這種關(guān)系，

2、就可以從頂至下（遞歸），也可以從底至上（非遞歸）的來(lái)運(yùn)用。減治法查找范圍整數(shù)的思想：先把輸入的無(wú)序列表中的每個(gè)整數(shù)都標(biāo)記為1，用f1和f2存儲(chǔ)每次查找的最大和最小的整數(shù)，并標(biāo)記為0，作為刪除。接著循環(huán)遞歸，直到將范圍縮小到k1->k2.時(shí)就得到了所要的結(jié)果。三、實(shí)驗(yàn)過(guò)程：#include<iostream>using namespace std;#define max 100typedef struct Dataint data;bool flag;Data,Matmax;Mat a;void Found_k1_k2(Mat &a,int n,int k1,int k

3、2)/用減治法查找無(wú)序列表中第k1到第k2小的整數(shù)int x=0;int y=n-1;while(x<k1-1|y>k2-1)int temp;int f1,f2;/存儲(chǔ)最小和最大數(shù)的下標(biāo)f1=x;f2=y;for(int i=x; i<=y; i+)if(af1.data>ai.data)f1=i;if(af2.data<ai.data)f2=i;if(x<k1-1) temp=ax.data; ax.data=af1.data; af1.data=temp; ax.flag=0; x+;if(y>k2-1) temp=ay.data; ay.dat

4、a=af2.data; af2.data=temp; ay.flag=0; y-;void Show(Mat &a,int n,int k1,int k2)cout<<"第"<<k1<<"小到"<<k2<<"小之間的所有整數(shù)有:"for(int i=0; i<n; i+)if(ai.flag)cout<<ai.data<<" "cout<<endl;void main()int choice;cout<

5、;<" 1: 執(zhí)行程序！ 2: 退出程序！"<<endl;docout<<"請(qǐng)選擇你的操作:"cin>>choice;switch(choice) case 1:int n; int k1,k2; cout<<"請(qǐng)輸入無(wú)序列表n的大小:" cin>>n; cout<<"請(qǐng)輸入無(wú)序列表中的所有整數(shù):" for(int i=0; i<n; i+) ai.flag=1; cin>>ai.data; cout<<&q

6、uot;請(qǐng)輸入k1，k2的值:" cin>>k1>>k2; if(k1>k2) int temp=k1; k1=k2; k2=temp; if(k1<0|k2>n|n<0) cout<<"輸入不和法!請(qǐng)重新輸入!"<<endl;break; Found_k1_k2(a,n,k1,k2); Show(a,n,k1,k2); break; case 2: cout<<"退出程序！" break; default:cout<<"選擇不合理，請(qǐng)重選！"<<endl;while(choice!=2); 四、實(shí)驗(yàn)結(jié)果：該算法的時(shí)間復(fù)雜度取決于n的大小和輸入的K1、K2