# Chap 1 递归与分治
# 整数划分
将正整数 表示成一系列正整数之和
正整数 的一个这种表示称为正整数 的一个划分，记
解：
在 的所有不同的划分中，将最大加数
有递归关系如下:
: 任何正整数只有一种划分形式 : 最大加数实际上不能大于 : : 不大于 的划分由 和 组成
有递归函数如下：
q(n,m)=\left\{ \begin{array}{rcl} 1 & & {n=1,m=1}\\ q(n,n) & & {n \lt m}\\ 1+ q(n,n-1) & & {n = m}\\ q(n,m-1)+q(n-m,m) & & {n \gt m \gt 1} \end{array} \right.
# 汉诺塔
# 三柱汉诺塔
规则：每次移动一个圆盘，任意时刻不允许大圆盘压在小圆盘上
问题：从A到B的移动次数 + 移动过程
解答：
若
若
故递归函数如下：
T(n)=\left\{ \begin{array}{rcl} 1 & & {n=1}\\ 2 \times T(n-1)+1 & & {n \gt 1}\\ \end{array} \right.
故
Python 实现如下：
from dataclasses import dataclass
@dataclass
class Hanoi:
name: str
count: int
def move(n, A, B):
print('第{}个块从{}移到{}'.format(n, A.name, B.name))
def hanoi(n, A, B, C):
if n > 0:
hanoi(n-1, A, C, B)
move(n, A, B)
hanoi(n-1, C, B, A)
n = int(input('个数：'))
A = Hanoi('A', n)
B = Hanoi('B', 0)
C = Hanoi('C', 0)
hanoi(n, A, B, C)
# 四柱汉诺塔
算法：1941 Frame
1、将A柱上部分的n-r个碟子通过C柱和D柱移到B柱上 (
2、将A柱上剩余的n个碟子通过C柱移到D柱上 (
3、将B柱上的n-r个碟子通过A柱和C柱移到D柱上 (
递归方程如下：
2004年的一篇论文 (opens new window)证明了
# 多柱汉诺塔
留坑
# 大整数乘法
上式可知进行了 3次n/2位整数的乘法（AC，BD，(A-B)(D-C)），6次加减法 和 2次移位，故有递推式如下：
T(n)=\left\{ \begin{array}{rcl} O(1) & & {n=1}\\ 3T(n/2) + O(n) & & {n \gt 1}\\ \end{array} \right.
解得
# Strassen矩阵乘法
考虑n阶方阵的乘法运算
考虑 是 的幂，重写矩阵乘法为：\begin{bmatrix} C_{11} & C_{12} \\ C_{21} & C_{22} \end{bmatrix} = \begin{bmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{bmatrix} \quad \begin{bmatrix} B_{11} & B_{12} \\ B_{21} & B_{22} \end{bmatrix}
下面的传统分治策略使用了8次乘法4次加法
\begin{gathered} C_{11} = A_{11}B_{11}+A_{12}B_{21} \quad C_{12} = A_{11}B_{12}+A_{12}B_{22} \quad C_{21} = A_{21}B_{11}+A_{22}B_{21} \quad C_{22} = A_{21}B_{12}+A_{22}B_{22} \\ \\ T(n)=\left\{ \begin{array}{rcl} O(1) & & {n=2}\\ 8T(n/2) + O(n^2) & & {n \gt 2}\\ \end{array} \right.\end{gathered}
递归下去还是
Strassen提出了7次乘法的方法， 得到
目前最好的计算时间上界是
# 棋盘覆盖
在
考虑在中间放置一块L型牌，将一个
递归方程为：T(k)=\left\{
\begin{array}{rcl}
O(1) & & {k=0}\\
4T(k-1) + O(1) & & {k \gt 0}\\
\end{array} \right.，解得
# 线性时间选择
给定线性序集中 个元素和整数 ，
当 k = 1 或 k = n 时，即为找最大最小值，可以在
当
考虑一般情况，使用快排中的切分法，每次找正确的一半，也能在
def partition(a, start, end):
'使第j个位置拥有正确的数'
i = start
j = end + 1
x = a[start]
while True:
while a[++i] < x
while a[--j] > x
if i >= j:
break
a[i], a[j] = a[j], a[i]
a[start] = a[j]
a[j] = x
return j
def quicksort(a, start, end):
'先搞定第j个位置，再处理前面和后面的位置'
if start < end:
q = partition(a, start, end)
quicksort(a, start, q-1)
quicksort(a, q+1, end)
def randomizedPartition(a, start, end):
i = Random(start, end)
a[i], a[start] = a[start], a[i]
return partition(a, start, end)
def randomizedSelect(a, start, end, k):
if start == end:
return a[start]
i = randomizedPartition(a, start, end)
j = i - start + 1
if k <= j:
return randomizedSelect(a, start, i, k)
else:
return randomizedSelect(a, i+1, end, k)
# 计算第k小的数
randomizedSelect(a, 0, n-1, k)
# 最接近点对问题
设有 个点，若两两计算距离，则时间复杂度为
考虑 个点的横坐标中位数是
递归处理
若 的最近点对
由 的意义可知，
易得