PowerPoint Presentation

Size: px

Start display at page:

Download "PowerPoint Presentation"

诲嘏贾
5 years ago
Views:

1 程式設計選手研習講師 : 林易民

2 104 學年度程式設計職種競賽規則評分標準 : 以學術科比例合計為個人總成績, 依參賽者總成績高低決定名次若總成績相同則以術科成績較高者為先, 若術科成績仍相同, 則依術科繳卷時間先者為先, 若繳卷時間仍相同則依序比較配分較高題得分者為領先

3 104 學年度程式設計職種競賽規則競賽方式 1. 實地上機撰寫程式 2. 每一試題提供 2 組測試資料及其正確解答以供學生測試用 3. 試題之輸出入資料均有其格式及範圍之要求, 選手應依指定之格式及範圍作答 4. 各題需依試題說明之指定路徑儲存執行檔, 執行時需直接讀取執行檔所在資料夾下的測試檔, 並將其結果檔輸出至同一資料夾, 未依規定者, 該題不予計分 5. 程式執行過程中應先隱藏顯示介面或訊息, 未依規定者, 該題不予給分 6. 輸出內容與答案不符者, 該題不予給分 7. 在限定時間內未執行結束者, 該題不予給分

4 規則分析分析重點存檔很重要, 不要存錯程式不能出現任何訊息只要你的程式能在規定時間內執行完畢而且執行正確, 程式寫得快比跑得快重要

5 程式基本架構

6 隱藏畫面 1. 設定表單屬性 Opacity=0% 2. 在 Form1_Load 副程式中最後一行加入 Me.Close() ( 關閉表單 )

7 如何計算程式執行時間 Dim Watch As New Stopwatch ( 定義計時器 ) Watch.Reset() ( 將計時器的時間歸零 ) Watch.Start() ( 啟動計時器 ) ( 被監控的程式 ) Watch.Stop() ( 停止計時器 ) MsgBox(" 執行 " &Watch.ElapsedMilliseconds & " 毫秒 ")

8 如何讀取不同輸入格式資料程式範例 Dim Sep As String() = {"{", "}", ","} Dim In() As String in=st.split(sep,stringsplitoptions.removeemptyentries)

9 解題的七個步驟 1. 依據題目要求建立視窗專案名稱 2. 設定表單程式透明度, 並於 Form1_Load 副程式中加入 Me.Close() 3. 設定必要的.NET 命名空間 4. 將測試資料檔放入 Debug 目錄中 5. 定義輸出入檔案變數及常用迴圈變數 6. 定義輸入分割符號 7. 不要忘記插入分別兩個輸入檔的空白行

10 基本程式架構 ( 練習用 ) Private Sub Form1_Load(sender As System.Object, e As System.EventArgs) Handles MyBase.Load Dim MyWatch As New Stopwatch MyWatch.Start() Dim Reader(1) As StreamReader, SR As StreamReader Dim SW As New StreamWriter("out.txt") Reader(0) = New StreamReader("in1.txt") Reader(1) = New StreamReader("in2.txt") Dim Sep() As String = {" "},U As Integer, Fn As Integer Dim I As Integer, J As Integer, K As Integer, L As Integer For Fn = 0 To 1 SR = Reader(Fn) ( 主要解題的程式 ) SW.WriteLine() Next MyWatch.Stop() SW.WriteLine(" 總共花費 {0} 奈秒 ", ChaneTickToNanoSecond(MyWatch)) Me.Close() End Sub Private Function ChaneTickToNanoSecond(MyStopWatch As Stopwatch) As Double Return (MyStopWatch.ElapsedTicks * / Stopwatch.Frequency) End Function

11 基本程式架構 ( 比賽用 ) Private Sub Form1_Load(sender As System.Object, e As System.EventArgs) _ MyBase.Load Dim Reader(1) As StreamReader, SR As StreamReader Dim SW As New StreamWriter("out.txt") Reader(0) = New StreamReader("in1.txt") Reader(1) = New StreamReader("in2.txt") Dim Sep() As String = {" "},U As Integer, Fn As Integer Dim I As Integer, J As Integer, K As Integer, L As Integer For Fn = 0 To 1 Next SR = Reader(Fn) Me.Close() ( 主要解題的程式 ) SW.WriteLine() Handles

12 良好解題習慣

13 解題步驟解題步驟 1. 先看完全部題目仔細閱讀並理解 2. 用自己熟悉的概念及術語來重新定義題目 3. 選擇簡單題目先做 4. 定義題目需要使用的演算法及資料結構 5. 想看看有沒有其他演算法如果有, 選擇最簡單的方法, 如果解不出來, 就用暴力法 6. 確定好你所要使用演算法及資料結構, 才開始寫程式 7. 測試

14 正確的儲存資料規定請將資料同時存放於硬碟及隨身碟檔名請千萬不要存錯儲存格式如有疑惑, 請於比賽開始前詢問評審教授

15 好的程式習慣盡量使用.Net Framework 函數, 少寫程式維持相同的程式設計風格及命名變數的習慣重複出現三次以上的程式就定義為函數能用表格, 就不要用 IF 多用 AndAlso 及 OrElse 來取代 And 及 Or If i=-1 Or A(i)=-1 If i=-1 OrElse A(i)=-1 如果有需要使用常數, 請先定義它在程式的最開頭選擇合適的字體及大小寫來進行 Coding, 避免英文 O 與數字 0 1 與 l 與 I, 搞混, 迴圈索引變數用大寫 I J K 取代小寫 i,j

UBound(b) - 1 check=false For j = 0 To UBound(b) - 1 - i If b(j) > b(j + 1) Then switch(b(j), b(j + 1))

16 好的程式習慣盡量使用.Net Framework 函數, 少寫程式假設你要升冪排序陣列 B 方法一 : 自己寫 Dim i, j, count As Integer Dim check As Boolean For i = 0 To UBound(b) - 1 check=false For j = 0 To UBound(b) i If b(j) > b(j + 1) Then switch(b(j), b(j + 1)) count += 1 : check = True Next If chk = False Then Exit For Next Private Sub switch(byref a as integer, ByRef b as integer) Dim c As Integer c = a : a = b : b = c End Sub 方法二 : 用.Net Framework 函數 Array.Sort(B)

17 好的程式習慣能用表格, 就不要用 IF 少用 If month=1 then return Jan If month=2 then return February If month=12 then return December 改用 MonthName() as String ={ None, January, February,, December } Return(MonthName(month))

18 解題策略養成良好編碼習慣, 盡量減少 Trival Error 範例一寫法一 return (x*y)+func(t)/(1-s) 寫法二 temp = func(t) RetVal = (x*y) + temp/(1-s) return RetVal

19 解題策略養成良好編碼習慣, 盡量減少 Trival Error 範例一寫法一 return (IIf(((x*8-111) mod 7)>5), y, 8-x) 寫法二 Temp = ((x*8-111) mod 7) If (5<Temp) Then return y else return 8-x End if

20 請注意一下 Counter =? Module Module1 Const Max As Integer = Sub Main() Dim I As Integer, Counter As Integer = 0 For I = 1 To Max Dim Y As Double = 1.0 / I If I * Y = 1.0 Then Counter = Counter + 1 Next Console.WriteLine(Counter) Console.Read() End Sub End Module

21 盡量不要使用使用浮點數 Counter =? Module Module1 Const Max As Integer = Sub Main() Dim I As Integer, Counter As Integer = 0 For I = 1 To Max Dim Y As Double = 1.0 / I If I * Y = 1.0 Then Counter = Counter + 1 Next Console.WriteLine(Counter) Console.Read() End Sub End Module Counter =86884

22 常見程式問題 Off By One Error 假設有一個籬笆長 100 公尺, 每 10 公尺立一個柱子, 請問總共要立多少柱子?

23 如何測試你的程式測試資料 1. 使用比賽給的測試資料 2. 測試題目的臨界值, 避免 Off By One Error 3. 至少連續相同的兩筆測試資料 4. 測試已知正確答案的大數據 5. 分析題目可能有錯的部分 6. 亂數產生測試數據

24 至少連續相同的兩筆測試資料求 Sum = Dim K as Interger Dim I as Integer, Sum as Interger For K = 1 to 2 For I = 1 to 10 Sum = Sum+I Next I Next

25 何時用遞迴或迴圈方式如果解題概念比較簡單, 請使用迴圈 Factorial Fibonacci 如果解題概念比較複雜, 請使用遞迴 Tower of Hanoi, Searching (DFS, BFS)

26 問題在那裡? Sub Main() Dim T as Integer = LCM(50000,100000) End Sub Private Function LCM(ByVal N1 As Integer, ByVal N2 As UInteger) As UInteger Return (N1* N2) / GCD(N1, N2) End Function

27 小心 OverFlow Sub Main() Dim T as Integer = LCM(50000,100000) End Sub Private Function LCM(ByVal N1 As Integer, ByVal N2 As UInteger) As UInteger Return (N1 * / GCD(N1, N2)*N2) End Function

28 解題考慮 1. 你遇到那一型的 Bug, 有沒有線索 2. 要不要修改資料結構或演算法 3. 你要 Debug 還是寫其他題目 4. 要不要解之前放棄的題目 5. 你還有多少時間可以用來解題

29 比賽常用函數

30 解題常用類別常用類別 Array String Convert Math

31 進位轉換 Convert.ToString(Value As Integer,Base As Integer) Base : 傳回值的基底, 必須是或 16 Value: 要轉換的 32 位元帶正負號的整數傳回值 : Value 所對應的 Base 為底數的字串 Example Convert.ToString(100, 8)= 144 Convert.ToUInt32(Value As String,Base As Integer) Base : 傳回值的基底, 必須是或 16 Value: 要轉換的 32 位元帶正負號的整數傳回值 : Value 所對應的 Base 為底數的數字 Example Convert.ToUInt32("100101", 2) =37

32 解題常用類別 System Collection ArrayList SortList Queue Stack System Math Array String

33 佇列 (queue) Def: 具有 FIFO (first in-first out) 性質的有序串列其插入元素的動作稱為發生在 Rear ( 尾 ) 端, 刪除元素的動作發生在 Front ( 前 ) 端.

34 如何在 VB2010 中使用 Queue 佇列 (Queue) 常用的方法 ( 函數 ) 如下 Dequeue Enqueue Peek 從佇列前端取出一個項目, 同時將其移除從佇列尾端加入一個項目從佇列前端取出一個項目, 但不移除佇列 (Queue) 常用的屬性 ( 變數 ) 如下 Count 取得佇列中目前的項目數量

35 如何在 VB2010 中使用 Queue 匯入 System.Collections 命名空間 Imports System.Collections 引用 Queue 類別 Dim myqueue As Queue(Of Integer) = New Queue (Of Integer) 用 Enqueue 加入佇列 myqueue.enqueue(2012) 用 Dequque 輸出資料 item = myqueue.dequeue()

36 堆疊 (Stack) 將資料依序從堆疊下面儲存起來, 並視需要從堆疊的上面將資料取出的方式之資料結構, 稱為堆疊 Push POP top top top top E D A Stack top top E D A Stack

37 如何在 VB2010 中使用 Stack 堆疊 (Stack) 常用的方法 ( 函數 ) 如下 Pop Push Peek 從堆疊最頂端取出一個項目, 同時將其移除從堆疊最頂端加入一個項目從堆疊最頂端取出一個項目, 但不移除堆疊 (Stack) 常用的屬性 ( 變數 ) 如下 Count 取得堆疊中目前的項目數量

38 如何在 VB2010 中使用 Stack 匯入 System.Collections 命名空間 Imports System.Collections 引用 Stack 類別 Dim mystack As Stack(Of Integer) = New Stack (Of Integer) 用 Push 加入佇列 mystack.push(2012) 用 POP 輸出資料 item = mystack.pop()

39 104 學年模擬試題解析

40 Problem 1: 數學問題子題 1: 質因數分解解題重點使用 Eratosthenes Sieve, 建立質數表

41 Problem 1: 數學問題子題 2:N! 尾數的 0 個數解題重點 1. N!=2 n 3 m 5 p (n>p) 2. 10= N! 尾數的 0 個數 =p

42 Problem 2: 其他子題 1: 計程車費率計算解題重點浮點數運算誤差

43 Problem 2: 其他迴文解題重點 String.ToCharArray() Array.Reverse()

44 Problem 3: 資料結構樹子題 1: 是否為樹解題重點 Tree 的條件 1. BFS Tree 的點數 = Tree 中所有點數 2. Tree 中所有邊數 +1=Tree 中所有點數

45 Problem 3: 資料結構樹二元搜尋樹的路徑長度最長的值解題重點使用 SortedList 來代表連接關係

46 Problem 4: 其他子題 1: 加減問題解題重點鴿籠原理若有 n 個籠子和 n+1 隻鴿子, 所有的鴿子都被關在鴿籠裡, 那麼至少有一個籠子有至少 2 隻鴿子將 3 個數字 (C B A) 視為鴿子, 正數及負數分別視為籠子, 又 3 個正負數字和必須等於 0, 所以 C=A+B

47 Problem 4: 其他子題 2: 數字反轉後相加解題重點 String.ToCharArray() Array.Reverse() Integer.Parse() VAL

48 學年度試題類型

49 學年度試題類型 1. 質數 (Eratosthenes Sieve) 2. Cramer s Rule 3. 中序式轉後序式後序式 4. 老鼠走迷宮 5. 找零錢 ( 動態規劃 ) 6. 撲克牌 7. 所有排列 ( 暴力法 ) 8. 判斷是否為樹, 路徑長度內部節點樹葉 9. 字串處理 (ArrayList, String, SortedList)

50 Eratosthenes Sieve

Eratosthenes Sieve 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74

51 Eratosthenes Sieve

52 Eratosthenes Sieve

53 Eratosthenes Sieve

54 Eratosthenes Sieve

55 Eratosthenes Sieve

56 Eratosthenes Sieve

57 Eratosthenes Sieve

58 Cramer s Rule 1 1 若令 Δ a b c1 b1,δ x, Δ a b c b 2 2 則二元一次方程組以二階行列式表示的 x y 解為 (1) 當 Δ 0時恰有一組解 x, y (2) 當 Δ= Δ Δ 有無限多組解 y 2 2 a1x b1 y c1 a x b y c x (3) 當 Δ= 0,Δ 與 Δ 有任一個不為 0 無解 x y y a a c c

59 中序式轉後序式由左至右讀取中序式中元素 T 如果 T 是運算式結束符號, 則輸出所有 Stack 中元素至後序式 Postfix 尾端如果 T= (, 將 T 放入 Stack 如果 T 是運算元, 將 T 輸出到後序式 Postfix 尾端如果 T 是 ), 則將 Stack 中的運算子輸出至後序式 Postfix 尾端, 直到遇見 ( 如果 T 是運算子, 和堆疊頂端運算子 P 比較優先順序如果 T 的優先序 > P 的優先序, 則將 T 放入 Stack 否則將 Stack 中所有優先序大於或等於 T 的運算子輸出到後序式 Postfix 尾端, 或者是 Stack 中沒有任何其他元素, 再將 T 輸入到 Stack 中 ( 在堆疊中優先序最小

60 後序式運算由左至右讀取後序式中元素 T 如果 T 是運算元, 將 T 放入 Stack 如果 T 是運算子, 則由堆疊中取出兩個運算元進行對應的運算, 然後將結果存回堆疊當運算式讀取完畢, 堆疊中的值就是運算結果

61 老鼠走迷宮

62 老鼠走迷宮

63 撲克牌 ( 同花順 ) 黑桃紅桃 1 方塊 2 梅花 3 合計

64 撲克牌 ( 順子 ) 黑桃紅桃 1 1 方塊 2 1 梅花 3 合計

65 撲克牌 ( 葫蘆 ) 黑桃 0 紅桃方塊梅花 3 1 合計 4 3 2

66 樹 A B C D E F G

67 樹 ( 樹葉內部節點 )

68 參考資料及網站

69 參考網站演算法筆記 tml 非關語言 : 常見程式演算 /

70 Lucky 貓的 UVA(ACM) 園地 Ruby 兔的 ACM 園地 UVA Tool Kit

71 參考網站 NPSC 補完計劃 USACO Trainning IOI

72 參考網站 USACO Trainning ( 中文簡體 ) ning USACO Trainning ( 中文簡體 ) ACM ICPC

73 參考網站 Nordic Collegiate Programming Contest The Central European Olympiad in Informatics Internet Problem Solving Contest ( CROATIAN OPEN COMPETITION IN INFORMATICS

74 參考書籍

75 參考書籍書名 : 演算法之道 -- 讓你學不會演算法都難作者 : 鄒恒明出版社 : 碁峯出版社

76 參考書籍書名 : 培養與鍛鍊程式設計的邏輯腦 : 世界級程式設計大賽的知識心得與解題分享作者 : 秋葉拓哉岩田陽一北川宜稔出版社 : 博碩文化

77 參考書籍書名 : 演算法 -- 使用 C++ 虛擬碼作者 :Richard Neapolitan 出版社 : 碁峯出版社

78 參考書籍書名 : 算法導論出版社 : 機械工業出版社

79 參考書籍書名 : 計算機程序設計藝術出版社 : 國防工業出版社

80 參考書籍書名 : 名題精選百則 : 技巧篇作者 : 冼鏡光出版社 : 儒林出版社

81 參考書籍書名 : 程式之美作者 : 編程之美小組出版社 : 悅知文化

參考書籍書名 :Art of Programming Contest 作者 :Ahmed Shamsul Arefin 下載網址 :http://www.

82 參考書籍書名 :Art of Programming Contest 作者 :Ahmed Shamsul Arefin 下載網址 : nus.edu.sg/~stevenha /database/art_of_pro gramming_contest_se _for_uva.pdf

83 參考書籍書名 : 啊哈! 圖解演算法必學基礎作者 : 啊哈磊出版社 : 碁峯出版社

84 參考書籍書名 : 打下好基礎 - 程式設計與演算法競賽入門經典作者 : 劉汝佳出版社 : 碁峯出版社

85 參考書籍書名 : 提升程式設計的解題思考力 -- 國際演算法程式設計競賽訓練指南作者 : 劉汝佳 / 陳鋒出版社 : 碁峯出版社

86 參考書籍書名 : 程式設計的解題策略活用資料結構與演算法作者 : 吳永輝 / 王建德出版社 : 碁峯出版社

87 參考書籍書名 : 提升程式設計的資料結構力國際程式設計競賽之資料結構原理題型解題技巧與重點解析作者 : 吳永輝 / 王建德出版社 : 碁峯出版社

88 歡迎指教

<4D F736F F D DA5BFA6A1C476C1C92DBEC7ACECB8D5A8F728B57BB35D292E646F63>

<4D F736F F D DA5BFA6A1C476C1C92DBEC7ACECB8D5A8F728B57BB35D292E646F63> 全國高級中等學校 106 學年度商業類科學生技藝競賽程式設計職種學科試卷選手證號碼 ( 崗位編號 ): 姓名 : 注意事項 : 請將答案劃記於答案卡, 未依規定劃記者不予計分試題說明 :( 選擇題共 25 題每題 4 分, 答錯不倒扣, 共 100 分 ) ( )1. 執行以下 Visual Basic 程式片段, 其結果為何?(A) 15 (B) 12 (C) 7 (D) 3 Dim