台大資工九十八學年度甄試入學，程式設計考題

這次參加台大資工的二階甄試，選擇了據說很難的程式設計。結果雖然大致上解出了每個問題，但似乎都有些粗心的小錯誤。不知道會得幾分呀？

題目共有四題，每題 25 分，要在三小時內解完。

我解完前三題時好像還剩下許多時間，然而第四題一直想不到好的解法。回頭看看前三題，抓出了一些小錯誤，想不到最後還是有沒發現的疏忽啊。然後雖然寫出了可能行的通的第四題解法，不過似乎會在某些情況下陷入無限迴圈呢。

註：其實我不太記得題目，以下乃參考他人分享而來，可能和原題目有出入，但意思上大致是不變的。

一、吊死鬼遊戲

吊死鬼猜單字遊戲，給你答案字串(長度<=10)及玩家猜的字母，印出遊戲每個步驟所顯示的字串。
尚未被猜出的字以 * 表示，已猜出的則顯示字母。

輸入的第一行是要猜的單字，接下來的每一行會有一個字母，表示玩家每次猜的字母。

輸出的每一行為遊戲的狀態。

Sample Input:
hangman
a
n
g
p
h
t

Sample Output:
*******
*a***a*
*an**an
*ang*an
*ang*an
hang*an
hang*an

這題很簡單，我用最直接的寫法：把字串讀入一陣列，接著再依序讀入每個猜測字母，從 0 到字串尾逐字掃描，遇到相同的字母就把另一個預先設的***字串中同一位置以此字母取代。

當然理論上用 strchr 會比較快啦，不過測資那麼小，應該沒差。

二、分數計算

輸入是一行分數的運算式，其中分數最多 5 個，運算子只有 + 和 – ，請輸出運算結果。

分數格式為 X/Y (X,Y為小於100的正整數)，內無空格，分數和運算子間均有一空格隔開。

輸出需為最簡分數，有負號請加在分子。

Sample Input:
1/2 + 1/3 - 1/6

Sample Output:
2/3

這題如果答案出現整數的話不知道該如何輸出才好，雖然題目好像說答案是「分數」啦。另外就是，分母可能出現非常大的數字，可是我只有用 int 宣告變數，裝不下那麼大的數字，若真有此種測資，則就會輸出錯誤了。

三、排列

給你N(1<=N<=9)個相異的 4-byte 整數，請按大小順序輸出所有排列可能。

輸入的第一行為整數 N ，第二行則有N個相異整數。

按大小順序，一行一個，輸出所有排列可能。

Sample Input:
4
30 10 20 40

Sample Output:
10 20 30 40
10 20 40 30
10 30 20 40
10 30 40 20
10 40 20 30
10 40 30 20
20 10 30 40
20 10 40 30
20 30 10 40
20 30 40 10
20 40 10 30
20 40 30 10
30 10 20 40
30 10 40 20
30 20 10 40
30 20 40 10
30 40 10 20
30 40 20 10
40 10 20 30
40 10 30 20
40 20 10 30
40 20 30 10
40 30 10 20
40 30 20 10

重點在於， 4-byte 整數用 int 還是裝不下，至少要用 unsigned int 才行，可是我還是用了 int 啊啊啊！當時好像以為它是 4-bit 整數！？

因為測資很小，所以用了偷懶的 next_permutation ，沒五分鐘就寫完這題了。

四、找群

有編號1~N的N個人(1<=N<=22)，若其中一群人彼此都是朋友，則這群人就稱為一個群。

輸入的第一行為N，接下來每一行有兩個數字 a, b ，表示 a 和 b 是朋友。

輸出最大的群之人數。

Sample Input:
4
1 2
2 3
3 1
1 4

Sample Output:
3

整體而言，實在不知道考得好還是不好。唉唉唉。