《程序員的數(shù)學(xué)》讀書筆記目錄
歸納
induction: 歸納
步驟
- 基底（base）- 證明P(0)成立
- 歸納（induction）- 假設(shè)P(k)成立邻遏，證明P(k+1)成立，其中k為不小于0的整數(shù)
循環(huán)不變式
遞歸
GNU is short for "GNU is Not UNIX"
發(fā)現(xiàn)遞歸的思路
從n層的整體問題中隱去部分問題
判斷剩余部分是否是n-1層的問題
遞推公式與解析式
遞推公式：利用自身推導(dǎo)自身的等式
解析式：只使用變量n表示自身的等式
在編程中虐骑，能使用解析式的盡量使用解析式准验，程序中的遞歸函數(shù)非常耗棧空間廷没，調(diào)用次數(shù)龐大糊饱，耗CPU，見斐波那契數(shù)列的例子颠黎。
漢諾塔（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} $$
菲波那切數(shù)列（fibonacci sequence）
$$
F(n)=\left{
\begin{aligned}
& 0 & n = 0 \
& 1 & n = 1 \
& F(n - 1) + F(n - 2) & n > 1
\end{aligned}
\right.
$$
斐波那契數(shù)列的代碼實現(xiàn)
遞歸實現(xiàn)
按照遞推公式
/**
* 原始實現(xiàn)
*
* @param n 第n個Fibonacci數(shù)另锋，從0開始
*/
public static long fibonacciRecursively(int n) {
if (n <= 1) {
return n;
} else {
return fibonacciRecursively(n - 1) + fibonacciRecursively(n - 2);
}
}
優(yōu)化一
/**
* 優(yōu)化一：減少一次遞歸調(diào)用
*
* @param n 第n個Fibonacci數(shù)，從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;
}
}
優(yōu)化二
/**
* 優(yōu)化二：使用迭代
*
* @param n 第n個Fibonacci數(shù)狭归，從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;
}
}
優(yōu)化三
/**
* 優(yōu)化三：使用迭代夭坪，每次迭代計算兩項，迭代總數(shù)少了一半
*
* @param n 第n個Fibonacci數(shù)过椎，從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）
組合數(shù)的遞歸定義
$$
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.
$$
組合數(shù)的數(shù)理意義
N個不同的元素台舱，其中一個元素a，從N中選K個元素的組合數(shù)等于包含a的組合數(shù)與不包含a的組合數(shù)之和
遞歸圖形--分形（fractale）
二叉樹
海龜作圖
- forward(n) // 前進n步并劃線
- backward(n) // 后腿n步不劃線
- left() // 逆時針轉(zhuǎn)動一定角度
- right() // 順時針轉(zhuǎn)動一定角度
謝爾平斯基三角形（sierpinski triangle）
顏色區(qū)分帕斯卡三角形的奇偶數(shù)得到謝爾平斯基三角形
遞歸與歸納的對比（recursion and induction）
遞歸與歸納潭流，方向不同竞惋，從一般性前提推出個別性結(jié)論的是遞歸思想，從個別性前提推出一般性結(jié)論的是歸納思想灰嫉。
演示代碼
// 歸納
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);
}
}
