九十学年度高级中学资讯学科能力竞赛决赛

《九十学年度高级中学资讯学科能力竞赛决赛》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、九十學年度高級中學資訊學科能力競賽決賽注意事項：1.所有程式的輸入檔的路徑為目前工作目錄。(Currentworkingdirectory)2.所有發展的程式必須在一分半鐘以內於試場的電腦輸出結果，否則不予計分。程式設計題（每題20分，共100分）1.影像之結構化特徵在影像比對中，有一種方法是利用影像中的邊緣(edge)資訊，計算每個邊緣資訊中具有代表性的結構化特徵，以作為比對兩張影像是否相似的判斷標準。Water-filling方法是從每個邊緣圖的一個端點開始，繞著相連的邊緣點走並依序編號。若走到某一步時，遇到一個以上不同的連接點，則分成不同路徑同時繼續走，直到沒有任何連接點為止。如果一個

2、點和另一個點為左右相鄰或上下相鄰，就稱為連接。例如，在圖一的影像中包含三個邊緣圖，每個邊緣圖由一些互相連接的邊緣點構成。圖中以黑色的方塊代表邊緣點，白色的方塊代表背景。在Water-filling方法中，首先，從第一列(row)開始，由左至右，由上至下，先找到第一個黑點並編號為1。接著，找1的下一個尚未編號的連接點並編號為2。依此方法繼續往下一個點前進並依序編號。在編號6的點之後有兩個尚未編號的連接點，此時，則分為兩條路線，並同時編號為7繼續往下走。當走到沒有任何的相連點時，則結束現有邊緣圖的編號，並繼續對影像中的其它邊緣圖編號。走完圖一所有邊緣圖後所得到的編號如圖二所示。所以，走完這三個邊

3、緣圖所需要的步數分別為12、7及3；所以，12、7及3可以作為代表此張影像的結構化特徵。請注意：位於斜對角上的兩點不能算做連接，如：123459876710871118231211109411052763圖一圖二請撰寫一個程式計算每個影像中，以water-filling方法走完其中所有的邊緣圖後，將每個邊緣圖需走的步數依走訪的順序列出。輸入說明:輸入檔案包含一個正方形的影像。每組影像以圖的寬度n開頭(1<=n<=50)，接下來的n行代表影像的內容：0表示背景的白點，1表示黑色的邊緣點。１輸出說明:對每一個輸入的影像，以water-filling方法走完所有的邊緣圖後，先印出此張影像中共有幾個

4、邊緣圖。接著，將每個邊緣圖需走的步數依走訪的順序列出。範例一:輸入:100000000000001111000000000100000011111000001011010000100101100011110010010001001001000001100100000000輸出:31273範例二:輸入:9000000011111111101100000101111111101100010101100010101111111101000000001000000011輸出:21112２2.王位繼承某王國其王位繼承的規則如下:(1)此國家重男輕女，只有皇室成員中的男性才有繼承權。(2)若國王退位或去

5、世，此時王位由國王在世的兒子繼承，年紀較大的優先繼承。(3)若國王退位或去世時，國王沒有在世的兒子，此時王位由國王的弟弟繼承，年紀較大的優先繼承。(4)若國王退位或去世時，沒有在世的兒子與弟弟，此時王位由國王在世的叔叔繼承，年紀較大的優先繼承。(所謂叔叔是指父親的弟弟)(5)若國王退位或去世時，沒有在世的兒子、弟弟、與叔叔，此時王位由國王在世的叔公繼承，年紀較大的優先繼承。（所謂叔公是指祖父的弟弟）我們以下面這個家族樹(familytree)為例來說明上述規則(假設不在樹上的人皆已去世，不需要列入考慮)。如果目前的國王是Charles，根據上述規則，當Charles退位或去世時，可能繼位者的

6、繼承優先順位依序為William、Edward、Adam、Benjamin、Peter、Chris與Bill。其中Adam排在William與Edward之後表示當現任國王Charles退位或去世時，如果William與Edward也都已經去世，Adam便可以繼承王位。同樣考慮下面這個家族樹，如果目前的國王是Peter，當Peter退位或去世時，繼位者的優先順位則為Allen、Chris與Bill。RobertGeorgeBillTomPeterChrisJohnCharlesAdamBenjaminAllenJamesWilliamEdward請撰寫一個程式，依據輸入的一棵家族樹與現任國王

7、名稱，將此家族樹中未來可能繼位者依繼承優先順位列出。所輸入的家族樹是一棵以現任國王或其某一位祖先為樹根的家族樹，樹中的成員都是男性，而且必定包括現任國王。３輸入說明：第一行是現任國王的名字。第二行之後，每一行是成對的父子名字，中間以一個空格隔開。若有兩對名字而其父親名字相同，先出現者，其年紀大於後出現者。每個名字由長度不大於30個的英文字元(a~z,A~Z)構成，大小寫字元視為不同。此外，家族成員最多不超過3