98 學年度第1 次考試(99.01.06) 2 題目一： 遊樂園的摩天輪 題目說明：反覆遊樂園是一家以摩天輪聞名的遊樂園。樂園中有各式各樣不同大小的摩天 輪， 可以讓遊客挑選。每個摩天輪的車廂都是以順時針的方式來編號。反覆樂園與其他樂園最 大 的不同是每個乘客可以搭乘的時間都不一樣。樂園老闆每天給出兩組不同的數字：右數與 左 數，當摩天輪開始運轉時，會先讓摩天輪被遊客搭滿，並且讓1 號車廂在出口位置(下摩 天輪 的位置，也就是摩天輪與地面最接近的地方)；開始旋轉時，會先逆時針轉右數個有乘客 的車 廂，並且請轉到出口位置的乘客下車，接下來再順時針轉左數個有乘客的車廂，並且請轉 到 出口位置的乘客下車，接著再逆時針轉右數個有乘客的車廂，依這個規則左右來回轉動， 直 到摩天輪中都沒有乘客，才會讓下一批的乘客搭乘。小明的女朋友聽說有這個反覆遊樂園 以 後，非常的想要去玩，所以小明決定明天帶著女朋友去反覆遊樂園，但是小明是個窮學生 ， 而樂園中每次搭乘摩天輪的價格都非常昂貴，所以小明希望自己選擇的車廂可以搭乘的最 久，可是他不知道該怎麼選擇，所以請嘉義大學資工系的同學們幫幫忙，讓他和女朋友的 約 會可以順利進行。請寫一個程式，自輸入檔中讀入左數、右數以及摩天輪的車廂數量，計 算 小明應該選擇幾號車廂才會是最後一個下摩天輪的乘客，並輸出車廂號碼。例如：左數是 2， 右數是1，車廂總數量是4，如下圖所示。因首先逆時針轉1 個有乘客的車廂，也就是2 號 必 須下摩天輪；接著順時針轉2 個有乘客的車廂，也就是4 號必須下摩天輪；接著逆時針轉 1 個有乘客的車廂，也就是1 號必須下摩天輪；此時只剩下3 號車廂有乘客，因此輸出3， 即 小明選擇3 號車廂可以搭乘最久。 輸入檔說明：輸入檔中第一行為一個正整數N，代表共有幾組測試資料。之後接下來有N 行， 每行中有3 個正整數 L、R 和C，分別代表左數、右數(1￡ L,R ￡100) 及車廂總數量 (2 ￡ C ￡100)，每個數字中間有一個空格。 輸出說明：每組測試資料輸出結果於一行。 Sample Run: Input file: 3 2 1 4 5 3 6 4 6 8 Output: 3 3 1 3 4 1 2 3 4 1 1 3 3 遊戲開始 2 下車 4 下車 1 下車 轉2 只剩3 轉 1 轉1 98 學年度第1 次考試(99.01.06) 3 題目二：辦公室中員工人數的極大值 題目說明：某單位總共有n 位員工，依照員工到達與離去的打卡時間，可得知第i 位員工 是 在xi 時到達，並在yi 時離開。因此第i 位員工待在辦公室中的時間是[xi, yi)，亦即 xi ￡ t < yi 中所有可能的t。請讀取xi 和yi，1 ￡ i ￡ n，找出同一時刻內，最多會有多少位員工 在辦公 室中。 輸入檔說明：每個案例的第一行應包含一個正整數N，表示該案例中，該單位總共有幾位 員 工。每個案例的第二行起接著的N 行，每行均包含兩個不小於1 的正整數(該行第一個整 數應 該小於該行第二個整數)，代表每位員工的到達與離去時間。案例之間緊連，無空行。若 在案 例的第一行輸入0，則表示結束輸入，程式停止執行。 輸出說明：當輸入完每個案例後，應輸出同一時刻內辦公室中員工人數的極大值。 Sample Run: Input file: 3 6 10 5 7 7 15 6 20 50 15 23 3 12 8 44 40 48 30 32 0 Output: Max = 2 Max = 3 98 學年度第1 次考試(99.01.06) 4 題目三：兔子繁殖問題（rabbit population） 題目說明：假設： 第零個月，只有一對兔子。(多出0 對兔子) 第一個月，這對兔子生出一對兔子。(多出1 對兔子) 第二個月，兩對兔子都各生出一對兔子，且第一對兔子死亡。(多出1 對兔子) 第三個月，三對兔子都各生出一對兔子，且第二對兔子死亡。(多出2 對兔子) 規則是每對兔子在它生命中會產下兩對兔子。問第n 個月時多出的兔子數量。 令第n 個月時多出的兔子數量為F(n)，即F(0)=0，F(1)=1，F(2)=1，F(3)=2，… 以此類 推。 請撰寫一個程式，可以從資料檔中讀入月份數n，求出Ｆ(n)。 輸入檔說明： 輸入檔第一行為一個正整數N 代表測試資料筆數，第二行起接下來有N 行 ， 每行為一個正整數或0 代表月份數n。 輸出說明： 輸出為Ｆ(n)，每組測試資料輸出結果於一行。 Sample Run: Input file: 2 10 20 Output: 55 6765 98 學年度第1 次考試(99.01.06) 5 題目四：變形漢諾塔問題 題目說明：盤子依大小編號，最小為1 號，盤子分散在A、B、C 柱子上，假設各柱子上的 盤 子皆依大小順序放置。因已經依大小順序放置，且要將盤子由A 柱子搬至C 柱子上，所以 最 大編號的盤子在C 柱子上，就沒有意義了，因此假設最大編號的盤子在A 或B 柱子上。輸 入 資料只要知道在A 與B 柱子上的盤子，其餘盤子在C 柱子。須將A 與B 柱子上的盤子以某 一資料結構儲存，假設每個柱子上不超過10 個盤子。 舉例說明做法： 例 1： A: 4 B: 3 C: 2 1 例 2： A: 4 B: 5 3 C: 2 1 較有效率做法：(此段落可以不讀) 假設目前A 柱子上只有一個編號4 的盤子，B 柱子只有一個編號3 的盤子，只要將C 柱子 上 的1 及2 號盤子搬移至B 柱子，即可將編號4 的盤子搬移至C 柱子，再將B 柱子的盤子搬 移 至C 柱子即可完成。但是若B 柱子上有5 及3 號盤子，其最佳解為將3 號盤子搬移至A 柱 子， C 柱子上的1 及2 號盤子也搬移至A 柱子，即可順利搬移5 號盤子至C 柱子。但是要這麼 做 考慮的條件較多，有一簡單但較無效率的方法。 較方便寫程式的做法： 假設目前A 與B 柱子上最小編號的盤子是h 號盤子，且假設此盤子在A 柱子上(若是B 柱 子， 則將以下之B 改成A)，欲將此h 號盤子搬移至C 柱子，此時，1 至h-1 號的盤子在C 柱子 上， 先以遞迴方式將C 柱子上的盤子搬移至B 柱子，將此h 號盤子搬移至C 柱子後，再以遞迴 方 式將B 柱子上的盤子搬移至C 柱子。如此，依次將A 與B 柱子上最小編號的盤子搬至C 柱 子。 請以此較方便寫程式的做法完成程式設計。 輸入檔說明： 第一行 執行次數，此例共4 次。 第二行 第一次執行之A 柱子上的盤子，可能空的，有多個盤子時，由大至小編號，並以 一 98 學年度第1 次考試(99.01.06) 6 個空格分開。此例而言，A 柱子上有3 號盤子。 第三行 第一次執行之B 柱子上的盤子，可能空的，不考慮A、B 兩柱子同時是空的。此例 而言，B 柱子上有4 號盤子，其餘在C 柱子上，亦即C 柱子上有2 號及1 號盤子。 第四行 第二次執行之A 柱子上的盤子。A 柱子上有3 號盤子。 第五行 第二次執行之B 柱子上的盤子。B 柱子上有2 號及1 號盤子，C 柱子上沒有盤子 。 第六行 第三次執行之A 柱子上的盤子。此行為空行，A 柱子上沒有盤子。 第七行 第三次執行之B 柱子上的盤子。B 柱子上有4 號及3 號盤子，C 柱子上有2 號及1 號盤子。 第八行 第四次執行之A 柱子上的盤子。A 柱子上有5 號盤子。 第九行 第四次執行之B 柱子上的盤子。B 柱子上有3 號盤子，C 柱子上有4 號、2 號及1 號盤子。 輸出說明：每次搬動盤子時，輸出將幾號盤子搬至哪個柱子，盤子編號與柱子代號以空格 分 開，以逗號分開每次的搬移。 Sample Run: Input file: 4 3 4 3 2 1 4 3 5 3 Output: 1 A,2 B,1 B,3 C,1 A,2 C,1 C,1 A,2 B,1 B,3 A,1 C,2 A,1 A,4 C,1 C,2 B,1 B,3 C,1 A,2 C,1 C, 1 C,1 A,2 C,1 C,1 A,2 B,1 B,3 C,1 A,2 C,1 C, 1 B,2 A,1 A,3 C,1 B,2 C,1 C,1 A,2 B,1 B,3 A,1 C,2 A,1 A,4 C,1 C,2 B,1 B,3 C,1 A,2 C,1 C, 1 B,2 A,1 A,3 C,1 B,2 C,1 C,1 A,2 B,1 B,3 A,1 C,2 A,1 A,4 B,1 B,2 C,1 C,3 B,1 A,2 B,1 B,5 C,1 A,2 C,1 C,3 A,1 B,2 A,1 A,4 C,1 C,2 B,1 B,3 C,1 A,2 C,1 C, 98 學年度第1 次考試(99.01.06) 7 題目 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.130.189.43