數(shù)據(jù)結(jié)構(gòu)總結(jié)

數(shù)據(jù)結(jié)構(gòu)應(yīng)用山東師大附中趙宗昌◆高精度運算◆排序的應(yīng)用◆棧的應(yīng)用◆隊列的應(yīng)用◆圖的應(yīng)用一、高精度運算主要解決的問題：1、高精度數(shù)的輸入和保存。2、運算時的進位與借位。3、運算結(jié)果的保存。4、運算結(jié)果的輸出。1、實數(shù)減法dec.pas/dec.in/dec.out【問題描述：】輸入兩個正的實數(shù)a,b，輸出a-b的值?！据斎耄骸績尚?，第一行a，第二行b，a和b的長度均小于1000位。【輸出：】一行，a-b的值?！緲永斎耄骸?.52.3【樣例輸出：】2.21、數(shù)據(jù)的輸入2、比較實數(shù)a和b的大小。從而確定結(jié)果的正負號

ifa>bthen+ifa<bthen-ifa=bthen03、借位問題。4、結(jié)果的輸出實數(shù)減法◆數(shù)據(jù)的輸入：

a和b的長度均小于1000位1、string:最大長度255位。2、單個數(shù)字字符讀入；3、ansistring：最大長度:256*256-1=65535正整數(shù)大小的比較：◆

實數(shù)數(shù)據(jù)大小的比較：S1;s2(s1<>s2)la:=length(s1);lb:=length(s2);if(la<lb)or((la=lb)and(s1<s2))thens1<s2Elses1>s2實數(shù)大小的比較：

a=‘1234.343’b=‘4.5545545’補齊：容易比較大小

a=‘1234.3430000’b=‘0004.5545545’

記錄小數(shù)點的位置p．去掉小數(shù)點．

a=‘12343430000’b=‘00045545545’根據(jù)整數(shù)大小的比較。運算按照整數(shù)減法?！艚Y(jié)果的輸出小數(shù)點的處理3435435.345453454000003444.4355454000000000.0004354554500000345534540000.000000輸出合法要求：不能有多余的0

k1:最后一位小數(shù)位置；

p：小數(shù)點位置。

k2:整數(shù)最高位。

k1:=1;while(a[k1]=0)and(k1<=p)doinc(k1);k2:=len;while(a[k2]=0)and(k2>p+1)dodec(k2);fori:=k2downtop+1dowrite(a[i]);ifk1<=pthenbeginwrite('.');fori:=p-1downtok1dowrite(a[i]);end;……342444.84584938……..k2k1p1、選擇排序2、冒泡排序3、插入排序4、快速排序5、堆排序二、排序的應(yīng)用時間：O(n2)N<1000時間：O(n*log(n))N<100001、區(qū)間合并【問題描述：】從鍵盤上任意輸入n個區(qū)間，然后按從小到大的順序依次輸出n個區(qū)間的并集?！据斎耄骸康谝恍?，區(qū)間個數(shù)n（<=1000）以下n行，每行兩個整數(shù)a、b（-1000000000<a<b<1000000000）,相應(yīng)區(qū)間的坐標，中間一個空格。【輸出：】n個區(qū)間的并集，n行，每行一個區(qū)間，坐標軸的左邊的區(qū)間先輸出?！緲永斎耄骸?251478【樣例輸出：】1578區(qū)間的合并注意：1、區(qū)間個數(shù)n的范圍（<=1000）2、區(qū)間的數(shù)據(jù)類型和范圍：整數(shù)類型、-109--109算法一：離散化思路：◆設(shè)f[i]:0..1,初始值全部為0?！裘孔x入一個區(qū)間abFori:=1tonForj:=atobdof[j]=1◆最后輸出f[j]=1的區(qū)間。時間復(fù)雜度：1012，只能過部分數(shù)據(jù)。算法二：直接合并1、按每個區(qū)間的左端的的值升序排列。由于N<=1000,任意排序算法。注意數(shù)據(jù)結(jié)構(gòu)的設(shè)置:

◆記錄類型

◆二維數(shù)組：

a:array[1..1000,1..2]oflongint;a:array[1..1000]ofarray[1..2]oflongint2、合并過程◆輸出第一個區(qū)間的左端點坐標（最小的）◆依次處理后面的n-1的區(qū)間。Ifa[I,2]<=tailTail不變If(a[I,1]<=tail)and(tail<=a[I,2])Tail=a[I,2]Iftail<a[I,1]Writeln(tail);Write(a[I,1]);Tail:=a[I,2];

write(a[1,1],'');tail:=a[1,2];fori:=2tondobeginif(a[i,1]<=tail)and(tail<=a[i,2])//2thentail:=a[i,2];iftail<a[i,1]then//3begin

writeln(tail);write(a[i,1],'');tail:=a[i,2];end;end;

writeln(tail);2、潛水比賽

在馬其頓王國舉行了一次潛水比賽。其中一個項目是從高山上跳下水，再潛水達到終點。這是一個團體項目，一支隊伍由n人組成。在潛水時必須使用氧氣瓶，但是每只隊伍只有一個氧氣瓶。最多兩人同時使用一個氧氣瓶，但此時兩人必須同步游泳，因此兩人達到終點的時間等于較慢的一個人單獨游到終點所需要的時間。好在大家都很友好，因此任何兩個人后都愿意一起游水。安排一種潛水的策略，使得最后一名選手盡量的達到終點。輸入：第一行：隊伍的人數(shù)n（<=1000）。第二行：n個數(shù)，分別是n個人潛水所用的時間ti(<=1000)。樣例：輸入：3134輸出：8分析:先從簡單入手:1)n=2,時間t:110所需的時間為:102)n=3,時間t:134所需的時間為:3+1+4=83)n=4,時間t:1101112所需的時間為:10+1+11+1+12=35貪心策略方法一:N個人:每個人所需的時間:t1，t2，……tn。假設(shè)t1最小。每次由t1接送人和氧氣瓶，則總時間：s=t2+t3+。。。。tn+（n-2）*t14）n=4，每個人所用時間：1258采用貪心策略方法一：計算所用的總時間為：2+5+8+1*2=17事實上：采用下面策略：第一步：12一起先過，用時：2第二步：

1送回氧氣瓶，用時：1第三步：58一起過，用時：8第四步：2送回氧氣瓶，用時：2第五步：1和2一起過去，用時：2完成。共用時：2+1+8+2+2=15<17貪心策略方法二:將n個人的時間從小到達排序，假設(shè)從小到大為：t1，t2，……tn1：t1和t2過：t22：t1帶瓶返回：t13：最大的兩個人：tntn-1過：tn4：t2帶瓶返回：t2把以上看作一趟：把用事最長的兩個人tn

，tn-1送過去：用時：2*t2+t1+tn重復(fù)上述過程：用t1和t2在把tn-2

，tn-3

送過去，用時：2*t2+t1+tn-2每趟都用t1和t2，每趟運送2人。最后如果剩2人：t1，t2：時間：t2最后如果剩3人：t1，t2，t3時間：t1+t2+t35）n=6，時間：1101112100101按照貪心策略方法二:計算總時間：165另外的方法：10101110010110110101121211111111111010157！貪心策略方法三：每一趟送用時間最長的兩個人時：根據(jù)情況選擇：用t1和t2兩個人還是只用t1一個人。用t1和t2送一趟用時：x=2*t2+t1+tn用t1一個人送一趟（2人）：y=2*t1+tn+tn-1每送一趟都要比較x和y的大?。篒fx>ythen用t1送else用t1和t2送貪心三算法：數(shù)組a存時間：把時間從小到大排序。sum:=0;ifodd(n)thenbeginsum:=sum+a[2]+a[1]+a[3]endelsesum:=sum+a[2];i:=n;whilei>3dobeginx:=2*a[2]+a[1]+a[i];{用a1和a2送一趟}y:=2*a[1]+a[i]+a[i-1];{用a1送一趟}ifx<ythensum:=sum+xelsesum:=sum+y;dec(i,2);{i=i-2:每趟送兩人}end;

writeln(sum);三、棧的應(yīng)用典型應(yīng)用：表達式類問題的求解中綴表達式轉(zhuǎn)化為后綴表達式中綴表達式求值【問題描述：】判斷包含有括號{，[，<，（，），>，]，}的字符串是否是合法匹配。例如以下是合法的括號匹配：(),[],(()),([]),()[],()[()]以下是不合法括號匹配的：(,[,],)(,([)],([()【輸入：】一行，字符串（長度范圍：[1，500]）?！据敵觯骸咳绻址欣ㄌ柶ヅ涫呛戏ǖ妮敵觥皔es”，不合法的輸出“no”?！緲永?輸入：】abc{a[bb]m}aa<ss>【樣例1輸出：】yes【樣例2輸入：】abc{a[bb]maa<ss>【樣例2輸出：】no1、括號匹配s:ansistring;ch:array[1..8]ofchar=('{','[','<','(',')','>',']','}');利用棧操作主程序：

begin

readlnI(s);ifcheckthenwriteln('yes')elsewriteln('no');end;functioncheck:boolean;//檢測函數(shù)：合法返回true；非法返回false；

begin

len:=length(s);t:=0;//棧頂指針；

i:=1;whilei<=lendobegink1:=find(s[i]);//返回序號

if(k1>0)and(k1<=4)thenpush(k1);//左括號進棧

ifk1>4then//右括號，出棧判斷是否配對。

beginift=0thenexit(false);//空棧：非法的，預(yù)防棧溢出；

k2:=pop;ifk1+k2<>9thenexit(false);//不匹配退出檢測

end;

inc(i);end;ift=0thenexit(true)elseexit(false);//棧空：合法；非空：非法；

end;functionfind(x:char):integer;//返回括號的序號函數(shù),用序號代替括號;0：不是括號

var

i:integer;beginfori:=1to8doifx=ch[i]thenexit(i);exit(0);end;Find(x:char)函數(shù)2、中綴表達式求值【問題描述：】輸入表達式，輸出值。1）、表達式中除了數(shù)字外0----9外，僅含有運算符合：+、-、*、/、（、）六種符號。2）、輸入的數(shù)全部為正整數(shù)，不含有如下類似的表達式：+3，-45等。3）、表達式長度不超過100，中間運算值以及最后的運算結(jié)果都在[-109，109]內(nèi)。4）、/運算只取整數(shù)部分。采用div即可。【輸入：】合法的中綴表達式。【輸出：】表達式的值【樣例輸入：】3*（7-2）【樣例輸出：】15表達式類問題的兩種求解算法：◆算符優(yōu)先算法：棧操作。

符號棧，操作數(shù)棧

1、先化中綴，再求值。

2、直接求值?？紤]情況復(fù)雜，代碼復(fù)雜，亂?！暨f歸處理算法分析:

采用遞歸算法:

設(shè)表達式：s=s1ops2;op是最低優(yōu)先運算符。

1）、找s中的最低優(yōu)先級運算符:op2）、先計算s1和s2；

3）、然后s1和s2再作op運算。

s1和s2采取同樣的方法。如：34*10+30+10*5主程序：BEGIN

readln（S）；

n:=length(S);

ans=work(1,n)

writeln(ans);END;functionwork(L,r:longint):longint;//求表達式SL……Sr的值

var

k,a,b:longint;beginifst[l]='('theninc(l);ifst[r]=')'thendec(r);k:=find1(l,r);//最低優(yōu)先級算符的位置

ifk=0thenexit(data(l,r));//返回數(shù)值

a:=work(l,k-1);//左邊求值

b:=work(k+1,r);//右邊求值

work:=opt(a,k,b);//按k位置的算符計算

end;遞歸算法標號法求運算符的優(yōu)先級：

◆+-的標號為1，*/的標號為2。

◆遇到括號標號加2。標號大的運算優(yōu)先級高。34+2*(23+3)-(2+(3+5)*3))+10+5預(yù)處理：求出表示式中S運算符號的優(yōu)先級

fori:=1tondoh[i]:=maxint;//運算數(shù)優(yōu)先級最大

base:=0;fori:=1tondocasest[i]of'(‘:inc(base,2);')‘:dec(base,2);'+‘,'-‘:h[i]:=base+1;'*‘,'/‘:h[i]:=base+2;end;

functionfind(l,r:longint):longint;

var

i,min:longint;beginmin:=maxint;find:=0;fori:=rdowntoldo//從右向左找？

ifh[i]<minthenbeginmin:=h[i];find:=i;end;end;find1(l,r);//最低優(yōu)先級算符的位置

functiondata(l,r:longint):longint;

var

i:longint;begindata:=0;fori:=ltordodata:=data*10+ord(st[i])-48;end;data(l,r)：返回數(shù)值functionopt(a,k,b:longint):longint;begincasest[k]of'+':opt:=a+b;'-':opt:=a-b;'*':opt:=a*b;'/':opt:=adivb;end;end;opt(a,k,b);按k位置的算符計算3、中綴表達式轉(zhuǎn)換為后綴表達式【問題描述：】輸入中綴表達式，輸出后綴表達式的形式，運算符號：+、-、*、/。每個操作數(shù)后面用“.”作為該操作數(shù)的結(jié)束標志。表達式除中的括號只有“（”和“）”。【輸入：】合法的中綴表達式（長度不超過100）【輸出：】后綴表達式。【樣例輸入：】3*(5–2)+7【樣例輸出：】3．5．2．-*7．+分析：假設(shè)表達式：s=s1ops2，op為最低優(yōu)先級運送符。1、首先把整個表達式中優(yōu)先級最低的符號op放在最后邊。變成：s1s2op2、再依次處理s1和s2：

s1=s11op1s12s2=s21op2s22

變成：s11s12op1s21s22op2

op3、再處理s11s12s21s2遞歸思想//Main;begin

readln(s);

Ans:=work(1,len);

writeln(Ans);end;functionwork(l,r:integer):string;//把表達式SL……Sr轉(zhuǎn)化為后綴表達式。

var

pos,i:integer;beginif(s[l]='(')theninc(l);if(s[r]=')')thendec(r);pos:=findlow(l,r);if(pos=0)thenexit(copy(s,l,r-l+1)+'.');work:=work(l,pos-1)+work(pos+1,r)+s[pos];end;四、隊列的應(yīng)用典型應(yīng)用：廣度優(yōu)先搜索概念在一端進行插入（進隊列），在另一端進行刪除（出隊列）的線性表。插入的一端稱為隊尾：closed;（指向隊尾，最后一個元素）

刪除的一端稱為隊首：open(習慣指向隊首的前一位置，空的位置)3265419openclosed隊列數(shù)組a下標：1234567……隊列空：open>=closed;非空：open<closed1、合并石子【問題描述：】

小Ray在河邊玩耍，無意中發(fā)現(xiàn)一些很漂亮的石子堆，于是他決定把這些石子搬回家。河灘上共有n堆石子，小Ray在把石子搬回家之前首先要把這n堆石子合并為一堆石子。已知小Ray每次可以選擇其中的兩堆石子合并為一堆，合并一次石子他要消耗的體力是兩堆石子的數(shù)量和。請計算小Ray把n堆石子合并成一堆最少消耗的體力值是多少?！据斎耄骸康谝恍校簄（<=30000）.第二行：那個用空格隔開的數(shù)，分別表示n堆石子的數(shù)量。（每堆<10000）【輸出：】n堆石子合并成一堆所消耗的最小體力值。說明:分別用隊列和堆兩種算法實現(xiàn)?！緲永斎耄骸?124【樣例輸出：】10

在最優(yōu)二叉樹中非葉結(jié)點的度均為2，因此采用順序存儲結(jié)構(gòu)為宜。如果帶權(quán)葉結(jié)點數(shù)為n個，則最優(yōu)二叉樹的結(jié)點數(shù)為2n-1個。由此得出最優(yōu)二叉樹的數(shù)據(jù)類型定義Maxn=30000;n=葉結(jié)點數(shù)的上限；

m=2*n-1；

{最優(yōu)二叉樹的結(jié)點數(shù)}Typenode=record{結(jié)點類型}data：integer；{權(quán)值}

prt，lch，rch：longint；

{父指針、左、右指針和路徑長度}end；Vara：array[1..maxn]oflongint；{其中a[1‥n]為葉結(jié)點，a[n+1‥2n-1]為中間結(jié)點，根為a[2n-1]}算法一(hafuman.pas)procedurecreat;//創(chuàng)建哈夫曼樹

var

i,j,k:longint;beginsum:=0;//費用

m:=2*n-1;fork:=n+1tomdobegini:=findmin(k-1);a[k].lch:=i;a[i].prt:=k;j:=findmin(k-1);a[k].rch:=j;a[j].prt:=k;

a[k].data:=a[i].data+a[j].data;sum:=sum+a[k].data;end;end;functionfindmin(k:longint):longint;//在前k個街道中找最小的結(jié)點，父結(jié)點為0

var

min,i:longint;beginmin:=maxlongint;fori:=1tokdoif(a[i].data<min)and(a[i].prt=0)thenbeginmin:=a[i].data;findmin:=i;end;end;Sum是所求的費用時間復(fù)雜度：O(n2)，無法完成n=30000算法二（stone.pas）設(shè)置兩個隊列：a，b隊列a：保存初始的n個葉結(jié)點，從小到大排序。隊列b:依次放生成的新結(jié)點，遞增的。生成結(jié)點過程：Mindata=min{a[opena]+a[opena+1];b[openb]+b[openb+1];

a[open]+b[open]}Inc(closedb);B[closedb]=mindata;采用快速排序；時間復(fù)雜度：O（n*long(n)）合并的時間復(fù)雜度：O（n）總的時間復(fù)雜度：O（n*long(n)）

opena:=1;openb:=1;closedb:=0;ans:=0;fori:=1ton-1dobeginsum:=a[opena]+a[opena+1];f:=1;ifa[opena]+b[openb]<sumthenbeginsum:=a[opena]+b[openb];f:=2;end;ifb[openb]+b[openb+1]<sumthenbeginsum:=b[openb]+b[openb+1];f:=3;end;

inc(closedb);b[closedb]:=sum;inc(ans,sum);casefof1:inc(opena,2);2:begininc(opena);inc(openb);end;3:inc(openb,2);end;end;將石子從小到大排序放入數(shù)組a；數(shù)組b，一次存放合并后的石子，同樣是遞增的的？將石子從小到大排序放入數(shù)組a；N=300001、快速排序算法。2、桶排序算法。readln(n);fori:=1tondobegin

read(k);

inc(t[k]);end;k:=0;fori:=1to10000doforj:=1tot[i]dobegin

inc(k);

a[k]:=i;end;

a[n+1]:=maxlongintdiv2;a[n+2]:=maxlongintdiv2;fori:=1ton+2dot[i]:=maxlongintdiv2;【問題描述：】在n*n的棋盤上有一匹馬在第x行第y列的格子上。棋盤上有些格子上有障礙物，馬不能達到有障礙物的格子。已知馬在棋盤中的走法按“日“字8個方向可走，如下圖所示：問：哪些格子能到達，到達這些格子的最小步數(shù)是多少?！据斎耄骸康谝恍?n（n<=100）,x,y

(馬的開始位置)。接下來n行為棋盤的描述：“-“為空格子，”+“表示該格子有障礙物?！据敵觯骸縩行，每行n個用空格隔開的數(shù)，表示馬到達該格子的最少步數(shù)，如果無法到達則用-1表示。2、馬的遍歷422----------+-----【樣例輸入：】4321303223-111214【樣例輸出：】０

dx:array[1..8]ofinteger=(-1,-2,-2,-1,1,2,2,1);dy:array[1..8]ofinteger=(2,1,-1,-2,-2,-1,1,2);varcan:array[-1..maxn+2,-1..maxn+2]ofboolean;//加邊界，方便判斷是否出界

dist:array[1..maxn,1..maxn]ofinteger;//記錄最少步數(shù)

n,i,j,x0,y0:integer;procedureinit;

var

s:string;beginreadln(n,x0,y0);

fillchar(can,sizeof(can),false);fori:=1tondobegin

readln(s);forj:=1tondocan[i,j]:=s[j]='-';end;end;procedurebfs;//廣度優(yōu)先搜索

varq:array[1..maxn*maxn,1..2]ofinteger;

open,closed,k,x,y,xx,yy:integer;beginfori:=1tondoforj:=1tondodist[i,j]:=-1;open:=0;closed:=1;dist[x0,y0]:=0;q[1,1]:=x0;q[1,2]:=y0;whileopen<closeddobegin

inc(open);x:=q[open,1];y:=q[open,2];fork:=1to8dobeginxx:=x+dx[k];yy:=y+dy[k];ifcan[xx,yy]and(dist[xx,yy]=-1)thenbegin

dist[xx,yy]:=dist[x,y]+1;

inc(closed);q[closed,1]:=xx;q[closed,2]:=yy;end;end;end;end;廣度優(yōu)先搜索算法（bfs）:1、適合的題目類型：

1）、求從給定初始狀態(tài)到目標狀態(tài)最少需要的步數(shù)。

2）、給定初始狀態(tài)，經(jīng)過k步后能夠到達哪些狀態(tài)。2、利用的數(shù)據(jù)結(jié)構(gòu)：隊列。3、狀態(tài)的最大值：決定隊列的大?。ǚ浅Ｖ匾?、隊列里需要記住哪些狀態(tài)：一般使用記錄數(shù)據(jù)類型。5、狀態(tài)的轉(zhuǎn)移：不能遺漏。6、狀態(tài)的判重：避免重復(fù)進入隊列。（結(jié)合跳馬題目分析）4、Bfs的基本框架：初始化；建立數(shù)據(jù)庫（隊列）；初始狀態(tài)進入隊列；Open=0：隊列的首指針；Closed=1：隊列的尾指針（開始時指向初始狀態(tài)）；Quene[1]:初始結(jié)點;While（open<closed{還有未擴展的結(jié)點，隊列不空}）doBeginInc（open）；{移動隊列的首指針：出隊列}

記錄open狀態(tài)；

Fori=1tomethoddo{按規(guī)則擴展下一層新的子結(jié)點}Begin

生成新的結(jié)點;If新結(jié)點是目標結(jié)點then輸出目標，搜索結(jié)束；

If新結(jié)點是以前沒出現(xiàn)過then保存新結(jié)點（入隊列）；

EndEnd；3、中國盒子問題給定10個盒子排成一行，其中有兩個相鄰的盒子是空的，其余的盒子中有4個A和4個B，例如：移動規(guī)則：任意兩相鄰字母可移到空盒子中去，但這兩個字母的原來順序保持改變。目標：全部的A在左邊，全部的B在右邊，空格在中間。如下圖：對于任意給定的一個排列順序，最少經(jīng)過多少次移動，能達到目標序列。輸入：一行：初始序列，空格用0代替。輸出：初始序列達到目標的最少移動次數(shù)。樣例：輸入：ABBA00ABAB輸出：5AAAABBBBABBAABAB中國盒子問題（box）1、問題：初始序列達到目標的最少移動次數(shù)。適合使用bfs算法。2、隊列需要保存的狀態(tài)：轉(zhuǎn)化后的字符串s;轉(zhuǎn)換需要的步數(shù)depth。適合用記錄數(shù)據(jù)類型：

typenode=recordstr:string[10];

depth:integer;end;3、狀態(tài)的多少（隊列的大?。?304、狀態(tài)的轉(zhuǎn)移：任意兩相鄰字母可移到空盒子中去，但這兩個字母的原來順序保持改變ABBAABAB1）、確定空格的位置：sp:=pos('0',s);spS=i（1---9）2）、i，i+1與sp，sp+1位置的字符交換：條件：(sp–i>=2)or(i–sp>=2)3）、交換：Tem=stem[sp]:=s[i];tem[sp+1]:=s[i+1];tem[i]:='0';tem[i+1]:='0';？5、判重：

fori=1tocloseddoifa[1].str=tem最簡單、最直接的判重方法。缺點：效率低，時間慢。st='AAAA00BBBB';open:=0;closed:=1;q[1].str:=s1;q[1].depth:=0;whileopen<closeddobegin

inc(open);s:=q[open].str;step:=q[open].depth+1;sp:=pos('0',s);fori:=1to9dobegintem:=s;if(i+2<=sp)or(i-2>=sp)thenbegin

tem[sp]:=s[i];tem[sp+1]:=s[i+1];

tem[i]:='0';tem[i+1]:='0';iftem=stthenprint(step);ifnotfind(tem)thenbegin

inc(closed);

q[closed].str:=tem;

q[closed].depth:=step;end;end;end;end;functionfind(tem:string):boolean;

var

j:integer;beginforj:=1tocloseddoiftem=q[j].strthenexit(true);

exit(false);end;4、翻硬幣問題描述有N個硬幣正面朝上排成一排（N>=6），每次將5個硬幣翻過來放在原位置，直到最后全部硬幣翻成反面朝上為止。編程找出最少步數(shù)輸入只有一個整數(shù)N（<1000）輸出翻幣的最少次數(shù)coin.in8Coin.out4關(guān)鍵：反的最少次數(shù)僅僅與正面朝上和反面朝上的硬幣各數(shù)有關(guān)，而與硬幣的順序無關(guān)。1、需要記錄的狀態(tài)有哪些？2、怎樣判重復(fù)狀態(tài)？3、狀態(tài)轉(zhuǎn)移及條件？4、隊列的大??？typenode=record

num:integer;{正面朝上個數(shù)}

depth:integer;{翻的次數(shù)}end;var

a:array[1..1000]ofnode;

n,open,closed,step:integer;

b:array[0..1000]ofboolean;{(b[i]：i個正面朝上的情況是否出現(xiàn)過)}procedurebfs;var

i,m:integer;beginopen:=0;closed:=1;a[1].num:=n;a[1].depth:=0;b[n]:=true;whileopen<closeddobegin

inc(open);m:=a[open].num;{(m表示當前正面朝上的硬幣個數(shù))}step:=a[open].depth+1;

fori:=1to5do{(翻i個正面朝上的硬幣)}if(m>=i)and(n-m>=5-i)then{(m-i+5-i:正面朝上的個數(shù))}beginifm-i+5-i=0thenprint(step);{正面朝上的個數(shù)為0時結(jié)束}ifnot(b[m-i+5-i])thenbegin

inc(closed);{進隊列}b[m-i+5-i]:=true;

a[closed].num:=m-i+5-i;{正面朝上的個數(shù)}

a[closed].depth:=step;{翻的次數(shù)}end;end;end;end;可以看出：除了6和8是特例外，其他滿足：1）if(nmod5=0)thens=ndiv52)if(nmod5=1)or(nmod5=3)thens=ndiv5+13)if(nmod5=2)or(nmod5=4)thens=ndiv5+2或者：Ifnmod5=0thens=ndiv5Elses=ndiv5+(nmod5-1)mod2+11、圖的存儲結(jié)構(gòu)：鄰接矩陣、鄰接表2、圖的遍歷：dfs、bfs、連通分量3、無向圖的傳遞閉包4、最短路徑算法：floyed,dijkstra5、最小生成樹算法：prim,kruskal五、圖1253412534678圖一圖二定義：連通：如果從頂點u到v有路徑，則稱u和v是連通的。連通圖：圖中任意的兩個頂點u和v都是連通的。圖一是連通圖，圖二是非連通圖連通分量：無向圖中的極大連通子圖。圖二中有3個連通分量：{1245}{36}{78}求連通分量數(shù)，最大連通分量等。有向圖：強連通、強連通圖、強連通分量◆圖的連通分量//連通分量的算法sum:=0;fori:=1tondoifnotf[i]thenbegin

inc(sum);

dfs(i);end;【犯罪團伙】

警察抓到了n個罪犯，警察根據(jù)經(jīng)驗知道他們屬于不同的犯罪團伙，卻不能判斷有多少個團伙，但通過警察的審訊，知道其中的一些罪犯之間相互認識，已知同一犯罪團伙的成員之間直接或間接認識。有可能一個犯罪團伙只有一個人。請你根據(jù)已知罪犯之間的關(guān)系，確定犯罪團伙的數(shù)量。已知罪犯的編號從1至n。輸入：第一行：n（<=10000,罪犯數(shù)量），第二行：m（<=100000，關(guān)系數(shù)量）以下若干行：每行兩個數(shù)：I和j，中間一個空格隔開，表示罪犯i和罪犯j相互認識。輸出：一個整數(shù)，犯罪團伙的數(shù)量。輸入：118124534135671051089輸出：3測試數(shù)據(jù)說明：1s共10個測試數(shù)據(jù)：（1）5個數(shù)據(jù)：

n<=1000,m<=5000;（2）5個數(shù)據(jù)：

10000>=n>=9000,

100000>=m>=90000;建立無向圖的模型。最容易想到的算法1：把n個人看成圖的n個頂點；相互認識的連一條邊。相互認識的所有人構(gòu)成一個極大連通子圖。問題轉(zhuǎn)化為：求無向圖的連通分量（有多少個極大連通子圖）

//建圖

readln(n);

readln(m);fori:=1tomdobegin

readln(x,y);

a[x,y]:=1;

a[y,x]:=1;end;//dfs

proceduredfs(i:longint);

var

j:longint;begin

visited[i]:=1;forj:=1tondoif(a[i,j]=1)and(visited[j]=0)thendfs(j);end;

proceduremain;

var

i:integer;begin

sum:=0;

fillchar(f,sizeof(f),false);fori:=1tondoifnotf[i]thenbegin

inc(sum);

dfs(i);end;

writeln(sum);end;?時間和空間！鄰接矩陣：空間太大，超時。鄰接表：空間滿足，時間>1s

無法通過后5個數(shù)據(jù)輸入：118124534135671051089高效的樹型結(jié)構(gòu)算法2：建立森森結(jié)構(gòu)，統(tǒng)計樹的數(shù)量constmax=10000;vara:array[1..max]oflongint;

i,j,m,n,ans,x,y,p,q:longint;functionfind(i:longint):longint;{非遞歸算法找i的根}

var

j,k,t:longint;beginj:=i;whilea[j]<>0doj:=a[j];find:=j;end;程序算法：

readln(n);

readln(m);fillchar(a,sizeof(a),0);{默認根標志是0，開始全是樹根}fori:=1tomdobegin

readln(x,y);p:=find(x);{查找x的根}q:=find(y);{查找y的根}ifp<>qthena[q]:=p;{合并p和q子樹}end;

ans:=0;{樹根記數(shù)}fori:=1tondoifa[i]=0theninc(ans);{記錄樹根結(jié)點}

writeln(ans);end.◆無向圖的傳遞閉包判斷無向圖的連通性1234657輸入圖的邊的信息，輸出各點的連通行。輸入：7122313345667輸出：11110001111000111100011110000000111000011100001110110000101000011010000010000000001000001010000010鄰接矩陣判斷結(jié)點i和j的連通性：ijk1、結(jié)點i和j如果原來有邊則連通。2、如果i和j之間沒有邊：如果存在另外的一個結(jié)點k，滿足：i與k連通，k與j連通，則i與j連通。否則i和j不連通。Can[i,j]:true，i與j之間有邊；false：無邊。則：Can[i,j]=can[i,j]or(can[i,k]andcan[k,j])

fork:=1tondofori:=1tondoforj:=1tondo

can[i,j]:=can[i,j]or(can[i,k]andcan[k,j]);過程：產(chǎn)生數(shù)【問題描述:】給出一個正整數(shù)n（n<10^50)和k個變換規(guī)則（k<=15）。每個變換規(guī)則是指：一位數(shù)可變換成另一個一位數(shù)：規(guī)則的右部不能為零。例如：n=234。有規(guī)則（k＝2）：

2－>53－>6上面的整數(shù)234經(jīng)過變換后可能產(chǎn)生出的整數(shù)為（包括原數(shù)）:

234534264564共4種不同的產(chǎn)生數(shù)。【任務(wù)：】給出一個整數(shù)n和k個變換規(guī)則。求經(jīng)過任意次的變換（0次或多次），能產(chǎn)生出多少個不同整數(shù)。僅要求輸出個數(shù)。【輸入：】第一行：n。第二行：k。以下k行：每行兩個一位數(shù)：xy，中間一個空格，表示一個變換規(guī)則：x可以變?yōu)閥。【輸出：】一個整數(shù)（滿足條件的個數(shù)）：【輸入樣例：】23422536【樣例輸出：】4應(yīng)用舉例?本題搜索顯然是不行的。?對于只需計數(shù)而不需求具體方案的題目，一般都不會用搜索解決。分析：?乘法原理直接進行計數(shù)。用F[i]表示數(shù)字i包括本身可以變成的數(shù)字總個數(shù)這里的變成可以是直接變成也可以是間接變成：比如3->5,5->7,那么3->7那么對于一個數(shù)a（用數(shù)組存,長度為n），根據(jù)乘法原理它能產(chǎn)生出不同整數(shù)數(shù)量：F[a[1]]*F[a[2]]*F[a[3]]*…F[a[n]]init；

//建圖

makef;//生成每個數(shù)字的轉(zhuǎn)化數(shù)量n:=length(s);fillchar(ans,sizeof(ans),0);//結(jié)果ans[1]:=1;ans[0]:=1;fori:=1tondobegink:=f[ord(s[i])-48];ifk<>0thenmul(k);end;

print；a:array[0..9,0..9]ofboolean;f: