其实我可以轻易写出求幂的函数
double power(double b, int y)
{
double s = 1.0;
for (int i = 0; i < y; i++)
{
s *= b;
}
return s;
}
但是这样的时间复杂度是O(y)，有没有什么更快的方法呢？
如果要求 $2^8$ ，我们可以这样做
先求出 $x=2^2$ ，这样 $y=x^2=2^4$，然后就可以求出 $z=y^2=2^8$。用这种新方法只需要3次乘法就可以做出结果。
但如果幂是奇数怎么办？所以我们就要分情况讨论：
于是我们可以写出一个简单的递归函数
double power(double b, int y)
{
if (y <= 0) {
return 1;
}
if (y % 2 == 0) {
double t = power(b, y/2);
return t * t;
} else {
return b * power(b, y - 1);
}
}
非常简单的