快速幂思想及实现，如何入门必学算法？

本文共计1096个文字，预计阅读时间需要5分钟。

目录

一、什么是快速幂

二、快速幂思想及实现

总结

一、什么是快速幂

快速幂是一种高效的计算幂的方法，它利用了幂的乘法性质来减少计算次数。快速幂算法主要用于快速计算大数的幂，如\(2^{10^9}\)等。

二、快速幂思想及实现快速幂算法的基本思想是将幂指数分解为二进制形式，然后逐步计算幂的值。具体实现如下：

1.将指数转换为二进制形式。

2.从最低位开始，逐位判断指数的二进制位是否为1。

3.如果为1，则将当前幂的值乘以当前底数的幂。

4.底数自乘。

5.循环至所有二进制位判断完毕。

例如，计算\(2^{10}\)的值：

1.将10转换为二进制：\(10=1010\)。

2.从最低位开始，判断二进制位：

- 第1位为1，将当前幂的值乘以\(2^1\)，即\(2 \times 2=4\)。 - 第2位为0，不进行操作。 - 第3位为1，将当前幂的值乘以\(2^2\)，即\(4 \times 4=16\)。 - 第4位为0，不进行操作。

3.最终结果为16。

总结

快速幂算法是一种高效的幂计算方法，可以减少计算次数，提高计算效率。在实际应用中，快速幂算法常用于大数幂的计算，如加密算法、计算机图形学等领域。

目录

• 一、什么是快速幂
• 二、快速幂思想及实现
• 总结

一、什么是快速幂

快速幂算法是用来快速计算指数表达式的值的，例如 210000000,普通的计算方法 2*2*2*2…乘10000000次，如果一个数字的计算都要计算那么多次的话，那么这个程序一定是失败的。

学完快速幂之后就可以用几十次计算求出答案了

二、快速幂思想及实现

快速幂思想其实很简单，就是公式的转换

1、当指数是偶数时，我们可以让指数除以2，底数乘以底数

2、当指数是奇数时，我们可以将指数变为奇数

例如 2¹⁰

• 指数是偶数，2¹⁰ = 4⁵
• 指数是奇数，4⁵ = 4 * 4⁴
• 指数是偶数， 4 * 4⁴ = 4 * 16²
• 指数是偶数，4 * 16² = 4 * 256¹
• 指数是奇数， 4 * 256¹=4 * 256 * 256⁰
• 指数为0时停止，那么答案就是计算 4 * 256 = 1024

下面代码就是模拟这个过程：

#include<iostream>//c++标准头文件，可以使用cout,cin等标准库函数 using namespace std;//命名空间，防止重名给程序带来各种隐患，使用cin,cout,stack,map,set,vector,queue时都要使用 long long fpow(long long a,long long b){//a是底数，b是指数 long long ans=1;//初始化答案为1 while(b){//当指数不为0时执行 if(b%2==0){//指数为偶数时，指数除以2，底数乘以2 b/=2; a*=a; }else{//指数为奇数时，分离指数，ans乘以底数 ans*=a; b--; } } return ans;//ans就是答案 } int main(){ long long n,m; cin>>n>>m; cout<<fpow(n,m)<<endl; }

3、快速幂精简模板

#include<iostream> using namespace std; long long fpow(long long a,long long b){ long long ans=1; while(b){ if(b&1)ans*=a; b>>=1; a*=a; } return ans; } int main(){ long long n,m; cin>>n>>m; cout<<fpow(n,m)<<endl; }

总结

到此这篇关于c++入门必学算法之快速幂思想及实现的文章就介绍到这了,更多相关c++快速幂算法内容请搜索自由互联以前的文章或继续浏览下面的相关文章希望大家以后多多支持自由互联！