台北市立高級中學八十七年度資訊學科能力競賽程式設計試卷.doc

时间就是金钱，效率就是生命！台北市立高級中學八十七年度 資訊學科能力競賽 程式設計試卷作答時間 180分鐘一. (有趣的數列問題, 20分)有一種有趣的數列可以由一個二位數 N開始產生, 其產生的規則如下: 求出 N2之值, 再將其百位及十位數留下, 又得出一個新的二位數; 依此方法, 可繼續產生新的二位數. 舉例而言, 若一開始時 N值為43, 那麼會產生的數列如下:A(0)=43 43*43=1849 取百位數及十位數; 得 84A(1)=84 84*84=7056 取百位數及十位數; 得 5A(2)=5 5* 5= 25 取百位數及十位數; 得 2A(3)=2 2* 2= 4 取百位數及十位數; 得 0A(4)=0 0* 0= 0 取百位數及十位數; 得 0A(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日之後的一個日子, X4001) 舉例而言, 西元1998年不是閏年, 故二月只有28日. 1998年1月 1日到1999年 1月 2日共經過一年又一天, 所以共經過 366天.輸入資料一律由鍵盤輸入參數 X, Y, Z之值, 1998=X4001.輸出資料一律由螢幕輸出經過之天數.輸入範例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 之值.輸入範例一500123571234輸出範例一格式不合輸入範例二87217107輸出範例二A+B=10030A*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=-1print ndo while lastnlast=nn=int(n*n/10) mod 100print nloop2. 日期計算這題也不需要算兩日期中間有幾個閏年幾個平年, 日期在二月前還是二月後直接這樣做days=0for year=1998 to 4000for 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 1000) 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 daynext monthnext year也許沒這麼直觀, 方法也相當爛, 總是拿到分數了.4000年距1998年大約730000天, 用 QB 可能要等一下, 不過我想一二十秒一定出得來3.k位數總和 a, 求第 b 個以k=5為例, 從 10000 到 99999 檢查總和是否為 a第 b 個找到的就是答案order=0for i=10(k-1) to 10k-1tmp=isum=0do while tmp0 這個迴圈算每一位數的總和 sum=sum+(tmp mod 10) tmp=int(tmp/10)loopif sum=a then order=order+1if order=b then print i endendifnext i4.大數n進位正整數加乘法大數加法:c=a+b (用陣列表示, 0是個位數), n表示位數, base表示幾進位carry=0for i=0 to ntmp=a(i)+b(i)+carryc(i)=tmp mod basecarry=int(tmp/base)next i大數乘法:c=a*b (用陣列表示, 0是個位數), n表示位數, base表示幾進位(我直接假設陣列夠大, 相乘不會超過)carry=0for i=0 to nfor j=0 to n-i c(i+j)=c(i+j)+a(i)*b(j)next jc(i+j)=c(i+j)+carrycarry=int(c(i+j)/base)c(i+j)=c(i+j) mod basenext i5.棋盤將士象問題這題方法好幾種, 首先可以用算法, 也可以用模擬的算的又分用手算和列式用電腦跑模擬的就看什麼方法了.遞迴是其中我覺得比較好寫的方法雖然我會算, 但很怕計算失誤, 我寧可用模擬的這裡我就不列出程式, 只不過就是遞迴產生各種將士象的可能位置用模擬的缺點是怕解數太多, 會跑太久, 使用前最好估計一下嗯, 假設將士象數量最多,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,