【文章內(nèi)容簡介】 輸出甲方贏 。 break。 end Else begin n:=na。 輸出現(xiàn)有 n枚棋子 ,甲方抓走 a枚棋子 。 K:=‘b’。 End。 End。 End。 練習： 假設(shè)有一堆小石子，二人輪流去取，誰拿走最后一顆石子便輸。先讓甲規(guī)定石子總數(shù) N以及每次最多取多少顆數(shù) k（ n=2*k+1），甲每次取 a顆 , （ N,k,a均為隨機數(shù)），乙怎樣取贏的可能性最大？設(shè)甲為計算機產(chǎn)生的隨機數(shù)，乙為由你編的計算機程序。 猜數(shù)游戲： 人和計算機做猜數(shù)游戲。人默想一個四位數(shù)，由計算機來猜。計算機將所猜的數(shù)顯示到屏幕上，并問兩個問題： （ 1）有幾個數(shù)字猜對了？（ 2）猜對的數(shù)字中有幾個位置也對？ 人通過鍵盤來回答這兩個問題。計算機一次又一次地猜，直到猜對為止。比如我們默想的一個數(shù)是 5122，假定計算機第一次猜 1166，然后問你： （ 1）有幾個數(shù)字猜對了？ 1（ 2）猜對的數(shù)字中有幾個位置也對？ 1 假定計算機第二次猜 1287 （ 1）有幾個數(shù)字猜對了？ 2（ 2）猜對的數(shù)字中有幾個位置也對？ 0 假定計算機第三次猜 5122 （ 1）有幾個數(shù)字猜對了？ 4（ 2）猜對的數(shù)字中有幾個位置也對？ 4 計算機顯示最后猜中的數(shù)，并報告共猜了幾次？ 問題 1： 編程實現(xiàn)這樣一個猜數(shù)的游戲程序。屏幕顯示格式為： 第二行顯示計算機所猜的四位數(shù)。 第三行提問猜對的數(shù)字個數(shù)，用“ Number:” 第四行提問位置對的數(shù)字個數(shù)，用“ Position:” 第五行顯示當前已猜的步數(shù)，用“ Step xx”. 注：其中末尾數(shù)字由鍵盤輸入。最后給出結(jié)束信息，其他由編程者自定。 問題 2 ： 仍是這樣一個游戲，但要求計算機既是猜數(shù)者，又要模擬默想這個數(shù)的人（要猜的數(shù)由鍵盤輸入）。屏幕顯示格式為： 第一行顯示人所默想的數(shù)，用“ xxxx”. 第二行至第五行同問題 1，只不過末尾數(shù)字不再由鍵盤輸入，而是計算機判斷后自動顯示。 問題 3： 從文本文件 20個四位數(shù)，一個接一個讓計算機猜，統(tǒng)計猜中所需的總步數(shù)。 算法分析： 計算機隨機產(chǎn)生一個猜數(shù) 設(shè) m當前的猜數(shù)集合。 var m:array[1..9000] of integer。 t:integer。 {m的長度 }； 初始時 m={1000， 1001， … ， 9999} t=9000 每一次猜數(shù)時，從 m[1]…m[t] 中隨機取出一個四位數(shù)，該數(shù)即為計算機的一個猜數(shù)。若 m集合為空（ t=0）時還未猜中，則游戲以失敗告終。計算機產(chǎn)生猜數(shù)的過程如下： function get_next :integer。 begin if t0 then get_next:=m[random(t)+1] else get_next:=1。{返回失敗信息 } End。{get_next} 計算機產(chǎn)生的猜數(shù)必須與 m集合中的每一個四位數(shù)比較，以確定其中哪些四位數(shù)與猜數(shù)默想一方的應答信息相符。出于逐位比較的方便，我們將猜數(shù)由整數(shù)類型轉(zhuǎn)化為整數(shù)數(shù)組類型。設(shè)： n—由計算機產(chǎn)生的猜數(shù)，即 n:=get_next。 now—n轉(zhuǎn)化為整數(shù)數(shù)組 now[0..3].定義如下： type nowtype=array[0..3] of 0..9 var now:nowtype。 轉(zhuǎn)化過程如下： procedure put (n:integer,var now:nowtype)。 begin for I:=0 to 3 do begin now[3i]:=n mod 10。n:=n div 10。end。{for} end。{put} 縮小猜數(shù)范圍：計算機從 m集合中隨機產(chǎn)生一個猜數(shù) now后，默想方必須應答（由鍵盤輸入或由計算機計算）：猜對多少個數(shù)字，其中有多少個數(shù)字位置也對。根據(jù)這一信息，我們將 m集合中的每一個元素與 now 比較，由比較結(jié)果確定哪些元素應從 m集合中去除。設(shè)： key—m集合中的某元素或默想數(shù)，其數(shù)據(jù)類型為 nowtype。 Now—計算機產(chǎn)生的猜數(shù)，其數(shù)據(jù)類型亦為 nowtype 。 我們通過 test1(key,now)函數(shù)計算 key中有多少數(shù)字曾在 now中出現(xiàn)： 我們通過 test2(key,now)函數(shù)計算 key中有多少數(shù)字曾在 now中出現(xiàn)且位置一一對應： function test1(key,now:nowtype):integer。 var h,i,j:integer。{h為 key和 now中的相同數(shù)字個數(shù) } mark:array[0..3] of boolean。{now和 key間有重復數(shù)字的標志。 } begin fillchar(mark,sizeof(mark),false)。{mark初始化 } h:=0。 for I:=1 to 3 do {依次搜索 key中的每一個數(shù)字 } begin j:=0 {在 now中尋找與 key[i]相同的數(shù)字 now[j]} while (j=3) and ((key[i]now[j]) or (mark[j])) do j:=j+1。 if j=3 then begin mark[j]:=true。h:=h+1。 end。{then} end。{for} test1:=h。 End。{test1} Function test2(key,now:nowtype):integer。 var h:integer。 begin h:=0。 for I:=0 to do if key[i]=now[i] then h:=h+1。 Test:=h。 End。{test2} 我們通過 test2(key,now)函數(shù)計算 key中有多少數(shù)字曾在 now中出現(xiàn)且位置一一對應： 當默想數(shù)為 key、計算機產(chǎn)生的猜數(shù)為 now時，我們可以通過調(diào)用上述兩個函數(shù)猜出猜對的數(shù)字個數(shù)t1[t1:=test1(key,now)]和猜對的數(shù)字中位置也對的數(shù)字個數(shù)t2[t2。=test2(key,now)].若 t14或者 t24，則計算機將 now與 m集合中的每一個四位數(shù)一一比較，將 m中與 now的相同數(shù)字個數(shù)為 t1且相同數(shù)字中位置對應的數(shù)字個數(shù)為 t2的所有四位數(shù)m[i](1=I=t)保留下來，即： I:=0 repeat I:=I+1。 put(m[i],key)。 if (test1(key,now)t1) or (test2(key,now)t2) then 從 m集合中剔除 m[i]。 Until It。 形成 m的一個子集， m[1]…m[t’](1=t’=t). 顯然，默想數(shù)應為該子集的一個元素。這一計算過程由子程序 delete(now)完成： procedure delete(now:nowtype)。 Begin I:=0。 repeat I:=I+1。 put(m[i],key)。 if (test1(key,now)t1) or (test2(key,now)t2) then begin m[i]:=m[t]。t:=t1。 I:=I1。 end。{then} Until It。 End。{delete} 算法流程： 問題（ 1）的算法。 for I:=1 to 9000 do m[i]:=I+999。 t:=9000。 randomize。 Repeat n:=get_next。 if n=1 then begin 打印猜數(shù)失敗西信息； halt。 end。{then} Put(n,now) 打印計算機產(chǎn)生的猜數(shù) now； 輸入猜對的數(shù)字個數(shù) t1和猜對數(shù)字中位置也對的數(shù)字個數(shù) t2。 Delete(now)。 Until(t1=4) and (t2=4)。 問題 2的算法。 設(shè) step—猜中一個數(shù)的不數(shù)。 step:=0。 m集合初始化； 讀默想數(shù) key； Repeat n:=get_next。put(n,now)。 t1:=test1(key,now)。t2:=test2(key,now)。 輸出 t1和 t2。 Step:=step+1。 Delete(now)。 Until(t1=4) and (t2=4)。 問題 3的算法： 設(shè) total— 猜中二十個數(shù)的總步數(shù) Total:=0。 For k:=0 to 19 do begin 執(zhí)行問題 2的算法； Total:total+step。 End。{for} 輸出猜中 20個數(shù)所需的總步數(shù) total。 題目 1: 某國為了防御敵國的導彈襲擊 ， 發(fā)展出一種導彈攔截系統(tǒng) 。 但是這種攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達任意的高度 ， 但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度 。 某天 ， 雷達捕捉到敵國的導彈來襲 ， 由于該系統(tǒng)還在試用階段 。 所以一套系統(tǒng)有可能不能攔截所有的導彈 。 輸入導彈依次飛來的高度 （ 雷達給出的高度不大于30000的正整數(shù) ） 。 計算要攔截所有的 導彈最少需配備多少套這種導彈攔截系統(tǒng) 。 輸入 ： 導彈數(shù) n和 n顆導彈依次飛來的高度 （ 1=n=1000） 輸出 ：要攔截所有的導彈最少配備的系統(tǒng)數(shù) 。 貪心法 貪心法 是從問題的某一個初始解出發(fā) ,向給定的目標推進 .但不同的是 ,推進的每一步不是依據(jù)某一固定的遞推式