葫芦娃关于快速幂流程的详细讲解

快速幂的流程大概是这样的,维护一个等式a^b=x^y*z。

比如说现在求3的10次方

第一步:3^10=3^10*1

第二步:3^10*1=9^5*1

第三步:9^5*1=9^4*9

第四步:9^4*9=81^2*9

第五步:81^2*9=6561^1*9

第六步:6561^1*9=1^1*59049

所以3^10=59049

上面总共进行了五次乘法运算,相比较朴素的十次来说,要好一些

经过上面的演算,抽象成自然语言大概是这样:

初始化,x=a,y=b,z=1,

每一次,首先如果y不大于0则退出,

然后判断y,若为奇数,那么z=z*x,,

最后,y=y/2。

退出之后答案就是z了。

附上我的实现代码:

int work(int a,int b){int x=a,y=b,z=1;while(y>0){if(y&1)z*=x;x*=x;y>>=1;}return z;}

要永不言弃坚持到底百折不挠宁死不屈,但我们好多人没想过,

葫芦娃关于快速幂流程的详细讲解

相关文章:

你感兴趣的文章:

标签云: