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

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

C++題目共有四題,每題 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

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

相關文章

About these ads

10 thoughts on “台大資工九十八學年度甄試入學,程式設計考題

  1. 您好啊
    你曾經在我的 blog (http://tw.myblog.yahoo.com/Inspot-EnglishWorld) 回應過
    但因為我實在沒時間回
    所以現在才來看看 = =||
    (我也剛台大二階完)

    看了你那篇學英文的
    覺得好厲害呢
    感覺你好有深度喔 啊哈哈哈
    而且針對樓上的那些東西…
    我完全沒頭緒

    不過 一座島真是一座好島 (這啥?)
    嗯嗯 很棒的 blog 啊 我會常來

    期待二階上囉!^^

  2. to vicky18921:
    可能我表達的不好?
    不過這篇文章本來設定的讀者就是會寫程式的人啦,所以用了很多術語 XD
    一起加油囉!

    to 林意晶:
    謝謝喔。
    其實寫那篇文章的時候,我是一邊拿著很多書一邊寫的呢!

  3. 我問你喔

    這些東西是你自己學會的嗎

    在我國小的時候,我跟我媽說我想學電腦

    記得我第一個學的是Excel

    不過上國中之後才知道巨匠一堂課600塊

    那時覺得太貴了,才沒繼續學

    上高中學了程式設計還蠻有興趣的

    你有什麼學習的訣竅嗎?

  4. to 喜德:
    Hello!
    基本上是自己學的喔。
    嗯,如果可以接受英文的話,在網路上可以找到很多資源(別擔心,程式設計教學不會有複雜的文法及單字)。
    不過中文資源也是很多啦,我會先告訴你我是怎麼學的,再告訴你一些雖然我沒有使用,但我覺得也很好的資源。

    最早學習 C++ 是在國三,當時是每天讀幾篇 Cprogramming.com 網站上的教學。
    後來又到台南市立圖書館借了一本《Linux C/C++ 入門進階》來看。
    後來我到 UVa Online Judge 找題目來解。
    後來我又買了一本《Algorithm Design》研讀。
    大概就像這樣。

    建議的可能入門法是,直接到台南市立圖書館借或直接買《C++ Primer Plus 4/e中文版》,還有《演算法導論》此外上面提到的《Linux C/C++ 入門進階》可當參考。
    可以使用免費的 Dev C++ 編輯器,參考Dev C++設定教學
    然後這裡有一大堆教學等著你學習呢:DJWS 的網路日誌

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 變更 )

Twitter picture

You are commenting using your Twitter account. Log Out / 變更 )

Facebook照片

You are commenting using your Facebook account. Log Out / 變更 )

Google+ photo

You are commenting using your Google+ account. Log Out / 變更 )

連結到 %s