第 5 章 归纳与递归
# 第 5 章 归纳与递归
# 5.1 数学归纳法
# 5.1.1 引言
# 5.1.2 数学归纳法
数学归纳法的原理
- 为证明对所有的正整数
, 为真,需要以下两个步骤 - 基础步骤
- 证明命题
为真
- 证明命题
- 归纳步骤
- 证明对于每个正整数
来说,蕴含式 为真
- 证明对于每个正整数
- 基础步骤
推理规则可描述为
- 论域为正整数集合
# 5.1.3 为什么数学归纳法是有效的
#
正整数集合的良序性公理
- 正整数集合的任何非空子集都有都有最小元素
借助此公理,采用反证法即可证明数学归纳法中的推理规则
# 5.1.4 选择正确的基础步骤
提示
- 数学归纳法也可以证明对于
为真 - 需要在基础步骤中证明
为真
- 需要在基础步骤中证明
# 5.1.5 运用数学归纳法进行证明的原则
数学归纳法证明模板
- 将需要证明的命题表示为 "对于所有的
" 的形式, 是一个固定的整数 - 写下 "基础步骤",证明
为真 - 写出 "归纳步骤",明确列出归纳假设
- 形式是对于任意的整数
,假设 为真
- 形式是对于任意的整数
- 列出归纳假设的前提下,需要证明的命题,即写出
的含义 - 利用
证明 - 在归纳步骤明确结论,如写下 "至此归纳步骤完成"
- 在基础步骤和归纳步骤之后明确结论,即 "依据数字归纳法,对于所有的
, 为真"
# 5.1.6 数学归纳法的优点和缺点
笔记
- 数学归纳法的优点是它能用于证明已经构造好的猜想
- 缺点是不能用于发现新的定理
- 不能提供关于定理为什么是正确的启示
# 5.1.7 利用数学归纳法进行证明的例子
实例
- P285 关于调和数的一个不等式
- P287 证明有关集合的结论
- P288 证明有关算法的结论
- 关于贪婪算法的证明
# 5.1.8 使用数学归纳法时犯的错误
提示
- 使用数学归纳法时,基础步骤和归纳步骤都必须是正确的
- 归纳步骤中一定要注意
的取值范围
- 归纳步骤中一定要注意
# 5.2 强归纳法与良序性
# 5.2.1 引言
# 5.2.2 强归纳法
强归纳法的基本步骤
- 为证明对所有的正整数
, 为真,需要以下两个步骤 - 基础步骤
- 证明命题
为真
- 证明命题
- 归纳步骤
- 证明对于每个正整数
来说,蕴含式 为真
- 证明对于每个正整数
- 基础步骤
强归纳法有时也称为数学归纳法第二原理,或称完全归纳法
- 数学归纳法有时称为不完全归纳法
# 5.2.3 利用强归纳法证明的例子
一般情况下,应该尽量采用强归纳法进行证明
数学归纳法的推广
- 为证明对所有的整数
, 为真,需要以下两个步骤 - 基础步骤
- 证明命题
为真
- 证明命题
- 归纳步骤
- 证明对于所有的
的整数而言,蕴含式 为真
- 证明对于所有的
- 基础步骤
证明实例
- 算术基本定理 的存在性证明
# 5.2.4 计算几何学中使用强归纳法
相关定义
- 多边形
- 顶点
- 简单多边形
- 两边不相邻的边没有交点
- 内部区域和外部区域
- 凸多边形
- 连接多边形内部任意两点的线段都整个包含在该多边形内
- 内部对角线
- 对角线除了两个端点外,整个包含在多边形内部
- 三角形化
- 通过加入不相交的对角线把书一个简单多边形划分成多个三角形
#
#
引理521
每个简单的至少四边的多边形都存在一条内部对角线
# 5.2.5 利用良序性证明
笔记
- 良序性原理可以用来证明整除算法的存在性
# 5.3 递归定义与结构归纳法
# 5.3.1 引言
有时难以用明确的方式来定义一个对象,不过,可以很方便的用这个对象定义它自身
- 可以用递归来定义序列、函数和集合
- 当通过规定如何从前面的各项求出序列各项来递归地定义序列时,可以用结构归纳法来证明关于这个序列的有关性质
# 5.3.2 递归地定义函数
定义以非负整数集合作为其定义域的函数
- 基础步骤
- 规定这个函数在 0 处的值
- 递归步骤
- 给出从较小的整数处的值来求出当前值的规则
递归定义的函数是良定义的
- 对于每一个正整数,函数对应的取值都是清楚定义的
- 是数学归纳法原理的一个结果
#
斐波那契数列的性质
- 当
时,有 ,其中
证明
- 采用强归纳法,借助斐波那契数列的性质和
进行证明
#
拉梅定理
- 设
和 是满足 的正整数。则欧几里得算法为了求出 而使用的除法次数小于或等于 的十进制位数的 倍 应用
- 证明了欧几里得算法用
次除法来求出正整数 , 的最大公因子
- 证明了欧几里得算法用
# 5.3.3 递归地定义集合与结构
递归定义默认包含一条排斥规则
- 递归定义的集合仅仅包含基础步骤所规定的以及递归步骤的应用所生成的那些元素
字符串集合的定义
- 字母表
上的字符串集合 递归地定义为: - 基础步骤:
( 为空串) - 递归步骤:若
且 ,则
- 基础步骤:
字符串的连接运算
- 可以如下定义两个字符串的连接运算,用
表示 - 基础步骤
- 若
,则 ,其中 是空串
- 若
- 递归步骤
- 若
且 以及 ,则
- 若
- 基础步骤
提示
- 求解
时,可以令 , ,然后反复的应用递归步骤,直至 为 ,然后再应用基础步骤即可得出结果
字符串长度的定义
定义各种类型的合式公式
- 复合命题的合式公式
- 运算符与运算数的合式公式
递归地定义树
根树
- 基础步骤
- 单个顶点
是根树
- 单个顶点
- 递归步骤
- 假设
是不相交的根树,分别带有树根 。则如下形成的图也是根树 - 树根
不属于根树 中的任何一个 - 从
到顶点 中的每个都加入一条边
- 树根
- 假设
图示
- 基础步骤
扩展二叉树
- 基础步骤
- 空集是扩展二叉树
- 基础步骤
满二叉树
- 基础步骤
- 存在一个只含有单个顶点的满二叉树
- 基础步骤
# 5.3.4 结构归纳法
目的是为了证明关于递归构造的集合中的所有元素具有一个特殊的性质
结构归纳法证明
- 基础步骤
- 证明对于递归定义的基础步骤所规定的属于该集合的所有元素来说,性质成立
- 递归步骤
- 证明如果对于定义的递归步骤中用来构造新元素的每个元素来说, 性质成立; 则对于这些新元素来说性质也成立
结构归纳法的有效性来自于非负整数的数学归纳法原理
#
递归的定义满二叉树的高度
- 基础步骤
- 只含有树根
的满二叉树 的高度是
- 只含有树根
- 递归步骤
- 如果
都是满二叉树,则满二叉树 有高度
- 如果
#
定理2
- 如果
是满二叉树,则 为满二叉树 的顶点个数
可以通过结构归纳法进行证明
# 5.3.5 广义归纳法
可以扩展数学归纳法来证明关于除整数集合以外的其他具有良序性的集合的结果
- 如具有字典序的良序性集合
# 5.4 递归算法
有时可以把带有具体输入的一组问题的解归约带带更小的一组输入的相同问题的解,直到把问题归约到解是已知的某个初始情形为止
递归算法的定义
- 若一个算法通过把问题归约到带更小输入的相同问题的实例来解决原来的问题,则这个算法是递归的
实例
- 计算
- 计算
- 计算两个数的最大公因子
- 借助
时, 来进行求解
- 借助
- 模指数算法
- 根据指数的奇偶性,设计不同的算法
# 5.4.2 证明递归算法的正确性
借助强归纳法,即可证明递归算法的正确性
# 5.4.3 递归与迭代
迭代的定义
- 从函数在较小整数点处的值开始,连续地应用递归定义一个一个地求得函数在较大整数点处的函数值,这样的过程称为迭代
递归算法可能比迭代算法需要更多的计算量
- 如斐波那契算法
- 采用递归算法计算
需要 次加法 - 采用迭代算法,当
时,需要 次加法
- 采用递归算法计算
# 5.4.4 归并排序
先拆分, 再合并
示例图
#
定理 541
- 对
个元素进行归并排序所需要比较次数为
证明
- 见第 11 章
# 5.5 程序正确性
# 5.5.1 引言
# 5.5.2 程序验证
若对每个可能的输入来说,程序都能产生正确的输出, 则说明这个程序是正确的
- 一个程序的正确性证明包括两个部分
- 若程序终止, 则获得正确的答案
- 证明这一部分证明了程序的部分正确性
- 程序总是终止
- 若程序终止, 则获得正确的答案
霍尔三元组
- 若当对一个程序或程序段
的输入值来说初始断言 为真时, 就有对 的输出值来说终结断言 为真, 则说 是相对于 和 部分正确的, 记为 即被称为霍尔三元组 - 初始断言
- 规定程序输入值所具有的性质的命题
- 终结断言
- 规定若程序正确地工作则输出值所应当具有的性质的命题
# 5.5.3
合成规则
- 通过把一个程序分成一系列子程序, 然后证明每个子程序为正确的来证明这个程序是正确的
# 5.5.4 条件语句
推理规则
if-then
if-then-else
# 5.5.5 循环不变量
循环不变量的定义
对于下述程序片段
while condition S
1
2每次执行
时都保持为真的断言, 称为循环不变量 - 即在程序的每次执行期间都保持为真的性质
推理规则
编辑 (opens new window)