從圓桌問題談數(shù)據(jù)結(jié)構(gòu)的綜合運(yùn)用

1、從圓桌問題談數(shù)據(jù)結(jié)構(gòu)的綜合運(yùn)用圓桌問題題目：圓桌上圍坐著2n個(gè)人。其中n個(gè)人是好人，另外n個(gè)人是壞 人。如果從第一個(gè)人開始數(shù)數(shù)，數(shù)到第m個(gè)人，則立即處死 該人；然后從被處死的人之后開始數(shù)數(shù)，再將數(shù)到的第m個(gè) 人處死依此方法不斷處死圍坐在圓桌上的人。試問預(yù)先應(yīng) 如何安排這些好人與壞人的座位，能使得在處死n個(gè)人之后, 圓桌上圍處的剩余的n個(gè)人全是好人。輸入:文件中的每一行都有兩個(gè)數(shù)，依次為n和m,表示一個(gè)問題 的描述信息，nw32767,32767輸出:依次輸出每一個(gè)問題的解。每一個(gè)問題的解可以用連續(xù)的若 干行字符來表示，每行的字符數(shù)量不超過50。但是在一個(gè)問 題的解中不允許出現(xiàn)空白字符和空行，相

2、鄰的兩個(gè)問題的解 之間用空行隔開。用大寫字母g表示好人，大寫字母b表示 壞人。圓桌問題實(shí)現(xiàn)思想圖示(n=5,m=3)6 61zvv分段式數(shù)據(jù)結(jié)構(gòu)示意（思想模型）（實(shí)際模型）amount鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)group=4順序存儲(chǔ)結(jié)構(gòu)共進(jìn)行1+2+2+3+5=13次操作改進(jìn)前后程序效率比較（測試機(jī)器：p166）測試數(shù)據(jù)法 表” 性找 綴查“優(yōu)化直接定位”法amount=400改進(jìn)前用時(shí)是 改進(jìn)后的多少倍n=200m= 1000.000s0.000s/n=1000m=500.440s0.000s/n=32767 m=2005.870s0.930s6.312n=32767 m=100029.440s0.980

3、s30.041n=32767 m=10000294.120s1.260s233.43n=32767 m=20000588.530s1.590s370.14n=32767 m=32767963.560s1.970s489.12橫向延伸約瑟夫環(huán)類的問題女m翻牌游戲、猴子選大王縱向延伸數(shù)據(jù)結(jié)構(gòu)的綜合運(yùn)用在解決一些數(shù)據(jù)規(guī)模較大的問題時(shí)有很好的效用。如隱 藏的碼字（ior99）o在解決這道題目時(shí)，如果建立起鏈?zhǔn)胶?順序相結(jié)合的數(shù)據(jù)結(jié)構(gòu)（如下圖），程序效率就比較高。鏈?zhǔn)胶晚樞蛳嘟Y(jié)合的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)簡單，效果顯著，應(yīng)用 比較廣泛。當(dāng)然還有其它的結(jié)合，比如二叉堆和順序結(jié)構(gòu)的一 一映射（單射），在解決某些問題時(shí)會(huì)有很好的效果。順序存儲(chǔ)結(jié)構(gòu)操作示意123456789101245678910124578910124578101457810145810共進(jìn)行7+4+1+5+2=19次操作，時(shí)間復(fù)雜度0(/)。鏈?zhǔn)酱鎯?chǔ)結(jié)