精华内容
下载资源
问答
  • 很多同学在已知数列递推关系,求解数列通项公式的时候,由于不会对通项公式变形或者是变形后不会化简,从而求解不出数列的通项。因此今天叶老师将推出:高考倒计时决战60日系列的第二十集:破解...

    各位同学,在上期内容《另辟蹊径,探寻本源——有关阿氏圆的本质及其作用的深入探究》中,叶老师向大家介绍了一种求解三角形面积最值与线段之和最值的模型——阿波罗尼斯圆模型。并向大家推导了阿氏圆的原理,大家有时间可以回顾一下!

    很多同学在已知数列递推关系,求解数列通项公式的时候,由于不会对通项公式变形或者是变形后不会化简,从而求解不出数列的通项。因此今天叶老师将推出:高考倒计时决战60日系列的第二十集:破解数列通项公式的最强外援——不动点法。希望能够帮助大家解决数列通项公式的求解问题!

    作者简介:叶老师,笔名“动人定理”,专职教师,数学学科研究员,目前担任机构数学教研组组长及学生学业规划师。曾供职合作于多家上市教育公司,对中高考数学考点有着深入认知与理解。拥有超过10000小时的高三毕业班学生一对一辅导经验。

    c9a79ae1cdcae69ab4cae10f49c54290.png

    破解数列通项公式的最强外援——不动点法

    导读

    在高中阶段,“求解数列通项公式”算是一种非常常见的题型了,几乎每年高考必考,因此许多老师也根据数列递推关系的结构或者是系数之间的关系总结出了一系列求解数列通项公式的方法,比如:公式法,累加累乘法,取倒数法,嵌套法等等。这些方法虽然巧妙,但是必须得对应其独有的递推结构才能使用,这无疑中增加了同学们的记忆难度与理解难度!特别是很多时候,递推关系各个项的系数并没有很明显的关系,此时求解数列的通项公式便更加困难了。因此求解数列的通项公式必定得依靠强大的外援作为支撑,今天叶老师介绍的这个“不动点”法,将能帮助同学们解决数列递推公式的化简与构造问题!那么接下来,叶老师将通过:①不动点法的概念及化简机制。②不动点法的应用举例。等两个方面向大家全面介绍一下这个强大的外援——不动点法。

    一、不动点法的概念及化简机制

    首先我们先来介绍一下不动点的概念:使方程f(x)=x成立的解x称作是函数f(x)的不动点。

    所以不动点法我们可以这样定义:我们把数列的递推关系看作是"an+1=f(an)"这样的函数关系然后直接令an+1与an为x,这样便可得到一个只关于x的不动点方程,解出不动点之后,我们便可利用递推数列的不动点,将某些递推关系所确定的数列化为等比数列或较易求通项的数列。

    因此对于任意的数列递推关系,我们都能将其看做是an+1与an的函数关系,然后解出函数的不动点x,对数列进行构造,这样便可解决通项公式的求解问题。

    至于为什么能用不动点法构造数列,这个原理比较复杂要用到许多高等数学的知识,同学们可能无法理解,因此在这里叶老师站在大家的角度向大家简单地说一下不动点法的化简机制从高中的角度上来说使用不动点法恰好可以使等式左右两边出现相同的因式,当你解出f(x)=x这个方程的解x0之后,等式左右两边都可以分解出(x-x0),这样再把an+1与an回带,递推公式就可以改写成:(an+1 - x0)=(an - x0)*f(an)。直白一点说就是:用不动点法构造出来的数列递推式恰好便是同学们利用待定系数法历经千辛万苦所化出来的式子。因此不动点法的作用:就是为了直接凑出相同的形式以便省略复杂的待定系数过程,从而轻松求解数列通项!

    a17e4f5db2fbde8abec3bb6e0a2512c8.png

    二、不动点法的应用举例

    通过上述不动点法的概念以及化简机制,我们可以得知:在高中阶段,不动点法主要是用来解决一次函数型和分式型的数列递推,因为这两种形式的递推关系,都可以使用不动点法进行化简,使得等号左右两边出现相同的因式,从而达到化简的目的!

    下面我们就来具体看看这两种应用举例

    1.用不动点法解决一次函数型递推数列

    (1)化简机制的简单介绍

    e5098420e0cdad471af98fbe9ada82d3.png

    化简机制的简单介绍

    (2)例题详解

    52dde2b89425a3f8eb08e4331e6f7e9a.png

    小结:因此当数列的递推关系为一次函数时,利用不动点方程,解出不动点后,在等式左右两边同时减去不动点,同学们便可轻松利用提取公因式的方法,构造出一个新的有关an的等比数列,从而轻松求出通项公式an!

    2.利用不动点法解决分式型递推数列通项问题

    (1)化简机制的简单介绍

    670b07d66ff8e86d0700391928288582.png

    化简机制的简单介绍1

    d5a8ea0b45ba46ee6a2fa1eef0776894.png

    化简机制的简单介绍2

    PS:当不动点方程无解时,数列an必为周期数列。其原因是:数列在高等数学里可以看做差分方程。差分方程的解可以用e的指数型来表示,如果这时特征方程解出来的根是虚根,那么根据欧拉公式,可以将e的指数型化为正弦与余弦函数和的形式,由于正余弦函数具有周期性,所以说这种数列就具有周期性!

    (2)例题详解

    718c38da1adc5beca45634c0daadf24e.png

    小结:因此对于分式型递推关系的数列通项求解,我们仍然是使用不动点法进行求解,只不过在计算过程中,同学们还应该注意分式通分运算的使用,这便要求同学们得有一定的运算能力了,否则一旦所得,得不偿失!

    971110a8b367ac8402f2b89eb3fbaa37.png

    写在文末

    到这里,本期内容就接近尾声了,不知同学们对叶老师这回请来的外援——不动点,是否满意。其实说来说去,在高中阶段,同学们要想真正明白不动点法的根本原理是非常难的,因为不动点法的原理推导用到了非常多高等数学的知识,而同学们的知识储备还没到达那个高度,因此研究起来肯定特别费劲。因此在文末,叶老师想最后提醒一下同学们有关不动点法使用的注意事项,希望同学们可以牢记于心:

    ①不动点法的化简机制要比原理好懂很多,还可以自己推导,因此希望同学们把精力花在推导化简机制上,对于不动点法的真正原理不要做过多的深究!

    ②不动点法优于常规构造法的地方是:省略了复杂的待定系数过程,大大提升了做题的速度与准确性,因此希望同学们记住这点,合理使用!

    ③对于分式型递推数列,同学们在使用不动点法时,一定要注意通分运算的准确性!

    最后希望同学们看完本期内容后,都能有所收获!

    c7ad4fbb855d6f8da7bcb1bb0d3905e0.png

    欢迎大家关注【叶老师数学课堂】,让我们一起思考和探讨。

    如果觉得有帮助,请点个赞,谢谢O(∩_∩)O~

    你的认可,是我们努力的方向!

    展开全文
  • 高观点下递推数列通项公式的推导及应用 申明:数学符号与公式显示故障,需要完整论文的读者可以与我联系(blue-eutopia@live.cn) 摘要:递推数列通项公式的推导及应用是高考的热点之一.随着新课程改革的推进...

     

    高观点下递推数列通项公式的推导及应用

     

    申明:数学符号与公式显示故障,需要完整论文的读者可以与我联系(blue-eutopia@live.cn

     

    摘要:递推数列通项公式的推导及应用是高考的热点之一.随着新课程改革的推进,越来越多的高等数学知识进入高中课程,也进入高考,这就需要我们从高观点的角度出发寻找高等数学与中学数学的结合点,提高中学数学教学的深度.本文首先归纳总结中学数学中八种常见的递推数列通项公式推导方法,然后以高等数学的相关知识为工具,把它们推广到更一般的形式,并给出常系数线性与非线性递推数列、分式型递推数列等通项公式的一般解法.

     

    关键词:递推数列;通项公式;不动点;特征方程;矩阵;Fibonacci数列;三角代换;Catalan

     

    1中学数学中几种常见的递推数列通项公式的推导方法

    1.1 型,这类型的递推数列的通项公式推导常使用累乘法. 时, .

    1.2 型,采用叠加法,

    .

    1.3 (p为常数且不为零)型,采用待定系数法,引入辅助函数 ,把递推数列变形为 ,则 为等比数列,那么 的通项也就不难得到.特别地,当 时,可采用叠加法.

    1.4 ( p为常数且不为零))型,利用对数的运算法则,构造新的等差或等比数列.

    已知数列 满足 ,求 的通项公式.

    分析:对 两边取以10为底的对数,得 ,从而 ,得到新的等比数列 ,那么 的通项公式也就不难得到.

    1.5 为常数且不为零)型,常采用倒数变换或拆分变化的方法.

    已知数列 满足 ,求 的通项公式.

    分析: 可转化为 ,进行倒数变换得到 ,令 ,则得到新的递推数列 ,转化到1.3型,从而 的通项公式的都可以得到.

    1.6 为常数且不为零)型,这属于二阶齐次线性递归数列类型.这里仅对中学常见的 情况进行讨论,更一般的形式涉及到高等数学的知识,将随后给出.

    分析:当 时,递推关系可以写成 ,即 ,则得到等比数列 ,首项为 ,公比为

    从而 ,此时问题转为1.2.

    1.7 pqr为不为零的常数)型,这属于二阶非齐次线性递归数列类型,更一般的形式涉及到高等数学的知识,将随后给出.中学阶段常常使用换元法求解,限于篇幅,此处不做具体说明,有兴趣的读者可以参见《换元法求一类递推数列的通项公式》(陈健)一文.

    1.8 p,q,e,f为常数)型,这属于分式型递推数列类型,中学阶段常借助函数中的一个概念完成转化,更一般的形式涉及到高等数学的知识,将随后给出.

    已知函数 ,满足 x称为函数的不动点,此种求通项的方法称为不动点法. x得到方程 ,此方程可有一个解或者两个解,也可能无解.

    若无解,则数列为循环数列,周期性变化.若有解,求根,具体做法以实例说明.

    已知数列 满足 ,求 的通项公式.

    解析:令 ,则 . 两边分别减去

    ,得:

    二式相除得:

    从而数列 是以 为首项,以

    公比的等比数列,所以 ,整理得到 .

    2 高观点下的推广

    2.1   常系数线性齐次递推数列

    常系数线性齐次递推关系是一种极其常见的递推关系类型,在实际生活中有着广泛的应用,前文中提到的1.6 型就是其较为简单的一种形式.

    定义1形如  1  都是常数且 称为常系数线性齐次递推数列. 是初始条件.

    定义2方程  叫做递推数列(1)的特征方程,它的 个根 叫做递推数列(1)的特征根.

    根据特征根的不同情况,可分三种情形讨论:

    1)特征根全是单根

    定理1设递推数列(1)的特征根 互不相同,则递推数列(1)的通解是

     .

    证明:令 是递推数列任一解,那么 由它的初始条件  完全确定,待定常数 由方程组

               *

    解出,方程组(*)的系数矩阵是

    . 因为所有的特征根 都不相同,所以这个系数矩阵行列不为零,于是方程组(*)关于 有唯一的解,证毕.

    1 斐波那契(Fibonacci)数列, ,求通项公式 .

    解:Fibonacci数列所对应的特征方程为 ,其特征根为

    通项公式 ,将 代入得,

    所以 .

    2)特征根中有重根

    定理2 是递推数列(1)的全部不同的特征根其重数分别为   ),那么递推数列(1)的通解为 ,其中 .

    证明:由初始条件  得到关于 的联立方程组,其系数矩阵行列式的值为 ,故可由初始条件唯一地确定 ,这说明递推数列(1)的任意解均可写成 的形式,其中 如前所示.

    2 求递推数列   的通项公式.

    解:该递推数列所对应的特征方程为 ,其特征根为 ,其中-1是三重根,故一般解中对应-1这个根的部分是 ,而对一般解中对应2的部分是 .因此,递推数列的通项公式为 .

    由初始条件,联立方程组解得 .

    故通项公式为 .

    3)特征根中有复根(这种情形实际上已经包含在前两种情形中,但是为了计算的方便这里单独进行讨论)

    定理3 , 是递推数列(1)特征根的一对复根,则这对共轭复根,对应的齐次解为

    其中 .

    3 求递推数列    的通项公式.

    解:该递推数列对应的特征方程为 ,其特征根为

    ,故该递推数列的通项公式为 .

    由初始条件联立方程  解得: .

    故通项公式为: .

    2.2   常系数线性非齐次递推数列

    常系数线性非齐次递推关系也是一种常见的递推关系类型,前文中提到的1.21.31.7型就是其较为简单的几种形式.

    定义3 形如  2  都是常数且 称为常系数线性齐次递推数列,其中 为对应的齐次部分, 为非齐次部分, 是初始条件.

    定理4 常系数线性非齐次递推数列(2)的通解是(2)的一个特解加上其对应的齐次部分的通解.

    证明:设序列 ,……, ,……和 ,……, ,……是(2)的解,则序列 ,……, ,……是齐次递推关系的解,即要求的非齐次递推关系的解等于齐次递推关系的解和一个非齐次递推关系特解的叠加. ,……, ,……是(2)的解.

    4 解线性非齐次递推数列 通项公式.

    解:先求特解.假设 是一个解,则代入得到: ,解得 ,从而 是一个特解,接下来求出 的通解即可,限于篇幅,这里省略.

    特别地,对于不同的非齐次部分,特解的求法往往都不一样,这里给出几种最常见的几种情况供参考.为了更好的说明,设 .

    型,若 ,则可以假设特解为 ,如例4所示;若 ,即 k重根,则可以假设特解为 .

    型,可转化为 ,若 ,可以假设特解为 ns次多项式;若 ,即1 k重根,则可以假设特解为 .

    2.3   分式型递推数列(前文1.8型的推广)

    定理5 设数列满足初始条件和如下递推关系

    是特征方程组的两复数解,其中

          

    则(1)当 时:

     

    .

    2)当 时:

    .

    其中

    .

    证明:略.

    5 已知数列满足初始条件和递推关系

    求通项公式.

    解:根据定理可知 考虑特征方程组

      

    由定理可知

    .

    例6 已知数列满足初始条件和递推关系,求通项公式,并计算的值.

    解:根据定理可知, ,考虑特征方程

    由定理可知

     

    特别的,对于二阶分式型递推数列,前文1.8给出了不动点法,作为推广现再给出一种矩阵法:

    设数列{ }的首项为 ,且     3

    其中a,b,c,d为常数,同时, ,我们称这个递推公式为分式递推公式,而数列{ }称为由分式递推公式给定的分式递推数列.可定义为:

    = p     4

    由(4)的递推关系和矩阵的乘方,存在 ,使

               5

    于是(5)就给出了数列{ }的通项矩阵表达式,余下就是求 .

    定理6 A= ,那么

    1、  A有两相异的特征根 ,则(3)的通项公式为:

    .       (6)

    2、  A有二重特征根 ,则(3)的通项公式为:

    .        (7)

    证明:略.

    7 在数列.

    解:由题设设  A的特征多项式

    有两个不相等的特征根25,由公式(4).

    2.4   其他

    2.4.1       二元线性一阶递推数列

    设两个数列满足:   8),

    则由(8)式所确定的数列称为二元线性一阶递推数列.

    ①若,则(8)式可以转化为一阶线性递推数列的情形.

    ②若bc均不为零,由(8)式可得

    .

    ,则有.于是问题转化为分式线性的通项公式的情形.

    2.4.2 含根式的递推数列

    某些含有根式的递推数列问题,用三角代换法去其根式,进而转化为我们熟知的递推数列问题.限于篇幅,这里简单的例析说明若干类型,以期抛砖引玉.

    8 数列的项由递推方法定义如下:,试证明:

    数列是单调的.1981年第15届全苏中学生数学奥林匹克试题)

    证明:易知 ,与三角公式的类比,可作三角代换,由已知条件可得

              

     ,故数列是单调递增的.

    9 数列定义如下:

    . 证明对于每个

    .1989年第30IMO备选题)

    证明:根据数列的递推式及首项易知,对,有.注意到

    相类似,故可作三角代换

    ,则

    类似地,由的类比,可作三角代换

    借助数列的递推式及初始值,可求出

    ,即题述不等式成立.

    注:本题结论中的后一不等式,即为1990年匈牙利数学奥林匹克试题.

    2.4.3          Catalan

    Catalan数是一种经典的递推关系,在现实生活中的应用颇广,这里作简单介绍,有兴趣的读者可以进一步参见《组合数学》一书.

    定理7  Catalan满足以下递推关系:

    .

    并且Catalan数通项公式为.

    参考文献:

    [1] 宋立温. 用特征根法求常系数线性递推数列的通项 [J]. 山东电大学报,2007,(2

    [2] 卞祖菼. 用特征方程组求一类分式型递推数列的通项公式 [J]. 中学数学教学,1999增刊

    [3] 欧云华. 矩阵与分式递推数列的结合点 [J]. 益阳师专学报,2001,(5

    [4] 邓勇. 递归数列通项与不动点原理 [J].  喀什师范学院学报,2008,5

    [5] 李春雷. 含有根式的递推数列问题求解策略 [J]. 数学通报,2006,(21

    转载于:https://www.cnblogs.com/vincent-lwx/archive/2008/12/08/1350263.html

    展开全文
  •  话说真查便发现这玩意鼎鼎大名无处不在,反正我高数不好大部分看懂,就觉得不明觉厉……  所谓斐波那契数列就是指1 1 2 3 5 8 ....这一数列数列的格式是F(1)=1 ,F(2)=1,F(n)=F(n-1)+F(n-2)(n

           真没啥好说的QAQ。但是前阵子公司的技术BOSS和咱纠结这个数列的一些问题,于是我只好记录一下一些东西,表示自己还是学到了一点东西滴~

           话说真查便发现这玩意鼎鼎大名无处不在,反正我高数不好大部分看不懂,就觉得不明觉厉……

           所谓斐波那契数列就是指1 1 2 3 5 8 ....这一数列。数列的格式是F(1)=1 ,F(2)=1,F(n)=F(n-1)+F(n-2)(n>=3)。 斐波那契数列原型是个非常典型的递归算法,根据上述定义可以很简单的写出求该数列第n位的递归算法为:

      

    int fib(int n){   
       if(n>=2){       
          return 1;    
       }    
       return fib(n-1)+fib(n-2);
    }


             这个丑陋的函数十分鲜明滴证明了一个道理,那就是递归算法严重影响计算性能=-=。我自己实际运行了一下,电脑在计算到第43位数字时开始耗费大量的时间:

    计算位数32结果2178309计算次数4356617套O(n)2178309
    计算位数33结果3524578计算次数7049155套O(n)3524578
    计算位数34结果5702887计算次数11405773套O(n)5702887
    计算位数35结果9227465计算次数18454929套O(n)9227465
    计算位数36结果14930352计算次数29860703套O(n)14930352
    计算位数37结果24157817计算次数48315633套O(n)24157817
    计算位数38结果39088169计算次数78176337套O(n)39088169
    计算位数39结果63245986计算次数126491971套O(n)63245986

    计算位数40结果102334155计算次数204668309套O(n)102334155


            可以看到当计算数列第40位即F(40)时,这个函数已经需要执行2亿多次。

           据说在代数里这种本项等于前两项之和的式子叫做二阶齐次差分方程(http://bbs.pediy.com/archive/index.php?t-123051.html)?!数学上这个数列的通项公式可以根据齐次差分方程的求解公式获得。于是该数列第n位的值F(n)就是:

          得到通项公式也差不多就可以知道算法的时间复杂度了。于是上面这个函数的算法复杂度是指数级的。

          时间复杂度的衡量一般都是按级别划分,从小到大依次为O(1),O(logn),O(n),O(n^a),O(a^n)和(n!)。指数级的算法是不可接受的,基本上很难在实际场合中运用。log级别的则一般是最为理想的。这个数列当然也有log级别的算法,是利用矩阵相乘原理得到的。这个网上证明很多,我不贴了,贴了还是看不懂- -。

          在上面我贴了一段函数运行结果,套O(n)后面的数字其实就是利用该函数的通项公式获得。计算次数则是调用了上述函数的次数。可以发现函数调用次数正好是F(n)的2倍少1.关于这个也很好解释。举个例子,比如求F(6),那么函数的运行情况如下图所示:

         

          可以看出这是一颗二叉树,每个节点表示函数被运行了一次。F(2)=F(1)=1 ,所以运行到F(2)时函数即可返回值。可以发现树的叶子节点的个数就是F(6)的值,它和通项公式获得的解是一致的。而非叶子节点的个数则比叶子节点数少1.因为叶子节点最终会汇集到根节点,根节点只有1个,叶子节点有n个,而二叉树每次汇集会减少一个叶子节点,所以非叶子节点的数量比叶子节点数少1,因此该函数的运行次数就是2F(n)-1。也就是说该函数的时间复杂度是通项公式的2倍少1.

          我是觉得际计算机运行时是不可能用通项公式去计算数列某位的值的,因为这个通项公式里有无理数,必然造成计算结果不精确。后来网上资料也显示正确的计算机算法就是之前说的那个矩阵相乘法。


           BOSS说和我们纠结这个问题是因为将来如果我们成长到要写某些系统的核心算法时,会遇到这种优化递归算法的问题。优化算法有这么几种思路,一是从算法思想上进行变化,找到一种计算次数更少的算法,这是算法上的改进;二是对代码进行优化,将递归算法改写成循环迭代,会大大减少空间占用等问题,而当算法很难改写成迭代形式时,可以尝试将代码改写成“尾递归”。我是觉得叫“伪递归”不是更形象么。。

          尾递归就是从最后开始计算, 每递归一次就算出相应的结果, 也就是说, 函数调用出现在调用者函数的尾部, 因为是尾部, 所以根本没有必要去保存任何局部变量. 直接让被调用的函数返回时越过调用者, 返回到调用者的调用者去.

           伪递归,哦,是尾递归-。-。 尾递归可以大大减少程序内存栈的使用率,从而在对代码进行更改的难度和算法效率上得到了折中,应该算是一种中庸思想吧……

           在斐波那契数列这个问题上用尾递归显得没必要,因为即使写成迭代for循环的形式也很简单,但将来或许会碰上一些难以用简单形式表达的算法,那么这时候尾递归就会显示出它的优越性了。

           斐波那契数列的定义写成函数,其实是一种自顶向下的计算过程,其中有大量的计算重复,从上面的树图中就能发现,F(3)和F(4)都计算了多次。有种比较好的思路是自底向上,这种思想应该说事动态规划的思想。像斐波那契数列中自底向上的算法就可以方便的写成循环迭代形式,空间效率和时间效率都比递归算法好很多:

    int n;
    int i;
    int S0=1;
    int S1=1;
    for(i=3;i<=n;i++){
       S1=S0+S1;
       S0=S1-S0;
    }
    
              S1就是数列第n位的值。
    展开全文
  • 北航计算机学院-计算机组成原理课程设计-2020秋,PreProject-Logisim-Logisim组合逻辑电路-斐波那契数列问题(简单迭代法+矩阵乘法的快速幂)。 北航计算机学院的计算机组成原理课程设计,是高度实践性的专业课程,...

    北航计算机学院-计算机组成原理课程设计-2020秋

    PreProject-Logisim-斐波那契数列问题(简单迭代法+矩阵乘法的快速幂)


    从本节开始,课程组给出的教程中增添了很多视频讲解。为了避免侵权,本系列博客将不会搬运课程组的视频讲解,而对于文字讲解也会相应地加以调整,重点在于根据笔者自己的理解给出习题的解析。因此带来的讲解不到位敬请见谅。



    斐波那契数列问题的简单迭代法

    提交要求

    使用Logisim搭建一个根据输入序号x计算对应序号斐波那契数fib[x]的电路(输入序号0对应输出数0,输入序号1对应输出数1,输入序号2对应输出数1,以此类推)并提交。

    • 输入: N(3bit)
    • 输出: Nth(4bit)
    • 文件内模块名: main
    • 测试要求:每次给定一个固定输入保持不变,电路在64个周期内计算出结果并稳定输出,在结果未计算出之前输出端口输出0
    • 请使用时序逻辑完成本题目。未按照要求(或采用捷径)完成并提交通过的同学,请重新提交。

    提到斐波那契数列,想必大家小学二年级就已经学过了经典的1, 1, 2, 3, 5, 8, …,在程序设计入门的时候大家也一定写过斐波那契数的实现代码,最直观地,我们通过定义可以写出递归版本的斐波那契数(以下展示C语言版本):

    int fib(int n) {
    	if (n <= 2) return 1; // fib(1) = fib(2) = 1
        return fib(n - 1) + fib(n - 2);
    }
    

    但是放在本题,是无法用这样的思路直接实现电路的,因为递归实质上是操作系统在不断索取硬件资源,我们无法让电路实现递归式的栈增长,因此需要考虑迭代的方法:

    int fib(int n) {
    	int prev = 1, now = 0; // fib(-1) = 1, fib(0) = 0;
    	for (int i = 0; i < n; i++) {
    		now = now + prev;
    		prev = now - prev;
    	}
    	return now;
    }
    

    我们有没有可能用电路实现循环控制呢?答案是肯定的。我们可以使用寄存器来存储变量的值,然后通过其他运算器件在相邻时钟上升沿之间改变寄存器的输入,更新寄存器的值,最后通过计数器确定运算的次数进行输出即可。

    题外话,题目所述的“必须采用时序逻辑电路”、“禁止走捷径”,走捷径的方法是什么呢?很容易,输入只有3位,我们将输入范围内的斐波那契数全部存储在RAM里,根据输入读出该值即可(大家不要采用这种方法。

    下面的介绍将自顶向下地描述电路构建成果。首先电路在顶层之下划分出“计数逻辑”和“计算逻辑”两个子电路,“计算逻辑”是整个电路的核心,其功能主要是计算出不断更新的fib(n)的值“计数逻辑”是电路正确输出的保障,其主要功能是给出电路何时应当输出答案的信号。两者配合达到的效果是:一端不断更新fib(n)数列,另一端在合适的时候输出数列的当前值,就像是列车的发动机只负责提供向前的动力,而控制系统掌管列车何时到站停下。

    在这里插入图片描述

    顶层电路的设计如下图所示。 按照题目要求,左侧三位输入是待求fib(n)中的n,右侧四位输出是fib(n)的值,在计算得到结果之前输出0,得到正确结果之后稳定输出fib(n)。为了增强电路的可读性,我在设计中尽可能多地使用了Tunnel来说明每一根信号的功能。

    在这里插入图片描述

    左下方的reset信号是在设计过程中为了方便调试添加的复位信号,在调试时将该信号设置为1则整个电路回到初始状态,子电路中所有计数器和寄存器的值全部清零。该信号单纯为了调试方便,和整体的功能没有直接关系,可以直接删除。该信号接入了两个子电路,下文的子电路介绍中不再阐述。

    上面已经提到,计数逻辑子电路主要功能是给出电路何时应当输出答案的信号,当计数逻辑右侧的输出信号output_signal为0时,右侧多路选择器选择常数0,输出保持为0,而当output_signal为1时,将输出计算逻辑子电路的输出值,也就是计算得到的正确答案。上文同样提到,计算逻辑将会不断地更新fib(n)数列,而并不关心输出值如何稳定保持,因此output_signal信号会被接入计算逻辑,在应当输出的时候,通过寄存器enable端口冻结计算逻辑中寄存器的值,让计算逻辑的输出一直保持为正确输出,这样就实现了“得到结果前一直输出0,得到结果后该结果稳定输出”的效果。

    计算逻辑子电路的设计如下图所示。 首先观察中部两个寄存器的设计,回顾在前面的分析中我们得到的fib(n)算法,其中循环体里用到了两个变量prev和now,分别表示数列当前值和上一个值,初始时要对两个值赋初值,分别表示fib(-1) = 1, fib(0) = 0,随后开始的循环中now = now + prev; prev = now - prev。

    在这里插入图片描述

    根据这样的思路,我们使用两个寄存器来分别存储prev和now的值,在每一次循环中,now寄存器应当被更新为now + prev,那么只需将两个寄存器输出端口求和接入now寄存器即可。而对于prev寄存器,只需要直接接入now的输出值即可,而不是计算now - prev,这是由于我们书写在C语言中的算法,其语句是顺序执行的,在now被更新后就必须使用now - prev的值作为新的prev值,而在此处prev和now是同时更新的。换句话说,正确的算法是prev’ = now’ - prev = now,因此直接接入now的输出即可。根据这样的特点我们也会发现,原本每个循环需要执行两次的循环体,在电路实现中只需要一个时钟周期就可以完成。

    真正的计算很简单,但还有一个棘手的问题,就是如何优雅地为寄存器赋初值。考虑到电路的应用性,我们不应当每次手动为寄存器赋值为1,因此需要考虑设计一种机制,让第一个时钟周期给prev寄存器赋值为1,now寄存器赋值为0,而在后面的时钟周期根据上面一段叙述的逻辑改变两者的值。在此处我采用的解决办法是使用一个1位计数器,并设置计数器达到上限后"stay at value",保持最大值不变(具体设置方法如下图),这样一来该计数器只有第一个时钟周期输出0,后面一直输出1,而此时将其输出作为选择信号接入多路选择器,就实现了prev寄存器第一个周期赋初值,后面的周期赋值为now。而对于now寄存器,第一个周期now和prev之和本身就是0,无需特殊处理。最终电路始终输出now的值即可。

    在这里插入图片描述

    在顶层电路的描述中我们提到,为了保证得到正确答案后稳定输出,我们采用的方式是将计数逻辑输出信号接入计算逻辑,也就是左下方的freeze信号,当该信号为1时,代表外部提醒:已经得到正确答案了,请冻结输出。此时将freeze信号取反接入两个寄存器的enable端即可,没有得到正确答案前寄存器正常工作,一旦得到冻结信号,寄存器停止工作,稳定输出当前值。

    分析过后我们考虑电路的计算特点:在第一个周期为寄存器赋初值,其后的每一个周期输出当前值,那么计算fib(n)就需要(n+1)个时钟周期,具体来说就是(n+1)个时钟上升沿,这条结论就指导了我们下一步设计计数逻辑,应当在(n+1)个时钟上升沿过后再发出输出指令。就像列车的目标是前进100公里,我们只有知道了发动机每小时让列车前进例如50公里,才能够设计控制系统,让列车在2小时之后停下。

    **计数逻辑子电路如下图所示。**有了上面计算逻辑的分析和构建,下面我们很容易设计计数逻辑:让该子电路在第(n+1)个时钟上升沿之前都输出0,代表着此时还未计算出结果,在第(n+1)个上升沿之后输出1,代表此时已得到正确结果,计算逻辑冻结并输出当前值。下面的电路中只需要使用counter,当计数器的值小于等于输入n时均输出0,随后输出1即可,注意此处的counter也需要设置到达最大值时"stay at value"。

    在这里插入图片描述

    至此整个电路已经构建完毕了。本设计更注重的是模块化的思路,而不在乎一两个元件的得失,例如我们完全可以将计数逻辑中counter的值作为一路信号接入计算逻辑,可以省去计算逻辑中赋初值所用的counter,但是本设计并没有这么做,而是让两个逻辑子电路尽可能地解耦。当然,这也只是笔者个人想法,应当有更精巧的思路值得大家探索。笔者认为,不管是软件还是硬件设计,有时候工程化模块化的设计布局,工整良好的可读性,可维护和可扩展性,是比小技巧更值得我们注意的关键点。


    斐波那契数列-矩阵乘法快速幂法

    黄小板同学暗中观察了公司负责人很久,觉得他搭建的电路性能实在太差,他提出只需要64个周期就能计算出32位无符号整数能表示的最大数位置上的斐波那契数的(最后32bit),在完成搭建这样的电路后,公司负责人五体投地,宣布给黄小板开出了东门烤串无限量供应的实习工资,从此黄小板每日吃串,终于吃成了黄老板…

    那么,这个电路是什么样子的呢?

    注意:这道题是一个对你的挑战,需要一定的算法和工程能力,请谨慎思考,大胆尝试!

    提交要求

    使用Logisim搭建一个根据输入序号x计算对应序号斐波那契数fib[x]的电路(输入序号0对应输出数0,输入序号1对应输出数1,输入序号2对应输出数1,以此类推)并提交。

    • 输入: N(32bit无符号数)
    • 输出: Nth(32bit无符号数,表示第N个斐波那契数)
    • 文件内模块名: main
    • 测试要求:在64个周期内计算出结果并稳定输出,在结果未计算出之前输出端口输出0。
    • HINT:矩阵乘法的快速幂

    观察此题,和上题一样都是计算斐波那契数,区别仅仅在于输入从3位变成了32位无符号整数,而时间要求仍然是64个时钟周期。我们试想,如果仍用上面的电路会如何?该电路计算fib(n)需要(n+1)个时钟周期,此时输入变为32位,那么最大输入则为232-1,需要232个时钟周期,这远远超过了64个。换言之,想要在64个时钟周期内计算出32位无符号整数输入,算法的复杂度应当为O(logn)级的。有没有可能实现这样的算法呢?

    题目的最后一句给出HINT:矩阵乘法的快速幂。小伙伴们立马懵逼了,矩阵乘法和斐波那契数有啥关系呀,还快速幂?这一概念我们拆开来看,先是矩阵乘法,后是快速幂

    斐波那契数与矩阵乘法

    斐波那契数的通项我们都知道, f i b ( n ) = f i b ( n − 1 ) + f i b ( n − 2 ) fib(n) = fib(n-1) + fib(n-2) fib(n)=fib(n1)+fib(n2) ,但现在我们多写一项,写成如下形式:
    f i b ( n ) = 1 ∗ f i b ( n − 1 ) + 1 ∗ f i b ( n − 2 ) f i b ( n − 1 ) = 1 ∗ f i b ( n − 1 ) + 0 ∗ f i b ( n − 2 ) fib(n) = 1 * fib(n-1) + 1 * fib(n-2)\\ fib(n-1) = 1 * fib(n-1) + 0 * fib(n-2) fib(n)=1fib(n1)+1fib(n2)fib(n1)=1fib(n1)+0fib(n2)

    为什么要多写一次没用的第二项呢?受上面一道题的启发,如果要将原本复杂度为O(2n)的算法,我们多使用了一个变量空间,同时更新fib(n)和fib(n-1),将上一个斐波那契数的值保留下来,是一种“空间换时间”的策略,那么此时我们所做的操作和上一道题是完全一样的,想要实现同时更新fib(n)和fib(n-1)。换言之,在“矩阵乘法”部分,我们相对上一题还没有实现任何优化,而仅仅是改换了计算形式。

    接着,根据我们刚刚学过的线性代数,引入矩阵乘法如下:

    ( 1 1 1 0 ) ∗ ( f i b ( n − 1 ) f i b ( n − 2 ) ) = ( 1 ∗ f i b ( n − 1 ) + 1 ∗ f i b ( n − 2 ) 1 ∗ f i b ( n − 1 ) + 0 ∗ f i b ( n − 2 ) ) = ( f i b ( n ) f i b ( n − 1 ) ) \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} * \begin{pmatrix} fib(n-1) \\ fib(n-2) \end{pmatrix} = \begin{pmatrix} 1 * fib(n-1) + 1 * fib(n-2) \\ 1 * fib(n-1) + 0 * fib(n-2) \end{pmatrix} = \begin{pmatrix} fib(n) \\ fib(n-1) \end{pmatrix} (1110)(fib(n1)fib(n2))=(1fib(n1)+1fib(n2)1fib(n1)+0fib(n2))=(fib(n)fib(n1))

    由此我们得到了全新的,一次更新两项的递推公式:

    ( 1 1 1 0 ) ∗ ( f i b ( n − 1 ) f i b ( n − 2 ) ) = ( f i b ( n ) f i b ( n − 1 ) ) \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} * \begin{pmatrix} fib(n-1) \\ fib(n-2) \end{pmatrix} = \begin{pmatrix} fib(n) \\ fib(n-1) \end{pmatrix} (1110)(fib(n1)fib(n2))=(fib(n)fib(n1))

    记 ( f i b ( n ) f i b ( n − 1 ) ) = F I B ( n ) , ( 1 1 1 0 ) = A , 记 \begin{pmatrix} fib(n) \\ fib(n-1) \end{pmatrix} = FIB(n), \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} = A, (fib(n)fib(n1))=FIB(n),(1110)=A,

    则 有   F I B ( n ) = A ∗ F I B ( n − 1 ) ,   其 中   F I B ( 0 ) = ( f i b ( 0 ) f i b ( − 1 ) ) = ( 0 1 ) 则有\space FIB(n) = A * FIB(n-1), \space 其中 \space FIB(0) = \begin{pmatrix} fib(0) \\ fib(-1) \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \end{pmatrix}  FIB(n)=AFIB(n1),  FIB(0)=(fib(0)fib(1))=(01)

    我们惊喜地发现,这一版本的递推公式不仅可以一次更新两项,还成功地将加法转化为乘法,将二阶递推式转化为一阶递推式,将加和关系转化为等比数列。又根据矩阵乘法满足交换律,该递推式容易得到通项如下:
    F I B ( n ) = A n ∗ F I B ( 0 ) = ( 1 1 1 0 ) n ∗ ( 0 1 ) FIB(n) = A^n * FIB(0) = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n * \begin{pmatrix} 0 \\ 1 \end{pmatrix} FIB(n)=AnFIB(0)=(1110)n(01)
    根据线性代数学过的知识,2*2的矩阵不管多少次乘方,其结果都还是2*2的矩阵,
    记   ( 1 1 1 0 ) n = ( a b c d ) ,   则   F I B ( n ) = ( f i b ( n ) f i b ( n − 1 ) ) = ( 1 1 1 0 ) n ∗ ( 0 1 ) = ( a ∗ 0 + b ∗ 1 c ∗ 0 + d ∗ 1 ) = ( b d ) 记 \space \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} a & b \\ c & d \end{pmatrix}, \space 则 \space FIB(n)= \begin{pmatrix} fib(n) \\ fib(n-1) \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n * \begin{pmatrix} 0 \\ 1 \end{pmatrix} = \begin{pmatrix} a * 0 + b * 1 \\ c * 0 + d * 1 \end{pmatrix} = \begin{pmatrix} b \\ d \end{pmatrix}  (1110)n=(acbd),  FIB(n)=(fib(n)fib(n1))=(1110)n(01)=(a0+b1c0+d1)=(bd)
    也就是说,我们所关心的fib(n),只是矩阵A的n次乘方,这一2*2矩阵的右上角的数。

    有了以上的分析,我们的目标很明确:计算A的n次乘方即可。但小伙伴们会发现,这一顿操作猛如虎,结果好像并没有改进算法的时间复杂度:矩阵的n次乘方还是要计算n次,毕竟Logisim并没有内置一次计算某数n次方的元件,更不用说矩阵还同时涉及乘法和加法。因此有了矩阵乘法的改写还远远不够,下面我们引入快速幂。

    快速幂

    先做一个引入的思考:假设每次只能做两个数之间加减乘除的运算,对于一个整数a,要求an,应当如何设计算法?

    最简单直观的算法:引入一个变量s赋初值为1,使用n次循环,每次为s乘上一个a,最终s = an,如下:

    int power(int a, int n) { // 计算 a^n 的值 
        int s = 1;
        for (int i = 0; i < n; i++)
            s *= a;
        return s;
    }
    

    这种算法的时间复杂度显然是O(n),有没有什么办法更快地计算a的n次幂呢?我们思考,假设我们已经计算得到了22=4,那么要求24就无需再花两次的时间计算23 = 22 * 2, 24 = 23 * 2,可以直接进行计算:24 = 22 * 22,只需要一次计算。更进一步地,我们会发现在每次只能做两个数的乘法的条件下,相乘的两数尽可能大,就可以尽可能快地接近待求结果。例如:
    a 17 = ( a 8 ∗ a 8 ) ∗ a = ( ( a 4 ∗ a 4 ) 2 ) ∗ a = ( ( a 2 ∗ a 2 ) 2 ) 2 ∗ a = ( ( ( a 2 ) 2 ) 2 ) 2 ∗ a a^{17} = (a^8 * a^8) * a = ((a^4 * a^4)^2)*a=((a^2*a^2)^2)^2*a=(((a^2)^2)^2)^2*a a17=(a8a8)a=((a4a4)2)a=((a2a2)2)2a=(((a2)2)2)2a
    将高次幂向下拆解的过程中,每次尽可能使用最大的两数平方来逼近高次幂,这样原本需要计算17次的a17现在只需要计算5次。在分析中我们还可以发现,当前幂次如果是偶数,就可以直接分解为两个数的平方:a2n = (an)2,需要一次计算;而如果当前幂次为奇数,则必须分解为两个数的平方再乘底数:a2n+1 = (an)2 * a,需要两次计算(一次算两数平方,一次算平方后再与底数相乘),根据这样的规律可以得到递推关系如下:

    p o w e r ( a , n ) = { p o w e r ( a , n / 2 ) ∗ p o w e r ( a , n / 2 ) n为偶数,且 n > 0 p o w e r ( a , [ n / 2 ] ) ∗ p o w e r ( a , [ n / 2 ] ) ∗ a n为奇数,[x]表示不超过x的最大整数 1 n = 0 power(a, n)= \begin{cases} power(a, n/2) * power(a, n/2)& \text{n为偶数,且 n > 0}\\ power(a, [n/2]) * power(a, [n/2]) * a& \text{n为奇数,[x]表示不超过x的最大整数}\\ 1 & \text{n = 0} \end{cases} power(a,n)=power(a,n/2)power(a,n/2)power(a,[n/2])power(a,[n/2])a1n为偶数,且 n > 0n为奇数,[x]表示不超过x的最大整数n = 0

    根据递推关系就可以直接写出如下的递归算法(逻辑与(n&1)用以快速判定奇偶,内联函数用以减少power()的调用,逻辑右移(n >> 1)用以快速实现n / 2取整):

    inline int sqr(int a) {
    	return a * a;
    }
    
    int power(int a, int n) {
    	if (n == 0) return 1;
    	return (n & 1) ? sqr(power(a, n >> 1)) * a : sqr(power(a, n >> 1));
    } 
    

    分析这一递归算法,每一递归实例唯一地调用下一个递归实例,每次调用时递归变量a不变,n减小为原来的一半,直到n = 0,因此递归深度应当为log2n;而在每个递归实例之中,n为偶数时需要1次计算(一次平方即可),n为奇数时需要2次计算(一次算平方,一次算平方的结果再乘底数a),因此整体的算法最多计算2log2n次(每次遇到的n都是奇数),最少计算log2n次(每次遇到的n都是偶数),时间复杂度O(logn),成功地实现了将O(n)降为O(logn)。这便是快速幂的思想,其本质是一种分治算法。

    这种快速幂算法能否移植到矩阵乘法上呢?也就是说,上文中的整数a能否替换为矩阵A呢?答案是肯定的,因为矩阵乘法满足结合律,并且同阶的方阵相乘后,其结果仍是与原来阶数相同的方阵。只需要将上面算法中的整数乘法全部替换为矩阵阵法,就得到了矩阵乘法的快速幂算法。

    快速幂的迭代表达

    当我们欣喜地发现已经找到O(logn)计算n次幂的算法后,现实的问题又摆在了眼前:硬件设计中我们无法使用递归。因此与上一题O(n)算法一样,我们需要将递归改写为迭代,通过寄存器的更新和外部计数控制来实现循环。如果你的数据结构功底扎实,将递归改写为迭代应该不是什么困难的事,你可以跳过本节的讲解。

    本题将递归改为迭代主要的难点在于,递归的过程中有针对当前递归值的判断:当前的n若为奇数,则取 ( a n / 2 ) 2 ∗ a (a^{n/2})^2*a (an/2)2a ,若为偶数则取 ( a n / 2 ) 2 (a^{n/2})^2 (an/2)2 ,在反向后自底向上迭代的过程中,无法确定当前的i是由奇数n还是偶数n递归而来。事实上大部分有难度的递归改迭代,其难点都在于反向后的计算逻辑和正向的有较大差别,需要分析计算的本质。

    针对递归中的奇偶分类判断,我们做如下的思考:先从极端情况考虑,什么样的数n每次递归实例都是偶数?什么样的数n每次递归实例都是奇数?第一个问题容易回答,如果n是2的幂,n = 2k,那么每次n >> 1之后仍旧是偶数,这意味着n的二进制展开除了最高位之外每一位都是0(这样右移一位之后最低位是0,仍是偶数);有了第一个问题,第二个问题也有了思路:如果每次n >> 1后都是奇数,这意味着n的二进制每一位都是1(这样右移一位之后最低位还是1,仍是奇数)。推广到一般情况:任意数n在递归过程中有多少次奇数多少次偶数?这取决于n的二进制展开中有几个1和几个0,1的个数就是递归实例为奇数的个数。

    有了这样的启发,我们可以重新思考快速幂的计算过程:

    a 13 = a ( 1101 ) b = a ( 1000 ) b + ( 0100 ) b + ( 0001 ) b = a 8 + 4 + 1 = a 8 ∗ a 4 ∗ a 1 = ( ( a 2 ) 2 ) 2 ∗ ( a 2 ) 2 ∗ a a^{13} = a^{(1101)_b} = a^{(1000)_b+(0100)_b+(0001)_b} = a^{8+4+1}\\ = a^8 * a^4 * a^1 = ((a^2)^2)^2 * (a^2)^2 * a a13=a(1101)b=a(1000)b+(0100)b+(0001)b=a8+4+1=a8a4a1=((a2)2)2(a2)2a
    在上面的例子中,假设幂次n本身是2的幂,其二进制展开除了最高位都是0,那么最终形式里不会有多余的乘号(只会是a的log2n次平方),计算log2n次平方即结束。该例子中的13次方,二进制展开后有3个1,最终形式里有3个乘号,多算3次,这与递归方法中的特点相吻合。重要的是,以这种形式展开后,计算过程是自底向上的:我们想象一个乘子m,其初始值为a,每次更新让m变为自身的平方(1次计算),同时扫描幂次n的二进制展开位,当扫描到当前位是1时,意味着“需要多一次乘法了”,就将当前乘子的值乘入最终结果(多1次计算)。仍旧分析上面的例子,初始乘子为a,扫描到13最低位是1,此时将乘子a乘入最终结果(最终形式中最后一项"a");第二轮乘子更新为自身的平方a2,扫描到13二进制展开次低位为0,无需将乘子乘入最终结果;第三轮乘子更新为自身的平方(a2)2,扫描到13二进制展开次高位为1,将乘子乘入最终结果(最终形式中的第二项"(a2)2");第四轮乘子更新为自身的平方((a2)2)2,扫描到13二进制展开最高位为1,将乘子乘入最终结果(最终形式中的第一项"((a2)2)2"),四轮结束后算法结束,得到了最终形式的正确结果。

    int power(int a, int n) {
    	int s = 1; // 存储最终结果 
    	while (n > 0) { // 依次扫描 n 的每个二进制位直到 n = 0 
    		if (n & 1) s *= a; // 如果当前二进制位为 1,则将乘子当前值乘入最终结果 
    		a *= a; // 乘子更新为自身的平方 
    		n >>= 1; // n 向右移位,扫描下一位 
    	}
    	return s;
    }
    

    Logisim电路实现

    有了上面大篇幅的算法理论分析,接下来就是在电路中实践了——将上面的C语言算法转化为Logisim电路。

    在这里插入图片描述

    如上图,本次工程延续了上一道题中,计算逻辑和计数逻辑解耦的基本结构,但由于本题设计矩阵乘法,存储和计算所用的元件比较多,根据模块化设计思想拆分出了较多的子电路,分别设计和调试以实现高效地开发。本节的讲解我们首先介绍作为支持功能的几个子电路。

    在这里插入图片描述

    上图展示了寄存器矩阵子电路。由于计算逻辑中矩阵乘法需要以整个矩阵的形式一次存储四个数,摆放过多的寄存器显得臃肿杂乱,因此将这部分单独拆开为子电路,其功能和结构非常明确,4个32位寄存器,其输入输出接口和传统寄存器完全一致。

    在这里插入图片描述

    上图展示了矩阵乘法子电路。在前文的算法分析中可以看出,我们需要在计算逻辑中作2*2矩阵的乘法,因此讲乘法过程单独拆开作为子电路。2*2矩阵乘法的计算也相对简单,套用公式用元件计算相应结果的输出即可。

    在这里插入图片描述

    上图展示了矩阵MUX子电路。该子电路的构建是由于计算逻辑中,我们会遇到需要选择两个矩阵中的一个进行运算的情况(例如当前n的末位为1时乘入乘子的值,为0则乘单位阵),因此为了方便一次选择一组四个数,我们将四个多路选择器组合单独设计为子电路,由一路1位信号选择两个矩阵的其中一个作为输出。

    在这里插入图片描述

    上图展示了矩阵初始值子电路和单位阵子电路。没错,我将常数单独封装为子电路应用于设计中,这可能并不符合某些设计原则,但可以在上层电路中节省空间,让电路更加简洁。矩阵初始值,也是乘方的底数矩阵;任意矩阵与单位阵作乘法后保持不变,用以实现“若当前n最低位为0则不将乘子乘入最终结果”。

    在这里插入图片描述

    上图展示了作为本项目核心的计算逻辑子电路。这一子电路中的核心在于中部靠右侧的两个寄存器矩阵:矩阵A和矩阵S。矩阵A作为乘子,第一个时钟周期存入初始值,后面每个时钟周期更新为自身的平方,因此其左侧使用一个矩阵MUX选择初值或自身平方,而自身平方通过矩阵乘法单元进行计算(初始值的存入和上一道题相同,使用了1位counter,并选择达到最大值时stay at value,不再赘述)。矩阵S作为存储最终结果的矩阵,其左侧在初始时存入单位阵(相当于int s = 1;),其后的每一个周期根据当前n的最低位进行判断,如果最低位为0则乘单位阵(不改变),如果为1则乘入当前乘子的值。有了这样的核心计算逻辑,电路可以不断计算出当前最终结果。

    和上题一样的点在于,我们仍旧使用计数逻辑来提示计算是否结束,是否可以输出计算结果,这一功能使用freeze信号来表示,最右侧的输出在计算得到正确结果之前一直输出0,freeze信号为1时输出当前结果。同样的为了调试方便增设了重置信号clr。而与上一题不同的是,n的最低位也由计数逻辑来计算生成并传入计算逻辑,以保证计算逻辑知晓当前的乘子是否应当乘入最终结果。

    在这里插入图片描述

    上图展示了计数逻辑子电路。本题的计数逻辑和上一题的计数逻辑有较大差别,因为本题只需要每次将n右移一位,当n等于0时即可宣告计算结束,无需等待固定个时钟周期。因此我们看到右上方使用寄存器来存储并更新n的值,初始存入输入值input,随后每个时钟周期将其右移一位,右下方的输出等待n为0时向外部报告计算结束。此外,计数逻辑需要向计算逻辑报告每一个时钟周期当前n的最低位,以便计算逻辑判断是否将乘子乘入最终结果,因此右侧中部多出一路n_low输出。

    在这里插入图片描述

    上图展示了本项目顶层的main电路,此时的顶层电路已经变得简单,计数逻辑向计算逻辑报告当前n的最低位n_low和是否计算完成的freeze,计算逻辑经过log2n个时钟周期计算出正确结果,再加上赋初值的一个周期,一共需要1+log2n个周期即可得到结果,32位输入最多需要33个周期,达到了题目要求的计算时间。


    后记:两个斐波那契数列问题是本课程Logisim部分难度巅峰,熟练掌握Logisim设计对后续的Logisim实现单周期CPU有极大的帮助,祝大家计组顺利渡劫!

    展开全文
  • 斐波那契数列

    2016-11-03 20:30:04
    你真的了解Fibonacci数列吗?
  • 第一次见到了线性递推数列的特征根解法。后来学习物理竞赛,学解微分方程,在线性常系数常微分方程的解法中了解到了特征根解法。学线代的时候又接触到了矩阵的特征值。在数列、微分方程、矩阵三个不同的领域中都见到...
  • java 动态规划策略原理及例题

    万次阅读 多人点赞 2017-08-22 19:44:32
    动态规划(dynamic programming)是运筹学的一个分支,是解决策过程(decision process)最优化的数学方法。在面试笔试中动态规划也是经常作为考题出现,其中较为简单的DP题目我们应该有百分之百的把握顺利解决才可以...
  • 如果大家还是能理解这个原理建议用演算纸自己计算一番,这里就过多赘述了。这种状态转移的思路就是DP的核心。 动态规划案例实现 1. 数塔取数问题: 一个高度为N的由正整数组成的三角形,从上走到下,经过的...
  • 通项公式 通项公式推导 此问题的线性递推数列属于二阶线性递推数列(n+2 -n = 2) 由上可知,斐波那契数列递推公式的特征方程为: 解得 则,, 斐波那契数列的性质 与黄金分割的关系 有趣的是,...
  • 斐波那契数列集锦

    千次阅读 2012-01-06 19:35:33
    不过显然有更好的解法——如果我们知道Fibonacci序列的通项公式 F(n) = (((1+Sqrt(5))/2)^n - ((1-Sqrt(5))/2)^n)*1/Sqrt(5) 不过组合数学里也有这一公式的推导方法 叫做“线性齐次递推式” 这个解法的核心...
  • 为什么80%的码农都做了架构师?>>> ...
  • 细说斐波那契数列的四种代码实现

    千次阅读 2020-07-25 21:37:35
    关于斐波那契数列的背景相信大家都有所耳闻,知道的可以去搜索一下兔子问题。在大多数的应用场合,没有人会...言归正传,该问题的四种代码实现分别为 递归法、迭代法、通项公式法和矩阵法,后两种方法对于线性代数基
  • 大数斐波那契数列+取余

    千次阅读 2015-09-24 00:24:54
    不过显然有更好的解法——如果我们知道Fibonacci序列的通项公式 F(n) = (((1+Sqrt(5))/2)^n - ((1-Sqrt(5))/2)^n)*1/Sqrt(5) 不过组合数学里也有这一公式的推导方法 叫做“线性齐次递推式” 这个解法...
  • f(n)={​f(n−1)+f(n−2)1​n>2n=1,2​ 但是也不是所有满足以上两个的问题都需要我们使用动态规划算法来求解,比如过如果一个数列通项公式是 f(n)=n+3f(n) = n + 3f(n)=n+3,那么在通项公式极易出或者说已知...
  • 在codewars上做了一道斐波那契数列求和的题目,做完之后做了一些简单的优化和用另一种方法实现。 题目 function fibonacci(n) { if(n==0 || n == 1) return n; return fibonacci(n-1) + fibonacci(n-2); } 以上...
  • 其前四位数: log10(x)=log10(1.234567)+6. 所以1.234567=10^(log10(x)-6). 1234 =(int) 10^(log10(x)-6)*1000. [6=length-4,length=(int)log10(x)+1]同时我们知道:对于小于10000的数字可以存储在数组中直接输出...
  • 奇妙的裴波那契数列和黄金分割

    千次阅读 2012-11-19 20:09:25
    “斐波那契数列”的发明者,是意大利数学家列昂纳多·斐波那契(Leonardo Fibonacci,生于公元1170年,卒于1240年。籍贯大概是比萨)。他被人称作“比萨的列昂纳多”。1202年,他撰写了《珠算原理》(Liber Abaci)一...
  • 斐波那契数列谈矩阵(1)

    千次阅读 2015-03-24 17:20:36
    不过显然有更好的解法——如果我们知道Fibonacci序列的通项公式 F(n) = (((1+Sqrt(5))/2)^n - ((1-Sqrt(5))/2)^n)*1/Sqrt(5) 不过组合数学里也有这一公式的推导方法 叫做“线性齐次递推式” 这个解法...
  • ByHolyPushBy\quad HolyPushByHolyPush 幸好聪明的txltxltxl告诉愚蠢的HPHPHP生成函数一般在数学中用的比较少,在信息竞赛里用的比较多,愚蠢的HPHPHP...已知正项数列{an},Sn\{a_n\},S_n{an​},Sn​表示该数列的前nn...
  • 计算机的工作原理

    万次阅读 多人点赞 2018-09-13 15:14:58
    计算机的工作原理 你需要有一定的电学知识,然后就可以去看模拟电路和数字电路相关的书籍了,了解完这两个东西后你就能基本明白计算机是怎么运作起来的了。这里只做简单回答。简单回答的意思是说,这个回答旨在让...
  • 不过显然有更好的解法——如果我们知道Fibonacci序列的通项公式 F(n) = (((1+Sqrt(5))/2)^n - ((1-Sqrt(5))/2)^n)*1/Sqrt(5) 不过组合数学里也有这一公式的推导方法 叫做“线性齐次递推式” 这个解法...
  • 计算机处理器基础原理笔记

    千次阅读 多人点赞 2019-10-24 20:47:59
    如下所示: 开关A一开始断开,B一开始合上,当A接时线圈产生磁性,合上的开关B就会被吸到线圈而断开,于是整个电路断开,电路断开导致电磁线圈产生磁场,那么开关B又回去合上,再次接电路,如此循环。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,502
精华内容 600
关键字:

不动点求数列通项原理