求X的N次方的2分实现
求X的N次方的二分实现
今天在看到网易里的算法导论的公开课，听到老外讲分治法时提到了下算一个数的N次方的可以通过二分思想来实
现，于是便想自己写个代码来实现它。虽然很简单，还是想写在博客中。一是可以加深自己的印象，以后遇到这类问
题时可以马上想到用二分来解决；二是可以方便以后的复习，再次用到的时候可以直接来这找模板。
#include<iostream>
using namespace std;
int Pow(int x, int n)
{
if (n == 1)
return x;
else if (n > 1)
{
int s;
int m = n / 2;
s = Pow (x, m);
if (n % 2 == 0)
return (s * s);
else
return (s * s * x);
}
}
int main()
{
int x, n;
while (cin >> x >> n)
{
cout << Pow(x, n) << endl;
}
return 0;
}