50. Pow(x, n)

1.問題

• 實作pow(x, n)

2.想法

• 提問

  • n, x的範圍

• function header, parameter

• test input

• 說明想法

  • 次方的base case為n = 0, 結果為1

  • n > 0

    • n為奇數時則結果為x * pow(x, n - 1) * pow(x, n - 1)

      n為偶數時則結果為 pow(x, n - 1) * pow(x, n - 1)

  • n < 0

    • n為奇數時則結果為1 / x * pow(x, n - 1) * pow(x, n - 1)

• 測試計算複雜度

3.程式碼

class Solution {
public:
    double myPow(double x, int n) {
        if (n == 0) {
            return 1;
        }

        double half = myPow(x, n / 2);
        
        
        //n is an even and postitive number
        if (n % 2 == 0) {
            return half * half;    
        } 
        
        //n is a positive number
        if (n > 0) {
            return half * half * x;
        }
        //n is a negative number
        return half * half / x;
        
    }
};