python - 如何在不使用递归的情况下确定一组整数的总和

Question

这是我在 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 日

感谢大家的回复和回答。它们都非常好，而且绝对比我走的路线更优雅。但是，我的学生从未使用过“导入”或任何比列表更高级的数据结构。但是，他们确实知道不少列表函数。我还应该指出，学生们在数学方面很有天赋，他们中的许多人都参加过国际数学奥林匹克竞赛并名列前茅。所以这个赋值不超出范围他们的智慧，也许只是超出了他们的 python 知识范围。

昨晚我有一个 Eureka !片刻。我还没有实现它，但会在周末实现，然后在此处发布我的结果。它可能有些粗糙，但我认为它可以完成工作。

抱歉，我花了这么长时间才回复，我的互联网已达到上限，我不得不等到 1 号才能重置。这提醒了我，大家 Spring 快乐(南半球的你们)。

再次感谢您的贡献。我会在周末后选择最佳答案。问候!

Answer 1

一个找到所有解的程序可以优雅地表达在functional中。风格。

分区

首先，编写一个函数以各种可能的方式对字符串进行分区。 (以下实现基于 http://code.activestate.com/recipes/576795/ 。)示例:

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']]