算法大全(數(shù)據(jù)結(jié)構(gòu))

算法大全（C，C++）數(shù)論算法1．求兩數(shù)的最大公約數(shù)functiongcd(a,b:integer):integer;beginifb=0thengcd:=aelsegcd:=gcd(b,amodb);end;2．求兩數(shù)的最小公倍數(shù)functionlcm(a,b:integer):integer;beginifa<bthenswap(a,b);lcm:=a;whilelcmmodb>0doinc(lcm,a);end;3．素?cái)?shù)的求法A.小范圍內(nèi)判斷一個(gè)數(shù)是否為質(zhì)數(shù)：functionprime(n:integer):Boolean;varI:integer;beginforI:=2totrunc(sqrt(n))doifnmodI=0thenbeginprime:=false;exit;end;prime:=true;end;B.判斷l(xiāng)ongint范圍內(nèi)的數(shù)是否為素?cái)?shù)（包含求50000以內(nèi)的素?cái)?shù)表）：proceduregetprime;vari,j:longint;p:array[1..50000]ofboolean;beginfillchar(p,sizeof(p),true);p[1]:=false;i:=2;whilei<50000dobeginifp[i]thenbeginj:=i*2;whilej<50000dobeginp[j]:=false;inc(j,i);end;end;inc(i);end;l:=0;fori:=1to50000doifp[i]thenbegininc(l);pr[l]:=i;end;end;{getprime}functionprime(x:longint):integer;vari:integer;beginprime:=false;fori:=1toldoifpr[i]>=xthenbreakelseifxmodpr[i]=0thenexit;prime:=true;end;{prime}二、圖論算法1．最小生成樹A.Prim算法：procedureprim(v0:integer);varlowcost,closest:array[1..maxn]ofinteger;i,j,k,min:integer;beginfori:=1tondobeginlowcost[i]:=cost[v0,i];closest[i]:=v0;end;fori:=1ton-1dobegin{尋找離生成樹最近的未加入頂點(diǎn)k}min:=maxlongint;forj:=1tondoif(lowcost[j]<min)and(lowcost[j]<>0)thenbeginmin:=lowcost[j];k:=j;end;lowcost[k]:=0;{將頂點(diǎn)k加入生成樹}{生成樹中增加一條新的邊k到closest[k]}{修正各點(diǎn)的lowcost和closest值}forj:=1tondoifcost[k,j]<lwocost[j]thenbeginlowcost[j]:=cost[k,j];closest[j]:=k;end;end;end;{prim}B.Kruskal算法：(貪心)按權(quán)值遞增順序刪去圖中的邊，若不形成回路則將此邊加入最小生成樹。functionfind(v:integer):integer;{返回頂點(diǎn)v所在的集合}vari:integer;begini:=1;while(i<=n)and(notvinvset[i])doinc(i);ifi<=nthenfind:=ielsefind:=0;end;procedurekruskal;vartot,i,j:integer;beginfori:=1tondovset[i]:=[i];{初始化定義n個(gè)集合，第I個(gè)集合包含一個(gè)元素I}p:=n-1;q:=1;tot:=0;{p為尚待加入的邊數(shù)，q為邊集指針}sort;{對所有邊按權(quán)值遞增排序，存于e[I]中，e[I].v1與e[I].v2為邊I所連接的兩個(gè)頂點(diǎn)的序號，e[I].len為第I條邊的長度}whilep>0dobegini:=find(e[q].v1);j:=find(e[q].v2);ifi<>jthenbegininc(tot,e[q].len);vset[i]:=vset[i]+vset[j];vset[j]:=[];dec(p);end;inc(q);end;writeln(tot);end;2.最短路徑A.標(biāo)號法求解單源點(diǎn)最短路徑：vara:array[1..maxn,1..maxn]ofinteger;b:array[1..maxn]ofinteger;{b[i]指頂點(diǎn)i到源點(diǎn)的最短路徑}mark:array[1..maxn]ofboolean;procedurebhf;varbest,best_j:integer;beginfillchar(mark,sizeof(mark),false);mark[1]:=true;b[1]:=0;{1為源點(diǎn)}repeatbest:=0;fori:=1tondoIfmark[i]then{對每一個(gè)已計(jì)算出最短路徑的點(diǎn)}forj:=1tondoif(notmark[j])and(a[i,j]>0)thenif(best=0)or(b[i]+a[i,j]<best)thenbeginbest:=b[i]+a[i,j];best_j:=j;end;ifbest>0thenbeginb[best_j]:=best；mark[best_j]:=true;end;untilbest=0;end;{bhf}B.Floyed算法求解所有頂點(diǎn)對之間的最短路徑：procedurefloyed;beginforI:=1tondoforj:=1tondoifa[I,j]>0thenp[I,j]:=Ielsep[I,j]:=0;{p[I,j]表示I到j(luò)的最短路徑上j的前驅(qū)結(jié)點(diǎn)}fork:=1tondo{枚舉中間結(jié)點(diǎn)}fori:=1tondoforj:=1tondoifa[i,k]+a[j,k]<a[i,j]thenbegina[i,j]:=a[i,k]+a[k,j];p[I,j]:=p[k,j];end;end;C.Dijkstra算法：vara:array[1..maxn,1..maxn]ofinteger;b,pre:array[1..maxn]ofinteger;{pre[i]指最短路徑上I的前驅(qū)結(jié)點(diǎn)}mark:array[1..maxn]ofboolean;proceduredijkstra(v0:integer);beginfillchar(mark,sizeof(mark),false);fori:=1tondobegind[i]:=a[v0,i];ifd[i]<>0thenpre[i]:=v0elsepre[i]:=0;end;mark[v0]:=true;repeat{每循環(huán)一次加入一個(gè)離1集合最近的結(jié)點(diǎn)并調(diào)整其他結(jié)點(diǎn)的參數(shù)}min:=maxint;u:=0;{u記錄離1集合最近的結(jié)點(diǎn)}fori:=1tondoif(notmark[i])and(d[i]<min)thenbeginu:=i;min:=d[i];end;ifu<>0thenbeginmark[u]:=true;fori:=1tondoif(notmark[i])and(a[u,i]+d[u]<d[i])thenbegind[i]:=a[u,i]+d[u];pre[i]:=u;end;end;untilu=0;end;3.計(jì)算圖的傳遞閉包ProcedureLonglink;VarT:array[1..maxn,1..maxn]ofboolean;BeginFillchar(t,sizeof(t),false);Fork:=1tondoForI:=1tondoForj:=1tondoT[I,j]:=t[I,j]or(t[I,k]andt[k,j]);End;4．無向圖的連通分量A.深度優(yōu)先proceduredfs(now,color:integer);beginfori:=1tondoifa[now,i]andc[i]=0thenbegin{對結(jié)點(diǎn)I染色}c[i]:=color;dfs(I,color);end;end;B寬度優(yōu)先（種子染色法）5．關(guān)鍵路徑幾個(gè)定義：頂點(diǎn)1為源點(diǎn)，n為匯點(diǎn)。a.頂點(diǎn)事件最早發(fā)生時(shí)間Ve[j],Ve[j]=max{Ve[j]+w[I,j]},其中Ve(1)=0;b.頂點(diǎn)事件最晚發(fā)生時(shí)間Vl[j],Vl[j]=min{Vl[j]–w[I,j]},其中Vl(n)=Ve(n);c.邊活動最早開始時(shí)間Ee[I],若邊I由<j,k>表示，則Ee[I]=Ve[j];d.邊活動最晚開始時(shí)間El[I],若邊I由<j,k>表示，則El[I]=Vl[k]–w[j,k];若Ee[j]=El[j]，則活動j為關(guān)鍵活動，由關(guān)鍵活動組成的路徑為關(guān)鍵路徑。求解方法：a.從源點(diǎn)起topsort,判斷是否有回路并計(jì)算Ve;b.從匯點(diǎn)起topsort,求Vl;c.算Ee和El;6．拓?fù)渑判蛘胰攵葹?的點(diǎn)，刪去與其相連的所有邊，不斷重復(fù)這一過程。例尋找一數(shù)列，其中任意連續(xù)p項(xiàng)之和為正，任意q項(xiàng)之和為負(fù)，若不存在則輸出NO.7.回路問題Euler回路(DFS)定義：經(jīng)過圖的每條邊僅一次的回路。（充要條件：圖連同且無奇點(diǎn)）Hamilton回路定義：經(jīng)過圖的每個(gè)頂點(diǎn)僅一次的回路。一筆畫充要條件：圖連通且奇點(diǎn)個(gè)數(shù)為0個(gè)或2個(gè)。9．判斷圖中是否有負(fù)權(quán)回路Bellman-ford算法x[I],y[I],t[I]分別表示第I條邊的起點(diǎn)，終點(diǎn)和權(quán)。共n個(gè)結(jié)點(diǎn)和m條邊。procedurebellman-fordbeginforI:=0ton-1dod[I]:=+infinitive;d[0]:=0;forI:=1ton-1doforj:=1tomdo{枚舉每一條邊}ifd[x[j]]+t[j]<d[y[j]]thend[y[j]]:=d[x[j]]+t[j];forI:=1tomdoifd[x[j]]+t[j]<d[y[j]]thenreturnfalseelsereturntrue;end;10．第n最短路徑問題*第二最短路徑：每舉最短路徑上的每條邊，每次刪除一條，然后求新圖的最短路徑，取這些路徑中最短的一條即為第二最短路徑。*同理，第n最短路徑可在求解第n-1最短路徑的基礎(chǔ)上求解。三、背包問題*部分背包問題可有貪心法求解：計(jì)算Pi/Wi數(shù)據(jù)結(jié)構(gòu)：w[i]:第i個(gè)背包的重量；p[i]:第i個(gè)背包的價(jià)值；1．0-1背包：每個(gè)背包只能使用一次或有限次(可轉(zhuǎn)化為一次)：A.求最多可放入的重量。NOIP2001裝箱問題有一個(gè)箱子容量為v(正整數(shù)，o≤v≤20000)，同時(shí)有n個(gè)物品(o≤n≤30)，每個(gè)物品有一個(gè)體積(正整數(shù))。要求從n個(gè)物品中，任取若千個(gè)裝入箱內(nèi)，使箱子的剩余空間為最小。l搜索方法proceduresearch(k,v:integer);{搜索第k個(gè)物品，剩余空間為v}vari,j:integer;beginifv<bestthenbest:=v;ifv-(s[n]-s[k-1])>=bestthenexit;{s[n]為前n個(gè)物品的重量和}ifk<=nthenbeginifv>w[k]thensearch(k+1,v-w[k]);search(k+1,v);end;end;lDPF[I,j]為前i個(gè)物品中選擇若干個(gè)放入使其體積正好為j的標(biāo)志，為布爾型。實(shí)現(xiàn):將最優(yōu)化問題轉(zhuǎn)化為判定性問題f[I,j]=f[i-1,j-w[i]](w[I]<=j<=v)邊界：f[0,0]:=true.ForI:=1tondoForj:=w[I]tovdoF[I,j]:=f[I-1,j-w[I]];優(yōu)化：當(dāng)前狀態(tài)只與前一階段狀態(tài)有關(guān)，可降至一維。F[0]:=true;ForI:=1tondobeginF1:=f;Forj:=w[I]tovdoIff[j-w[I]]thenf1[j]:=true;F:=f1;End;B.求可以放入的最大價(jià)值。F[I,j]為容量為I時(shí)取前j個(gè)背包所能獲得的最大價(jià)值。F[i,j]=max{f[i–w[j],j-1]+p[j],f[i,j-1]}C.求恰好裝滿的情況數(shù)。DP:Procedureupdate;varj,k:integer;beginc:=a;forj:=0tondoifa[j]>0thenifj+now<=ntheninc(c[j+now],a[j]);a:=c;end;2．可重復(fù)背包A求最多可放入的重量。F[I,j]為前i個(gè)物品中選擇若干個(gè)放入使其體積正好為j的標(biāo)志，為布爾型。狀態(tài)轉(zhuǎn)移方程為f[I,j]=f[I-1,j–w[I]*k](k=1..jdivw[I])B.求可以放入的最大價(jià)值。USACO1.2ScoreInflation進(jìn)行一次競賽，總時(shí)間T固定，有若干種可選擇的題目，每種題目可選入的數(shù)量不限，每種題目有一個(gè)ti（解答此題所需的時(shí)間）和一個(gè)si（解答此題所得的分?jǐn)?shù)），現(xiàn)要選擇若干題目，使解這些題的總時(shí)間在T以內(nèi)的前提下，所得的總分最大，求最大的得分。*易想到：f[i,j]=max{f[i-k*w[j],j-1]+k*p[j]}(0<=k<=idivw[j])其中f[i,j]表示容量為i時(shí)取前j種背包所能達(dá)到的最大值。*實(shí)現(xiàn)：BeginFillChar(f,SizeOf(f),0);Fori:=1ToMDoForj:=1ToNDoIfi-problem[j].time>=0ThenBegint:=problem[j].point+f[i-problem[j].time];Ift>f[i]Thenf[i]:=t;End;Writeln(f[M]);End.C.求恰好裝滿的情況數(shù)。Ahoi2001Problem2求自然數(shù)n本質(zhì)不同的質(zhì)數(shù)和的表達(dá)式的數(shù)目。思路一，生成每個(gè)質(zhì)數(shù)的系數(shù)的排列，在一一測試，這是通法。proceduretry(dep:integer);vari,j:integer;begincal;{此過程計(jì)算當(dāng)前系數(shù)的計(jì)算結(jié)果，now為結(jié)果}ifnow>nthenexit;{剪枝}ifdep=l+1thenbegin{生成所有系數(shù)}cal;ifnow=ntheninc(tot);exit;end;fori:=0tondivpr[dep]dobeginxs[dep]:=i;try(dep+1);xs[dep]:=0;end;end;思路二，遞歸搜索效率較高proceduretry(dep,rest:integer);vari,j,x:integer;beginif(rest<=0)or(dep=l+1)thenbeginifrest=0theninc(tot);exit;end;fori:=0torestdivpr[dep]dotry(dep+1,rest-pr[dep]*i);end;{main:try(1,n);}思路三：可使用動態(tài)規(guī)劃求解USACO1.2moneysystemV個(gè)物品，背包容量為n，求放法總數(shù)。轉(zhuǎn)移方程：Procedureupdate;varj,k:integer;beginc:=a;forj:=0tondoifa[j]>0thenfork:=1tondivnowdoifj+now*k<=ntheninc(c[j+now*k],a[j]);a:=c;end;{main}beginread(now);{讀入第一個(gè)物品的重量}i:=0;{a[i]為背包容量為i時(shí)的放法總數(shù)}whilei<=ndobegina[i]:=1;inc(i,now);end;{定義第一個(gè)物品重的整數(shù)倍的重量a值為1，作為初值}fori:=2tovdobeginread(now);update;{動態(tài)更新}end;writeln(a[n]);四、排序算法A.快速排序：procedureqsort(l,r:integer);vari,j,mid:integer;begini:=l;j:=r;mid:=a[(l+r)div2];{將當(dāng)前序列在中間位置的數(shù)定義為中間數(shù)}repeatwhilea[i]<middoinc(i);{在左半部分尋找比中間數(shù)大的數(shù)}whilea[j]>middodec(j);{在右半部分尋找比中間數(shù)小的數(shù)}ifi<=jthenbegin{若找到一組與排序目標(biāo)不一致的數(shù)對則交換它們}swap(a[i],a[j]);inc(i);dec(j);{繼續(xù)找}end;untili>j;ifl<jthenqsort(l,j);{若未到兩個(gè)數(shù)的邊界，則遞歸搜索左右區(qū)間}ifi<rthenqsort(i,r);end;{sort}B.插入排序：思路：當(dāng)前a[1]..a[i-1]已排好序了，現(xiàn)要插入a[i]使a[1]..a[i]有序。procedureinsert_sort;vari,j:integer;beginfori:=2tondobegina[0]:=a[i];j:=i-1;whilea[0]<a[j]dobegina[j+1]:=a[j];j:=j-1;end;a[j+1]:=a[0];end;end;{inset_sort}C.選擇排序：proceduresort;vari,j,k:integer;beginfori:=1ton-1doforj:=i+1tondoifa[i]>a[j]thenswap(a[i],a[j]);end;D.冒泡排序procedurebubble_sort;vari,j,k:integer;beginfori:=1ton-1doforj:=ndowntoi+1doifa[j]<a[j-1]thenswap(a[j],a[j-1]);{每次比較相鄰元素的關(guān)系}end;E.堆排序：proceduresift(i,m:integer);{調(diào)整以i為根的子樹成為堆,m為結(jié)點(diǎn)總數(shù)}vark:integer;begina[0]:=a[i];k:=2*i;{在完全二叉樹中結(jié)點(diǎn)i的左孩子為2*i,右孩子為2*i+1}whilek<=mdobeginif(k<m)and(a[k]<a[k+1])theninc(k);{找出a[k]與a[k+1]中較大值}ifa[0]<a[k]thenbegina[i]:=a[k];i:=k;k:=2*i;endelsek:=m+1;end;a[i]:=a[0];{將根放在合適的位置}end;procedureheapsort;varj:integer;beginforj:=ndiv2downto1dosift(j,n);forj:=ndownto2dobeginswap(a[1],a[j]);sift(1,j-1);end;end;F.歸并排序{a為序列表，tmp為輔助數(shù)組}proceduremerge(vara:listtype;p,q,r:integer);{將已排序好的子序列a[p..q]與a[q+1..r]合并為有序的tmp[p..r]}varI,j,t:integer;tmp:listtype;begint:=p;i:=p;j:=q+1;{t為tmp指針，I,j分別為左右子序列的指針}while(t<=r)dobeginif(i<=q){左序列有剩余}and((j>r)or(a[i]<=a[j])){滿足取左邊序列當(dāng)前元素的要求}thenbegintmp[t]:=a[i];inc(i);endelsebegintmp[t]:=a[j];inc(j);end;inc(t);end;fori:=ptordoa[i]:=tmp[i];end;{merge}proceduremerge_sort(vara:listtype;p,r:integer);{合并排序a[p..r]}varq:integer;beginifp<>rthenbeginq:=(p+r-1)div2;merge_sort(a,p,q);merge_sort(a,q+1,r);merge(a,p,q,r);end;end;{main}beginmerge_sort(a,1,n);end.G.基數(shù)排序思想：對每個(gè)元素按從低位到高位對每一位進(jìn)行一次排序五、高精度計(jì)算高精度數(shù)的定義：typehp=array[1..maxlen]ofinteger;1．高精度加法procedureplus(a,b:hp;varc:hp);vari,len:integer;beginfillchar(c,sizeof(c),0);ifa[0]>b[0]thenlen:=a[0]elselen:=b[0];fori:=1tolendobegininc(c[i],a[i]+b[i]);ifc[i]>10thenbegindec(c[i],10);inc(c[i+1]);end;{進(jìn)位}end;ifc[len+1]>0theninc(len);c[0]:=len;end;{plus}2．高精度減法proceduresubstract(a,b:hp;varc:hp);vari,len:integer;beginfillchar(c,sizeof(c),0);ifa[0]>b[0]thenlen:=a[0]elselen:=b[0];fori:=1tolendobegininc(c[i],a[i]-b[i]);ifc[i]<0thenbegininc(c[i],10);dec(c[i+1]);end;while(len>1)and(c[len]=0)dodec(len);c[0]:=len;end;3．高精度乘以低精度proceduremultiply(a:hp;b:longint;varc:hp);vari,len:integer;beginfillchar(c,sizeof(c),0);len:=a[0];fori:=1tolendobegininc(c[i],a[i]*b);inc(c[i+1],(a[i]*b)div10);c[i]:=c[i]mod10;end;inc(len);while(c[len]>=10)dobegin{處理最高位的進(jìn)位}c[len+1]:=c[len]div10;c[len]:=c[len]mod10;inc(len);end;while(len>1)and(c[len]=0)dodec(len);{若不需進(jìn)位則調(diào)整len}c[0]:=len;end;{multiply}4．高精度乘以高精度procedurehigh_multiply(a,b:hp;varc:hp}vari,j,len:integer;beginfillchar(c,sizeof(c),0);fori:=1toa[0]doforj:=1tob[0]dobegininc(c[i+j-1],a[i]*b[j]);inc(c[i+j],c[i+j-1]div10);c[i+j-1]:=c[i+j-1]mod10;end;len:=a[0]+b[0]+1;while(len>1)and(c[len]=0)dodec(len);c[0]:=len;end;5．高精度除以低精度proceduredevide(a:hp;b:longint;varc:hp;vard:longint);{c:=adivb;d:=amodb}vari,len:integer;beginfillchar(c,sizeof(c),0);len:=a[0];d:=0;fori:=lendownto1dobegind:=d*10+a[i];c[i]:=ddivb;d:=dmodb;end;while(len>1)and(c[len]=0)thendec(len);c[0]:=len;end;6．高精度除以高精度procedurehigh_devide(a,b:hp;varc,d:hp);vari,len:integer;beginfillchar(c,sizeof(c),0);fillchar(d,sizeof(d),0);len:=a[0];d[0]:=1;fori:=lendownto1dobeginmultiply(d,10,d);d[1]:=a[i];while(compare(d,b)>=0)do{即d>=b}beginSubtract(d,b,d);inc(c[i]);end;end;while(len>1)and(c.s[len]=0)dodec(len);c.len:=len;end;六、樹的遍歷1．已知前序中序求后序procedureSolve(pre,mid:string);vari:integer;beginif(pre='''')or(mid='''')thenexit;i:=pos(pre[1],mid);solve(copy(pre,2,i),copy(mid,1,i-1));solve(copy(pre,i+1,length(pre)-i),copy(mid,i+1,length(mid)-i));post:=post+pre[1];{加上根，遞歸結(jié)束后post即為后序遍歷}end;2．已知中序后序求前序procedureSolve(mid,post:string);vari:integer;beginif(mid='''')or(post='''')thenexit;i:=pos(post[length(post)],mid);pre:=pre+post[length(post)];{加上根，遞歸結(jié)束后pre即為前序遍歷}solve(copy(mid,1,I-1),copy(post,1,I-1));solve(copy(mid,I+1,length(mid)-I),copy(post,I,length(post)-i));end;3．已知前序后序求中序的一種functionok(s1,s2:string):boolean;vari,l:integer;p:boolean;beginok:=true;l:=length(s1);fori:=1toldobeginp:=false;forj:=1toldoifs1[i]=s2[j]thenp:=true;ifnotpthenbeginok:=false;exit;end;end;end;proceduresolve(pre,post:string);vari:integer;beginif(pre='''')or(post='''')thenexit;i:=0;repeatinc(i);untilok(copy(pre,2,i),copy(post,1,i));solve(copy(pre,2,i),copy(post,1,i));midstr:=midstr+pre[1];solve(copy(pre,i+2,length(pre)-i-1),copy(post,i+1,length(post)-i-1));end;七進(jìn)制轉(zhuǎn)換1.任意正整數(shù)進(jìn)制間的互化除n取余2.實(shí)數(shù)任意正整數(shù)進(jìn)制間的互化乘n取整3.負(fù)數(shù)進(jìn)制：設(shè)計(jì)一個(gè)程序，讀入一個(gè)十進(jìn)制數(shù)的基數(shù)和一個(gè)負(fù)進(jìn)制數(shù)的基數(shù)，并將此十進(jìn)制數(shù)轉(zhuǎn)換為此負(fù)進(jìn)制下的數(shù)：-R∈{-2，-3，-4,....-20}八全排列與組合的生成1.排列的生成：（1..n）proceduresolve(dep:integer);vari:integer;beginifdep=n+1thenbeginwriteln(s);exit;end;fori:=1tondoifnotused[i]thenbegins:=s+chr(i+ord(''0''));used[i]:=true;solve(dep+1);s:=copy(s,1,length(s)-1);used[i]:=false;end;end;2.組合的生成(1..n中選取k個(gè)數(shù)的所有方案)proceduresolve(dep,pre:integer);vari:integer;beginifdep=k+1thenbeginwriteln(s);exit;end;fori:=1tondoif(notused[i])and(i>pre)thenbegins:=s+chr(i+ord(''0''));used[i]:=true;solve(dep+1,i);s:=copy(s,1,length(s)-1);used[i]:=false;end;end;九.查找算法1.折半查找functionbinsearch(k:keytype):integer;varlow,hig,mid:integer;beginlow:=1;hig:=n;mid:=(low+hig)div2;while(a[mid].key<>k)and(low<=hig)dobeginifa[mid].key>kthenhig:=mid-1elselow:=mid+1;mid:=(low+hig)div2;end;iflow>higthenmid:=0;binsearch:=mid;end;2.樹形查找二叉排序樹：每個(gè)結(jié)點(diǎn)的值都大于其左子樹任一結(jié)點(diǎn)的值而小于其右子樹任一結(jié)點(diǎn)的值。查找functiontreesrh(k:keytype):pointer;varq:pointer;beginq:=root;while(q<>nil)and(q^.key<>k)doifk<q^.keythenq:=q^.leftelseq:=q^.right;treesrh:=q;end;十、貪心*會議問題（1）n個(gè)活動每個(gè)活動有一個(gè)開始時(shí)間和一個(gè)結(jié)束時(shí)間，任一時(shí)刻僅一項(xiàng)活動進(jìn)行，求滿足活動數(shù)最多的情況。解：按每項(xiàng)活動的結(jié)束時(shí)間進(jìn)行排序，排在前面的優(yōu)先滿足。（2）會議室空閑時(shí)間最少。（3）每個(gè)客戶有一個(gè)愿付的租金，求最大利潤。（4）共R間會議室，第i個(gè)客戶需使用i間會議室，費(fèi)用相同，求最大利潤。十一、回溯法框架1.n皇后問題proceduretry(i:byte);varj:byte;beginifi=n+1thenbeginprint;exit;end;forj:=1tondoifa[i]andb[j+i]andc[j-i]thenbeginx[i]:=j;a[j]:=false;b[j+i]:=false;c[j-i]:=false;try(i+1);啊撒打算工a[j]:=true;b[i+j]:=true;c[j-i]:=true;end;end;工基苛基基本原理工基本原理基本原理as在莽工左基基本原理棋打算打算苛奇萊苛打算打算打算左左苛苛打算打算打算苛在棋基本原理苛打算榛莽在2.HanoiTower漢諾塔苛基本原理阿達(dá)撒基本原理工大大枯工苛幵二大專生一大起大落二地奎屯在博大需二大起大落亙古未有地亙古未有地素面朝天原封不動dsgh(n)=2*h(n-1)+1h(1)=1原封不動要基棋棋基本原理初始所有銅片都在a柱上procedurehanoi(n,a,b,c:byte);{將第n塊銅片從a柱通過b柱移到c柱上}begin打算打算打算ifn=0thenexit;hanoi(n-1,a,c,b);{將上面的n-1塊從a柱通過c柱移到b柱上}write(n,’movedfrom’,a,’to’,c);hanoi(n-1,b,a,c);{將b上的n-1塊從b柱通過a柱移到c柱上end;dadasdasdasdasdasdasdasdasdaasdasdas按時(shí)的按時(shí)的按時(shí)暗暗上大蘇打初始銅片分布在3個(gè)柱上，給定目標(biāo)柱goalh[1..3,0..n]存放三個(gè)柱的狀態(tài)，now與nowp存最大的不到位的銅片的柱號和編號,h[I,0]存第I個(gè)柱上的個(gè)數(shù)?？涟“」_(dá)撒啊撒啊啊Proceduremove(k,goal:integer);{將最大不到位的k移到目標(biāo)柱goal上}Begin大大賽Ifk=0thenexit;ForI:=1to3doForj:=1tohan[I,0]doIfh[I,j]=kthenbeginnow:=I;nowp:=j;end;{找到k的位置}Ifnow<>goalthenbegin{若未移到目標(biāo)}Move(k-1,6-now-goal);{剩下的先移到?jīng)]用的柱上}Writeln(kmovedfromnowtogoal);H[goal,h[goal,0]+1]:=h[now,nowp];h[now,nowp]:=0;Inc(h[goal,0]);dec(h[now,0]);Move(k-1,goal);{剩下的移到目標(biāo)上}End;十二、DFS框架NOIP2001數(shù)的劃分procedurework(dep,pre,s:longint);{入口為work(1,1,n)}{dep為當(dāng)前試放的第dep個(gè)數(shù),pre為前一次試放的數(shù),s為當(dāng)前剩余可分的總數(shù)}varj:longint;beginifdep=nthenbeginifs>=pretheninc(r);exit;end;forj:=pretosdiv2dowork(dep+1,j,s-j);end;類似：proceduretry(dep:integer);vari:integer;beginifdep=kthenbeginiftot>=a[dep-1]theninc(sum);exit;end;fori:=a[dep-1]tototdiv2dobe