如何在不使用递归的情况下求一组整数的和
这是我在Stack Overflow上的第一篇帖子，希望能写得不错。
这是我自己想出来的问题，现在有点不好意思说，但它真的让我很困扰。请注意，这不是作业，发誓不是。
基本上，这个程序的输入是一个由0到9的数字组成的字符串。
strInput = '2415043'
然后你需要把这个数字字符串分成更小的数字组，直到这些组的和等于一个预先设定的总数。在上面的例子中，目标是289。
iTarget = 289
对于这个例子，有两个正确的答案（但很可能只会显示一个，因为程序在达到目标后就会停止）：
Answer 1 = 241, 5, 043 (241 + 5 + 043 = 289)
答案2 = 241, 5, 0, 43 (241 + 5 + 0 + 43 = 289)
注意，数字的位置不变。它们仍然保持在原始字符串中的顺序。
现在，我知道如何用递归来解决这个问题。但让我感到沮丧的是我不允许使用递归。
这个问题需要用仅仅是'while'和'for'循环来解决。当然，列表和函数也是可以的。
下面是我目前写的一些代码：
我的代码：
#Pre-defined input values, for the sake of simplicity
lstInput = ['2','4','1','5','0','4','3'] #This is the kind of list the user will input
sJoinedList = "".join(lstInput) #sJoinedList = '2415043'
lstWorkingList = [] #All further calculuations are performed on lstWorkingList
lstWorkingList.append(sJoinedList) #lstWorkingList = ['2415043']
iTarget = 289 #Target is pre-defined
-
def SumAll(_lst): #Adds up all the elements in a list
iAnswer = 0 #E.g. lstEg = [2,41,82]
for r in _lst: # SumAll(lstEg) = 125
iAnswer += int(r)
return(iAnswer)
-
def AddComma(_lst):
#Adds 1 more comma to a list and resets all commas to start of list
#E.g. lstEg = [5,1001,300] (Note only 3 groups / 2 commas)
# AddComma(lstEg)
# [5,1,0,001300] (Now 4 groups / 3 commas)
iNoOfCommas = len(_lst) - 1 #Current number of commas in list
sResetString = "".join(_lst) #Make a string with all the elements in the list
lstTemporaryList = []
sTemp = ""
i = 0
while i < iNoOfCommas +1:
sTemp += sResetString[i]+',' #Add a comma after every element
i += 1
sTemp += sResetString[i:]
lstTemporaryList = sTemp.split(',') #Split sTemp into a list, using ',' as a separator
#Returns list in format ['2', '415043'] or ['2', '4', '15043']
return(lstTemporaryList)
return(iAnswer)
所以基本上，伪代码看起来会像这样：
伪代码：
while SumAll(lstWorkingList) != iTarget: #While Sum != 289
if(len(lstWorkingList[0]) == iMaxLength): #If max possible length of first element is reached
AddComma(lstWorkingList) #then add a new comma / group and
Reset(lstWorkingList) #reset all the commas to the beginning of the list to start again
else:
ShiftGroups() #Keep shifting the comma's until all possible combinations
#for this number of comma's have been tried
#Otherwise, Add another comma and repeat the whole process
呼！这真是说了不少。
我在纸上写下了程序将要遵循的过程，下面是预期的输出：
输出：
[2415043] #Element 0 has reached maximum size, so add another group
#AddComma()
#Reset()
[2, 415043] #ShiftGroups()
[24, 15043] #ShiftGroups()
[241, 5043] #ShiftGroups()
#...etc...etc...
[241504, 3] #Element 0 has reached maximum size, so add another group
#AddComma()
#Reset()
[2, 4, 15043] #ShiftGroups()
[2, 41, 5043] #ShiftGroups()
#etc...etc...
[2, 41504, 3] #Tricky part
现在这里是棘手的部分。在下一步中，第一个元素必须变成24，其他两个必须重置。
#Increase Element 0
#All other elements Reset()
[24, 1, 5043] #ShiftGroups()
[24, 15, 043] #ShiftGroups()
#...etc...etc
[24, 1504, 3]
#Increase Element 0
#All other elements Reset()
[241, 5, 043] #BINGO!!!!
好的。这就是程序逻辑的基本流程。现在我唯一需要弄清楚的是如何在不使用递归的情况下让它工作。
对于那些一直读到这里的人，我真心感谢你们，希望你们还有精力来帮助我解决这个问题。如果有什么不清楚的地方，请问我，我会详细解释（可能会详细到让人受不了 X-D）。
再次感谢！
编辑：2011年9月1日
感谢大家的回复和答案。它们都很好，绝对比我之前的思路更优雅。不过，我的学生从未使用过'import'或任何比列表更复杂的数据结构。不过，他们确实知道很多列表函数。
我还要指出，学生们在数学方面很有天赋，很多人参加过国际数学奥林匹克并获奖。所以这个作业并不超出他们的智力范围，可能只是超出了他们的Python知识。
昨晚我有了一个灵光一现的时刻。我还没有实现它，但会在这个周末进行，并在这里发布我的结果。可能会有点粗糙，但我觉得能完成任务。
抱歉花了这么久才回复，我的网络流量达到了上限，得等到1号才能重置。顺便说一句，祝大家春天快乐（对于南半球的朋友们）。
再次感谢你们的贡献。周末后我会选择最佳答案。
祝好！
3 个回答
为了更好地理解pst的提示，除了像递归那样使用调用栈，你还可以自己创建一个明确的栈，然后用它来实现递归算法，而不需要真正进行递归调用。具体的细节就留给你自己去练习啦；)
递归其实不是解决这个问题的最佳工具，itertools.product 更合适。
我搜索的方法是这样的：
想象一下搜索的范围是所有长度为 l 的二进制字符串，其中 l 是你的字符串长度减去一。
选取其中一个二进制字符串。
把这个二进制字符串里的数字写在你的搜索字符串的数字之间。
2 4 1 5 0 4 3
1 0 1 0 1 0
把 1 替换成逗号，把 0 替换成空白。
2,4 1,5 0,4 3
把所有的结果加起来。
2,4 1,5 0,4 3 = 136
结果是 289 吗？不是。那就换一个不同的二进制字符串再试。
2 4 1 5 0 4 3
1 0 1 0 1 1
你明白这个意思了吧。
接下来是代码！
import itertools
strInput = '2415043'
intInput = map(int,strInput)
correctOutput = 289
# Somewhat inelegant, but what the heck
JOIN = 0
COMMA = 1
for combo in itertools.product((JOIN, COMMA), repeat = len(strInput) - 1):
solution = []
# The first element is ALWAYS a new one.
for command, character in zip((COMMA,) + combo, intInput):
if command == JOIN:
# Append the new digit to the end of the most recent entry
newValue = (solution[-1] * 10) + character
solution[-1] = newValue
elif command == COMMA:
# Create a new entry
solution.append(character)
else:
# Should never happen
raise Exception("Invalid command code: " + command)
if sum(solution) == correctOutput:
print solution
编辑： agf 发布了另一个版本的代码。这个版本是把字符串连接起来，而不是我那种有点笨的方法：乘以 10 然后加上去。此外，它用真和假代替了我用的 JOIN 和 COMMA 常量。我觉得这两种方法都挺好，但当然我 有点偏心。:)
import itertools
strInput = '2415043'
correctOutput = 289
for combo in itertools.product((True, False), repeat = len(strInput) - 1):
solution = []
for command, character in zip((False,) + combo, strInput):
if command:
solution[-1] += character
else:
solution.append(character)
solution = [int(x) for x in solution]
if sum(solution) == correctOutput:
print solution
一个可以找到所有解决方案的程序可以用一种优雅的方式用函数式编程来表达。
分割
首先，写一个函数，把你的字符串以所有可能的方式进行分割。（下面的实现是基于这个链接的。）举个例子：
def partitions(iterable):
'Returns a list of all partitions of the parameter.'
from itertools import chain, combinations
s = iterable if hasattr(iterable, '__getslice__') else tuple(iterable)
n = len(s)
first, middle, last = [0], range(1, n), [n]
return [map(s.__getslice__, chain(first, div), chain(div, last))
for i in range(n) for div in combinations(middle, i)]
条件判断
接下来，你需要过滤这个列表，找出那些加起来等于你想要的值的分割。所以写一个小函数来测试一个分割是否满足这个条件：
def pred(target):
'Returns a function that returns True iff the numbers in the partition sum to iTarget.'
return lambda partition: target == sum(map(int, partition))
主程序
最后，写你的主程序：
strInput = '2415043'
iTarget = 289
# Run through the list of partitions and find partitions that satisfy pred
print filter(pred(iTarget), partitions(strInput))
注意，结果是在一行代码中计算出来的。
结果：[['241', '5', '043'], ['241', '5', '0', '43']]