算法大全(數(shù)據(jù)結構)

算法大全（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．素數(shù)的求法A.小范圍內(nèi)判斷一個數(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ù)是否為素數(shù)（包含求50000以內(nè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{尋找離生成樹最近的未加入頂點k}min:=maxlongint;forj:=1tondoif(lowcost[j]<min)and(lowcost[j]<>0)thenbeginmin:=lowcost[j];k:=j;end;lowcost[k]:=0;{將頂點k加入生成樹}{生成樹中增加一條新的邊k到closest[k]}{修正各點的lowcost和closest值}forj:=1tondoifcost[k,j]<lwocost[j]thenbeginlowcost[j]:=cost[k,j];closest[j]:=k;end;end;end;{prim}B.Kruskal算法：(貪心)按權值遞增順序刪去圖中的邊，若不形成回路則將此邊加入最小生成樹。functionfind(v:integer):integer;{返回頂點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個集合，第I個集合包含一個元素I}p:=n-1;q:=1;tot:=0;{p為尚待加入的邊數(shù)，q為邊集指針}sort;{對所有邊按權值遞增排序，存于e[I]中，e[I].v1與e[I].v2為邊I所連接的兩個頂點的序號，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.標號法求解單源點最短路徑：vara:array[1..maxn,1..maxn]ofinteger;b:array[1..maxn]ofinteger;{b[i]指頂點i到源點的最短路徑}mark:array[1..maxn]ofboolean;procedurebhf;varbest,best_j:integer;beginfillchar(mark,sizeof(mark),false);mark[1]:=true;b[1]:=0;{1為源點}repeatbest:=0;fori:=1tondoIfmark[i]then{對每一個已計算出最短路徑的點}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算法求解所有頂點對之間的最短路徑：procedurefloyed;beginforI:=1tondoforj:=1tondoifa[I,j]>0thenp[I,j]:=Ielsep[I,j]:=0;{p[I,j]表示I到j的最短路徑上j的前驅(qū)結點}fork:=1tondo{枚舉中間結點}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ū)結點}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)一次加入一個離1集合最近的結點并調(diào)整其他結點的參數(shù)}min:=maxint;u:=0;{u記錄離1集合最近的結點}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.計算圖的傳遞閉包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{對結點I染色}c[i]:=color;dfs(I,color);end;end;B寬度優(yōu)先（種子染色法）5．關鍵路徑幾個定義：頂點1為源點，n為匯點。a.頂點事件最早發(fā)生時間Ve[j],Ve[j]=max{Ve[j]+w[I,j]},其中Ve(1)=0;b.頂點事件最晚發(fā)生時間Vl[j],Vl[j]=min{Vl[j]–w[I,j]},其中Vl(n)=Ve(n);c.邊活動最早開始時間Ee[I],若邊I由<j,k>表示，則Ee[I]=Ve[j];d.邊活動最晚開始時間El[I],若邊I由<j,k>表示，則El[I]=Vl[k]–w[j,k];若Ee[j]=El[j]，則活動j為關鍵活動，由關鍵活動組成的路徑為關鍵路徑。求解方法：a.從源點起topsort,判斷是否有回路并計算Ve;b.從匯點起topsort,求Vl;c.算Ee和El;6．拓撲排序找入度為0的點，刪去與其相連的所有邊，不斷重復這一過程。例尋找一數(shù)列，其中任意連續(xù)p項之和為正，任意q項之和為負，若不存在則輸出NO.7.回路問題Euler回路(DFS)定義：經(jīng)過圖的每條邊僅一次的回路。（充要條件：圖連同且無奇點）Hamilton回路定義：經(jīng)過圖的每個頂點僅一次的回路。一筆畫充要條件：圖連通且奇點個數(shù)為0個或2個。9．判斷圖中是否有負權回路Bellman-ford算法x[I],y[I],t[I]分別表示第I條邊的起點，終點和權。共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最短路徑的基礎上求解。三、背包問題*部分背包問題可有貪心法求解：計算Pi/Wi數(shù)據(jù)結構：w[i]:第i個背包的重量；p[i]:第i個背包的價值；1．0-1背包：每個背包只能使用一次或有限次(可轉化為一次)：A.求最多可放入的重量。NOIP2001裝箱問題有一個箱子容量為v(正整數(shù)，o≤v≤20000)，同時有n個物品(o≤n≤30)，每個物品有一個體積(正整數(shù))。要求從n個物品中，任取若千個裝入箱內(nèi)，使箱子的剩余空間為最小。l搜索方法proceduresearch(k,v:integer);{搜索第k個物品，剩余空間為v}vari,j:integer;beginifv<bestthenbest:=v;ifv-(s[n]-s[k-1])>=bestthenexit;{s[n]為前n個物品的重量和}ifk<=nthenbeginifv>w[k]thensearch(k+1,v-w[k]);search(k+1,v);end;end;lDPF[I,j]為前i個物品中選擇若干個放入使其體積正好為j的標志，為布爾型。實現(xiàn):將最優(yōu)化問題轉化為判定性問題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)化：當前狀態(tài)只與前一階段狀態(tài)有關，可降至一維。F[0]:=true;ForI:=1tondobeginF1:=f;Forj:=w[I]tovdoIff[j-w[I]]thenf1[j]:=true;F:=f1;End;B.求可以放入的最大價值。F[I,j]為容量為I時取前j個背包所能獲得的最大價值。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．可重復背包A求最多可放入的重量。F[I,j]為前i個物品中選擇若干個放入使其體積正好為j的標志，為布爾型。狀態(tài)轉移方程為f[I,j]=f[I-1,j–w[I]*k](k=1..jdivw[I])B.求可以放入的最大價值。USACO1.2ScoreInflation進行一次競賽，總時間T固定，有若干種可選擇的題目，每種題目可選入的數(shù)量不限，每種題目有一個ti（解答此題所需的時間）和一個si（解答此題所得的分數(shù)），現(xiàn)要選擇若干題目，使解這些題的總時間在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時取前j種背包所能達到的最大值。*實現(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ù)和的表達式的數(shù)目。思路一，生成每個質(zhì)數(shù)的系數(shù)的排列，在一一測試，這是通法。proceduretry(dep:integer);vari,j:integer;begincal;{此過程計算當前系數(shù)的計算結果，now為結果}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個物品，背包容量為n，求放法總數(shù)。轉移方程：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);{讀入第一個物品的重量}i:=0;{a[i]為背包容量為i時的放法總數(shù)}whilei<=ndobegina[i]:=1;inc(i,now);end;{定義第一個物品重的整數(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];{將當前序列在中間位置的數(shù)定義為中間數(shù)}repeatwhilea[i]<middoinc(i);{在左半部分尋找比中間數(shù)大的數(shù)}whilea[j]>middodec(j);{在右半部分尋找比中間數(shù)小的數(shù)}ifi<=jthenbegin{若找到一組與排序目標不一致的數(shù)對則交換它們}swap(a[i],a[j]);inc(i);dec(j);{繼續(xù)找}end;untili>j;ifl<jthenqsort(l,j);{若未到兩個數(shù)的邊界，則遞歸搜索左右區(qū)間}ifi<rthenqsort(i,r);end;{sort}B.插入排序：思路：當前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]);{每次比較相鄰元素的關系}end;E.堆排序：proceduresift(i,m:integer);{調(diào)整以i為根的子樹成為堆,m為結點總數(shù)}vark:integer;begina[0]:=a[i];k:=2*i;{在完全二叉樹中結點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])){滿足取左邊序列當前元素的要求}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ù)排序思想：對每個元素按從低位到高位對每一位進行一次排序五、高精度計算高精度數(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;{進位}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{處理最高位的進位}c[len+1]:=c[len]div10;c[len]:=c[len]mod10;inc(len);end;while(len>1)and(c[len]=0)dodec(len);{若不需進位則調(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];{加上根，遞歸結束后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)];{加上根，遞歸結束后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;七進制轉換1.任意正整數(shù)進制間的互化除n取余2.實數(shù)任意正整數(shù)進制間的互化乘n取整3.負數(shù)進制：設計一個程序，讀入一個十進制數(shù)的基數(shù)和一個負進制數(shù)的基數(shù)，并將此十進制數(shù)轉換為此負進制下的數(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個數(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.樹形查找二叉排序樹：每個結點的值都大于其左子樹任一結點的值而小于其右子樹任一結點的值。查找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個活動每個活動有一個開始時間和一個結束時間，任一時刻僅一項活動進行，求滿足活動數(shù)最多的情況。解：按每項活動的結束時間進行排序，排在前面的優(yōu)先滿足。（2）會議室空閑時間最少。（3）每個客戶有一個愿付的租金，求最大利潤。（4）共R間會議室，第i個客戶需使用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漢諾塔苛基本原理阿達撒基本原理工大大枯工苛幵二大專生一大起大落二地奎屯在博大需二大起大落亙古未有地亙古未有地素面朝天原封不動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按時的按時的按時暗暗上大蘇打初始銅片分布在3個柱上，給定目標柱goalh[1..3,0..n]存放三個柱的狀態(tài)，now與nowp存最大的不到位的銅片的柱號和編號,h[I,0]存第I個柱上的個數(shù)。苛啊啊哈達撒啊撒啊啊Proceduremove(k,goal:integer);{將最大不到位的k移到目標柱goal上}Begin大大賽Ifk=0thenexit;ForI:=1to3doForj:=1tohan[I,0]doIfh[I,j]=kthenbeginnow:=I;nowp:=j;end;{找到k的位置}Ifnow<>goalthenbegin{若未移到目標}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);{剩下的移到目標上}End;十二、DFS框架NOIP2001數(shù)的劃分procedurework(dep,pre,s:longint);{入口為work(1,1,n)}{dep為當前試放的第dep個數(shù),pre為前一次試放的數(shù),s為當前剩余可分的總數(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