Concrete Mathematics 1 :Recurrent

2017-01-15 阅读量

第一章看着难度还是很友好的,算是在这个大坑中填了微小的一块。仔细看了推导,能领会作者的意思并对递归问题有了一些新的认识。

主要说了三个经典递归问题,河内塔和平面上的直线这两个问题相对简单明了。第三个问题是约瑟夫问题,就这个问题作者延伸的讲了几种递归思想,个人觉得很赞。

(BTW:其实写之前想参考一些别人写的笔记,发现能参考的东西太少了,很多是未填完的坑,实在觉得可惜,希望自己能坚持写完)

目录:   0.递归问题的两种常用解法:数学归纳法和成套方法   1.河内塔问题和平面上的直线问题的递归推导   2.约瑟夫问题的几种递归推导 (以下是正文)

数学归纳法

主要步骤:   0.对于实际问题,首先引入适当的记号。   1.对于n=1,命题成立;   2.假设命题对于n成立(n∈N+),证明在此命题对于n+1成立;

作者在这三个问题中都用到了数学归纳法,所用方法也是一样的:    首先研究小数据的情况;而对于一般情况,思考整个过程并推理出当前状态和前一个状态之间的关系,猜测递归式以及递归解;对于数学表达式求出封闭形式并用数学归纳法进行证明;

成套方法

第一次接触成套方法,体会就是:名字很奇怪,思想很奇妙233333333 :-D    作者在讲约瑟夫问题的推广时提到了这个方法,用以求出递归的封闭形式。    例如约瑟夫问题的推广:   存在数列的递归式是f(1)=a,f(2n)=2f(n)+b,f(2n+1)=2f(n)+c;   对于n取小范围的数据,我们可以知道f(n)可以表示成依赖于a,b,c的值。把f(n)对a,b,c,的依存关系分离开来看,我们可以把它表示成形式:f(n)=A(n)a+B(n)b+C(n)c;   对于f(n)而言,A(n),B(n),C(n)是固定不变的,那我们可以根据小范围数据或特殊值确定a,b,c,代入等式,可以求出A(n),B(n),C(n)的值或表达式;(a,b,c与A(n),B(n),C(n)根据情况而定谁先解出)   最后反求f(n);    个人感觉,成套方法是一种逆推的过程,为什么这样说呢?我们知道对于一个确定的数列f(n),常数a,b,c是固定的;而A(n),B(n),C(n)本身也是固定的(这些函数与a,b,c无关,也就不随数列而变化);那么,我们当然也可以根据a,b,c来确定f(n);

河内塔问题

河内塔问题(The Tower of Hanoi)这个问题描述倒是不陌生(当然因为英译缘故也有翻译成汉诺塔的)。最初我学习这个问题的时候,是在高中学习递归算法的时候接触到的,但是学习的角度有所差别。当时学习的重点是塔的移动途径问题,没有关注移动次数上的关系(在这里第一次思考这个问题的递归关系,算是对于熟悉的河内塔问题有了新的认识)。    简单的说一下问题描述:有3个柱子,n个圆盘,目的是要整个塔移到另一根柱子上,每次移动一个圆盘并且在移动过程中较大的圆盘不能放在较小圆盘上面。    猜想以及证明:   1.设T(n)为根据规则所需移动的最小次数。显然,n=0,T(0)=0;n=1,T(1)=1;接着考虑一般情况:移动过程中,首先需要把n-1个圆盘移动到另一个柱子上,那么就需要T(n-1)次移动;接着需要移动最大的圆盘,那么次数+1;最后,需要把n-1个圆盘移到最大的圆盘上,需要T(n-1)次;   2.根据特殊数据以及一般情况,猜测T(n)的递归式是:    T(0)=0,T(n)=2T(n-1)+1;   3.代入小范围数据,猜测递归解为:T(n)=2^n-1;   4.用数学归纳法进行证明:当n=1时,成立;当n>1时,假设等式成立,那么T(n+1)=2T(n)+1=2*(2^n-1)+1=2^(n+1)-1,对n+1也成立;即递归式对于n属于自然数均成立;     

平面上的直线问题

依旧是很熟悉的问题背景,问题描述:平面上n条直线所界定的区域的最大个数L(n)是多少?    我们知道,第n条直线最多与前面的直线产生n-1个交点,即最多产生n个区域。根据这个,我们很容易得到递归式:L(0)=1, L(1)=2, L(n)=L(n-1)+n;    对递归式进行迭代,得到:L(n)=L(0)+1+2+3+…+(n-1)+n = 1+n*(n+1)/2;    用数学归纳法进行证明即可;

(平面上的直线问题的变形也相类似,这里不说了)

约瑟夫问题

作者给的约瑟夫问题的解法就很有趣了。

简单的说一下问题描述:n个人围成一圈,标记1到n,每隔一个删去一个人(第一个人不删),直到只有一个人活着。

作者用了三种方式求解,在这里都提一下;

第一种方法和前面两个问题的套路一样,比较容易想到,同样用了数学归纳法:   1.设J(n)是幸存者的号码。当n=1时,显然J(1)=1;当n>1时,我们需要根据删人的过程找到当前状态与上一个状态之间的关系,那么我们简单的手动模拟一下一次完整的循环过程,发现对于奇数个(2n+1),一次完整的循环过程结束之后,标记为1的人在标记为2n的人后面被删掉,再次得到了与有n个人开始的状态,但是它们的标记号码加倍并增加了1,猜测人数为(2n+1)时的递归式为:J(2n+1)=2J(n)+1;同理,猜测人数为(2n)时的递归式为:J(2n)=2J(n)-1;   2.根据小范围数据进行列表,观察到数据略有些有趣(似乎是与2的幂有关),我们令n=2^m+l,那么根据这个表,猜测递归解为:J(2^m+l)=2l+1;   3.用数学归纳法进行证明即可;

作者提供的第二种方法很有意思,首先得先观察到解与2的幂有关,研究n和J(n)的以2为基数的表示。假设n的二进制展开式是 $n=(bmb{m-1}…b_1b_0)_2$,分别用这种方式表示n,l,2l,2l+1(由于我还不太懂如何显示LaTeX,这里就不一一列出来毒害审美了233333333),接着可以推出J(n)的二进制展开式,发现n的二进制展开式向左循环移动一位可以得到J(n)。

第三种方法是所谓的成套方法研究约瑟夫问题的推广。 引入常数α,β,γ,试图求出其封闭形式; 那么有递归式:J(1)=α,J(2n)=2J(n)+β,J(2n+1)=2J(n)+γ; 对于小范围数据列一般性表(这个表挺关键的,但是hexo插表太麻烦了…那就算了吧) 用成套方法的思想,我们设 J(n)=A(n)α+B(n)β+C(n)γ; 容易推测:A(n)=2^m,B(n)=2^m-1-l,C(n)=l,用数学归纳法证明即可; 确定了A(n),B(n),C(n),那么我们只要确定α,β,γ就可以确定数列J(n)。而α,β,γ可根据特殊值解出,即可求解J(n);

恩第一章的笔记就到这里,如有错误欢迎指正。