资源描述：
《489-台北市九十六学年度高级中等学校电脑程式设计竞赛决赛试题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、臺北市九十六學年度高級中等學校電腦程式設計競賽決賽試題(高中組)說明：1.本試卷共有四題，每題25分。2.請記得隨時備份自己的程式。試題：1.俄羅斯方塊給你兩塊俄羅斯方塊如圖(a)。每個俄羅斯方塊都是由小正方格所組成的任意形狀，彼此相連。每一塊俄羅斯方塊可以任意的進行90度順時鐘或逆時鐘的旋轉。給你兩個俄羅斯方塊，請找出一個將兩個俄羅斯方塊最緊密結合的方式。當然，彼此的小正方格不能重疊。以圖(a)為例。最緊密結合的方式為圖(b)。在圖(b)中有接觸到另一個俄羅斯方塊的小正方格，以灰色來表示，分別是編號024678。
2、所以在這個例子中，我們定義兩個俄羅斯方塊的緊密度是6。給你兩個俄羅斯方塊，請寫個程式，計算出最大的緊密度。輸入格式每個俄羅斯方塊的資料以一個正整數N開始。N是小正方格的數量。接著是N行的小正方格座標。第一個小正方格的座標永遠為00作為原點。然後以00為基礎，描述其他的小正方格，例如圖(a)中編號為0的小正方格是00，則編號1的小正方格為01，編號3的小正方格為0-1。以此類推。輸出格式請輸出兩個俄羅斯方塊結合的最大緊密度。彼此小方格不能重疊。輸入範例5600010-1111-140010-1001輸出範例62.城市
3、有一個國家有N個城市，其編號分別為1,2,3,…,N，其中編號1的城市是首都，已知每個城市至少會有一條道路直接跟其它城市相連(也就是沒有城市是到不了的)，例如：若城市2與城市3有道路直接相連，且這條道路長10公里，則以(2,3,10)表示這條道路(為簡化，我們假設所有道路長度都是整數)。現在國王想要由首都出發走訪ㄧ些城市，但他國務繁忙時間有限，無法走訪所有的城市，所以他想知道由首都出發到每個城市的最短距離，再來做進一步的決定。現在你就要為國王來設計這樣的程式以解決他的問題。輸入：data.in第一行為城市數；第二行
4、列出所有城市1跟其它城市直接相連的道路，以#結束；第三行列出所有城市2跟其它城市直接相連的道路，以#結束；…以此類推。範例：5(1,2,2)(1,3,5)(1,4,1)#(2,1,2)(2,3,3)(2,4,2)#(3,1,5)(3,2,3)(3,4,3)(3,5,1)#(4,1,1)(4,2,2)(4,3,3)(4,5,1)#(5,3,1)(5,4,1)#輸出：data.out第一行為首都(即城市1)到城市2的最短距離，中括弧內為依序所必須經過的城市編號；第二行為為首都到城市3的最短距離，中括弧內為依序所必須經過
5、的城市編號；…以此類推。2[]3[4,5]61[]2[4]提示：「中括弧內為依序所必須經過的城市編號」這部份較難，所以作答時你可以先以求出最短距離為主。3.實數的連續分數表示法任何一個有理數p/q都可以表示成唯一的連續分數,例如118/41=,其中每一個分數的分子都固定是1我們可以簡寫為118/41=[2;1,7,5]另一個有理數的例子12345/729=4115/243=[16;1,14,5,2,1]同樣的,一個無理數也可以用唯一的連續分數表示,但是分母會有無限多項,例如p=可以簡寫為p=[3;7,15,1,29
6、2,...]上面這種連續分數的表示法和用十進位表示時一樣都可能是有限位數或是無限位數，比較不太一樣的是用十進位表示時有理數也可能需要無限位數才能精確地表示出來，例如1/3，所有的無理數也都需要無限且不出現循環的位數來表示；使用連續分數來表示的話，有理數一定是有限位數，很多無理數的連續分數表示則會出現循環,例如Ö2(=21/2)=[1;2,2,2,....]=[1;(2)]，上式中我們用(2)代表2,2,...的循環；另外例如Ö3(=31/2)=[1;1,2,1,2,1,2,....]=[1;(1,2)]，上式中我們
7、用(1,2)代表1,2,1,2,....的循環;或如Ö31(=311/2)=[5;(1,1,3,5,3,1,1,10)]請注意一個無理數的連續分數表示法一定有無窮多項,如果只取有限項的話,一定小於所要表達的無理數,例如p>[3;7,15],p-[3;7,15]»8.321963´10-5根據上面的定義和特性描述，請撰寫程式完成下列功能1.[5]請由鍵盤輸入a,b,c,d,…z,-1,其中a,b,…,z為正整數,代表一[a;b,c,d,...,z]連續分數格式的有理數，請以p/q格式輸出該有理數(請將公因數約掉)2.
8、[5]由鍵盤輸入p和q兩個正整數,轉換有理數p/q6為連續分數的表示法並以[a;b,c,d,...,z]格式在螢幕上輸出1.[5]請輸入一兩個正整數(例如2,8),令此整數為s1及s2,利用三角函數atan()計算s1×p並將無理數s1×p轉換為連續分數的表示法到誤差小於10-s2,以[a;b,c,d,...]格式在螢幕上輸出,並印出s1×p與這個有理數之間
