甘肃龙网

  1. 首页 > 生活 > >

1.从简单的幂运算说起( 二 )

生活百科矩阵


代码里值得说明的地方：
1.除以是向下取整，无论n的奇偶性，直接除以二就行，这里合并了两种情况；
2.整个过程中不断对n折半，也需要不断对x平方，这点别忘
3.n=1的时候，就是折半结果了，刚好1也是奇数，所以循环条件是n>=1即n>0；
来测试一下这个程序， ！！
3.另一种角度
理解了上面的，快速幂可以说已经学的比较到位了 。为了理解更透彻，下面就结合位运算再深入地探讨一下 。
分析一下上面的代码，每一轮while循环，x都在不断平方，x的变化过程如下：
这还看的不够清楚，我们以3的13次方为例，整个变化过程为

1.从简单的幂运算说起

文章插图
然后模拟运行一下快速幂的程序，会发现最后ans的值为
是不是想到了某种东西，别急，把指数补全看看
噢（恍然大悟），这不就是13的二进制展开形式吗，就是这么神奇！
这也就是说，我们可以用指数的二进制逐位进行判断，1的话就跟ans相乘，0的话就接着往后走，可以想象成一个选择过滤器，x在不断地平方，每平方一次，都要根据指数二进制上对应的位（0或1）进行选择性相乘，x只管走自己的，判断让指数来决定！
对应到代码上改动比较小，一是把n%2 改成n&1, 二是把n%=2改成n>>=1,即移位运算符，虽然代码差异不大，但理解确实两个角度，直呼过瘾！
int quickPow(int x, int n, int mod){int ans = 1;//初始化while (n>0){if (n&1)ans = ans%mod * x%mod;//取模n>>=1;x = x%mod * x%mod;}return ans;
4.矩阵快速幂
最后谈一下快速幂的拓展应用，幂运算也不是数字独有的，定义了乘法的其他结构也可以，最典型的就是矩阵求幂，当然，根据线代的知识，方阵才能求幂，但这也不妨碍矩阵幂有很多的应用
先来说一下咋实现的：
问题的关键在于定义一个矩阵类型，然后定义它的乘法，取模等运算，到时候只需要把底数换成矩阵就行，没有更多的要求，来看代码：
1.矩阵类的实现
struct Matri{int a[15][15];int n;Matri (int N){n = N;for (int i=0; i
用了很多C++语言的特性，构造函数，重载运算符等，这些语言的细节就不再多说了，构造函数是在定义一个单位矩阵 。
2.矩阵快速幂
Matri quickPow(Matri x, int n, int m){Matri res(x.n);while (n>0){if (n&1){res = res%m * x%m;res= res%m;}x = x%m * x%m;x = x%m;n >>=1;}return res;}
值得注意的一点是，在数字的快速幂中，我们的res定义的是1，是乘法的单位元，对于矩阵来说，单位矩阵便是“1”，因此，要通过构造函数建立一个单位矩阵 。这点最容易出错 。
矩阵快速幂，最典型的应用就是求斐波那契数列，使复杂度降低到了logn，有些求斐波那契数列的题目会卡时间，到时候可以用矩阵快速幂进行优化 。
今天的总结就先到这里吧！


上一篇：品牌童鞋排行榜 童鞋品牌排行榜前十名

下一篇：chatgpt赋能python：Python3.9:最新版本的下载指南