作者jerry771210 (嘿嘿嘿)
看板NTUE-CS102
標題程式大賽題目(去年)
時間Thu Dec 10 14:45:39 2009
1.(難度1)
設計一個程式,輸入一個整數N,N>=0,輸出為N!之值
2.(難度1)
寫出一個程式,輸入為正整數,輸出為小於等於此整數的
所有perfect number
3.(難度1)
設計一個程式讓使用者輸入一個數值,然後輸出這個數值相對應的
2進位表示法與16進位表示法的數值,須能接受9位數的數值
(不可使用 printf內建的%x)
4.(難度1)
小名想利用矩形磁磚拼成一個正方形,但又想利用最少磁磚
磁磚不可分割,輸入為矩形磁磚的邊長為整數.分別為a與b:輸出最少磁磚數量
5.(難度2)
給訂一個n*n的矩陣,矩陣中所有元素為實數,找出一個子矩陣
使得子矩陣中所有數的和,在所有可能的子矩陣中為最大
(限定O(n^4)或更小)
6.(難度2)
老鼠走迷宮,(1牆壁:0路)把找到的路用"@"表示出來
7.(難度3)
設計一的程式以亂數的方式在XY平面上產生60個彼此相異的點
這些座標都是整數,且介於[-20,-20]~[20,20]之間
然後找出能包住這60個點的凸多邊形,盡可能在螢幕上呈現結果
8(難度3)
給訂一個實數的連續數列X1,X2....Xn,設計一個O(n)的程式
找出一個連續子數列Xi,Xi+1...Xj,使其乘積在所有可能的子數列中為最小
空數列乘機設定為1
9.(難度3)
廣播法,影片分成n個區段,每段撥放時間為b,有m個伺服器
伺服器均有此檔案的所有區段,但是每個伺服器完成傳送一個區段的時間可能不同
找出一種下載方式,讓使用者等待時間最短
EX:
input n b m:9 0.5 4
input 第一個伺服器S1傳輸區段所需的時間:1
input 第二個伺服器S2傳輸區段所需的時間:2
input 第三個伺服器S3傳輸區段所需的時間:3
input 第四個伺服器S4傳輸區段所需的時間:4
output
S1:1,2,4,6,9
S2:3,7
S3:5
S4:8
(上面冒號後的數字代表使用者從不同伺服器下載區段的編號)
10.(難度4)
假設XY平面上有水平或垂直的線段共N條
設計一個程式找出此N條線的交點
時間複雜度必須是 NlogN+I,N是線段個數,I是焦點個數
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.5.53
1F：推 game0416:有機會可以向您拿原始題目卷嗎QQ? 12/10 17:32
2F：→ game0416:感覺題目都少了點什麼東西(抓頭 12/10 17:32
3F：→ jerry771210:妳是哪一題不懂 12/10 17:33
4F：→ CaptainWill:火藥味? 12/10 17:35
5F：→ jerry771210:樓上不要亂引戰XDD 12/10 17:38
6F：推 yantchen:樓樓上有梗XD 12/10 17:41
7F：推 game0416:第八題是給定 n 跟j嗎QQ? 12/10 17:44
8F：→ game0416:主要是想看題目上可能列及的input 跟output格式 12/10 17:45
9F：→ game0416:跟大部分題目input的範圍這樣QQ" 12/10 17:46
10F：推 linjrming:我想問一下 當時最後一題是要實作程式 12/10 22:40
11F：→ linjrming:還是只要說明流程並且計算時間複雜度就好? 12/10 22:41
12F：→ jerry771210:第八題不就是你給他一串數列 然後他給你一串答案 12/11 00:24
13F：→ jerry771210:什麼i跟j = = 12/11 00:24
14F：→ jerry771210:然後志明大大 題目有寫:程式是要找交點(限定其複雜度) 12/11 00:25
15F：→ game0416:不限定要取多大的子數列的話，不是就只要取1(抓頭 12/11 00:28
16F：→ jerry771210:EX:input:1,2,3,4 output:1 12/11 00:33
17F：推 linjrming:囧 煩耶 演算法很難背 雖然題目給了提示太多了 12/11 01:08
18F：推 chchwy:也許有小數呀 input:1 0.5 0.3 0.22 12/11 10:23
19F：→ jerry771210:我只是照去年的題目敘述貼上而已 12/11 17:06
20F：推 game0416:我搞懂第八題的影響範圍有多少了...Orz 12/11 21:18
21F：→ game0416:還有負數要討論...這樣題目寫起來麻煩程度加很多耶QQ 12/11 21:19
22F：推 j2612280:有限定要使用哪種語言嗎? 12/11 23:46
23F：推 Markseinn:去年是C++跟JAVA的樣子,今年要等規則出來 12/12 00:14
24F：推 yantchen:一.競賽使用的程式語言為 Visual C++ 2005、Dev C++ 或Ja 12/12 02:10
25F：→ yantchen:va三種。 12/12 02:10
26F：推 game0416:是"可以被Visual C++ 2005、Dev C++"編譯，還是? 12/12 23:16
27F：→ game0416:將軟體名稱視為程式語言(?)很怪... 12/12 23:17
28F：推 yantchen:規則上面是這樣寫 我想他想表達的是 vc.net/g++/jdk 這三 12/13 02:47
29F：→ yantchen:個compiler都可以用來解題吧 12/13 02:50
30F：→ jerry771210:gcc也可以吧 12/14 00:03
31F：推 yantchen:gcc是g++的子集 12/14 01:07