# 归纳 & 递归
# 数学归纳法
# 利用数学归纳法证明的例子
# 证明求和公式
例子:
# 证明不等式
例子:
# 证明整除性结论
例子:
# 证明有关算法的结论
例子:
# 使用数学归纳法时犯的错误
例子:
# 运用数学归纳法证明的原则
# 强归纳法 & 良序性
# 强归纳法
例子:
# 利用强归纳法的例子
例子:
# 计算几何学中使用强归纳法
# 利用良序性证明
数学归纳法原理和强归纳法的有效性源于整数集合的基本公理『 良序性公理 』
良序性公理:任意一个非空的非负整数集合都有最小元素。
例子:
# 递归定义 & 结构归纳法
有时难以用明确的方式来定义一个对象。不过,用这个对象来定义它自身,这也许是容易的。这种过程称为递归。
# 递归地定义函数
为了定义以非负整数集合作为其定义域的函数,使用两个步骤:
例子:
例子:
例子:
# 递归地定义集合与结构
例子:
例子:
# 结构归纳法
例子:
例子:
# 递归算法
定义:
例子:
# 证明递归算法的正确性
“数学归纳法” 和 “强归纳法”,都可以证明一个递归算法的正确性,即可以证明算法对所有可能的输入值,都能产生所需要的输出。
例子:
# 递归与迭代
# 归并排序
例子:
# 程序正确性
# 程序验证
定义:
例子:
# 推理规则
一条有用的推理规则是通过把一个程序分成一系列子程序,然后证明每个子程序为正确的来证明这个程序为正确的。