Python中如何实现整数划分？

本文共计327个文字，预计阅读时间需要2分钟。

题目描述：将正整数n表示成一系列正整数的和，其中每个正整数都不超过n，k个正整数。正整数n的这种表示称为正整数n的划分。输入：一个正整数n。输出：n的不同划分个数以及n的划分。

问题阐述

将正整数n表示成一系列正整数之和：n=n1+n2+…+nk，

其中n1≥n2≥…≥nk≥1，k≥1。

正整数n的这种表示称为正整数n的划分。

输入：一个正整数n

输出：n不同划分个数以及n的划分结果。

问题实例

例如正整数6有如下11种不同的划分：

6；

5+1；

4+2，4+1+1；

3+3，3+2+1，3+1+1+1；

2+2+2，2+2+1+1，2+1+1+1+1；

1+1+1+1+1+1

def division(n, m, string):
if n == 0:
#print(string+'hah')
i= len(string)-1
j=' '
s=list(string)
s[i]=j
s1=''.join(s)
print(s1)
else:
if m > 1:
division(n, m - 1, string)
if m <= n:
division(n - m, m, str(m) + '+' + string)

n = int(input("输入一个整数："))
m = n#m为最大分解因子
print('%d的划分如下：'%n)
division(n, m, '')

结果如下

输入一个整数：5

5的划分如下：

1+1+1+1+1

1+1+1+2

1+2+2

1+1+3

2+3

1+4

5