8 8.4O【安排 例8-1最大連續(xù)和。 8-1最大連續(xù)和tot=bestA[1];for(i=1;i<=n;i++)for(ji;jn;j++)A[i],…,A[j]intsum=0;for(ki;kj;k++)sum+=A[k];}if(sum> bestsum;}nnnT(n)n

(ji1)

(ni1)(ni2)n(n1)(nnn

8-2：基本操作的數(shù)量往往可以寫成關(guān)于“輸入規(guī)模”的表達(dá)式，保留最大項(xiàng)并提示8-3：確的。盡管如此，如果成功抓住了最主要的運(yùn)算量所在，算法分析的結(jié)果常常十分有用的。n3。這就是“上界分析。上界也有記號(hào)：T(n)=O(n3)。提示8-4：在算法設(shè)計(jì)中，常常不進(jìn)行精確分析，而是假定各種情況同時(shí)取到，8-2最大連續(xù)和S[0]=for(i=1;i<=n;i++)S[i]=S[i-1]+for(i=1;i<=n;for(ji;j<=n;j++)if(S[j]-S[i-1]>=best=S[j]-S[i-1];}}S[1],S[2],S[3]…,每個(gè)只“nnT(n)

(ni1)n(n2O(n2)。38-3最大連續(xù)和（3）（8-1intmaxsum(int*A,intx,inty){inti,m,v,L,R,max;if(y-x==1) returnA[x];//只有一個(gè)元素，直接返回m=x+(y-x)/2;//分治第一步：劃分成[x,m)和[m,y)maxmaxsum(A,x,m)maxsum(A,m,ymaxsum(A,x,m)：maxsum(A,m,y);v0;LA[m-1];（1）Lfor(i=m-1;i>=x;i--){v+=if(v>L)}v=0;R=A[m]; for(i=m;i<y;i++){v+=if(v> }if(L+R maxL+R;LRreturn}8-1ntotT(n)T(n)=2T(n/2)+n， 也稱為有效算法；而n!或者2n這樣的低效的算法稱為指數(shù)時(shí)間算法（exponential-time一是本身的精確性；二是對(duì)程序?qū)崿F(xiàn)細(xì)節(jié)與計(jì)算機(jī)硬件的依賴性。

n。8-28-4歸并排序（從小到大voidmerge_sort(int*A,intx,inty,int*T){if(y-x>1){intm=x+(y-x)/2; intp=x,q=m,i=x;merge_sort(A,x,mT);//遞歸求解merge_sort(A,m,yT);//遞歸求解while(p<m||q<y){if(q>=y||(p<m&&A[p]<=A[q]))//從左半數(shù)組到臨時(shí)空T[i++]= //從右半數(shù)組到臨時(shí)空T[i++]=}for(i=x;i<y;i++)A[i]= //從輔助空間到A數(shù)}}如果第二個(gè)序列為空（此時(shí)第一個(gè)序列一定非空），A[p]A[p]。 例8-2逆序?qū)?shù)。 給一列a1,a2,…,an，求它的逆序?qū)?shù)，即有多少個(gè)有序?qū)?i,j)，使得i<j但ai>aj。np（左邊所剩的元素在區(qū)間[p,mm-。#includeintA[]=intT[]=voidinverse_pair(int*A,intx,inty,int*cnt,int*T){if(y-x>1){intm=x+(y-x)/2; intp=x,q=m,i=x;inverse_pair(A,x,m,cnt,T);//遞歸求解inverse_pair(A,m,y,cnt,T);//遞歸求解while(p<m||q<y){if(q>=y||(p<m&&A[p]<=A[q]))/從左半數(shù)組到臨時(shí)空T[i++]=else T[i++]=*cnt+=m-p; }}for(i=x;i<y; A[i]= //從輔助空間到A數(shù)}}intinti,cnt=0;;inverse_pair(A,0,6,&cnt,T);printf("%d\n",cnt);return} 例8-3第k小的數(shù)。 （1≤k≤n，O(n)。#include<iostream>#include<cmath>usingnamespacestd;constintN=100;intPartition(inta[Nintlow,inthigh){inti=intj=high+1;intx=a[low];while(a[++i]<while(a[--j]>x);if(i>=j)break;swap(a[i],a[j]);}a[low]=a[j];a[j]=x;returnj;}intSelect_k(inta[N],intlow,inthigh,intintq=intposq- k-1high-low returna[low]; returna[q];elseif(k<pos)returnSelect_k(a,low,q-1,k);return}

returnSelect_k(a,q+1,high,k- int{intlow,q,high,n,i,k,highes,a[N];for(i=0;i<n;i++)}return}在有序表中查找元素常常使用二分查找（BinarySearch），有時(shí)也譯為“折半查找”。它midhigh8-7：逐步縮小范圍法是一種常見的思維方法。二分查找便是基于這種思路，它8-5二分查找（迭代實(shí)現(xiàn)#include<stdio.h>#includeintA[]=intbsearch(int*A,intx,inty,intv)（迭代）intm;while(x<y){m=x+(y-x)/2;if(A[m]==v) returnm;elseif(A[m]>v) y=m;elsex=m+1;}return-}intmain(){inti;for(i=1;i<=11;i++)assert(bsearch(A,0,11,i)==i-1);return0;}8-6二分查找求下界intlower_bound(int*A,intx,inty,intv){intm;while(x<y){m=x+(y-x)/2; }return}x,x+1,x+2,…,y-1，還可能是候選區(qū)間卻是閉區(qū)間[x,y]。A[mv全部往后移動(dòng)一個(gè)位置）后序列仍然有序。upper_boundintupper_bound(int*A,intx,inty,intv){intm;while(x<y){m=x+(y-if(A[m]<=v)x=m+1;elsey=m;}return}vL=R，區(qū)間為空。 例8-4范圍統(tǒng)計(jì)。 1：aLalower_boundaL=n，相當(dāng)于把不存在的元素看作無(wú)窮大。bR=0，相當(dāng)于把不存在的元素看作無(wú)窮大。#include#includealgorithm>//STLsort,lower_boundupper_boundusingnamespacestd;intv[10000];intmain(){intn,m,a,b;scanf("%d%d",&n,&m);for(inti0;ini++)scanf("%d",&v[i]);sort(v,v+n); for(inti=0;i<m;scanf("%d%d",&a,&b); printf("%d\n",upper_bound(v,v+n,b)-lower_bound(v,v+n,a));}}

3L能同時(shí)被兩個(gè)或骨牌覆蓋。如圖8-3所示為L(zhǎng)型骨牌（三格板）的4種旋轉(zhuǎn)方式。① ② ③ ④8-3L方格，且任何2個(gè)L型骨牌不得。，，立求解了。當(dāng)使用一個(gè)①號(hào)三格板（圖中陰影）2、3、432、3、412殘12殘3412殘①34 8-44×43（8-5312殘12殘②341212③④殘4343殘 8-54×4Board[][]來(lái)模擬棋盤，Board[1][1]是棋盤的左上角方格。titleL0。覆蓋殘缺棋盤所需要的三格板數(shù)目為：(size2-1)/3。將這8-58-6(b0，相同數(shù)字的為同一骨牌。殘 2殘2233021341154455 8-64×4#include<iostream>usingnamespacestd;constintN=11;intBoard[N][N];inttile=dcsizevoidChessBoard(inttr,inttc,intdr,intdc,int{if(size==intt=++tile,s=if(dr<tr+s&&dc<tc+s)ChessBoard(tr,tc,dr,dc,s); tLBoard[tr+s-1][tc+s-1]=ChessBoard(tr,tc,tr+s-1,tc+s-1,}if(dr<tr+s&&dc>=tc+s)ChessBoard(tr,tc+s,dr,dc,s);else{Board[tr+s-1][tc+s]=t;ChessBoard(tr,tc+s,tr+s-1,tc+s,s);}if(dr>=tr+s&&dc<tc+s)ChessBoard(tr+s,tc,dr,dc,s); Board[tr+s][tc+s-1]=ChessBoard(tr+s,tc,tr+s,tc+s-1,}if(dr>=tr+s&&dc>=tc+s)ChessBoard(tr+s,tc+s,dr,dc,s);else{Board[tr+s][tc+s]=t;ChessBoard(tr+s,tc+s,tr+s,tc+s,s);}}voidDisyBoard(intsize){for(inti=1;i<=size;++i){for(intj=1;j<=size;++j)printf("%2d",Board[i][j]);}}int{ChessBoard(1,1,2,1,4);return}nn-1i行第j列為第ij12345678278564323465872876543218-7k=3#include<iostream>usingnamespacestd;intvoidCreattable(intr1,intc1,intr2,intc2,intsize){inti,j; inthalfsize=size/2; for(j=0;j<size;j++)halfsizeif(i<halfsize&&(j>=halfsize&&j<size))if((i>=halfsize&&i<size)&&if((i>=halfsize&&i<size)&&(j>=halfsize&&j<size))}}intmain(){inti,j,k,n=1; cout<<"運(yùn)動(dòng)員"<<table[i][0]<<cout<<table[i][j]<<"";}return}8.3.3的鬼，向其發(fā)送質(zhì)子流消滅它。質(zhì)子流由巨人發(fā)射，沿直線行進(jìn)，遇到鬼后。由于質(zhì)子流交叉是很的所有質(zhì)子流經(jīng)過(guò)的線段不能有交點(diǎn)請(qǐng)?jiān)O(shè)計(jì)一種給巨人和鬼配對(duì)的方法8-8(a)所示。8-8(b)所示。這個(gè)配對(duì)過(guò)程是遞歸的，好比棋盤覆蓋中一樣。不會(huì)找不到這樣的配對(duì)區(qū)1。因此“從少到多”的過(guò)程中一定會(huì)有“一樣多”的時(shí)候。abc（按復(fù)利x，a(1+x)-cbxa=2000，b=4，c=510intmain(){doublea,c,x=0,y=100;inti,b;scanf("%lf%d%lf",&a,&b,&c);while(y-x>1e-5){doublem=x+(y-x)/2;doublef=a;for(i=0;i<b;i++)f+=f*m/100.0-c;if(f<0)x=m;elsey=m;}printf("%.3lf%%\n",x);return0;}nm（每個(gè)正整數(shù)恰好屬于一個(gè)序232543123|25|4S(1)、S(2)、S(36109。xP(x)計(jì)算，每次盡量往右劃分即可。二分最小值xP(x)MO(logM)，P(xO(n)（從左到右掃描一次即可O(nlogM)。#include<iostream>#include<ctime>usingnamespacestd;#defineN10#defineINFintjuge(inta[],intmid,int{intintseg=0;int{if(sum>mid){}} return0;return}intvalue(inta[],intlow,inthigh,int {returnhigh+1;{int 半returnvalue(a,low,mid- return}}int{inta[N];for(intifor=0;ifor<N;ifor++)cout<<a[ifor]<<"";//intintm=3;intmin=INF,max=0;for(inti=0;i<N&&a[i]!='{}int return}8.4貪心niwiC#include<stdio.h>#defineN100intvoidSort(intw[],intt[],intn)wt[i]wiwintfor(i=1;i<=n;i++)w1w for(i=1;i<n;i++){ if(k!=j)wt//排序完成后，t[iiw（標(biāo)}}}voidLoading(intx[],intw[],intc,intn){inti;Sort(w,t,n);//對(duì)數(shù)組wtw xfor(i=1;i<=n&&w[t[i]]<=c;i++)}}intinti,n,c;intwhile(scanf("%d%d",&n,&c)!=EOF)n,總重量{for(i=1;i<=n;i++)wfor(i=1;i<=n;i++){max+=w[i]*x[i];}}} 125 1612923845110217168180 1 選擇物體的最大總重量為n個(gè)物體,第iwiviCC。由C，而且除了最后一個(gè)以外，所有的物體要么不拿，要么拿走全部。#include<stdio.h>#include<iostream>#defineMAXSIZE100#defineM15//背包的載荷能力usingnamespacestd;//算法，貪心算voidGREEDY(floatw[],floatx[],intsortResult[],int{floatc=M;inti=0;inttemp=0;for(i0;in;i++)x[i]=0;for(i=0;i<n;i++) for(intj=0;j<n;j++) tempj;//得到取物體的順序}if(w[temp]>c) }x[temp]1;/cw[temp];//}if(in)//x[temp]=c/w[temp]; }voidsort(floatx[],intsortResult[],int{inti=0,j=0;intindex=0,k=0;for(i0;in;i++)/0sortResult[i]=0;for(i=0;i<n;i++) floattemp=0;index=for(j=0;j<n;j++) if((temp<x[j])&&(sortResult[j]==0)) temp=x[j];index=}}if(sortResult[index]==0)sortResult[index]=}for(i=0;i<n;i++) }voidgetData(floatp[],floatw[],int*n){inti=0;printf("pleaseinputthetotalcountofobject:");scanf("%d",n);printf("Pleaseinputarrayofp:\n");for(i=0;i<(*n);i++)scanf("%f",printf("Nowpleaseinputarrayofw:\n");for(i=0;i<(*n);i++)scanf("%f",&w[i]);}voidoutput(floatx[],int{intprintf("\n\nafterarithmeticdata:advisemethod\n");for(i=0;i<n;i++)printf("x[%d]\t",i);for(i=0;i<n;i++)printf("%2.3f\t",x[i]);}int{floatp[MAXSIZE],w[MAXSIZE],inti=0,n=intsortResult[MAXSIZE];getData(p,w,&n); for(i=0;i<