如何快速求x得n次方呢?
首先C++里面有个pow如何实现呢?自己查查,里面使用double,肯定更麻烦,还有jianzhi
我们会顺手写下
int res=1;
for(int i=1;i<=n;i++)
{
res*=x;
}
学习一下快速幂,logn内计算出来,使用N的二进制,只需要logN就可以计算。
正要的就是计算每个为1对应的基数。列入: 11是多少?是二进制的话,就是1*2^1+1
那么x^(11)呢,两个1对应的基数是多少呢?低位1对应的是X,高位1对应的是X^2,因此,就是位于第一位基数为x,第二位基数为X^2,第三位是X^4,X^8 ,从中我们看出前一位的基数的平方是后一位的基数。
因此对于 11011 就是对于0位,就是1,对于1为……
#include<iostream> using namespace std; int pow1(int x,int n) { int res=1; for(int i=1;i<=n;i++) { res*=x; } return res; } int pow2(int x,int n) { int base=x; int res=1; while(n) { if(n&1) res*=base; base=base*base;//每一位的基数的增长。 n=n>>1; } return res; } //顺便写一个 int main() { int x, n; cin>>x>>n; while(x) { cout<<pow1(x,n)<<endl; cout<<pow2(x,n)<<endl; cout<<pow(x,n)<<endl; cin>>x>>n; } }
原文:http://www.cnblogs.com/hansongjiang/p/3775183.html