發表文章

Tree Search（樹狀搜尋)

-
一、什麼是 Tree Search（樹狀搜尋）？ 在人工智慧（AI）與演算法中，許多問題都可以表示成一棵樹(圖一)： 起點(A) / | \ B C D /|\ | / \ E F G H I J 每個節點(Node)代表一種狀態(State)。 例如： 迷宮中的位置 棋局的盤面 路徑規劃中的城市 遊戲中的決策 搜尋演算法的目的： 從起點找到目標節點（Goal Node） 二、Breadth First Search (BFS) 核心思想 先搜尋離起點最近的節點。 一層一層往外擴展。 Level 0: A Level 1: B C D Level 2: E F G H I J 搜尋順序： A B C D E F G H I J 圖一結果： A → B → C → D → E → F → G → H → I → J 使用資料結構 Queue（佇列） FIFO： First In First Out 先進先出 例如： Queue: A 取出A 加入B,C,D Queue: B,C,D BFS特性 優點 如果邊權重相同： BFS一定找到最短路徑。 缺點 需要大量記憶體。 假設每個節點有10個子節點： 深度5： 10^5 = 100000 需要保存很多節點。 時間複雜度 O(V + E) V = Vertex（節點數） E = Edge（邊數） 三、Depth First Search (DFS) 核心思想 一路往下走到底。 不能走才回頭。 A | B | E 然後： A | B | F 搜尋順序 圖一結果： A B E F G C H D I J 使用資料結構 Stack（堆疊） LIFO Last In First Out 後進先出 例如： push(B) push(C) push(D) pop() => D DFS特性 優點 記憶體需求小。 只需保存： 目前路徑 即可。 缺點 可能找到很差的解。 例如： A ├── Goal └── 巨大子樹 DFS可能先跑完整個巨大子樹。 時間複雜度 O(V+E)...
張貼留言
Read more »

Code Maintenance & Programming Rules

-
 This guide outlines essential best practices spanning code style, architectural design, debugging, testing, performance, and portability—all aimed at reducing the long-term cognitive load of code maintenance. 🎨 1. Style Code is written for humans to read, and only incidentally for computers to execute. Variable Naming : Use descriptive names for global variables, and short names for local variables. Precision and Consistency : Use active names for functions (e.g., calculateTotal ). Above all, keep your coding style consistent throughout the project. Structure & Expressions : Use a consistent indentation and brace ( {} ) style to show program structure visually. Use the natural form for expressions. Use parentheses to make the semantics unambiguous. Break up overly complex expressions to keep them clear. Side Effects & Macros : Beware of functions with side effects. Avoid function-like macros; if unavoidable, parenthesize the macro body and arguments carefully. Magic Numbe...
張貼留言
Read more »

APCS 程式識讀與實作題全方位解題技巧與備考攻略

-
在面對 APCS（大學程式設計先修檢測）以及各類程式線上評測系統（如 ZeroJudge 高中生解題系統、LeetCode、UVa、HackerRank 等）時，許多考生常卡在「寫不出程式」或「時間不夠」的窘境。本文將從 理解、分析、工具、實戰 四個維度，系統化解析如何有效提升 APCS 的程式識讀題與實作題分數。 一、 策略一：看懂題目，培養關鍵字敏銳度 「看不懂題目，就等於準備交白卷。」 > 這是許多初學者的痛點。APCS 的題目敘述往往結合了生活情境或數學模型，字數繁多。要克服這個障礙，秘訣在於 「多讀題、少動手」 的階段性訓練。 1. 如何訓練「看懂題目」的能力？ 刻意練習「只讀不解」 ：挑選 20 到 30 題歷屆試題或 ZeroJudge 基礎題， 限制自己只看題目與範例輸入輸出，先不寫程式 。嘗試在 3 分鐘內用自己的話解釋：「這題要我輸入什麼？經過什麼處理？最後輸出什麼？」 熟悉標準出題結構 ：APCS 實作題通常包含四大區塊： 問題描述 （情境與規則） 輸入說明 （資料範圍、型態、資料筆數） 輸出說明 （格式要求，如空格、換行） 範例輸入/輸出 （驗證理解的最強工具） 2. 題型大解密 程式識讀題（選擇題） ： 主要評量程式邏輯追蹤。核心考點包括 遞迴函式（Recursion） 、迴圈控制、條件判斷、二維陣列、以及基礎指標運算。考生必須具備「肉眼模擬 CPU」的能力。 實作題（程式撰寫） ： 每場考試固定 4 題，難度由易入難（第一題通常為基本邏輯與陣列操作；第四題多為複雜圖論、動態規劃或高階演算法）。 實作題採「部分得分制」 ，每題都有明確的測資範圍（如 N <= 100  得 40 分， N <= 100000  得 100 分），作答時應優先搶下所有題目的基本分數。 二、 策略二：分析題目，用紙筆解構演算法 當讀懂題目後，不要立刻敲鍵盤，盲目寫程式只會讓邏輯陷入泥沼。 1. 用紙筆追蹤規律 面對複雜的觀念題或卡住的實作題， 紙與筆是你最好的武器 。 觀念題 ：在紙上畫出變數的變更表格（Trace Table）或是遞迴樹（Recursion Tree），一步步記錄每行程式碼執行後的結果，通常就能看出數列或邏輯的「規律」。 實作題 ：利用題目提供的「範例輸入」，手動模擬一次運算流程，確認自己的想法與「範例輸出...
張貼留言
Read more »

APCS實作題2025年10月第1題彗星撞擊參考解法

-
圖片
題目連結 https://zerojudge.tw/ShowProblem?problemid=r488 。 解題思維： 此題用兩個二維陣列分別用來存放每個座標上的恐龍數量(dino[][])與地面高度(height[][])，並檢查撞擊範圍是否超出地圖範圍。 在範圍內 超出範圍 C++ 程式碼 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 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 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 #include <bits/stdc++.h> using namespace std ; int main () { int r,c,d,k; //c是行，r是列 cin >> r >> c >> d >> k; int dino[ 105 ][ 105 ] = { 0 },height[ 105 ][ 105 ] = { 0 }; // 讀取恐龍座標 while (k -- ){ int x,y; cin >> x >> y; dino[x][y] ++ ; // 此座標增加一隻恐龍 } // 設定地圖地面高度 for ( int i = 0 ;i < r;i ++ ){ for ( int j = 0 ;j < c;j ++ ){ height[i][j] = d; } } int m; // 撞擊次數 cin >> m; while (m -- ){ ...
張貼留言
Read more »