第 1 章 递归问题
# 第 1 章 递归问题
# 1.1 河内塔
公式提练
- 从递归式到封闭形式
封闭方程
- 方程是封闭的,是指不用它本身来定义
- 即不产生递归式
笔记
- 通过小的情形猜测递推式
- 证明递推式的正确性
- 从具体的问题出发进行证明
- 求出递推式的封闭形式,并给出证明
- 一般采用数学归纳法
# 1.2 平面上的直线
公式提练
指的是平面上的 条直线所界定的区域
折线问题可以转换为直线问题
- 每条折线相对于直线来说,损失两个区域
指的是平面上 条折线所界定的区域
# 1.3 约瑟夫问题
基本思路
- 从问题抽象到递归式,再用数学规纳法求得其封闭形式,再推广到二进制的形式
约瑟夫问题求解
- 转一圈会消掉所有的偶数,如果将剩余的人数重新从 1 开始编号,则下一圈仍然会去掉全部的偶数
- 可以猜出递归式的形式与奇偶有关
表示有 个人时,最后存活的人编号
- 递推式可以从很小的值的规律进行猜测
- 可以由较小值的情形进行猜测,从规律可以看出应按照 2 的幂进行分组
- 可以由较小值的情形进行猜测,从规律可以看出应按照 2 的幂进行分组
- 形式上理解
, 由 可以得出 - 当
时,当经过 次行型后,人数正数变为 ,此时的第一个人的编号为 ,这个人即为最后幸存下来的人
由约瑟夫问题的递推解联系到二进制的循环移位
应用循环移位的性质
- 不断的对函数
进行迭代,最终进入"不动点" - 可以从循环移位的性质理解,循环移位后,当首位为
时,其会被丢弃掉,最终剩下的各位全是 ,再循环移位,其值也不会发生变化 - 在不动点处有
, 的二进制全为
- 可以从循环移位的性质理解,循环移位后,当首位为
- 满足
的 值 - 即二进制数向左循环移位得到的效果与向右移动一位(减半)的效果相同
引用常数变量
- 先猜测解的通用形式,然后再由特例进行求解
最终推广
- 可以理解为变动基数的解
- 第 2 个公式相当于把
进行转换为 进制
笔记
- 注意数学归纳法要对某一个变量进行使用
- 从简单形式得出猜想,再用一些特殊的函数进行验证
编辑 (opens new window)