矩阵(神奇算法)

  昨晚学长教了我们这样一个神奇的算法---矩阵快速幂,矩阵快速幂在递推优化上相当神奇,并且效率很高。

 一、 先举这样一个例子。斐波那契数列大家都知道的吧。f[n]=f[n-1]+f[n+2](n=108),求f[n];

  这种题目,要是用递归做下去肯定超时。但是用矩阵就很容易解决。

   f[n]           *        0 1       =   f[n+1]

   f[n+1] ...A          1 1 ...C        f[n+2] ...B   A矩阵*C矩阵得到B矩阵。C矩阵是推出来的;主要的核心就是推出一个矩阵与A得到B矩阵。(即我知道当前状态和下一状态,我就要求出中间的媒介,这样的话就是可以无限知道下下状态,下下下状态....的值~~)我们知道f[1]=1,f[2]=1;  A*Cn=B,接着对Cn快速幂取模就OK了!

  略懂一点之后,转变一下。

  二、有a,b,c,d四个城市,如同所示求从a->d在正好n步的条件下走到。n很大很大。求有多少种方法。 

  这个的初始的是走0步到达下一个位置的矩阵A=E(单位矩阵),然后很明显的中介矩阵就是  a b c d

                                           a 0 1 1 0  

                                            b 0 0 1 1

                                            c 1 1 0 1

                                            d 0 1 1 0....C 然后A*C就可以得到走两步到一个地方的种数。其中"1"表示a->b有一种方法。

  三、依旧是有a,b,c,d四个城市,如图所示。我现在要从a到d在正好n步的条件下走到,加一个要求就是路程最短。求最短的路程。和上一个类似,这里就不进行详解了0.0

 

学长还讲了区域赛里的几个题目,一时半会说不清楚,从早上总结到现在,该去吃饭了==总结一下吧

矩阵快速幂主要的就是要写出那三个矩阵来解决问题,虽然现在讲的只是一种思想,里面掺杂一些动态规划的问题,不过是很实用的,可以很快速的来解决n值特别大,或者类似的组合问题。

 

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。