设为首页 加入收藏

TOP

矩阵乘法(四):分析问题,确定递推式,采用矩阵快速幂求解(一)
2019-09-06 00:26:44 】 浏览:40
Tags:矩阵 乘法 分析 问题 确定 采用 快速 求解

      应用矩阵快速幂运算可以解决递推问题。在实际应用中,有时候题目并没有直接给出递推式,需要认真分析问题,找出递推式,然后再利用矩阵快速幂运算加快问题的求解。

【例1】程序阅读理解。

      有如下的C语言程序:

#include <stdio.h>
int main()
{
     int n,m,f,i;
     while(scanf("%d%d",&n,&m)!=EOF)
     {
           f=0;
           for(i=1;i<=n;i++)
           {
                if (i&1)f=(f*2+1)%m;
                else f=f*2%m;
           }
           printf("%d\n",f);
     }
     return 0;
}

       阅读上面的程序,根据输入的n和m,写出程序运行的结果。例如,输入 3  10,输出应为5。

       但由于给定输入的n和m的数据范围为1<=n, m <= 1000000000,且测试集中数据量较大,因此如果直接将给定的程序提交会超时的。请你编写一个程序,能根据输入的n和m快速完成问题的求解,以实现给定程序的功能。

      (1)编程思路。

      给定程序段实际是通过迭代的方式求f(n)%m的值。先不考虑求余,找到f(n)的求法。

      分析给定程序知,f(0)=0, 当 n为奇数时,f(n)=2*f(n-1)+1;当n为偶数时,f(n)=2*f(n-1)。

      下面进一步分析,找到不考虑n的奇偶性的一个统一的递推式。

       当 n为奇数时,f(n)=2*f(n-1)+1,n-1一定为偶数,f(n-1)=2*f(n-2)。因此,

                f(n)=f(n-1)+f(n-1)+1=2*f(n-2)+f(n-1)+1。

       当 n为偶数时,f(n)=2*f(n-1),n-1一定为奇数,f(n-1)=2*f(n-2)+1。因此,

                f(n)=f(n-1)+f(n-1)=2*f(n-2)+f(n-1)+1。

      由此,得到统一的递推式: f(0)=0,f(1)=1,  f(n)=2*f(n-2)+f(n-1)+1  (n>=3)。

      确定了递推式后,可以构造矩阵P,进行快速幂运算求解。

       

      

 

      

 

       (2)源程序。

#include <stdio.h>
#include <string.h>
struct Matrix
{
      __int64 mat[4][4]; // 存储矩阵中各元素
};
Matrix matMul(Matrix a ,Matrix b,int n,int m)
{
      Matrix c;
      memset(c.mat,0,sizeof(c.mat));
      int i,j,k;
      for (k = 1; k<=n ; k++)
          for (i=1 ;i<=n ; i++)
              if (a.mat[i][k]!=0)
                  for (j = 1 ;j<=n ;j++)
                      c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % m;
      return c;
}
Matrix quickMatPow(Matrix a ,int n,int b,int m) // n阶矩阵a快速b次幂
{
      Matrix c;
      memset(c.mat ,0 ,sizeof(c.mat));
      int i;
      for (i = 1 ;i <= n ;i++)
           c.mat[i][i] = 1;
      while (b!=0)
      {
           if (b & 1)
               c = matMul(c ,a ,n,m); // c=c*a;
           a = matMul(a ,a ,n,m); // a=a*a
           b /= 2;
      }
      return c;
}
int main()
{
      int n,m;
      __int64 ans;
      Matrix p;
      while(scanf(&quo
矩阵乘法(四):分析问题,确定递推式,采用矩阵快速幂求解(一) https://www.cppentry.com/bencandy.php?fid=49&id=250204

首页 上一页 1 2 3 下一页 尾页 1/3/3
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇洛谷 p1010 幂次方 下一篇数据结构:队列queue 函数push() ..