## 快速冪 --- ## 認識快速冪 ---- <span> 快速冪是什麼？<br><!-- .element: class="fragment" data-fragment-index="1" --> </span> <span> 其實你們早就會了<br><!-- .element: class="fragment" data-fragment-index="2" --> </span> <span> 只是不知道它叫快速冪<br><!-- .element: class="fragment" data-fragment-index="3" --> </span> ---- ### 舉個例子 請計算出$2^8$的值 ---- ### 方法一 一個一個乘 $2*2*2*2*2*2*2*2$ 效率好差== ---- ### 方法二 可以將$2^8$拆成$2^4*2^4$ 然後再不斷地拆下去直到$2^1$ 而$2^2$就會等於$2^1*2^1$ $2^4$就會等於$2^2*2^2$ $2^8$就會等於$2^4*2^4$ ---- ### 比較 方法一算了8次 因為2乘了8次 方法二只算了3次 $2^2 == 2^1*2^1$ $2^4 == 2^2*2^2$ $2^8 == 2^4*2^4$ --- ## 程式碼 ---- 道理我都懂 但是程式碼怎麼寫？ <img src="https://i.imgur.com/GPAh4Lm.png" width="400"> ---- 剛剛例子中的我不斷地拆一半 然後往下繼續拆 聽起來是不是很像遞迴？ <!-- .element: class="fragment" data-fragment-index="1" --> ---- <img src="https://i.imgur.com/XmJfdeB.png" width="400"> 右半邊之所以沒有東西 是因為在左半邊已經算過了 所以直接取用它的值就好 ---- 那如果指數(右上角那個小小的數字)是奇數呢？ 像是$2^7$怎麼辦 那只要把它變成$2^1*2^6$就好 這樣$2^6$的指數就是偶數 就可以繼續拆半 ---- ## 遞迴 ```cpp= int power(int a, int b){ if(b == 0) return 1; //指數為0，代表到底了，回傳1 if(b % 2 == 1) return a * power(a, b-1); //指數b為奇數，把它變成a * a^(b-1)，這樣b-1就是偶數 int temp = power(a, b/2); //指數b為偶數，對半拆 return temp * temp; } ``` ---- ## 迴圈 ```cpp= int res = 1, base = a; while(b != 0){ if(b % 2 == 1) res *= base; base *= base; b /= 2; } cout << res << endl; ```