底下分享筆者在解APCS實作題相關題目(如高中生解題系統、LeetCode、UVa Online Judge、HackerRank等)以及APCS觀念題所用到的技巧。
一、看懂題目
這一點是最重要的，因為看不懂APCS的題目時，也就等於準備交白卷啦。但請在仔細想想，若看不懂題目時，要怎麼辦呢？這部分要怎麼讓自己增加看懂題目的能力呢？
請嘗試看很多不同的題目並看懂，但先不要解題。為什麼要這樣子做呢？因為我們不知道APCS的題目類型會是怎麼樣，讓自己熟悉不同類型的題目時，就可以很快地知道題目的重點在那兒。底下分別以幾個例子說明APCS觀念題與實做題的一些題目類型。
請嘗試看很多不同的題目並看懂，但先不要解題。
請嘗試看很多不同的題目並看懂，但先不要解題。
觀念題部份（圖取自APCS官方提供的歷屆試題）：
這部份的每一次考試的試題會有四題，題目幾乎都是由易入難（第一題最簡單，第四題最困難），且每題都會說明評分方式，因此會有部份給分的情況，所以作答時應依自己最容易取得分數的部份開始做起。
二、分析題目
遇到不熟悉的觀念題題目時，可以先用紙筆將程式的每一行程式碼執行結果記錄下來，這樣子可以了解程式碼的運算結果是什麼，接著再來分析這些結果有什麼規律來找出規則。實作題部份都會說明題目以及範例說明，基本上也是得看懂題目才能想出解法。根據官方所提供的實作題：2017-10-28_實作題_試題下載、2017-03-04_實作題_試題下載、2016-10-29_實作題_試題下載、 2016-03-05_實作題_試題下載。可以了解到，考題都是偏向要想出演算法來解題，所以除了程式語言的語法觀念外，還需熟悉一些基礎演算法，例如排序、搜尋、堆疊、佇列等觀念。主流的程式語言通常會有這些常見演算法的函式可用，這部份在後面說明。
大數運算
電腦的數值表示方式有上限值，比如整數最大值可能為232 - 1等於4,294,967,295 。要計算12345678901234567890 + 98765432109876543210 時，通常就會發生overflow了。但在Java語言中，可以使用BigInteger來解題，本部落格的文章：「高中生程式解題系統：大數運算」就是使用BigInteger來解題。
函式庫
以函式庫的豐富性來說，C語言的內建函式庫是最少的。這樣來說，對選用C語言實作的考生們不就吃虧大了？這也別擔心太多，根據筆者目前所看到的實作題題庫來說，出題方向很少會需要使用內建函式庫來解題的。不過多了解程式語言的內建函式庫，可讓自己在解題有更多的選擇喔！因為APCS實作題是考解題方法，偏重演算法與資料結構，在這兩個主題上，C++可以學習Standard Template Library；Java語言本身就有常見的資料結構可以使用了，用Java實作演算法也會比C與C++還容易一些；而Python也有內建資料結構可用，以及豐富的函式庫喔，這也是為什麼熟悉Python語法與內建函式庫的人，大多會選用Python來實作。
以上的資訊提供給要考APCS的考生們，希望對考生們在解題時有些幫助。
實做題部份（圖取自APCS官方提供的歷屆試題）：
這部份的每一次考試的試題會有四題，題目幾乎都是由易入難（第一題最簡單，第四題最困難），且每題都會說明評分方式，因此會有部份給分的情況，所以作答時應依自己最容易取得分數的部份開始做起。
二、分析題目
遇到不熟悉的觀念題題目時，可以先用紙筆將程式的每一行程式碼執行結果記錄下來，這樣子可以了解程式碼的運算結果是什麼，接著再來分析這些結果有什麼規律來找出規則。實作題部份都會說明題目以及範例說明，基本上也是得看懂題目才能想出解法。根據官方所提供的實作題：2017-10-28_實作題_試題下載、2017-03-04_實作題_試題下載、2016-10-29_實作題_試題下載、 2016-03-05_實作題_試題下載。可以了解到，考題都是偏向要想出演算法來解題，所以除了程式語言的語法觀念外，還需熟悉一些基礎演算法，例如排序、搜尋、堆疊、佇列等觀念。主流的程式語言通常會有這些常見演算法的函式可用，這部份在後面說明。
三、善用工具
朋友們有看過本部落格的「APCS 解題：特殊編碼」這篇文章嗎？這篇文章用了字典的觀念，並以C++、Java、Python三種程式語言來實作。疑！沒有用C程式語言來實作耶！這是因為C語言內建函式工具沒有支援hash table的資料結構。
這部份會用幾個例子來說明善用APCS所指定的程式語言：C、C++、Java、Python的工具函式會有多便利，先以最常見的排序與搜尋演算法當例子。
排序
C語言有內建的qsort。C++除了可以使用qsort外，還可以使用STL的sort。Java有Arrays.sort與Collections.sort。Python則有list.sort與sorted可用。
搜尋
最常見的搜尋為線性搜尋與二分搜尋。線性搜尋的演算容易實作出來，所以直接說明二分搜尋的部份。C語言有內建的bsearch。C++除了可以使用bsearch外，還可以使用STL的binary_search。Java有Arrays.binarySearch與Collections.binarySearch。Python則有bisect模組可用。
String字串相關函式
電腦的數值表示方式有上限值，比如整數最大值可能為232 - 1等於4,294,967,295 。要計算12345678901234567890 + 98765432109876543210 時，通常就會發生overflow了。但在Java語言中，可以使用BigInteger來解題，本部落格的文章：「高中生程式解題系統：大數運算」就是使用BigInteger來解題。
函式庫
以函式庫的豐富性來說，C語言的內建函式庫是最少的。這樣來說，對選用C語言實作的考生們不就吃虧大了？這也別擔心太多，根據筆者目前所看到的實作題題庫來說，出題方向很少會需要使用內建函式庫來解題的。不過多了解程式語言的內建函式庫，可讓自己在解題有更多的選擇喔！因為APCS實作題是考解題方法，偏重演算法與資料結構，在這兩個主題上，C++可以學習Standard Template Library；Java語言本身就有常見的資料結構可以使用了，用Java實作演算法也會比C與C++還容易一些；而Python也有內建資料結構可用，以及豐富的函式庫喔，這也是為什麼熟悉Python語法與內建函式庫的人，大多會選用Python來實作。
以上的資訊提供給要考APCS的考生們，希望對考生們在解題時有些幫助。
沒有留言:
張貼留言