个人主页：丷从心·
系列专栏：分治算法
学习指南：Python学习指南
问题描述
- 将正整数 n n n表示成一系列正整数之和， n = n 1 + n 2 + ⋯ + n k ( n 1 ≥ n 2 ≥ ⋯ ≥ n k ≥ 1 , k ≥ 1 ) n = n_{1} + n_{2} + \cdots + n_{k} (n_{1} \geq n_{2} \geq \cdots \geq n_{k} \geq 1 , k \geq 1) n=n1+n2+⋯+nk(n1≥n2≥⋯≥nk≥1,k≥1)
- 正整数 n n n的这种表示称为正整数 n n n的划分，正整数 n n n的不同的划分个数称为正整数 n n n的划分数，记为 p ( n ) p(n) p(n)
分治算法
- 在正整数 n n n的所有划分中，将最大加数 n 1 n_{1} n1不大于 m m m的划分个数记作 q ( n , m ) q(n , m) q(n,m)，可以建立 q ( n , m ) q(n , m) q(n,m)的递归关系
q ( n , m ) = { 1 , n = 1 , m = 1 q ( n , n ) , n < m q ( n , n − 1 ) + 1 , n = m q ( n , m − 1 ) + q ( n − m , m ) , n > m > 1 q(n , m) = \begin{cases} 1 , & n = 1 , m = 1 \\ q(n , n) , & n < m \\ q(n , n - 1) + 1 , & n = m \\ q(n , m - 1) + q(n - m , m) , & n > m > 1 \end{cases} q(n,m)=⎩ ⎨ ⎧1,q(n,n),q(n,n−1)+1,q(n,m−1)+q(n−m,m),n=1,m=1n<mn=mn>m>1
Python_40">Python实现
def integer_partition(n, m):if n < 1 or m < 1:return 0if n == 1 or m == 1:return 1if n < m:return integer_partition(n, n)if n == m:return integer_partition(n, m - 1) + 1return integer_partition(n, m - 1) + integer_partition(n - m, m)n = 6res = integer_partition(n, n)print(f'The number of partitions for {n} is: {res}')
The number of partitions for 6 is: 11
![[软件工具]批量根据文件名查找PDF文件复制到指定的地方，如何批量查找文件复制，多个文件一起查找复制](https://img-blog.csdnimg.cn/img_convert/692bd908f35322a9272095f8fd0df5d0.webp?x-oss-process=image/format,png)
