【算法笔记·数论】快速幂,加速幂运算,超级详细。C/C++
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【算法笔记·数论】快速幂,加速幂运算,超级详细。C/C++,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3484字,纯文字阅读大概需要5分钟。
内容图文
![【算法笔记·数论】快速幂,加速幂运算,超级详细。C/C++](/upload/InfoBanner/zyjiaocheng/593/b8a39e9963ec4141aacdddcfaab4d33c.jpg)
前言:
欢迎光临大千小熊的博客,我是一只又会MMD又会C++的正派熊,B站和CSDN同步更新,欢迎关注。
幂运算含义:
形如
x
n
x^n
xn 指数是x,底数是x的一个幂。(
n
n
n是变量)
例如
2
4
=
16
,
2
2
=
4
2^4=16,2^2=4
24=16,22=4这样的运算。
计算幂运算的方法:
例如,我们想去计算
2
4
2^4
24。我们可以循环4次,另res=1,然后res*=4。
但是这样的算法是不高效率的。
这是因为,我们想计算
2
?
2
?
2
?
2
2*2*2*2
2?2?2?2的时候,人类一般都会用
2
?
2
=
4
2*2=4
2?2=4,然后是
4
?
4
=
16
4*4=16
4?4=16。来计算答案,这样只需要两步。这个方法的时间复杂度比上面算法的时间复杂度小,而且是因为拆开成两个部分,因此新的算法复杂度是
l
o
g
(
x
)
log(x)
log(x)级别的。而最先的那个笨方法是
x
x
x级别的。
那么我们怎么做到那样的巧妙的方法去计算快速幂呢?
请看下面的内容。
快速幂的设计思想:
例如上面的例子
2
?
2
?
2
?
2
2*2*2*2
2?2?2?2。我们可以设计一个递归函数。来不停的拆分上面的算式。
设函数
Q
u
i
c
k
P
o
w
(
x
,
n
)
QuickPow(x,n)
QuickPow(x,n)表示
x
n
x^n
xn的结果。下一个状态是
Q
u
i
c
k
P
o
w
(
x
?
x
,
n
/
2
)
QuickPow(x*x,n/2)
QuickPow(x?x,n/2)。
那么
Q
u
i
c
k
P
o
w
(
2
,
4
)
QuickPow(2,4)
QuickPow(2,4)意思就是上面的
2
?
2
?
2
?
2
2*2*2*2
2?2?2?2。
然后
Q
u
i
c
k
P
o
w
(
4
,
2
)
QuickPow(4,2)
QuickPow(4,2)意思是
4
?
4
4*4
4?4。
最后
Q
u
i
c
k
P
o
w
(
16
,
1
)
QuickPow(16,1)
QuickPow(16,1)的意思是到此为止。因为第二个参数是1。
看到这里也许你可能还是一头雾水,下面请看这种说法:
例如:
3
?
3
?
3
?
3
?
3
?
3
?
3
?
3
3*3*3*3*3*3*3*3
3?3?3?3?3?3?3?3。(总共8个3)
我们这样计算
(
3
?
3
?
3
?
3
)
?
3
?
3
?
3
?
3
(3*3*3*3)*3*3*3*3
(3?3?3?3)?3?3?3?3先进行一个
3
?
3
3*3
3?3的运算。所以我们可以说上面的这个方程实际等价于
(
9
?
9
)
?
3
?
3
?
3
?
3
(9*9)*3*3*3*3
(9?9)?3?3?3?3。
最后通过递归到
(
81
)
?
3
?
3
?
3
?
3
(81)*3*3*3*3
(81)?3?3?3?3知道81就是一个其中的一个解。然后前面是81,那么后面的
3
?
3
?
3
?
3
3*3*3*3
3?3?3?3也一定是81。所以最终81*81就是我们要的一个解。
再再看看下面这种说法:
Q
u
i
c
k
P
o
w
(
x
,
n
)
QuickPow(x,n)
QuickPow(x,n)的
n
n
n的意思是有几个
x
x
x需要相乘。如果
n
=
1
n=1
n=1,那么就不需要继续进行相乘了。
小小的疑问:
那如果指数是奇数怎么办呢?
其实和偶数是一样的,奇书/2==偶数/2(“/”的意思是“整除”)。
我们只需要计算完结果然后像这样
x
?
Q
u
i
c
k
P
o
w
(
x
,
n
)
x*QuickPow(x,n)
x?QuickPow(x,n)手动的把
x
x
x多乘一份就可以了。
现在动手试一试吧,我想你一定能搞清楚递归函数是怎么样的。下面请看示例代码:
快速幂(递归)实现代码:
这里我为你准备了两个版本:
版本1:
#include <cmath>
#include <iostream>
using namespace std;
typedef long long ll;
ll res = 1;
ll QuickPow(int x, int n) {
if (n == 1) //函数的退出条件
return res *= x;
if (n % 2 == 0) { //偶数
return QuickPow(x * x, n / 2);
} else { //基数
return x * QuickPow(x * x, n / 2);
}
}
int main() {
cout << QuickPow(2, 3);
return 0;
}
版本2:
#include <cmath>
#include <iostream>
using namespace std;
typedef long long ll;
ll res = 1;
ll QuickPow(int x, int n) {
if (n == 0)
return 1;
ll res = QuickPow(x * x, n / 2);
if (n & 1)
res = res * x; //发现n是一个奇数,手动乘入x
}
int main() {
cout << QuickPow(2, 3);
return 0;
}
快速幂的设计思想2:
那么如果不用递归能不能实现快速幂呢?
答案当然是可以的。
我们设
n
=
2
k
n=2^k
n=2k,为什么底数是
2
2
2呢?这个我们做一个悬念。
那么原来的方程:
x
n
x^n
xn可以写成
(
(
x
2
)
2
)
2
.
.
.
((x^2)^2)^2...
((x2)2)2...
只要进行k次那么答案就被我们求出来了。
又因为
所以计算机是2进制的世界,我们可以很轻松的操作二进制比如>>。所以将n转为2的倍数然后进而来表示n。
例如计算:
我们做一个16次的循环,不停的乘x,然后如果遇到指数是2,4,16(也就是22的二进制中10110为1的部分),就把他们乘入res中,最后就可以得到最终答案。这个方法的只要循环16次,比22次要少了很多。
快速幂(二进制)实现代码:
#include <cmath>
#include <iostream>
using namespace std;
typedef long long ll;
ll QuickPow(int x, int n) {
ll res = 1;
while (n > 0) {
if (n & 1 == 1)
res *= x;
x *= x;
n >>= 1;
}
return res;
}
int main() {
cout << QuickPow(4, 9);
return 0;
}
内容总结
以上是互联网集市为您收集整理的【算法笔记·数论】快速幂,加速幂运算,超级详细。C/C++全部内容,希望文章能够帮你解决【算法笔记·数论】快速幂,加速幂运算,超级详细。C/C++所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。