《程序员的数学》读书笔记目录
归纳
induction: 归纳
步骤
- 基底（base）- 证明P(0)成立
- 归纳（induction）- 假设P(k)成立，证明P(k+1)成立，其中k为不小于0的整数
循环不变式
递归
GNU is short for "GNU is Not UNIX"
发现递归的思路
从n层的整体问题中隐去部分问题
判断剩余部分是否是n-1层的问题
递推公式与解析式
递推公式：利用自身推导自身的等式
解析式：只使用变量n表示自身的等式
在编程中，能使用解析式的尽量使用解析式，程序中的递归函数非常耗栈空间，调用次数庞大，耗CPU，见斐波那契数列的例子。
汉诺塔（hanoi tower）
递推公式（recursion relation）
$$
H(n)=\left{
\begin{aligned}
& 0 & n = 0 \
& H(n-1) + 1 + H(n-1) & n > 0
\end{aligned}
\right.
$$
解析式
$$ H(n) = 2^n - 1 $$
演示代码
#include <stdio.h>
#include <stdlib.h>
void hanoi(int n, char x, char y, char z);
void hanoi(int n, char x, char y, char z) {
if (0 == n) {
// do nothing
} else {
hanoi(n - 1, x, z, y);
printf("%c --> %c, ", x, y);
hanoi(n - 1, z, y, x);
}
}
int main(void) {
hanoi(6, 'A', 'B', 'C');
}
阶乘（factorial）
递推公式
$$
n!=\left{
\begin{aligned}
& 1 & n = 0 \
& n × (n-1)! & n > 0
\end{aligned}
\right.
$$
求和公式
递推公式
$$
SUM(n)=\left{
\begin{aligned}
& 0 & n = 0 \
& n + SUM(n - 1) & n > 0
\end{aligned}
\right.
$$
解析式
$$ SUM(n) = \dfrac{n × (n + 1)}{2} $$
菲波那切数列（fibonacci sequence）
$$
F(n)=\left{
\begin{aligned}
& 0 & n = 0 \
& 1 & n = 1 \
& F(n - 1) + F(n - 2) & n > 1
\end{aligned}
\right.
$$
斐波那契数列的代码实现
递归实现
按照递推公式
/**
* 原始实现
*
* @param n 第n个Fibonacci数，从0开始
*/
public static long fibonacciRecursively(int n) {
if (n <= 1) {
return n;
} else {
return fibonacciRecursively(n - 1) + fibonacciRecursively(n - 2);
}
}
优化一
/**
* 优化一：减少一次递归调用
*
* @param n 第n个Fibonacci数，从0开始
*/
public static long fibonacciRecursivelyWithLoop(int n) {
if (n <= 1) {
return n;
} else {
long result = 1;
do {
result += fibonacciRecursivelyWithLoop(n - 2);
n--;
} while(n > 1);
return result;
}
}
优化二
/**
* 优化二：使用迭代
*
* @param n 第n个Fibonacci数，从0开始
*/
public static long fibonacciIteratively(int n) {
if (n <= 1) {
return n;
} else {
long a = 0, b = 1;
do {
long tmp = b;
b += a;
a = tmp;
} while(--n > 1);
return b;
}
}
优化三
/**
* 优化三：使用迭代，每次迭代计算两项，迭代总数少了一半
*
* @param n 第n个Fibonacci数，从0开始
*/
public static long fibonacciIterativelyFaster(int n) {
if (n <= 1) {
return n;
} else {
long a, b = 1;
n--;
a = n & 1;
n /= 2;
while(n-- > 0) {
a += b;
b += a;
}
return b;
}
}
帕斯卡三角形（Pascal's Triangle）
组合数的递归定义
$$
C^K_N=\left{
\begin{aligned}
& 1 & N = 0 或 N = K \
& C^{K - 1}{N - 1} + C^K{N - 1} & K > 0 且 K < N
\end{aligned}
\right.
$$
组合数的数理意义
N个不同的元素，其中一个元素a，从N中选K个元素的组合数等于包含a的组合数与不包含a的组合数之和
递归图形--分形（fractale）
二叉树
海龟作图
- forward(n) // 前进n步并划线
- backward(n) // 后腿n步不划线
- left() // 逆时针转动一定角度
- right() // 顺时针转动一定角度
谢尔平斯基三角形（sierpinski triangle）
颜色区分帕斯卡三角形的奇偶数得到谢尔平斯基三角形
递归与归纳的对比（recursion and induction）
递归与归纳，方向不同，从一般性前提推出个别性结论的是递归思想，从个别性前提推出一般性结论的是归纳思想。
演示代码
// 归纳
void prove(int n) {
int k;
// step 1 start
k = 0;
printf("P(%d)成立\n", k);
// step 1 end
while (k < n) {
// step 2 start
printf("P(%d)成立，则P(%d)也成立\n", k, k + 1);
// step 2 end
k++;
}
printf("证明完成");
}
// 递归
void prove(int n) {
if (0 == n) {
printf("步骤1 --> P(%d)成立。\n", n);
} else {
prove(n - 1);
printf("步骤2 --> 若P(%d)成立，则P(%d)也成立。\n", n - 1, n);
printf("因此，P(%d)成立。\n", n);
}
}
