基隆商工第八届校内ACM程式设计竞赛试题.doc

基隆商工第八屆校內ACM程式設計競賽試題 首先，輸入都是假設採用輸入檔案 (檔名為ProbX.in X表示題號例如試題二的輸入檔是Prob2.in) 的方式，輸出檔名為 Prob2.out)，如果參賽者在平常上課中並未學過這種方法，可考慮改用鍵盤的方式作為輸入測試資料的方法。而且除非特別指明，否則一個空白與連續多個空白視為相同。 請將答案存在磁片中(不需加子目錄，因為將直接以磁片上註明的題號為準)而且不論對、錯，都只有告知結果，而不會還磁片，所以在送審前先自行存在C,或D 碟中備份好！而且存檔的檔名為”T隊號_題號.bas (.bas看語言不同自行調整，例如perl則為.pl)=一、畫星星現在要用一堆星星的符號來表示一個近似直角三角形的形狀。並用M來表示這個三角形的高度與寬度。輸入檔案格式：第一行是一個整數 K, 表示有K組測試資料。而接下來的K行分別表示 K組樣本。在每個樣本的那一行中有一個整數 M ( 1Mdoog,代換就是先準備對照表，再依表代換每個文字(例如最簡單的 fire= gjsf)。而DES加密法的原理亦是如此。其中為了將64bit的資料位置打散，所以準備了一個8*8的對照表，在上面填上164的數字，代表將要放入的bit,來打散原來的資料。再加上16回合的加密(解密)過程而成。現在為了簡化問題，我們假設原來輸入的是16bit的資料，而且只有考慮打亂順序的部分。請參考4*4的位置變換對照表，來將原資料打散。並將打散後的結果印出。輸入檔案格式：第一行是一個整數 K, 表示有K組測試資料。而接下來有K組樣本。在每個樣本的行數都是五行，其中的第一行是輸入的16個字的密文(由a到z)(A到Z)(./)(0到9)共有64種可能字元所組成),接下來的四行，各有四個數字，所以共有16個 1到16的數字。(剛好各寫一次)輸出檔案格式：如果有K組輸入，也就應有K組的輸出(每組一行)。將放入的原密文按照先印完水平行再印下一水平行直到印完16個字元。輸入檔範例21234567890abcdef4 3 2 116 15 14 135 6 7 89 10 11 12 ./WR56Z890abcdef4 3 2 112 15 14 135 6 7 89 10 11 16輸出檔範例4321fedc567890abRW/.bedc56Z890af五、文字排序問題： (ascii sort)有一個輸入檔，這個檔是由文字數字組成的文字檔，現在是用空白來分隔開為一個個的單字，請將這些單字，按ASCII的順序排序之。輸入檔案格式：內容是一個文字檔，可以包含英文數字。只有一組測試資料。但個數必需自己計算。輸出檔案格式： 將這些單字先每行一個單字印一遍，再印出一行Now sorting.，再按照 ascii的順序排序後，每個單字自成一行再印一遍。輸入檔範例test0 test09 test8 test test99 TQXYZ輸出檔範例test0test09test8 test test99 TQXYZNow sorting.TQXYZtesttest0test09test8test99六之一RFC & port：(本題為二選一,二者皆可因為程式應該是完全相同)RFC是在網路世界中定出通訊方法的文件，在發展通訊程式，常要參考這些文件資料，現在為了方便搜尋參考資料所以請由輸入檔案，來得知要參考的RFC編號為多少？例如想看smtp傳送郵件的協定，就可以參考RFC821，想了解ftp檔案傳輸的協定，就可以參考RFC959。輸入檔案格式：內容是一個文字檔，每一行只有一個:用來分隔成前後兩段，前段是網路應用的英文縮寫，後段則是 RFC的編號資料，在發現五個=號，表示開始查詢。查詢的英文字可能有一個以上，且可能會有大小寫混用的情形，請印出查到的RFC號碼。輸出檔案格式：每一個查詢先印出要查的英文(大寫)，再印一個:, 最後再印出一個RFC+編號, 若沒發現則RFC+編號的位置則印出”not found”。輸入檔範例：smtp:RFC821ftp:RFC959telnet:RFC854gopher:RFC1436usenet:RFC977nntp:RFC977finger:RFC742IP:RFC791TCP:RFC793UDP:RFC768=smtpTelnetwinzipFTP輸出檔範例：SMTP:RFC821TELNET:RFC854WINZIP:not foundFTP:RFC959六之二：port (埠號)port 是在網路世界中簡單實現一部電腦，多種服務的機制。如果你曾玩過bbs或mud之類的遊戲，應該知道 port的重要性，如 未來最舊小站的 telnet 3002 在網址後面加上的數字 3002就是一個port-number(埠號)，而不同的網路服務也常有固定的埠號，現在為了方便搜尋各種服務的標準埠號所以請由輸入檔案，來得知要參考的port編號為多少？例如想使用News_server (新聞群組伺服器)就可以連到 port 25 (telnet localhost 25)，想使用ftp檔案傳輸，就可以連到 port 21(telnet localhost 21)(註：因為一般的telnet port 是23 , 其他的port號，則因服務不同而有不同反應，但一般皆有 help,quit 等指令可看出是否動作正常。)輸入檔範例：WWW:port80HTTP:port80smtp:port25pop3:port110ftp:port21telnet:port23gopher:port70Usenet:port119nntp:port119finger:port79whois:port43ping:port7time:port13mysql:port3306=smtpTelnetwinzipFTP輸出檔範例：SMTP:port25TELNET:port23WINZIP:not foundFTP:port21七、找出關鍵字所在的那行，並排序，(grep+sort)在處理系統的記錄檔的時候，(例如Linux的 $last 指令, 或是/var/log)常常是文字檔的形式，現在想要由這個檔案中找出特定使用者的那一行資訊出來，(就是所謂的grep)而且可能因為種類很多，可能ftp ,telnet .所以希望可以將這些過濾出來的資料行可以再作一下排序的動作，如此即可容易的觀察該使用者的使用情況。例如：假設有以下的 系統記錄檔。檔名為 last_testuser1 tty1 Sun May 27 18:56 still logged in user3 pts/0 :0 Sun May 27 10:12 - down (00:48) user1 pts/1 :0 Sat May 26 23:22 - down (01:41) user1 tty1 Sat May 26 16:13 - down (08:51) reboot system boot 2.2.17-14 Sat May 26 16:11 (08:52) user1 pts/4 :0 Sat May 26 15:44 - 16:07 (00:23) user3 pts/6 bn04 Sat May 26 15:02 - 16:07 (01:05) user1 pts/5 :0 Sat May 26 15:02 - down (01:07) user2 tty4 Sat May 26 14:12 - down (01:57) user2 ftpd11001 bn04.klcivs.kl.e Tue May 22 18:59 - 18:59 (00:00) 現在輸入一個使用者的名字，就可過濾出該使用者的記錄行，並且按排序的順序印出。例如要查 user1 則結果為：user1 pts/1 :0 Sat May 26 23:22 - down (01:41) user1 pts/4 :0 Sat May 26 15:44 - 16:07 (00:23) user1 pts/5 :0 Sat May 26 15:02 - down (01:07) user1 tty1 Sat May 26 16:13 - down (08:51) user1 tty1 Sun May 27 18:56 still logged in 例如要查 user2 ，則結果為：user2 ftpd11001 bn04.klcivs.kl.e Tue May 22 18:59 - 18:59 (00:00) user2 tty4 Sat May 26 14:12 - down (01:57) 輸入user1,或user2的方式，自由決定。八、IP的問題 在 Internet 上是用 Ip來識別不同的電腦，就像電話號碼，因為大家都不同，所以可以打出國際電話也不會弄錯通訊對象。而IP是由InterNIC()所統籌管理的。IP最早的設計是有4個0到255的數字所組成。(下一代的IP有6位，簡稱為IPv6)對於這些IP為了方便運用，所以分為幾個類別，主要是A,B,C 三類，分辨這些類別的方法是由最前面的三個位元。任何一個IP是由32個二進位所組成。等級分類中的A 是第1位元 0 加上 7個位元網路識別號(NetId), 加上 24個位元的主機識別號(HostId)，等級分類中的B 是由前兩位元的10 加上14位元網路識別號(NetId), 加上 16個位元的主機識別號(HostId)，等級分類中的C 是由前三位元的110 加上21位元網路識別號(NetId), 加上 8個位元的主機識別號(HostId)，為了方便了解，所以只要由第一個十進位的數字即可判別：等級A=1126 , 等級B=128191 ,等級C=192223 ,特別的 127開頭的ip是localhost若有其他的 IP，在此，我們就認為是其他 (other)即可。同時，關於IP的表示方法常用加點的4個十進位數字法(dotted decimal notational)之外，還有一種直接用一個十進位數字的表示法，例如 就可以表示為 127*2563+70*2562+60*256+1 = 3527818241所以如果要 ping 可以簡寫成 ping 3527818241，如果要35就可以ttp:/3527818731 (因為4個十進位數字可以想成256進位的數字) 現在要請各位完成的任務是(1)看這IP 的分級與(2)表示成單1個十進位數字表示法。輸入檔案格式：內容是一個文字檔，每一行只有一個 IP(有用三個點號分開的四個十進位數字)，而每一個數字都是 0255的合法數字。輸出檔案格式：先印出單一個十進位數字表示的IP, 並空一格後印出代表的級數，要考慮的級數有 A,B,C,localhost,other.輸入檔範例：357輸出檔範例：3527818241 Cother3527818731 C2130706433 localhost2356221747 B167903269 A九、CIDR (Classless Inter-Domain Routing)不分級網域間路由 在IPv6普及前，IP已嚴重不足，為了緩合這情況，提出CIDR的方式可以不理會ABC的分級，而且近日來寬頻愈來愈多，如果一天你申請了一個固定IP，則常見的情況是你將獲得8個IP,但只可用5個，為什麼呢？因為第一個IP為子網路代號(NetId)，第二個IP作為閘道器用(Gateway), 最末個IP作為區域內的廣播用(Broadcast)。例如 八個IP則 NetId是 ，GateWay是, 廣播是 可以自由使用的範是 五個IP。為了表達較特殊的 mask設定方式，可參考CIDR ，透過遮罩(mask)來分割子網路。本校用的IP是C級，而mask是 ，現在CIDR就是希望可以表示其他的mask,例如將C級的256個網路機器分為兩個128的子網路。只要將mask設為28對於設mask的方式，因為 共有24個1,8個0所以 CIDR 表示為 /24, 而 28則可表示為 /25 , 同理48表示為29個1,5個0 可用 /29來表示遮罩。 如果你對上述有初步的了解，那可以開使看以下的問題：(為了簡化問題，所以請只要注意IP中的第四個數字即可！, 而且以下的問題都可假設是 /29 )假設有個朋友的 IP 0/29 那請問他的 NetId,Gateway, Broadcast,mase各是多少？ 因為是 /29 所以是每個 子網路有8個IP, 所以可將IP分組成07, 815,1623.因為這個IP 是 .10 所以是在第二組組中，所以 NetId 是.8, Gateway是.9,Broadcast是.15 而mask 是 48輸入檔案格式：內容是每行一個數字x,代表192.168.0.X /29的IP,X的範圍是在0255輸出檔案格式：三個數字，分別代表 NetId, Gateway, Broadcast輸入檔範例：158724915253輸出檔範例：0 1 70 1 78 9 150 1 7248 249 2558 9 15248 249 255十、RE 正則表示式： 本問題是請完成一個固定的re 表示式 p?r.*$在 ms-dos 中有所謂的 dir ，可以列出檔案的名稱。而在列檔前，可用萬用字元(Wildcard)的?*來表任意一字元、任意數量的任意字元。而這種方法，在Linux或Unix的世界中也可，而且也可用 x表示某字元不是x字元。例如想找所有字尾不是k的檔案的方法： $ls *k enter. 。另外在Linux中也有另一種稍不易學，但卻功能卻更強的表示法：Regulrr