30. 某機要部門安裝了電子鎖。Ｍ個工作人員每人發一張磁卡，卡上有開鎖的密碼特征。為了確保安全，規定至少要有Ｎ個人同時使用各自的磁卡才能將鎖打開。問電子鎖上至少要有多少種特征? 每個人的磁卡上至少要有多少特征? 如果特征的編號以小寫英文字母表示，將每個人的磁卡的特征編號打印出來，要求輸出的電子鎖        

 的總特征數最少。                                                                

    設 3<=M<=7, 1<=N<=4, Ｍ與Ｎ由鍵盤輸入，工作人員編號用 1#,2#,...表示.         

                                                                                 

 31. 甲乙兩人從２４枚棋子中輪流取子，甲先取，規定每次所取的枚數不能多于上        

 一個人所取的枚數，也不可不取。                                                  

  （１）甲第一次取多少枚才能保證甲取得最后一枚，當然，他也不能第一次就把         

 所有棋子都取走。                                                                

  （２）討論棋子總數Ｎ（一定是偶數）從６到３０的各種情況。討論內容包括：         

 對各個Ｎ，是否存在一個小于Ｎ的枚數Ｍ，甲第一次取Ｍ枚后就能保證甲如果策略        

 正確,一定能取到最后一枚棋子。                                                   

                                                                                 

 32. ( 走棋 ) 一個４＊４的方陣如圖。有一個小卒從上往下走。走至格子１后就         

 不能走動，走至０后，若下方為１，則向左或向右走，下方為０，則向下走。求所        

 有走法。                                                                        

              ┌─┬─┬─┬─┐                                                 

              │1 │0 │0 │0 │                                                 

              ├─┼─┼─┼─┤                                             

              │0 │0 │1 │0 │                                                 

              ├─┼─┼─┼─┤                                                 

              │0 │1 │0 │0 │                                             

              ├─┼─┼─┼─┤                                                 

              │1 │0 │0 │0 │                                                 

              └─┴─┴─┴─┘                                                 

                                                                                 

 33. ( 野人與傳教士 ) 設有三個傳教士和三個野人來到河邊，打算乘一只船從右         

 岸渡到左岸去。該船最大負載能力為兩人，在任何時候，如果野人人數超過傳教士        

 人數，那么野人就會把傳教士吃掉。他們怎樣才能用這條船安全地把所有人都渡過        

 河去呢？                                                                        

                                                                                 

 34. ( 取棋子 ) 設有Ｎ顆棋子，由人和計算機輪流從中取走若干顆。每方每次最         

 多取Ｋ顆，最少取１顆 (Ｋ值不能超過總數的一半，也不能小于１)。試編寫一程         

 序使計算機有較多的獲勝機會。                                                    

    屏幕輸入提示:

    (1) 輸入競賽規則：A. 取最后一顆棋子的那一方為敗.                                  

                      B. 取最后一顆棋子的那一方為勝.

    (2) 總共有多少顆棋子？                            

    (3) 一次最多取幾顆？                                              

    (4) 誰先取？                                               

    (5) 每個回合都應顯示: A. 你取幾顆？                                        

                          B. 我取走......顆，還剩......顆.                                             

    (6) 競賽過程中發生違例時，打印出:  競賽無法進行下去！                             

    (7) 競賽結束后打印：                                                             

    I win!（我勝！）或  You win!（你勝！）。                                     

 

 35. ( Grundy博弈 ) 在兩位選手面前放著一堆銅幣。第一位選手把原堆分成不相        

 等的兩堆。然后每個選手輪流地這樣做，即當輪到某一方分時, 他把已被分開的任        

 一堆再分成不相等的兩堆。博弈這樣一直進行下去，直到每一堆都只剩下一個或兩        

 個銅幣為止，這時博弈結束。規定首先遇到這種情況的選手為輸。                      

                                                                                 

 36. 猴子選大王：                                                                

   ① N 只猴子站成一行，每隔 M 只從頭到尾報數，反復進行,報過數的退出，打         

 印每次退出的猴子的編號,直到剩下一只為止。                                       

   ② N 只猴子站成一行，每 M 只報數。先從頭到尾，報到尾后，再返回從尾到頭        

 報數，打印每次方向及過程，直到剩下二只時，以排到后面的(指報數方向)為大王。      

   ③ N 只猴子圍成一圈，從第 P 個開始，每隔 M 只報數，打印每次過程，只剩下       

 一個時為大王。                                                                  

                                                                                 

 37. 已知 N 個正整數滿足 K1+K2+...+Kn=M。求一組最佳的分解，使得                  

 K1*K2*....*Kn 為最大。                                                          

   例如：N=2時，給定 K1+K2=6,當 K1=3,K2=3 時，K1*K2=9 為最大                     

                                                                                 

 38. 有一集合中有 N 個元素，每個元素均為自然數。給定一個 total （假設每個        

 元素值均小于total)，求滿足條件的所有子集，子集中各元素之和應等于total。         

                                                                                 

 39. 一個集合滿足如下條件：                                                      

   (1)１是集合的元素；                                                           

   (2) 若 P 是集合的元素，則 2*P+1，4*P+5 也是集合的元素。                       

 求：此集合中最小的 K 個元素。                                                   

 　③ 對ＡＢＣ作全排列而得的六個三位數之和為 2886。                              

                                                                                 

 40. 一個整型變量只能用來存貯較小的 N！的值，當 N 較大時，可將階乘值中的         

 每一個數字放在一個一維數組的一個元素中。使用這方法，打印：                      

    ① Ｎ！的值；                                                                

    ② Ｎ！－Ｍ！（Ｍ＞Ｎ）；                                                    

    ③ Ｎ！＋Ｍ！                                                                

 

 41. (合并鏈表) 已知兩個鏈表 AN={a1,a2,...an}, BN={b1,b2,...bm}, 將其合并        

 為一個鏈表 CN={a1,b1,a2,b2,...}                                                 

                                                                                 

 42. (算術表達式求值) 輸入一個由數字、+，-，*，/ 及括號組成的算術表達式，        

 求其值。                                                                        

                                                                                 

 43. 對于次數很高，但項目很少的多項式，可用鏈表來表示。                          

  例如：X^1000－76*X^76＋3*X^3－7可表示為                                        

  ┌─┬──┬─┐  ┌──┬─┬─┐   ┌─┬─┬─┐  ┌─┬─┬──┐          

  │1 │1000│  ┼→│-76 │78│  ┼→ │3 │3 │  ┼→│-7│0 │ NIL│          

  └─┴──┴─┘  └──┴─┴─┘   └─┴─┴─┘  └─┴─┴──┘          

 在此方式下，編程完成兩個多項式的加法與乘法。                                    

                                                                                 

 44. (一元多項式加法) 實現兩個整系數一元多項式的加法。例如, 對于多項式           

 5*X^6＋4*X^3－7*X^4＋1 與多項式 50*X^2＋4*X, 運算結果為：                       

 5*X^6－7*X^4＋4*X^3＋50*X^2＋4*X＋1。                                           

   程序要求：鍵盤輸入多項式的各項系數及指數，每項系數及指數為一組數據（系        

 數及指數之一可為零），以'0,0'結束一個多項式的輸入，結果按降冪排列，同類         

 項要合并（指數最大不超過３０）。                                                

   上例第一式的輸入為：    5,6                                                   

                           4,3                                                   

                          -7,4                                                   

                           1,0                                                   

                           0,0                                                   

  輸出結果應為：5*x^6-7*x^4+4*x^3+50*x^2+4*x+1.                                  

                                                                                 

 45. (數列的最小代價) 給定一個正整數序列，例如：4,1,2,3, 不改變數的位置把        

 它們相加， 并且由括號來標記每一次加法所得到的和。例如：((4+1)+(2+3))=           

 ((5)+(5))=10. 除去原數4、1、2、3之外，其余都為中間結果，如：5,5,10, 將中        

 間結果相加，得到：5+5+10=20, 數 20 稱為此數列的一個代價。對于另一種算法:        

 (4+((1+2)+3))=(4+((3+3))=(4+(6))=10, 得到數列的另一個代價為：3+6+10=19.         

 若給出 N 個數的數列，求出此數列的最小代價。                                     

                                                                                 

 46. 設有一個字符串，長度小于 100，且全部以英文字母組成。對字串中的每個字        

 母可用 0,1,2 三個數字進行編碼，且數字可以重復使用。                             

 程序要求：(1) 輸入字符串，并能判斷輸入是否有錯；                                

           (2) 輸出對應的編碼表及碼長，要求字串的編碼總長度為最短；              

           (3) 根據上述編碼表，給出一些編碼，然后求出其原字符串。