小殘的程式光廊

簡介插入排序法 (Insertion Sort) 是排序演算法的一種，他是一種簡單容易理解的排序演算法，其概念是利用另一個數列來存放已排序部分，逐一取出未排序數列中元素，從已排序數列由後往前找到適當的位置插入。運算流程如下： 從未排序數列取出一元素。 由後往前和已排序數列元素比較，直到遇到不大於自己的元素並插入此元素之後；若都沒有則插入在最前面。 重複以上動作直到未排序數列全部處理完成。 流程示意圖： 然而實作上通常不使用額外的數列來儲存已排序的部分，而使用原地 (In-place) 的方式來完成，數列的左半部表示已排序部分，右半部表示未排序部分，不另外使用數列。在與已排序的部分比較時，利用指派 (Assign) 的方式將元素往右位移，來達到插入的效果，因為位移的關係需要有另一個變數來暫存最右邊的數值。運算流程如下： 將未排序的部分最左邊元素儲存到暫存變數。 由後往前和已排序部分元素比較，若比自己大則將該元素往右邊位移。 重複2的動作直到遇到不大於自己的元素，將暫存變數寫入在該元素之後；若都沒有則寫入在最前面。 重複以上動作直到未排序部分全部處理完成。 流程示意圖： 分析 最佳 ...

簡介氣泡排序法 (Bubble Sort) 是最容易理解和實作的一種排序演算法，也翻譯作冒泡排序法。由於它很容易學習，所以也是許多演算法課程中第一個學習的排序演算法。 由於他的演算法過程會將最大的數值移動到陣列最後面，而較小的數值則逐漸的往陣列前端移動，就像有許多氣泡慢慢從底部浮出，因此稱為氣泡排序法。他的運作流程如下： 比較相鄰的兩個元素，若前面的元素較大就進行交換。 重複進行 1 的動作直到最後面，最後一個元素將會是最大值。 重複進行 1, 2 的動作，每次比較到上一輪的最後一個元素。 重複進行以上動作直到沒有元素需要比較。 流程示意圖： 實作上直接使用迴圈就可以很容易的完成。另外可以使用額外的旗標 (Flag) 來判斷這一輪是否有發生交換情形，若都沒有發生交換表示數列已經是排序好的，即可跳出迴圈，因此最佳時間複雜度是有可能達到 O(n)。 分析 最佳時間複雜度：O(n) 平均時間複雜度：O(n^2) 最差時間複雜度：O(n^2) 空間複雜度：O(1) Stable sort：是 虛擬碼一般版本1234567891011function sort(list) // 重複 N ...

拍攝時間：2012 年 10 月 10 日 今天是國慶日，一早來到真理大學附近吃傳說中的阿給當早餐，據說這家是最有名的阿給，不過忘記拍照了。 這家的阿給吃起來的確有些不同，一般的店是使用關東煮醬當醬料，這家用特製的醬料比較好吃一點，魚丸吃起來也比較好吃。 似乎每天限量很快就賣完了，所以早上來吃這當早餐。 小白宮吃完早餐後先來到附近的小白宮 地址：新北市淡水區真理街 15 號 電話：0226282865 網站：http://www.tshs.ntpc.gov.tw/ 結果來的太早還沒開門，不過等了一下就開放了，根據照片的時間顯示，應該是 9 點半左右開放 進去之後先來到了畫面上這棟建築物，廁所 廁所出來旁邊有個木棚 接著我發現我忘記照主建築物，只照了模型將就一下 主建築物內部結構 那時間有展覽淡水國中美術班的一些作品，數張椅子拼成的鯉魚 外面的花圃 外面的觀景平台，可以看到淡水河 淡水稅關所屬地，小白宮之前是清代的淡水關稅事務官邸 院子裡有顆雞蛋花樹 雞蛋花只是俗稱，真正的名字叫緬梔 看起來有像雞蛋嗎 另一面的花圃，種植著不同顏色的植物 真理大學 地址：251新北市淡水區真理街3 ...

拍攝時間：2012 年 10 月 9 日 今天來到赫赫有名的故宮博物院，久聞大名卻未曾來過，總算到此一遊。 地址：台北市士林區至善路二段 221 號 電話：(02)28812021 網址：https://www.npm.gov.tw/ 票價：全票 160 (2023 年 150 元) 從捷運士林站下車轉搭公車就可以到，有很多種公車都會到故宮，下車之後就看到入口處的階梯 走上階梯會看到天下為公的牌樓，一大早遊客還不是很多 經過牌樓後就可以看到正館，還有一段距離 牌樓後面階梯兩旁各有一隻石獅子 在通往本館的兩旁放了很多這樣擺設，看了上面的圖示才知道原來是垃圾桶 正館前有個仿製鼎 現在還沒甚麼人，不過過了一陣子就有大批的陸客湧入，不愧為陸客必訪行程之一 除了正館之外，另外也有一些建築物，似乎是行政大樓和別館，不過今天沒有去 故宮裡面禁止拍照，所以就沒有拍到任何照片。今天裡面正在展覽赫赫宗周，從大陸借了一些周代出土的文物來展覽，一堆陸客大老遠的跑來看他們的東西不知有何感想？ 當時有導覽志工免費解說，一群人就跟著導覽員觀看，其中幾乎都是同一團的陸客，不知道是甚麼特別的單位，不只相當勇於發 ...

拍攝時間：2012 年 10 月 8 日 今天又來到了陽明山，不過走的點不一樣，這次是在陽明公園這邊下車，從陽明公園往大屯瀑布行走。 地址：112 台北市北投區湖山路二段 26 號 電話：0228832130 10 月這個季節來陽明山似乎看不到甚麼特別的花季，就看看綠色的樹木吧 剛進來不久就看到一隻松鼠 他在吃甚麼呢？其實是剛剛有放一塊餅乾在地上，他就跳下來拿去吃了 夏秋交際的日子，開的花就這麼多了 原來陽明山的名字是來自王陽明的陽明兩字，陽明山以前叫做草山 公園裡面有些小河和池塘 辛亥光復樓，裡面有賣些特產和紀念品 在辛亥光復樓旁邊的大樹，不過流動廁所和汽車在後面倒是挺搶鏡的 繼續往前走來到了一個木棚步道，看起來還不錯 來到了觀景台，可以看到另一邊的山，下方都被樹擋住了，視野似乎不是很好 觀景台旁的山坡也有一些小花 來到大屯瀑布，大部分的人都在這休息和運動 從旁邊可以走到上一張照片的上面的橋梁，往下照一張 離開瀑布區後來到了停車場附近的花鐘，這邊沒有比較好的視角可以從上往下照，倒是沒注意時間有沒有準 在停車場這邊有開一些小吃店，午餐就在這邊解決，價格並沒有因為是觀光景點而變貴 ...

簡介排序 (Sorting) 演算法是常用到的一種演算法，顧名思義他是用來將資料依據特定的規則做排序後輸出；既然稱為排序就會有一個比較順序的依據，例如數字就比較數值大小、字串則依 ASCII 字母順序或者物件會有自定義的規則。一般沒有特別指定的話，輸出是以遞增排序為準。 穩定排序排序演算法分為穩定 (Stable) 和不穩定 (Unstable) 兩種，是指當資料中有相等數值的兩元素，經過排序之後是否能夠保持原有的相對位置，例如： 1(猴子, 智商60) (丁丁, 智商20) (拉拉, 智商20) (路人甲, 智商90) 將這些資料依據智商來排序，會發現智商 20 的有兩位，因此我們可能得到以下兩種情況 12(丁丁, 智商20) (拉拉, 智商20) (猴子, 智商60) (路人甲, 智商90)(拉拉, 智商20) (丁丁, 智商20) (猴子, 智商60) (路人甲, 智商90) 第一種情況丁丁和拉拉與原始的相對位置一致 (丁丁在前)，能夠總是維持相對位置的排序法我們稱之為穩定排序，反之則稱為不穩定排序，不能確保相對位置與原來一樣 (但是也有可能一樣)。 如果是純數字的排序基本上是 ...

資訊 路徑：Tournament \ 1-16 \ 2 - Inv 2001 Semi A+B \ Tothello 分數：500 題目程式介面12345Class Name: TothelloMethod Name: bestMoveParameters: String[], String[], StringReturns: intMethod signature (be sure your method is public): int bestMove(String[] redPieces, String[] blackPieces, String whoseTurn); 說明Tothello 是一個 Othello 遊戲的修改版，Othello 是一種兩人玩的遊戲，一方使用紅色的棋子，一方使用黑色的棋子，輪流在一個 8x8 大小的棋盤上下棋。當一方下棋之後，如果有將對方的棋子兩端包夾起來，對方的棋子就會變成自己的棋子；而若有棋子變成自己的棋子後，又產生其他的包夾，則又可以變成自己的棋子，直到沒有任何包夾。另外自己的回合的時候，也可以選擇 Pass 不下棋。 現在請實作一個程 ...

簡介連結串列 (Linked List 或稱鏈結串列) 是串列 (List) 的一種，是一種常見的資料結構，利用這個資料結構也能進一步實作出其他的資料結構，例如堆疊 (Stack) 和佇列 (Queue) 等。 它的特性是能夠不使用連續的記憶體空間的情況下，能夠保有並使用一份連續的資料；相對來看，陣列則需要使用連續的記憶體空間。 他的的實作方式是每個節點除了記錄資料之外，還使用額外的指標指向下一個節點，將節點以此方式串連起來形成一個連結串列。 由以上的說明可以知道，使用連結串列的優點如下： 不需使用連續記憶體空間，不需事先指定串列大小。 能夠容易的修改指標，插入或移除節點。 但也有缺點如下： 使用額外的記憶體空間紀錄節點指標。 無法快速索引到某個節點，必須迭代搜索。 此資料結構可以實作的操作變化相當多，這裡實作以下幾種操作： getFirst：取得第一個節點。 getLast：取得最後一個節點。 addFirst：加入節點在最前面。 addLast：加入節點到最後。 addBefore：加入節點在某節點之前。 addAfter：加入節點在某節點之後。 removeFirst： ...

簡介佇列 (Queue) 中文也翻作隊列，顧名思義是一種像排隊一樣的概念，以生活中的情況為例如下圖 人們一個接一個的從隊伍後面加入排隊，而窗口的服務人員則從最前面的民眾一個接一個處理事務；當然現實生活是會有中途離開的人，而在程式世界裡面一般情況是不會有。 在這個模式下我們可以知道他是一種先進先出 (First-In-First-Out, FIFO) 的排程，而在此資料結構中至少會實作兩個操作： enqueue：將資料放入佇列尾端。(註：C++ 中用 push、Java 用 offer、也有 add 等不同的用字) dequeue：取出佇列前端之資料。(註：C++ 中用 pop、Java 用 poll、也有 remove 等不同的用字) 有時候也會多實作一些額外的操作以方便使用，例如： peek：看佇列前端的資料而不取出。(註：也有 front 等不同的用字) size：取得佇列的數目。 在實作上一般使用連結串列 (LinkedList) 來實作，使用陣列同樣可以達成，但較為複雜： 連結串列用指標將資料串起來，將新的東西不斷接在最後面，而取出時則移除最前面的東西即可。由於加入和移 ...

簡介堆疊 (Stack) 是資料結構的一種，是一種很基本常見的資料結構，首先利用現實生活中的例子來說明，如下圖 假設你有一些書把他們疊起來，一層一層的往上疊，所以每次新的書本會放在最上面，而當想要拿取書本的時候，也是從最上面的開始拿。當然現實生活會有可能從中間抽出書本，不過在程式中是不可以的，在程式世界下圖會更貼切。 所以他是一種後進先出 (Last-In-First-Out, LIFO) 的排程，而在此資料結構中至少會實作兩個操作： push：將資料放入堆疊頂端 pop：取出堆疊頂端之資料 有時候也會多實作一些額外的操作以方便使用，例如： peek：看堆疊頂端的資料而不取出。。(註：也有 top 等不同的用字) size：取得堆疊的數目。 在實作上一般可以使用陣列或連結串列 (LinkedList) 兩種方式來實作： 陣列堆疊建立時即建立一個陣列，並使用一個索引來記錄目前所指到的位址，新增或移除資料時，同步修改索引位址；如果有實作堆疊數目的功能時，這數字正好可做為此索引之用。優點是不用處理指標鏈結建立與移除，缺點是容量超過陣列大小時需要額外處理。 連結串列用指標將資料串起來， ...