整数分拆
文章概述
本文介绍了整数分拆的问题，即给定正整数n，求不同数组(a1,a2,…,ak)的数目。在数论上，跟这些和式有关的问题称为整数拆分、整数剖分、整数分割、分割数或切割数。使用golang代码实现求解，代码为：func main() { n := 20 for i := 0; i <= n; i++ { fmt.Print(q(i, i), “,”) } } func q(n int, m int) int { if n == 0 || m == 0 { return 1 } if n == 1 || m == 1 { return 1 } if n < m { return q(n, n) } if n == m { return q(n, m-1) + 1 } if n > m { return q(n, m-1) + q(n-m, m) } return 0 } 输出结果为：1,1,2,3,5,7,11,15,22,30,42,56,77,101,135,176,231,297,385,490,627。
关键要点
1.整数分拆是指将一个正整数表示为多个正整数之和的方式。
2.给定正整数n，需要求出不同的数组(a1,a2,…,ak)，其中a1+a2+…+ak=n的数目。
3.使用递归函数q(n,m)来计算从n个物品中选取m个物品的不同组合数。
4.在程序中调用q函数并输出结果即可得到不同数组的数量。
5.这种算法常用于数学中的整数分拆问题，也可以应用于计算机科学中的搜索和排序算法等领域。
介绍
一个正整数可以写成一些正整数的和。在数论上，跟这些和式有关的问题称为整数拆分、整数剖分、整数分割、分割数或切割数（英语：Integer partition）。 其中最常见的问题就是给定正整数n，求不同数组(a1,a2,…,ak)的数目。
整数分割，以5为例：
5=5 //0行
5=4+1 //1行
5=3+1+1 //2行
5=2+1+1+1 //3行
5=1+1+1+1+1 //4行
5=2+2+1 //5行
5=2+3 //6行
定义p(0)=1 p(5)=7。
使用golang代码实现求解：
func main() {
n := 20
for i := 0; i <= n; i++ {
fmt.Print(q(i, i), ",")
}
}
func q(n int, m int) int {
if n == 0 || m == 0 {
return 1
}
if n == 1 || m == 1 {
return 1
}
if n < m {
return q(n, n)
}
if n == m {
return q(n, m-1) + 1
}
if n > m {
return q(n, m-1) + q(n-m, m)
}
return 0
}
输出结果：
1,1,2,3,5,7,11,15,22,30,42,56,77,101,135,176,231,297,385,490,627,
对照A000041