C语言程序实践第一周报告(.doc版)

C语言程序实践第一周报告

矩阵乘方

一种朴素的思想

对于普通类型的求a^n，我们的求法是a*a*a*a....，这样乘以n次，时间复杂度为O(n)，对于普通n比较小的我们可以接受，然而当n比较大的时候，计算就慢了，所以我们就去寻找更快捷的计算方法，学过快速幂的同学应该不难想到矩阵的快速幂

例如：我们要求2^8，我们通过当为偶数的时候，a^n=(a*a)^(n/2)，当n为奇数时，a^n=a*(a*a)^(n/2)的形式，是不是可以转化为4^4->8^2->64^1，就可以了，2^5的话2*4^2->2*16^1。(把幂化为底数，减少乘法的次数）

其实类似这样的思想不少见，我们不应该感到陌生：

例如著名的秦九昭算法（扯远了，但还是要说一下）

背景：

你怎么算呢？暴力乘，好我们来分析一下时间复杂性的问题，你需要加法运算n次，乘法运算1+2+....+n=n*(n+1)/2次，但我们有一个很简单的优化：秦九昭算法

我们只需要n次乘法运算，n次加法运算就可实现多项式求值时间复杂度为o(n)

其实本质是什么呢？

本质是利用已有的数据，就比如说我已经有了x，我去算x^2就不用两次运算，直接在原有的基础上再乘一个x，其实很多别的算法也是基于这个大思想，例如记忆化搜索，前缀和，差分，线段树懒标记

说回正题，基于这样的思想

矩阵快速幂板子应运而生

Mat pow(Mat x,int y)

{

Mat ans;

for(int i=1;i<=n;i++)

{

for(int j=1;j<=n;j++)

{

i==j?ans.m[i][j]=1:ans.m[i][j]=0;//单位矩阵*任何矩阵=任何矩阵本身 单位矩阵定义：对角线上元素为1，其他为0

}

}

while(y) //矩阵快速幂模板

{

if(y&1)

{

ans=Mul(ans,x);

}

x = Mul(x,x);

y>>=1;

}

return ans;

}

唯一要注意的就是奇数和偶数的差别：奇数多乘一次，偶数则不用

之前程序没过的原因：

第一次:没看题目要求n,b,m按顺序输入

第二次：快速幂最后返回的是ans矩阵而不是x矩阵