節點為根節點的字符串形式。程序輸出無根樹的字符串形式時，各個節點的名稱無        

 關緊要，所有節點都以Ｐ表示，以后的各種輸出也采用這種形式。例如：輸入無根        

 樹的字符串形式：Ａ（Ｂ（ＣＤ（ＥＦ））），指定根節點為Ｄ，程序應能輸出          

 Ｐ（Ｐ（ＰＰ）ＰＰ），Ｐ（ＰＰ（ＰＰ）Ｐ），Ｐ（ＰＰＰ（ＰＰ））中的任意        

 一種即可。                                                                      

    任務二：輸入兩個串表示的無根樹，判斷其結構是否一樣。注意它與節點名稱         

 無關，只考慮結構。                                                              

    任務三：輸入無根樹的總枝數Ｎ（1<=N<=11），輸出所有枝數為Ｎ的互不相同         

 的無根樹，并記錄總數。以字符串形式輸出，例如：N=5 時共有６種不同結構的無        

 根樹。                                                                          

    注意：各種樹結構的字符串表達形式不唯一。                                     

                                                                                 

 60. 用Ｎ＊Ｎ（１＜＝Ｎ＜＝８）的格點陣代表海，其中＊號代表島。給你一組編        

 碼信息，讓你重構一張地圖。這組信息是按垂直方向，水平方向島的情況摘取的。        

 下例中，每行右邊的數字按順序表示該行中“島組”的大小，如第一行數字為            

 “１２”，表示該行第一“島組”由一個島組成，第二“島組”由兩個島組成，而        

 第四列下面的“２３”則表示本列由兩個“島組”組成，第一個“島組”由兩個島        

 組成，第二個“島組”由三個島組成。                                              

    任務：編程執行以下步驟，直到給定的輸入 (ASCII) 文件中的信息組全部讀完        

 為止，步驟如下：                                                                

   （１）從輸入文件 (ASCII 文件）中讀入下一個信息塊，并將它顯示在屏幕上。        

 每個信息塊組成為：                                                              

    格點陣大小 (N)，以后是行的約束條件（Ｎ行的），列的約束條件（Ｎ列的）,        

 每行（或每列）的約束條件是                                                      

    一行數字，數字間有空格，最后用０結束。上面的例子如圖所示。                   

   （２）重構這張地圖（若有多個解，要逐個構成地圖），并顯示。                    

   （３）將重構的地圖以ＡＳＣＩＩ文件形式輸出。每島以＊后加一個空格表示；        

 空白處用連續的兩個空格表示。若同一已知條件可畫出多張地圖，相互間用空行隔        

 開；若一組已知條件畫不出地圖，用“ＮＯ  ＭＡＰ（占一行）表示。由不同的信        

 息組求得的解用“ＮＥＸＴ  ＰＲＯＢＬＥＭ”（占一行表示）１＜＝Ｎ＜＝８.         

                                                                                 

 61. 一個餐廳在相繼的Ｎ天里，第 i 天需要 Ri 塊餐巾(i=1，2，...，N)。餐廳         

 可以從三種途徑得到餐巾:                                                         

   (1) 購買新的餐巾，每塊需Ｐ分；                                                

   (2) 把用過的餐巾送到快洗部，洗一塊需Ｍ天，費用需Ｆ分(Ｆ＜Ｐ)；                

   (3) 把餐巾送到慢洗部，洗一塊需Ｎ天(Ｎ＞Ｍ)，費用需Ｓ分(Ｓ＜Ｆ)。              

 在每天結束時，餐廳必須決定將多少塊用過的餐巾送到快洗部，多少塊送慢洗部，        

 多少塊保存起來延期送洗。在每天開始時，餐廳必須決定是否購買新餐巾及購買多        

 少，使洗好的和新購的餐巾之和滿足當天的需求量Ri，并使Ｎ天總的費用最小。請        

 編程輸入總天數，每天所需的餐巾塊數以及每塊餐巾的新購費用Ｐ，快，慢洗費用        

 Ｆ，Ｓ，和所需天數Ｍ，Ｎ，輸出每天開始時需購新餐巾數，結束時送快，慢洗部        

 和延期送洗的餐巾數。                                                            

                                                                                 

 62. ( 旅行商 ) 一個推銷員計劃做一次旅行，他必須訪問如圖所示每個城市。每         

 兩個城市的路徑旁標有路徑。要求從城市Ａ出發，訪問每個城市一次，且只訪問一        

 次，最后返回城市Ａ，求一條距離最短的路線。                                      

                                                                                 

 63. (tic__tac__toe 游戲) tic__tac__toe 游戲的規則是：從一個空的 (N*N) 的        

 棋盤（例如Ｎ＝３）開始，甲乙二人輪流將棋子放置在棋盤上未被占據的方格中，        

 例如甲第一個放，他把棋子放在中央的方格里， 然后輪到乙放，他把棋子放在第        

 一行中間的方格里。于是又輪到甲放，......如此進行下去。判定勝負的方法是：        

 若某一游戲者有Ｎ枚棋子占據了一橫行，或一豎列，或一對角線，則此人獲勝；若        

 直至整個棋盤被占滿還沒有一方獲勝，則為平局。                                    

     ┏━┯━┯━┓         ┏━┯━┯━┓         ┏━┯━┯━┓                

     ┃  │  │  ┃         ┃  │  │  ┃         ┃  │Ｏ│  ┃                

     ┠─┼─┼─┨         ┠─┼─┼─┨         ┠─┼─┼─┨                

     ┃  │  │  ┃         ┃  │Ｘ│  ┃         ┃  │Ｘ│  ┃                

     ┠─┼─┼─┨         ┠─┼─┼─┨         ┠─┼─┼─┨                

     ┃  │  │  ┃         ┃  │  │  ┃         ┃  │  │  ┃                

     ┗━┷━┷━┛         ┗━┷━┷━┛         ┗━┷━┷━┛                

                                                                                 

 64.  以字符串形式由鍵盤輸入兩個高精度的８進制正整數，串長小于２５５，以         

 第一個數為被除數，第二個數為除數，進行高精度除法運算，并顯示按 8 進制表         

 示的商和余數。                                                                  

 ( 參看程序 8 )                                                                                

 

 65. ( NOI'94.1_1 ) 鍵盤輸入一個僅由小寫字母組成的字符串，輸出以該串中任         

 取Ｍ個字母的所有排列及排列總數。                                                

                                                                                 

 66. ( NOI'94.1_2 ) 編程實現兩個高精度實數減法，兩數分別由鍵盤輸入，均不         

  超過２４０位。                                                                  

 ( 參看程序 5 )                                                                                

 

 67. ( NOI'94.1_3 ) 一個實數數列共有Ｎ項，已知a(i)=(a(i-1)-a(i+1))/2+d，         

（１〈i〈Ｎ）(N<60) , 鍵盤輸入Ｎ，d，a(1)，a(n)，m，輸出 a(m)。                  

                                                                                 

 68. ( NOI'94.1_4 ) 鍵盤輸入一個高精度的正整數Ｎ，去掉其中任意Ｓ個數字后         

 剩下的數字按原左右次序將組成一個新的正整數。編程對給定的Ｎ和Ｓ，尋找一種        

 方案使得剩下的數字組成的新數最小。輸出應包括所去掉的數字的位置和組成的新        

 的正整數。（Ｎ不超過２４０位）                                                  

 

 69. 在兩個文本文件中各存有一個以西文制表符制成的未填入任何表項的表結構，        

 分別稱之為表１和表２，要求編程將表１和表２下述規則合并成表３：                  

     規則：表１在表２之上，表１和表２的左邊框對齊，將表１的最低行與表２的        

 最頂行合并。例：在你的Ｃ盤根目錄下有兩個文件 t0.1 和 t0.2，分別存放上述         

 的表１和表２，經上述規則合并后得到表３，放在文件中。三張表見下圖：              

  ┎─┰─┰─┰─┒                                ┎─┰─┰─┰─┒           

  ┃  ┃  ┃  ┃  ┃        ┎┰─┰─┒            ┃  ┃  ┃  ┃  ┃           

  ┠─╂─╂─╂─┨        ┃┃  ┃  ┃            ┠─╂─╂─╂─┨           

  ┃  ┃  ┃  ┃  ┃        ┖┸─┸─┚            ┃  ┃  ┃  ┃  ┃           

  ┖─┸─┸─┸─┚                                ┠┰┸┰┸┰┸─┚           

                                                    ┃┃  ┃  ┃                 

                                                    ┖┸─┸─┚                 

        表１                    表２                     表３                    

    編程要求：                                                                   

   (1) 程序應能自給定的文件中讀入兩個源表并顯示。                                

   (2) 若源表有錯，應能指出其錯。                                                

   (3) 將表１和表２規則合并成表３，并顯示之。                                    

   (4) 所有制表符的ＡＳＣＩＩ碼應由選手自己從給出的示例文件中截取。              

 

 70. (圓盤問題) 從左向右依次安放 4 根細柱 A,B,C,D. 在 A 上套有 N (N≤20)        

 個直徑相同的圓盤, 從下到上依次用連續的小寫字母 a,b,c,...編號, 將這些圓盤        

 經過 B, C 單向地移入 D (即不允許從右向左移動). 圓盤可在 B,C 中暫存. 從鍵        

 盤輸入 N, 及前 N 個小寫字母的一個排列, 它表示最后在 D 盤上形成的一個從下        

 到上的圓盤序列. 請用文本文件 ANS2.TXT 輸出形成這一排列的操作過程.               

   該文件的每一行為一個形如 "k M L" 的字母序列, 其中 k 為圓盤編號, M 為 k        

 盤原先的柱號, L 為新柱號. 或者直接在屏幕上輸出"No",表示不能生成這種排列.        

     例:                                ┃      ┃      ┃      ┃               

     鍵盤輸入:                          ┃      ┃      ┃      ┃               

         3                        d   ━╋━    ┃      ┃      ┃               

         acb                      c   ━╋━    ┃      ┃      ┃               

     則一個正確的輸出文件         b   ━╋━    ┃      ┃      ┃               

  可以是:                         a   ━╋━    ┃      ┃      ┃               

      c  A  B                       ━━┻━━━┻━━━┻━━━┻━