算法設(shè)計(jì)與分析-第03周-分治策略2課件_第1頁
算法設(shè)計(jì)與分析-第03周-分治策略2課件_第2頁
算法設(shè)計(jì)與分析-第03周-分治策略2課件_第3頁
算法設(shè)計(jì)與分析-第03周-分治策略2課件_第4頁
算法設(shè)計(jì)與分析-第03周-分治策略2課件_第5頁
已閱讀5頁,還剩87頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

第2章分治策略(2)教學(xué)目的與要求1.掌握設(shè)計(jì)有效算法的分治策略。2.要求通過范例的學(xué)習(xí)掌握分治策略的技巧。第2章分治策略(2)教學(xué)目的與要求2.9線性時間選擇給定線性序集中n個元素和一個整數(shù)k,1≤k≤n,要求找出這n個元素中第k小的元素。采用分治策略,利用在快速排序中使用到的RandomizedPartition算法,將序列隨機(jī)分成兩部分a[p…i]和a[i+1…r],使得a[p…i]的每個元素都不大于a[i+1…r]的每個元素,而此時a[i]恰好為第i小元素,接著計(jì)算子數(shù)組a[p…i]的元素個數(shù)j,如果k≤j,則a[p…r]中第k小的數(shù)落在子數(shù)組a[p…i]中,如果k>j,則a[p…r]中第k小的數(shù)落在子數(shù)組a[i+1…r]中,此時要找的a[p…r]中第k小的元素是a[i+1…r]中第k-j小的元素。2.9線性時間選擇給定線性序集中n個元素和一個整數(shù)k,1≤template<classType>intPartition(Typea[],intp,intr){inti=p,j=r+1;Typex=a[p],t;//將<x的元素交換到左邊區(qū)域,將>x的元素交換到右邊區(qū)域

while(true){while(a[++i]<x);//從左到右找到第一個不小于a[p]的元素a[i]while(a[--j]>x);//從右到左找到第一個不大于a[p]的元素a[j]if(i>=j)break;t=a[i];a[i]=a[j];a[j]=t;//交換a[i]和a[j]}a[p]=a[j];a[j]=x;//交換a[p]和a[j]returnj;}template<classType>template<classType>intRandomizedPartition(Typea[],intp,intr){inti=Random(p,r);Typet;t=a[i];a[i]=a[p];a[p]=t;returnPartition(a,p,r);}template<classType>template<classType>TypeRandomizedSelect(Typea[],intp,intr,intk){inti,j;if(p==r)returna[p];i=RandomizedPartition(a,p,r);j=i-p+1;//計(jì)算子數(shù)組a[p…i]的元素個數(shù)jif(k<=j)returnRandomizedSelect(a,p,i,k);elsereturnRandomizedSelect(a,i+1,r,k-j);}template<classType>在最壞情況下(如在找最小元素時,總在最大元素處劃分),算法RandomizedSelect需要(n2)計(jì)算時間,但該算法的平均性能較好。如果能在線性時間內(nèi)找到一個劃分基準(zhǔn),使得按這個基準(zhǔn)所劃分出的2個子數(shù)組的長度都至少為原數(shù)組長度的ε倍(0<ε<1是某個正常數(shù)),那么就可以在最壞情況下用O(n)時間完成選擇任務(wù)。例如,若ε=9/10,算法遞歸調(diào)用所產(chǎn)生的子數(shù)組的長度至少縮短1/10。所以,在最壞情況下,算法所需的計(jì)算時間T(n)滿足遞歸式T(n)≤T(9n/10)+O(n)。由此可得T(n)=O(n)。在最壞情況下(如在找最小元素時,總在最大元素處劃分),算法R例如,將n個輸入元素劃分成n/5個組,每組5個元素,只可能有一個組不是5個元素。用任意一種排序算法,將每組中的元素排好序,并取出每組的中位數(shù),共n/5個。遞歸調(diào)用Select來找出這n/5個元素的中位數(shù)(也就是這些中位數(shù)的中位數(shù)),若n/5是偶數(shù),則找它的兩個中位數(shù)中較大的一個,然后以這個元素作為基準(zhǔn)劃分。例如,將n個輸入元素劃分成n/5個組,每組5個元素,只可設(shè)所有元素互不相同。在這種情況下,找出的基準(zhǔn)x至少比3(n-5)/10個元素大,因?yàn)樵诿恳唤M中有2個元素小于本組的中位數(shù),而n/5個中位數(shù)中又有(n-5)/10個小于基準(zhǔn)x。同理,基準(zhǔn)x也至少比3(n-5)/10個元素小。而當(dāng)n≥75時,3(n-5)/10≥n/4所以按此基準(zhǔn)劃分所得的2個子數(shù)組的長度都至少縮短1/4設(shè)所有元素互不相同。在這種情況下,找出的基準(zhǔn)x至少比3(n-template<classType>intPartition(Type*a,intp,intr,Typex){inti,left=p,right=r;Type*b=newType[r-p+1];for(i=0;i<r-p+1;i++){b[i]=a[p+i];}for(i=p;i<=r;i++){if(b[i]<x){a[left++]=b[i];}elseif(b[i]>x){a[right--]=b[i];}}for(i=left;i<=right;i++)a[i]=x;delete[]b;returnleft;}template<classType>//找a[p..r]中第k小的元素返回template<classType>TypeSelect(Typea[],intp,intr,intk){inti,j;Typex,t;if(r-p<75){Sort(a,p,r);returna[p+k-1];}for(i=0;i<=(r-p-4)/5;i++){x=a[p+5*i]至a[p+5*i+4]的第3小元素;//將a[p+5*i...p+5*i+4]的第3小元素與a[p+i]交換位置

t=a[p+i];a[p+i]=x;x=t;}//找a[p..r]中第k小的元素返回/*每一組的中位數(shù)排在了a[p..p+(r-p-4)/5]的位置,現(xiàn)在找中位數(shù)的中位數(shù)x,r-p-4即上面所說的n-5*/x=Select(a,p,p+(r-p-4)/5,(r-p-4)/10);/*將a[p…r]中不大于x的放在x左邊,比x大的放在x右邊,返回中位數(shù)的中位數(shù)x的下標(biāo)i*/i=Partition(a,p,r,x),j=i-p+1;//求x左邊有多少個元素,這些元素都比x小

if(k<=j)returnSelect(a,p,i,k);elsereturnSelect(a,i+1,r,k-j);}/*每一組的中位數(shù)排在了a[p..p+(r-p-4)上述算法將每一組的大小定為5,并選取75作為是否作遞歸調(diào)用的分界點(diǎn)。這2點(diǎn)保證了T(n)的遞歸式中2個自變量之和n/5+3n/4=19n/20=εn,0<ε<1。這是使T(n)=O(n)的關(guān)鍵之處。當(dāng)然,除了5和75之外,還有其他選擇。設(shè)n=r-p+1,即n為輸入數(shù)組的長度,算法的遞歸調(diào)用在n≥75時才執(zhí)行,n<75的時候,算法Select所用的計(jì)算時間不超過常數(shù)C1,找到中位數(shù)的中位數(shù)x后,算法Select以x為基準(zhǔn)調(diào)用函數(shù)Partition對數(shù)組a[p…r]進(jìn)行劃分,這需要O(n)時間,算法Select的for循環(huán)體執(zhí)行了n/5次,每一次需要O(1)時間,因此執(zhí)行for循環(huán)共需要O(n)時間。上述算法將每一組的大小定為5,并選取75作為是否作遞歸調(diào)用的設(shè)對n個元素數(shù)組調(diào)用Select算法需要T(n)時間,那么找中位數(shù)的中位數(shù)x至多用了T(n/5)次時間,既然按照基準(zhǔn)x劃分所得到的兩個子數(shù)組分別至多3n/4個元素,所以不論對哪一個子數(shù)組調(diào)用Select算法都至多用了T(3n/4)的時間。因此,得到,T(n)=O(n)設(shè)對n個元素數(shù)組調(diào)用Select算法需要T(n)時間,那么找2.10最接近點(diǎn)對問題給定平面上n個點(diǎn),找出其中一對點(diǎn),使得在n個點(diǎn)所構(gòu)成的所有點(diǎn)對中,該點(diǎn)對的距離最小。最接近點(diǎn)對可能多于一對,簡單起見,只考慮找其中的一對作為問題的解。如果我們將每一個點(diǎn)和其他n-1個點(diǎn)的距離算出來,找到最小距離的兩個點(diǎn),算法效率需要O(n2)的計(jì)算時間,效率太低。下面設(shè)計(jì)一個耗時O(nlog2n)的算法:2.10最接近點(diǎn)對問題給定平面上n個點(diǎn),找出其中一對點(diǎn),使為了使問題易于理解和分析,先來考慮一維的情形。此時,S中的n個點(diǎn)退化為x軸上的n個實(shí)數(shù)x1,x2,…,xn。最接近點(diǎn)對即為這n個實(shí)數(shù)中相差最小的2個實(shí)數(shù)。假設(shè)我們用x軸上某個點(diǎn)m將S劃分為2個子集S1和S2,基于平衡子問題的思想,用S中各點(diǎn)坐標(biāo)的中位數(shù)來作分割點(diǎn)。遞歸地在S1和S2上找出其最接近點(diǎn)對{p1,p2}和{q1,q2},并設(shè)d=min{|p1-p2|,|q1-q2|},S中的最接近點(diǎn)對或者是{p1,p2},或者是{q1,q2},或者是某個{p3,q3},其中p3∈S1且q3∈S2。問題在于:能否在線性時間內(nèi)找到p3、q3?為了使問題易于理解和分析,先來考慮一維的情形。此時,S中的n如果S的最接近點(diǎn)對是{p3,q3},即|p3-q3|<d,則p3和q3兩者與m的距離不超過d,即p3∈(m-d,m],q3∈(m,m+d]。由于在S1中,每個長度為d的半閉區(qū)間至多包含一個點(diǎn)(否則必有兩點(diǎn)距離小于d),并且m是S1和S2的分割點(diǎn),因此(m-d,m]中至多包含S中的一個點(diǎn)。由圖可以看出,如果(m-d,m]中有S中的點(diǎn),則此點(diǎn)就是S1中最大點(diǎn)。因此,我們用線性時間就能找到區(qū)間(m-d,m]和(m,m+d]中所有點(diǎn),即p3和q3。從而我們用線性時間就可以將S1的解和S2的解合并成為S的解。如果S的最接近點(diǎn)對是{p3,q3},即|p3-q3|<d,則選取一垂直線l:x=m來作為分割直線。其中m為S中各點(diǎn)x坐標(biāo)的中位數(shù)。由此將S分割為S1和S2。遞歸地在S1和S2上找出其最小距離d1和d2,并設(shè)d=min{d1,d2},S中的最接近點(diǎn)對或者是d,或者是某個{p,q},其中p∈P1且q∈P2。問題在于:能否在線性時間內(nèi)找到p、q?選取一垂直線l:x=m來作為分割直線。其中m為S中各點(diǎn)x坐標(biāo)考慮P1中任意一點(diǎn)p,它若與P2中的點(diǎn)q構(gòu)成最接近點(diǎn)對的候選者,則必有distance(p,q)<d。滿足這個條件的P2中的點(diǎn)一定落在一個d×2d的矩形R中。由d的意義可知,P2中任何2個S中的點(diǎn)的距離都不小于d。由此可以推出矩形R中最多只有6個S中的點(diǎn)。因此,在分治法的合并步驟中最多只需要檢查6×n/2=3n個候選者。考慮P1中任意一點(diǎn)p,它若與P2中的點(diǎn)q構(gòu)成最接近點(diǎn)對的候選證明:將矩形R的長為2d的邊3等分,將它的長為d的邊2等分,由此導(dǎo)出6個(d/2)×(2d/3)的矩形。若矩形R中有多于6個S中的點(diǎn),由鴿舍原理易知至少有一個(d/2)×(2d/3)的小矩形中有2個以上S中的點(diǎn)。設(shè)u,v是位于同一小矩形中的2個點(diǎn),則distance(u,v)<d,與d的意義矛盾。證明:將矩形R的長為2d的邊3等分,將它的長為d的邊2等分,為了確切地知道要檢查哪6個點(diǎn),可將p和P2中所有S2的點(diǎn)投影到垂直線l上。由于能與p點(diǎn)一起構(gòu)成最接近點(diǎn)對候選者的S2中點(diǎn)一定在矩形R中,所以它們在直線l上的投影點(diǎn),距離p在l上投影點(diǎn)的距離小于d。由上面的分析可知,這種投影點(diǎn)最多只有6個。因此,若將P1和P2中所有S中點(diǎn)按其y坐標(biāo)排好序,則對P1中所有點(diǎn),對排好序的點(diǎn)列作一次掃描,就可以找出所有最接近點(diǎn)對的候選者。對P1中每一點(diǎn)最多只要檢查P2中排好序的相繼6個點(diǎn)。下面給出用分治法求二維最接近點(diǎn)對算法:為了確切地知道要檢查哪6個點(diǎn),可將p和P2中所有S2的點(diǎn)投影boolCpair2(S,&d){n=|S|;if(n<2)returnfalse;1、m=S中各點(diǎn)x坐標(biāo)下標(biāo)的中位數(shù);

構(gòu)造S1和S2,S1={p∈S|x(p)<=x(m)},S2={p∈S|x(p)>x(m)}2、Cpair2(S1,d1);Cpair2(S2,d2);3、dm=min(d1,d2);4、令P1是S1中距垂直分割線l的距離在dm之內(nèi)的所有點(diǎn)組成的集合;P2是S2中距分割線l的距離在dm之內(nèi)所有點(diǎn)組成的集合;將P1和P2中的點(diǎn)依其y坐標(biāo)值排序;并設(shè)X和Y是相應(yīng)的已排好序的點(diǎn)列;第1步:O(n)第3步:O(1)第2步:2T(n/2)第4步:O(nlog2n)boolCpair2(S,&d)第1步:O(n)第3步:O第5步:O(n)5、通過掃描X以及對于X中每個點(diǎn)檢查Y中與其距離在dm之內(nèi)的所有點(diǎn)(最多6個)可以完成合并;當(dāng)X中的掃描指針逐次向上移動時,Y中的掃描指針可在寬為2dm的區(qū)間內(nèi)移動;設(shè)dl是按這種掃描方式找到的點(diǎn)對間的最小距離;

6、d=min(dm,dl);returntrue;}若在每次執(zhí)行第4步的時候進(jìn)行排序,則最壞情況下第4步需要O(nlog2n)時間,這不符合要求,需要做一個技術(shù)處理。第6步:O(1)第5步:O(n)5、通過掃描X以及對于X中每個點(diǎn)檢查Y中與使用預(yù)排序技術(shù),在使用分治法之前,預(yù)先將S中n個點(diǎn)依其y坐標(biāo)排好序,設(shè)排好序的點(diǎn)為P*,在執(zhí)行分治法的第4步時,只要對P*進(jìn)行1次線性掃描,即可抽取出我們所需要排好序的點(diǎn)列X和Y。然后,在第5步中再對X做一次線性掃描,即可求得dl。因此,第4步和第5步兩遍掃描合在一起只要用O(n)時間。這樣,經(jīng)過預(yù)排序處理后算法后,算法Cpair2所需的計(jì)算時間T(n)滿足遞歸方程即T(n)=O(nlog2n)。根據(jù)這個思想,寫出的程序如下:使用預(yù)排序技術(shù),在使用分治法之前,預(yù)先將S中n個點(diǎn)依其y坐標(biāo)#include<iostream>#include<math.h>constintTOTAL=10000;usingnamespacestd;classPoint{public:doublegetx()const{returnx;}doublegety()const{returny;}doublesetx(doublexx){x=xx;returnx;}doublesety(doubleyy){y=yy;returny;}virtualbooloperator<=(Pointa){returntrue;}protected:doublex,y;};#include<iostream>//類PointX和PointY分別表示按照x坐標(biāo)和y坐標(biāo)排序的點(diǎn)classPointX:publicPoint{public:booloperator<=(Pointa)const{return(x<=a.getx());}friendinlinedoubledistance(constPointX&u,constPointX&v);};classPointY:publicPoint{public:booloperator<=(Pointa)const{return(y<=a.gety());}intsetp(intpp){p=pp;returnp;}intgetp(){returnp;}friendinlinedoubledistance(constPointY&u,constPointY&v);private:intp;//p表示以x坐標(biāo)排序時,該點(diǎn)對應(yīng)的下標(biāo)(序號)};//類PointX和PointY分別表示按照x坐標(biāo)和y坐標(biāo)排inlinedoubledistance(constPointX&u,constPointX&v){doubledx=u.getx()-v.getx();doubledy=u.gety()-v.gety();returnsqrt(dx*dx+dy*dy);}inlinedoulbledistance(constPointY&u,constPointY&v){doubledx=u.getx()-v.getx();doubledy=u.gety()-v.gety();returnsqrt(dx*dx+dy*dy);}inlinedoubledistance(constPtemplate<classType>voidMerge(TypeY[],TypeZ[],intl,intm,intr){//將有序的Z[l...m]與有序的Z[m+1...r]合并到Y(jié)[l...r]Type*a=&Z[l];Type*b=&Z[m+1];Type*c=&Y[l];intanum=m-l+1,ap=0;intbnum=r-m,bp=0;intcnum=r-l+1,cp=0;while(ap<anum&&bp<bnum){if(a[ap]<=b[bp])c[cp++]=a[ap++];elsec[cp++]=b[bp++];}while(ap<anum)c[cp++]=a[ap++];while(bp<bnum)c[cp++]=b[bp++];}template<classType>template<classType>voidMergeSort(Typea[],intn){intanum,bnum,i;Type*b,*c;if(n<=1)return;anum=n/2;b=a+anum;bnum=n-anum;MergeSort(a,anum);MergeSort(b,bnum);c=newType[n];Merge(c,a,0,anum-1,n-1);for(i=0;i<n;i++)a[i]=c[i];delete[]c;}template<classType>/*X存放輸入的點(diǎn)集,X和Y分別表示按照x坐標(biāo)和y坐標(biāo)排序的點(diǎn),l和r表示點(diǎn)集Y中成員p的范圍*/voidclosest(PointXX[],PointYY[],PointYZ[],intl,intr,PointX&a,PointX&b,double&d){doubled1,d2,d3,dp;intf,g,m,i,j,k;doubledr;PointXar,br;if(r-l==1)//2點(diǎn)的情況

{a=X[l];b=X[r];d=distance(X[l],X[r]);return;}/*X存放輸入的點(diǎn)集,X和Y分別表示按照x坐標(biāo)和y坐標(biāo)排序的if(r-l==2)//3點(diǎn)的情況

{d1=distance(X[l],X[l+1]);d2=distance(X[l+1],X[r]);d3=distance(X[l],X[r]);if(d1<=d2&&d1<=d3){a=X[l];b=X[l+1];d=d1;}elseif(d2<=d3){a=X[l+1];b=X[r];d=d2;}else{a=X[l];b=X[r];d=d3;}return;}if(r-l==2)//3點(diǎn)的情況m=(l+r)/2;//m為點(diǎn)集Y中成員p的范圍的中位數(shù)

/*將已經(jīng)按照y坐標(biāo)排序的點(diǎn)集Y[l..r],等分成兩個子集復(fù)制到Z,其中Z[l..(l+r)/2]中的每個點(diǎn)的x坐標(biāo)都小于Z[(l+r)/2+1..r]中的每個點(diǎn)的x坐標(biāo)*/f=l;g=m+1;for(i=l;i<=r;i++){if(Y[i].getp()>m)Z[g++]=Y[i];elseZ[f++]=Y[i];}m=(l+r)/2;//m為點(diǎn)集Y中成//遞歸處理這兩個子集(注意參數(shù)傳遞時Z與Y位置的變化)closest(X,Z,Y,l,m,a,b,d);closest(X,Z,Y,m+1,r,ar,br,dr);if(dr<d)//d表示這兩個子集中各自找到的最近點(diǎn)對的距離較小者

{a=ar;b=br;d=dr;}Merge(Y,Z,l,m,r);//重構(gòu)數(shù)組Y//將與分割線距離為d的點(diǎn)置如數(shù)組Z中

k=l;for(i=l;i<=r;i++){if(fabs(Y[m].getx()-Y[i].getx())<d)Z[k++]=Y[i];}//遞歸處理這兩個子集(注意參數(shù)傳遞時Z與Y位置的變//搜索Z[l..k-1],若其中存在兩點(diǎn)的距離小于d,則更新dfor(i=l;i<k;i++){for(j=i+1;j<k&&Z[j].gety()-Z[i].gety()<d;j++){dp=distance(Z[i],Z[j]);if(dp<d){d=dp;a=X[Z[i].getp()];b=X[Z[j].getp()];}}}}//搜索Z[l..k-1],若其中存在兩點(diǎn)的距離小于boolCpair2(PointXX[],intn,PointX&a,PointX&b,double&d){inti;PointY*Z,*Y;if(n<2)returnfalse;MergeSort(X,n);//將各點(diǎn)按照x坐標(biāo)排序

Y=newPointY[n];for(i=0;i<n;i++)//將數(shù)組X內(nèi)的信息寫入數(shù)組Y{Y[i].setp(i);//同一點(diǎn)在數(shù)組X中的坐標(biāo)的下標(biāo)

Y[i].setx(X[i].getx());Y[i].sety(X[i].gety());}MergeSort(Y,n);//將各點(diǎn)按照y坐標(biāo)排序

Z=newPointY[n];closest(X,Y,Z,0,n-1,a,b,d);delete[]Y;delete[]Z;returntrue;}boolCpair2(PointXX[],intn,intmain(){PointXX[TOTAL],a,b;intn=TOTAL;doubled;inti;for(i=0;i<n;i++){X[i].setx((double)rand()/100);X[i].sety((double)rand()/100);}Cpair2(X,n,a,b,d);printf("(%f,%f)(%f,%f)%f\n",a.getx(),a.gety(),b.getx(),b.gety(),d);return0;}intmain()2.11循環(huán)賽日程問題設(shè)有n=2k(k為正整數(shù))個運(yùn)動員進(jìn)行乒乓球循環(huán)賽正賽,現(xiàn)要求設(shè)計(jì)一個滿足以下要求的比賽日程表:(1)每個選手必須與其他n-1個選手各賽一次;(2)每個選手一天只能賽一次;(3)循環(huán)賽一共進(jìn)行n-1天。將比賽日程設(shè)計(jì)為n行和n-1列的一個表,在表中第i行第j列處填寫第i個選手在第j天的對手。按分治策略,將所有的選手分為兩半,n個選手的比賽日程表就可以通過為n/2個選手設(shè)計(jì)的比賽日程表來決定。遞歸地用對選手進(jìn)行分割,直到只剩下2個選手時,比賽日程表的制定就變得很簡單。這時只要讓這2個選手進(jìn)行比賽就可以了。

2.11循環(huán)賽日程問題設(shè)有n=2k(k為正整數(shù))個運(yùn)動員進(jìn)圖中所列出的正方形表是8個選手的比賽日程表。其中左上角與左下角的兩小塊分別為選手1至選手4和選手5至選手8前3天的比賽日程。據(jù)此,將左上角小塊中的所有數(shù)字按其相對位置抄到右下角,又將左下角小塊中的所有數(shù)字按其相對位置抄到右上角,這樣我們就分別安排好了選手1至選手4和選手5至選手8在后4天的比賽日程。依此思想容易將這個比賽日程表推廣到具有任意多個選手的情形。該算法沒有使用遞歸,這也說明并非所有的分治策略都要使用遞歸。1234567821436587341278564321876556781234658721437856341287654321圖中所列出的正方形表是8個選手的比賽日程表。其中左上角與左下12345678以k=3,n=8名選手為例。初始狀態(tài):填寫第0列。之后,進(jìn)行k=3個階段,設(shè)第s個階段要循環(huán)ns次,則n1=n/2=4,n2=n1/2=2,n3=n2/2=11221344356657887第1階段(s=1):填寫第1列(j=1)循環(huán)4次,循環(huán)次數(shù)為n1=n/2=4,8個大塊,每個大塊含m*m=1*1個小塊,每次循環(huán)復(fù)制2個大塊,在第t(t=0,1,2,3)次循環(huán)時,執(zhí)行a[i+2*t*m-m][j]=a[i+2*t*m][j-m]和a[i+2*t*m][j]=a[i+2*t*m-m][j-m],i=1,分別把左下角復(fù)制到右上角,把左上角復(fù)制到右下角

12345678以k=3,n=8名選手為例。初始狀態(tài):填寫第12342143341243215678658778568765第2階段(s=2):填寫第2,3列(j=2,3)循環(huán)2次,循環(huán)次數(shù)為n2=n1/2=2,4個大塊,每個大塊含m*m=2*2個小塊,每次循環(huán)復(fù)制2個大塊,在第t(t=0,1)次循環(huán)時,執(zhí)行a[i+2*t*m-m][j]=a[i+2*t*m][j-m]和a[i+2*t*m][j]=a[i+2*t*m-m][j-m],i=2,3,分別把左下角復(fù)制到右上角,把左上角復(fù)制到右下角1234567821436587341278564321876556781234658721437856341287654321第3階段(s=3):填寫第4,5,6,7列(j=4,5,6,7)循環(huán)1次,循環(huán)次數(shù)為n3=n2/2=2,2個大塊,每個大塊含m*m=4*4個小塊,每次循環(huán)復(fù)制2個大塊,在第t(t=0)次循環(huán)時,執(zhí)行a[i+2*t*m-m][j]=a[i+2*t*m][j-m]和a[i+2*t*m][j]=a[i+2*t*m-m][j-m],i=4,5,6,7,分別把左下角復(fù)制到右上角,把左上角復(fù)制到右下角123421433412432156786587785687voidTable(intk,inta[][N]){intn=1,m=1,i,j,t,s;for(i=1;i<=k;i++)n*=2;for(i=0;i<n;i++){a[i][0]=i+1;}//k個階段,從左到右

for(s=1;s<=k;s++){n/=2;/*每個階段有t次循環(huán),即復(fù)制n個大塊*/for(t=0;t<n;t++){//j表示列

for(j=m;j<2*m;j++){for(i=m;i<2*m;i++){a[i-m+2*t*m][j]=a[i+2*t*m][j-m];//右上角=左下角

a[i+2*t*m][j]=a[i-m+2*t*m][j-m];//右下角=左上角

}}}m*=2;}}voidTable(intk,inta[][N])voidTable(intk,inta[][N]){intn=1,m=1,i,j,t,s;for(i=1;i<=k;i++)n*=2;for(i=0;i<n;i++){a[i][0]=i+1;}voidTable(intk,inta[][N])for(s=1;s<=k;s++)//k個階段,從左到右

{n/=2;for(t=0;t<n;t++)//每個階段有t次循環(huán),即復(fù)制n個大塊

{for(j=m;j<2*m;j++)//j表示列

{for(i=m;i<2*m;i++){a[i-m+2*t*m][j]=a[i+2*t*m][j-m];////右上角=左下角

a[i+2*t*m][j]=a[i-m+2*t*m][j-m];//右下角=左上角

}}}m*=2;}}for(s=1;s<=k;s++)//循環(huán)賽日程安排問題也可以寫成遞歸算法,如下:voidtable(intx,intk,int**a){//此函數(shù)為從x號球員起的共2的k次方名球員安排日程表

inti,j,y;if(k==1)//只有兩名球員

{a[x][0]=x;a[x][1]=x+1;a[x+1][0]=x+1;a[x+1][1]=x;}循環(huán)賽日程安排問題也可以寫成遞歸算法,如下:

else{y=pow(2,k-1);table(x,k-1,a);table(x+y,k-1,a);for(i=x;i<x+y;i++){for(j=y;j<2*y;j++)a[i][j]=a[i+y][j-y];}else

for(i=x+y;i<x+2*y;i++){for(j=y;j<2*y;j++)a[i][j]=a[i-y][j-y];}}}for(i=x+y;i<x+2*y;i+本周課程結(jié)束,謝謝!本周課程結(jié)束,謝謝!第2章分治策略(2)教學(xué)目的與要求1.掌握設(shè)計(jì)有效算法的分治策略。2.要求通過范例的學(xué)習(xí)掌握分治策略的技巧。第2章分治策略(2)教學(xué)目的與要求2.9線性時間選擇給定線性序集中n個元素和一個整數(shù)k,1≤k≤n,要求找出這n個元素中第k小的元素。采用分治策略,利用在快速排序中使用到的RandomizedPartition算法,將序列隨機(jī)分成兩部分a[p…i]和a[i+1…r],使得a[p…i]的每個元素都不大于a[i+1…r]的每個元素,而此時a[i]恰好為第i小元素,接著計(jì)算子數(shù)組a[p…i]的元素個數(shù)j,如果k≤j,則a[p…r]中第k小的數(shù)落在子數(shù)組a[p…i]中,如果k>j,則a[p…r]中第k小的數(shù)落在子數(shù)組a[i+1…r]中,此時要找的a[p…r]中第k小的元素是a[i+1…r]中第k-j小的元素。2.9線性時間選擇給定線性序集中n個元素和一個整數(shù)k,1≤template<classType>intPartition(Typea[],intp,intr){inti=p,j=r+1;Typex=a[p],t;//將<x的元素交換到左邊區(qū)域,將>x的元素交換到右邊區(qū)域

while(true){while(a[++i]<x);//從左到右找到第一個不小于a[p]的元素a[i]while(a[--j]>x);//從右到左找到第一個不大于a[p]的元素a[j]if(i>=j)break;t=a[i];a[i]=a[j];a[j]=t;//交換a[i]和a[j]}a[p]=a[j];a[j]=x;//交換a[p]和a[j]returnj;}template<classType>template<classType>intRandomizedPartition(Typea[],intp,intr){inti=Random(p,r);Typet;t=a[i];a[i]=a[p];a[p]=t;returnPartition(a,p,r);}template<classType>template<classType>TypeRandomizedSelect(Typea[],intp,intr,intk){inti,j;if(p==r)returna[p];i=RandomizedPartition(a,p,r);j=i-p+1;//計(jì)算子數(shù)組a[p…i]的元素個數(shù)jif(k<=j)returnRandomizedSelect(a,p,i,k);elsereturnRandomizedSelect(a,i+1,r,k-j);}template<classType>在最壞情況下(如在找最小元素時,總在最大元素處劃分),算法RandomizedSelect需要(n2)計(jì)算時間,但該算法的平均性能較好。如果能在線性時間內(nèi)找到一個劃分基準(zhǔn),使得按這個基準(zhǔn)所劃分出的2個子數(shù)組的長度都至少為原數(shù)組長度的ε倍(0<ε<1是某個正常數(shù)),那么就可以在最壞情況下用O(n)時間完成選擇任務(wù)。例如,若ε=9/10,算法遞歸調(diào)用所產(chǎn)生的子數(shù)組的長度至少縮短1/10。所以,在最壞情況下,算法所需的計(jì)算時間T(n)滿足遞歸式T(n)≤T(9n/10)+O(n)。由此可得T(n)=O(n)。在最壞情況下(如在找最小元素時,總在最大元素處劃分),算法R例如,將n個輸入元素劃分成n/5個組,每組5個元素,只可能有一個組不是5個元素。用任意一種排序算法,將每組中的元素排好序,并取出每組的中位數(shù),共n/5個。遞歸調(diào)用Select來找出這n/5個元素的中位數(shù)(也就是這些中位數(shù)的中位數(shù)),若n/5是偶數(shù),則找它的兩個中位數(shù)中較大的一個,然后以這個元素作為基準(zhǔn)劃分。例如,將n個輸入元素劃分成n/5個組,每組5個元素,只可設(shè)所有元素互不相同。在這種情況下,找出的基準(zhǔn)x至少比3(n-5)/10個元素大,因?yàn)樵诿恳唤M中有2個元素小于本組的中位數(shù),而n/5個中位數(shù)中又有(n-5)/10個小于基準(zhǔn)x。同理,基準(zhǔn)x也至少比3(n-5)/10個元素小。而當(dāng)n≥75時,3(n-5)/10≥n/4所以按此基準(zhǔn)劃分所得的2個子數(shù)組的長度都至少縮短1/4設(shè)所有元素互不相同。在這種情況下,找出的基準(zhǔn)x至少比3(n-template<classType>intPartition(Type*a,intp,intr,Typex){inti,left=p,right=r;Type*b=newType[r-p+1];for(i=0;i<r-p+1;i++){b[i]=a[p+i];}for(i=p;i<=r;i++){if(b[i]<x){a[left++]=b[i];}elseif(b[i]>x){a[right--]=b[i];}}for(i=left;i<=right;i++)a[i]=x;delete[]b;returnleft;}template<classType>//找a[p..r]中第k小的元素返回template<classType>TypeSelect(Typea[],intp,intr,intk){inti,j;Typex,t;if(r-p<75){Sort(a,p,r);returna[p+k-1];}for(i=0;i<=(r-p-4)/5;i++){x=a[p+5*i]至a[p+5*i+4]的第3小元素;//將a[p+5*i...p+5*i+4]的第3小元素與a[p+i]交換位置

t=a[p+i];a[p+i]=x;x=t;}//找a[p..r]中第k小的元素返回/*每一組的中位數(shù)排在了a[p..p+(r-p-4)/5]的位置,現(xiàn)在找中位數(shù)的中位數(shù)x,r-p-4即上面所說的n-5*/x=Select(a,p,p+(r-p-4)/5,(r-p-4)/10);/*將a[p…r]中不大于x的放在x左邊,比x大的放在x右邊,返回中位數(shù)的中位數(shù)x的下標(biāo)i*/i=Partition(a,p,r,x),j=i-p+1;//求x左邊有多少個元素,這些元素都比x小

if(k<=j)returnSelect(a,p,i,k);elsereturnSelect(a,i+1,r,k-j);}/*每一組的中位數(shù)排在了a[p..p+(r-p-4)上述算法將每一組的大小定為5,并選取75作為是否作遞歸調(diào)用的分界點(diǎn)。這2點(diǎn)保證了T(n)的遞歸式中2個自變量之和n/5+3n/4=19n/20=εn,0<ε<1。這是使T(n)=O(n)的關(guān)鍵之處。當(dāng)然,除了5和75之外,還有其他選擇。設(shè)n=r-p+1,即n為輸入數(shù)組的長度,算法的遞歸調(diào)用在n≥75時才執(zhí)行,n<75的時候,算法Select所用的計(jì)算時間不超過常數(shù)C1,找到中位數(shù)的中位數(shù)x后,算法Select以x為基準(zhǔn)調(diào)用函數(shù)Partition對數(shù)組a[p…r]進(jìn)行劃分,這需要O(n)時間,算法Select的for循環(huán)體執(zhí)行了n/5次,每一次需要O(1)時間,因此執(zhí)行for循環(huán)共需要O(n)時間。上述算法將每一組的大小定為5,并選取75作為是否作遞歸調(diào)用的設(shè)對n個元素數(shù)組調(diào)用Select算法需要T(n)時間,那么找中位數(shù)的中位數(shù)x至多用了T(n/5)次時間,既然按照基準(zhǔn)x劃分所得到的兩個子數(shù)組分別至多3n/4個元素,所以不論對哪一個子數(shù)組調(diào)用Select算法都至多用了T(3n/4)的時間。因此,得到,T(n)=O(n)設(shè)對n個元素數(shù)組調(diào)用Select算法需要T(n)時間,那么找2.10最接近點(diǎn)對問題給定平面上n個點(diǎn),找出其中一對點(diǎn),使得在n個點(diǎn)所構(gòu)成的所有點(diǎn)對中,該點(diǎn)對的距離最小。最接近點(diǎn)對可能多于一對,簡單起見,只考慮找其中的一對作為問題的解。如果我們將每一個點(diǎn)和其他n-1個點(diǎn)的距離算出來,找到最小距離的兩個點(diǎn),算法效率需要O(n2)的計(jì)算時間,效率太低。下面設(shè)計(jì)一個耗時O(nlog2n)的算法:2.10最接近點(diǎn)對問題給定平面上n個點(diǎn),找出其中一對點(diǎn),使為了使問題易于理解和分析,先來考慮一維的情形。此時,S中的n個點(diǎn)退化為x軸上的n個實(shí)數(shù)x1,x2,…,xn。最接近點(diǎn)對即為這n個實(shí)數(shù)中相差最小的2個實(shí)數(shù)。假設(shè)我們用x軸上某個點(diǎn)m將S劃分為2個子集S1和S2,基于平衡子問題的思想,用S中各點(diǎn)坐標(biāo)的中位數(shù)來作分割點(diǎn)。遞歸地在S1和S2上找出其最接近點(diǎn)對{p1,p2}和{q1,q2},并設(shè)d=min{|p1-p2|,|q1-q2|},S中的最接近點(diǎn)對或者是{p1,p2},或者是{q1,q2},或者是某個{p3,q3},其中p3∈S1且q3∈S2。問題在于:能否在線性時間內(nèi)找到p3、q3?為了使問題易于理解和分析,先來考慮一維的情形。此時,S中的n如果S的最接近點(diǎn)對是{p3,q3},即|p3-q3|<d,則p3和q3兩者與m的距離不超過d,即p3∈(m-d,m],q3∈(m,m+d]。由于在S1中,每個長度為d的半閉區(qū)間至多包含一個點(diǎn)(否則必有兩點(diǎn)距離小于d),并且m是S1和S2的分割點(diǎn),因此(m-d,m]中至多包含S中的一個點(diǎn)。由圖可以看出,如果(m-d,m]中有S中的點(diǎn),則此點(diǎn)就是S1中最大點(diǎn)。因此,我們用線性時間就能找到區(qū)間(m-d,m]和(m,m+d]中所有點(diǎn),即p3和q3。從而我們用線性時間就可以將S1的解和S2的解合并成為S的解。如果S的最接近點(diǎn)對是{p3,q3},即|p3-q3|<d,則選取一垂直線l:x=m來作為分割直線。其中m為S中各點(diǎn)x坐標(biāo)的中位數(shù)。由此將S分割為S1和S2。遞歸地在S1和S2上找出其最小距離d1和d2,并設(shè)d=min{d1,d2},S中的最接近點(diǎn)對或者是d,或者是某個{p,q},其中p∈P1且q∈P2。問題在于:能否在線性時間內(nèi)找到p、q?選取一垂直線l:x=m來作為分割直線。其中m為S中各點(diǎn)x坐標(biāo)考慮P1中任意一點(diǎn)p,它若與P2中的點(diǎn)q構(gòu)成最接近點(diǎn)對的候選者,則必有distance(p,q)<d。滿足這個條件的P2中的點(diǎn)一定落在一個d×2d的矩形R中。由d的意義可知,P2中任何2個S中的點(diǎn)的距離都不小于d。由此可以推出矩形R中最多只有6個S中的點(diǎn)。因此,在分治法的合并步驟中最多只需要檢查6×n/2=3n個候選者??紤]P1中任意一點(diǎn)p,它若與P2中的點(diǎn)q構(gòu)成最接近點(diǎn)對的候選證明:將矩形R的長為2d的邊3等分,將它的長為d的邊2等分,由此導(dǎo)出6個(d/2)×(2d/3)的矩形。若矩形R中有多于6個S中的點(diǎn),由鴿舍原理易知至少有一個(d/2)×(2d/3)的小矩形中有2個以上S中的點(diǎn)。設(shè)u,v是位于同一小矩形中的2個點(diǎn),則distance(u,v)<d,與d的意義矛盾。證明:將矩形R的長為2d的邊3等分,將它的長為d的邊2等分,為了確切地知道要檢查哪6個點(diǎn),可將p和P2中所有S2的點(diǎn)投影到垂直線l上。由于能與p點(diǎn)一起構(gòu)成最接近點(diǎn)對候選者的S2中點(diǎn)一定在矩形R中,所以它們在直線l上的投影點(diǎn),距離p在l上投影點(diǎn)的距離小于d。由上面的分析可知,這種投影點(diǎn)最多只有6個。因此,若將P1和P2中所有S中點(diǎn)按其y坐標(biāo)排好序,則對P1中所有點(diǎn),對排好序的點(diǎn)列作一次掃描,就可以找出所有最接近點(diǎn)對的候選者。對P1中每一點(diǎn)最多只要檢查P2中排好序的相繼6個點(diǎn)。下面給出用分治法求二維最接近點(diǎn)對算法:為了確切地知道要檢查哪6個點(diǎn),可將p和P2中所有S2的點(diǎn)投影boolCpair2(S,&d){n=|S|;if(n<2)returnfalse;1、m=S中各點(diǎn)x坐標(biāo)下標(biāo)的中位數(shù);

構(gòu)造S1和S2,S1={p∈S|x(p)<=x(m)},S2={p∈S|x(p)>x(m)}2、Cpair2(S1,d1);Cpair2(S2,d2);3、dm=min(d1,d2);4、令P1是S1中距垂直分割線l的距離在dm之內(nèi)的所有點(diǎn)組成的集合;P2是S2中距分割線l的距離在dm之內(nèi)所有點(diǎn)組成的集合;將P1和P2中的點(diǎn)依其y坐標(biāo)值排序;并設(shè)X和Y是相應(yīng)的已排好序的點(diǎn)列;第1步:O(n)第3步:O(1)第2步:2T(n/2)第4步:O(nlog2n)boolCpair2(S,&d)第1步:O(n)第3步:O第5步:O(n)5、通過掃描X以及對于X中每個點(diǎn)檢查Y中與其距離在dm之內(nèi)的所有點(diǎn)(最多6個)可以完成合并;當(dāng)X中的掃描指針逐次向上移動時,Y中的掃描指針可在寬為2dm的區(qū)間內(nèi)移動;設(shè)dl是按這種掃描方式找到的點(diǎn)對間的最小距離;

6、d=min(dm,dl);returntrue;}若在每次執(zhí)行第4步的時候進(jìn)行排序,則最壞情況下第4步需要O(nlog2n)時間,這不符合要求,需要做一個技術(shù)處理。第6步:O(1)第5步:O(n)5、通過掃描X以及對于X中每個點(diǎn)檢查Y中與使用預(yù)排序技術(shù),在使用分治法之前,預(yù)先將S中n個點(diǎn)依其y坐標(biāo)排好序,設(shè)排好序的點(diǎn)為P*,在執(zhí)行分治法的第4步時,只要對P*進(jìn)行1次線性掃描,即可抽取出我們所需要排好序的點(diǎn)列X和Y。然后,在第5步中再對X做一次線性掃描,即可求得dl。因此,第4步和第5步兩遍掃描合在一起只要用O(n)時間。這樣,經(jīng)過預(yù)排序處理后算法后,算法Cpair2所需的計(jì)算時間T(n)滿足遞歸方程即T(n)=O(nlog2n)。根據(jù)這個思想,寫出的程序如下:使用預(yù)排序技術(shù),在使用分治法之前,預(yù)先將S中n個點(diǎn)依其y坐標(biāo)#include<iostream>#include<math.h>constintTOTAL=10000;usingnamespacestd;classPoint{public:doublegetx()const{returnx;}doublegety()const{returny;}doublesetx(doublexx){x=xx;returnx;}doublesety(doubleyy){y=yy;returny;}virtualbooloperator<=(Pointa){returntrue;}protected:doublex,y;};#include<iostream>//類PointX和PointY分別表示按照x坐標(biāo)和y坐標(biāo)排序的點(diǎn)classPointX:publicPoint{public:booloperator<=(Pointa)const{return(x<=a.getx());}friendinlinedoubledistance(constPointX&u,constPointX&v);};classPointY:publicPoint{public:booloperator<=(Pointa)const{return(y<=a.gety());}intsetp(intpp){p=pp;returnp;}intgetp(){returnp;}friendinlinedoubledistance(constPointY&u,constPointY&v);private:intp;//p表示以x坐標(biāo)排序時,該點(diǎn)對應(yīng)的下標(biāo)(序號)};//類PointX和PointY分別表示按照x坐標(biāo)和y坐標(biāo)排inlinedoubledistance(constPointX&u,constPointX&v){doubledx=u.getx()-v.getx();doubledy=u.gety()-v.gety();returnsqrt(dx*dx+dy*dy);}inlinedoulbledistance(constPointY&u,constPointY&v){doubledx=u.getx()-v.getx();doubledy=u.gety()-v.gety();returnsqrt(dx*dx+dy*dy);}inlinedoubledistance(constPtemplate<classType>voidMerge(TypeY[],TypeZ[],intl,intm,intr){//將有序的Z[l...m]與有序的Z[m+1...r]合并到Y(jié)[l...r]Type*a=&Z[l];Type*b=&Z[m+1];Type*c=&Y[l];intanum=m-l+1,ap=0;intbnum=r-m,bp=0;intcnum=r-l+1,cp=0;while(ap<anum&&bp<bnum){if(a[ap]<=b[bp])c[cp++]=a[ap++];elsec[cp++]=b[bp++];}while(ap<anum)c[cp++]=a[ap++];while(bp<bnum)c[cp++]=b[bp++];}template<classType>template<classType>voidMergeSort(Typea[],intn){intanum,bnum,i;Type*b,*c;if(n<=1)return;anum=n/2;b=a+anum;bnum=n-anum;MergeSort(a,anum);MergeSort(b,bnum);c=newType[n];Merge(c,a,0,anum-1,n-1);for(i=0;i<n;i++)a[i]=c[i];delete[]c;}template<classType>/*X存放輸入的點(diǎn)集,X和Y分別表示按照x坐標(biāo)和y坐標(biāo)排序的點(diǎn),l和r表示點(diǎn)集Y中成員p的范圍*/voidclosest(PointXX[],PointYY[],PointYZ[],intl,intr,PointX&a,PointX&b,double&d){doubled1,d2,d3,dp;intf,g,m,i,j,k;doubledr;PointXar,br;if(r-l==1)//2點(diǎn)的情況

{a=X[l];b=X[r];d=distance(X[l],X[r]);return;}/*X存放輸入的點(diǎn)集,X和Y分別表示按照x坐標(biāo)和y坐標(biāo)排序的if(r-l==2)//3點(diǎn)的情況

{d1=distance(X[l],X[l+1]);d2=distance(X[l+1],X[r]);d3=distance(X[l],X[r]);if(d1<=d2&&d1<=d3){a=X[l];b=X[l+1];d=d1;}elseif(d2<=d3){a=X[l+1];b=X[r];d=d2;}else{a=X[l];b=X[r];d=d3;}return;}if(r-l==2)//3點(diǎn)的情況m=(l+r)/2;//m為點(diǎn)集Y中成員p的范圍的中位數(shù)

/*將已經(jīng)按照y坐標(biāo)排序的點(diǎn)集Y[l..r],等分成兩個子集復(fù)制到Z,其中Z[l..(l+r)/2]中的每個點(diǎn)的x坐標(biāo)都小于Z[(l+r)/2+1..r]中的每個點(diǎn)的x坐標(biāo)*/f=l;g=m+1;for(i=l;i<=r;i++){if(Y[i].getp()>m)Z[g++]=Y[i];elseZ[f++]=Y[i];}m=(l+r)/2;//m為點(diǎn)集Y中成//遞歸處理這兩個子集(注意參數(shù)傳遞時Z與Y位置的變化)closest(X,Z,Y,l,m,a,b,d);closest(X,Z,Y,m+1,r,ar,br,dr);if(dr<d)//d表示這兩個子集中各自找到的最近點(diǎn)對的距離較小者

{a=ar;b=br;d=dr;}Merge(Y,Z,l,m,r);//重構(gòu)數(shù)組Y//將與分割線距離為d的點(diǎn)置如數(shù)組Z中

k=l;for(i=l;i<=r;i++){if(fabs(Y[m].getx()-Y[i].getx())<d)Z[k++]=Y[i];}//遞歸處理這兩個子集(注意參數(shù)傳遞時Z與Y位置的變//搜索Z[l..k-1],若其中存在兩點(diǎn)的距離小于d,則更新dfor(i=l;i<k;i++){for(j=i+1;j<k&&Z[j].gety()-Z[i].gety()<d;j++){dp=distance(Z[i],Z[j]);if(dp<d){d=dp;a=X[Z[i].getp()];b=X[Z[j].getp()];}}}}//搜索Z[l..k-1],若其中存在兩點(diǎn)的距離小于boolCpair2(PointXX[],intn,PointX&a,PointX&b,double&d){inti;PointY*Z,*Y;if(n<2)returnfalse;MergeSort(X,n);//將各點(diǎn)按照x坐標(biāo)排序

Y=newPointY[n];for(i=0;i<n;i++)//將數(shù)組X內(nèi)的信息寫入數(shù)組Y{Y[i].setp(i);//同一點(diǎn)在數(shù)組X中的坐標(biāo)的下標(biāo)

Y[i].setx(X[i].getx());Y[i].sety(X[i].gety());}MergeSort(Y,n);//將各點(diǎn)按照y坐標(biāo)排序

Z=newPointY[n];closest(X,Y,Z,0,n-1,a,b,d);delete[]Y;delete[]Z;returntrue;}boolCpair2(PointXX[],intn,int

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論