java将整数分解为k个部分
我在用java编程,我需要制定一个算法。算法的要求是:
- 我们有3个整数变量
n
,m
,k
李> - 我们想把
n
分成k
个部分,这样k
个部分的总和 等于n
,每个部分都是介于1
和m
之间的整数李> - 我们需要所有可能的整数组合李>
例如,对于输入集:
n = 7; m = 3; k = 4
我们可以制定两种不同的组合:
7 = 2 + 2 + 2 + 1
及
7 = 3 + 2 + 1 + 1
谢谢大家
你可以在下面搜索框中键入要查询的问题!
我在用java编程,我需要制定一个算法。算法的要求是:
n
,m
,k
李>
n
分成k
个部分,这样k
个部分的总和
等于n
,每个部分都是介于1
和m
之间的整数李>
例如,对于输入集:
n = 7; m = 3; k = 4
我们可以制定两种不同的组合:
7 = 2 + 2 + 2 + 1
及
7 = 3 + 2 + 1 + 1
谢谢大家
# 1 楼答案
其思想是一种回溯算法方法(使用递归),您可以减少参数并获得部分解,然后检查是否有正确的解
# 2 楼答案
要获得“分割数”的计数,可以使用Dynamic Programming,它遵循递归公式:
用
D(n,k,m)
表示的答案是这样的划分的数量。复杂性是
O(n*k*m)
Java代码:
作为旁注,这类似于stars and bars问题,但这里的顺序并不重要,此外,您还有单元格中“星”数的上限
# 3 楼答案
我相信用递归可以很容易地做到这一点。首先检查是否可以对
n
进行除法,即n<=m*k && n>=k
,如果不能,则返回空数组如果它是可除的,则依次从范围
[1..m]
中选择m'
,并选择该值作为第一个数字,然后递归地获取参数n'=n-'m, m'=m', k'=k-1
的其余值,然后返回所有结果递归将仅对
n=0
和k=0
成功停止。时间复杂度应与输出的大小相同