台北市立高级中学八十七年度资讯学科能力竞赛程式设计试卷.doc

时间就是金钱，效率就是生命！
台北市立高級中學八十七年度 資訊學科能力競賽  程式設計試卷
作答時間 180分鐘

一. (有趣的數列問題, 20分)
有一種有趣的數列可以由一個二位數 N開始產生, 其產生的規則如下: 求出 N^2之值, 再將其百位及十位數留下, 又得出一個新的二位數; 依此方法, 可繼續產生新的二位數. 舉例而言, 若一開始時 N值為43, 那麼會產生的數列如下:

 A(0)=43   43*43=1849 取百位數及十位數; 得 84
 A(1)=84   84*84=7056 取百位數及十位數; 得 5
 A(2)=5     5* 5=  25 取百位數及十位數; 得 2
 A(3)=2     2* 2=   4 取百位數及十位數; 得 0
 A(4)=0     0* 0=   0 取百位數及十位數; 得 0
 A(5)=0    因為 A(5)=A(4), 故停止

請你撰寫一程式來顯示開始為 N時, 逐次所產生的數列, 直到重覆時就停止.

輸入資料
一律由鍵盤輸入參數 N之值, N是一正整數, 1<=N<=99.

輸出資料
一律在螢幕上顯示逐次所產生的數列結果, 直到重覆時就停止. 每行最多顯示10個數, 數與數之間用逗點隔開. 如果超過10個數, 就另起一行, 再顯示後面的數, 依此類推.

輸入範例
43
輸出範例
43,84,5,2,0

二. (間隔的天數問題, 20分)
考慮西元 X年, 若 X可以為 4整除, 但不為 100整除, 或 X可以為 400整除, 則該年為閏年. 請撰寫一程式, 輸入三個整數 X, Y, Z, 試求自西元1998年 1月 1日到西元 X年 Y月 Z日共有幾日?(假設 X年 Y月 Z日是在1998年 1月 1日之後的一個日子, X<4001) 舉例而言, 西元1998年不是閏年, 故二月只有28日. 1998年1月 1日到1999年 1月 2日共經過一年又一天, 所以共經過 366天.

輸入資料
一律由鍵盤輸入參數 X, Y, Z之值, 1998<=X<4001.

輸出資料
一律由螢幕輸出經過之天數.

輸入範例
1999,1,2
輸出範例
366

三. ( k位數數字和問題, 20分)
考慮 k(<=5) 位的十進位整數所有數字的和等於 m, 其中最高位的數字不能為 0, 其餘位數可以為 0. 試寫一程式依序輸入  k,m,n 並求出所有滿足上述條件的
k位整數中第 n小的數. 舉例而言, 三位整數中所有數字和等於 6的由小到大為
105,114,123,132,141,150,204,213,222,231.... 其中第 5小的數為 141.

輸入資料
一律由鍵盤輸入參數  k,m,n 之值, 2<=k<=5.

輸出資料
一律由螢幕輸出答案.

輸入範例
3,6,5
輸出範例
141

四. (巨大整數計算問題, 20分)
受限於記憶單元儲存整數容量限制, 使用傳統程式語言設計程式時, 我們無法直接對巨大的整數進行算術運算. 本題目希望你設計出一個可執行巨大位數數字運算的 N進位正整數加法器與乘法器. 此程式接受三個輸入, 分別為 N,A與 B, 其中 N是一個 2至10之間的整數 (含 2與10),而 A與 B則是兩個以字串形式表示的N進位非負整數. 為方便程式設計, 你可以假定 A, B 兩字串的位數均 <= 40.你的程式需要判定輸入格式是否無誤, 然後正確的計算出  A+B 與  A*B 之值,最後再將結果以 N進位的格式印出. 舉例而言, 下列輸入範例一中, N=5,A=00123,B=571234.  由於 A中最高位數是 0, 此外, B中含有 5,7 兩數大於 4, 故輸出"格式不合". 範例二則做八進位之加法及乘法 (721+7107及721*7107).

輸入資料
一律由鍵盤輸入三行數字. 第一行含 N之值, 第二行含字串 A之值, 第三行含字串 B之值.

輸出資料
一律由螢幕輸出答案. 若輸入有誤, 請輸出"格式不合", 否則以 N進位格式分成
兩行輸出 A+B及A*B 之值.

輸入範例一
5
00123
571234
輸出範例一
格式不合

輸入範例二
8
721
7107
輸出範例二
A+B=10030
A*B=6367367

五. (象棋盤面問題, 20分)
象棋遊戲中將, 士, 象在棋盤上的合法位置如圖所示. 試寫一個程式依序輸入將, 士, 象的個數 (其中, 將的個數一定為 1, 士象的個數為 0至 2),輸出其不同的盤面總數. 舉例而言, 輸入範例一中只有一個將在棋盤上, 則有 9種不同的可能盤面. 輸入範例二中有一個將和一個士, 則有 5*8=40 種不同的可能盤面. 輸入範例三中有一個將和一個象, 當象在九宮內時, 將的位置有 8種可能; 象不在九宮內時, 將的位置有 9種可能, 故有 1*8+6*9=62 種不同的可能盤面.

輸入資料
一律由鍵盤輸入將的個數(固定為 1), 士的個數(0至2), 象的個數(0至2), 此三
個數字中間以逗號隔開.

輸出資料
一律由螢幕顯示盤面總數.

輸入範例一
1,0,0
輸出範例一
9

輸入範例二
1,1,0
輸出範例二
40

輸入範例三
1,0,1
輸出範例三
62

將士象在棋盤上的合法位置
┌ ┬ ┬將將將┬ ┬ ┐
├ ┼ ┼將將將┼ ┼ ┤
├ ┼ ┼將將將┼ ┼ ┤
├ ┼ ┼ ┼ ┼ ┼ ┼ ┼ ┤
├ ┴ ┴ ┴ ┴ ┴ ┴ ┴ ┤

┌ ┬ ┬ 士 ┬ 士 ┬ ┬ ┐
├ ┼ ┼ ┼ 士 ┼ ┼ ┼ ┤
├ ┼ ┼ 士 ┼ 士 ┼ ┼ ┤
├ ┼ ┼ ┼ ┼ ┼ ┼ ┼ ┤
├ ┴ ┴ ┴ ┴ ┴ ┴ ┴ ┤
┌ ┬象┬ ┬ ┬象┬ ┐
├ ┼ ┼ ┼ ┼ ┼ ┼ ┼ ┤
象┼ ┼ ┼象┼ ┼ ┼象
├ ┼ ┼ ┼ ┼ ┼ ┼ ┼ ┤
├ ┴象┴ ┴ ┴象┴ ┤

1.一個兩位數數列, 該數平方取百位十位成為下一項
last=-1
print n
do while last<>n
 last=n
 n=int(n*n/10) mod 100
 print n
loop

2. 日期計算這題
也不需要算兩日期中間有幾個閏年幾個平年, 日期在二月前還是二月後
直接這樣做
days=0
for year=1998 to 4000
 for month=1 to 12
   for day=1 to days_of_month(month)
     if month=2 and day=29 then
       if (year mod 4=0 and year mod 100<>0) or (year mod 400=0) then
         days=days+1
       endif
     else
       days=days+1
     endif
     if year=input_year and month=input_month and day=input_day then
       print days-1
       end
     endif
   next day
 next month
next year
也許沒這麼直觀, 方法也相當爛, 總是拿到分數了....
4000年距1998年大約730000天, 用 QB 可能要等一下, 不過我想一二十秒一定出得來

3.k位數總和 a, 求第 b 個
以k=5為例, 從 10000 到 99999 檢查總和是否為 a
第 b 個找到的就是答案
order=0
for i=10^(k-1) to 10^k-1
 tmp=i
 sum=0
 do while tmp>0              '這個迴圈算每一位數的總和
   sum=sum+(tmp mod 10)
   tmp=int(tmp/10)
 loop
 if sum=a then order=order+1
 if order=b then
   print i
   end
 endif
next i

4.大數n進位正整數加乘法

大數加法:
c=a+b (用陣列表示, 0是個位數), n表示位數, base表示幾進位
carry=0
for i=0 to n
 tmp=a(i)+b(i)+carry
 c(i)=tmp mod base
 carry=int(tmp/base)
next i

大數乘法:
c=a*b (用陣列表示, 0是個位數), n表示位數, base表示幾進位
(我直接假設陣列夠大, 相乘不會超過)
carry=0
for i=0 to n
 for j=0 to n-i
   c(i+j)=c(i+j)+a(i)*b(j)
 next j
 c(i+j)=c(i+j)+carry
 carry=int(c(i+j)/base)
 c(i+j)=c(i+j) mod base
next i

5.棋盤將士象問題
這題方法好幾種, 首先可以用算法, 也可以用模擬的
算的又分用手算和列式用電腦跑
模擬的就看什麼方法了...遞迴是其中我覺得比較好寫的方法
雖然我會算, 但很怕計算失誤, 我寧可用模擬的
這裡我就不列出程式, 只不過就是遞迴產生各種將士象的可能位置
用模擬的缺點是怕解數太多, 會跑太久, 使用前最好估計一下
嗯, 假設將士象數量最多,1,2,2,且位置可重複, 可能數是:
9*5*5*7*7=11025, 也不過一萬出頭, 所以模擬的肯定沒有問題

要聲明的是上面展現的也許算是錯誤的示範吧,
只要求達到題目要求, 拿到分數就好是在比賽時應急的想法
我這麼寫是想讓那些比賽當時沒寫出來的同學知道,
在比賽時有些題目不要想太複雜, 方法也許差了點, 但還是可以接受的.
而平常自己在練習時要求當然要更高才行

棋盤將士象的問題, 若大概會一點排列組合要用手算並不是難事, 不懂的同學請
參考基礎數學第四冊第一章的內容.

假設士與象的個數分別是 a,b, 因為士跟象彼此並不會擋到, 所以我把將的位置
分成三種情況討論:
   1.將占到士能站的位置
     可能的盤面數 = 將的可能位置 * 士的可能位置 * 象的可能位置
                  =  C(5,1)      *  C(4,a)      *  C(7,b)
   2.將占到象能站的位置
     可能的盤面數 = 將的可能位置 * 士的可能位置 * 象的可能位置
                  =  C(1,1)      *  C(5,a)      *  C(6,b)
   3.將在其他位置
     可能的盤面數 = 將的可能位置 * 士的可能位置 * 象的可能位置
                  =  C(3,1)      *  C(5,a)      *  C(7,b)

全部有可能出現的盤面數 = C(5,1)*C(4,a)*C(7,b)+
                        C(1,1)*C(5,a)*C(6,b)+
                        C(3,1)*C(5,a)*C(7,b)
再分別代入 a,b  就行了, 或是求出這式子再讓電腦來算也行.

唯有惜时才能成功，唯有努力方可成就！