当我为了好玩而看一堆算法时,我遇到了一个问题。我解决的算法(在 Java 中)要求我列出整数的所有分区。因此,4 的分区应接收以下打印输出:
4 , 3+1, 2+2, 2+1+1, 1+1+1+1
这是我在 Java 中的代码:
public static void partition(int n) {
partition(n, n, "");
}
public static void partition(int n, int max, String prefix) {
if (n == 0) {
StdOut.println(prefix);
return;
}
for (int i = Math.min(max, n); i >= 1; i--) {
partition(n-i, i, prefix + " " + i);
}
}
但是,当我尝试将我的 Java 代码转换为 Python 时,我收到"递归深度超过"错误。在这里:
def partition_rec(N):
def part(N,maximum = N, prefix = ""):
if(N==0):
print(prefix)
return
for i in range(N-1):
part(N-i,i,prefix + " " + str(i))
return part(N)
有人可以帮助我吗?谢谢!
你已经改变了你的 for 循环。在Java中,它以相反的方向运行。在 python 等效中,您正在从 0 to N - 2
运行它。
将 for 循环更改为: -
for i in range(min(maximum, N), 0, -1):
确切地说。因为,循环的形式n
1
。
-1
是步长值,它反向运行范围。
当我更改您的代码以匹配 Java 版本时,它对我有用:
def partition_rec(N):
def part(N,maximum = N, prefix = ""):
if(N==0):
print(prefix)
return
for i in range(min(maximum, N), 0, -1): # changed this line
part(N-i,i,prefix + " " + str(i))
return part(N)
partition_rec(4)