Search Results

數學中的遞迴 在高一數學課時，學習到使用遞迴解決數學上的問題，以下幾個是簡單的範例 小朋友上樓梯：有一位小朋友要走樓梯上樓，他一次可以往上走一階或一次走兩階，問你若要走 $n$ 階，共有幾種走法? 在此我們可以藉由上一階、上兩階的特性，將問題轉換成，若我要走到第 $i$ 階，則他必是從 $i - 1$ 和 $i - 2$ 階走過來的，下一步，就可以列成遞迴關係式 \[F(x)= \begin {cases} F(x-1)+F(x-2) & \text{if }x>1 \\ 1 & \text{if } x ...

輾轉相除法 輾轉相除法在求兩數的最大公因數(GCD)，是一種非常有效率的方法，我們不需要分別找出每個質因數，就可以找到其最大公因數，以下以求330, 210兩數的最大公因數為例 步驟 圖片 解釋 1 將330,210兩數併排寫下，並用3條直線做分隔 2 用 330 除以 210，得到商為 1，餘數為 120。(重點是那個餘數) 3 用前一次的除數(210)除以前一次的餘數(120)，得到商為1，餘數為 90。 4 用前一次的除數(120)除以前一次的餘數(90)，得到商為 1，餘數...

枚舉就是將所有答案的可能都跑過一次 若有時候答案的可能樹太多，會導致超時，在這個單元中，就要學習如何以合理的時間複雜度找到答案 枚舉簡單題目 給定一個數字$n(1\leq n\leq 10^3)$問可以湊成幾對$a, b$買足$a\times b = n$? 很直觀的做法，可以直接用$O(n^2)$的時間複雜度來完成 #include<iostream> using namespace std; int main() { int n; cin >> n; int ans = 0; ...

位元枚舉介紹 位元枚舉是一種通過遍歷所有的二進制數字來列舉所有可能的狀態的方法。通過對二進制數字中的每一位進行遍歷，可生成所有可能的狀態。 位元枚舉的優勢和定義： 用二進位的方式來簡單維護枚舉的技巧，程式碼量小 通常使用在枚舉部分只有要或不要(1/0)兩種可能，符合二進位原理 例如：10011代表在第1、2、5項要選擇3、4則不選擇 如何使用位元枚舉 進行位元枚舉的基本概念是通過遍歷所有的二進制數字來產生所有可能的狀態。可以通過以下步驟來實作位元枚舉： 定義好總共有幾項需要枚舉，在此設訂為$n$項 枚舉所有狀...