[算法作业][LeetCode] 50. Pow(x, n) -- 分治法 LeetCode解题

[算法作业][LeetCode] 50. Pow(x, n) – 分治法 【[算法作业][LeetCode] 50. Pow(x, n) -- 分治法】Implement pow(x, n).
对于 xn ，可以通过分治的方法，设 n=2k ：

xn=xn/2?xn/2?xn%2
xn/2=xn/4?xn/4?xn/2%2
.
.
.
xn/2k?1=x1?x1?xn/2k?1%2

function pow(x, n):
input x, n
outputxn
if (n == 0) return 1;
return pow(x, n/2) * pow(x, n/2) * pow(x%2)

function pow(x, n):
input x, n
outputxn
res = 1; base = x;
while (n):
if (n % 2) res *= base;
base *= base;
n /= 2;
return res;

递归

class Solution { public: double myPow(double x, int n) { if (n == 0) return 1; double tmp = myPow(x, n/2); double res = tmp * tmp; if (n > 0) { if (n%2) return res * x; else return res; } else { if (n%2) return res / x; else return res; } } };

非递归

double myPow(double x, int n) { double res = 1; double base = x; while (n) { if (n%2) { if (n < 0) res /= base; else res *= base; } base *= base; n /= 2; } return res; }