Как определить сумму группы целых чисел без использования рекурсии

Это мой первый пост на 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).

Спасибо еще раз!

Изменение: 1 сентября 2011 г.

Спасибо всем за отклик и за ваши ответы. Все они очень хороши и определенно более элегантны, чем маршрут, которым я следовал. Однако мои студенты никогда не работали с «импортом» или какими-либо более сложными структурами данных, чем списки. Однако они знают довольно много функций списка. Я также должен отметить, что студенты достаточно одарены математически, многие из них участвовали в международных математических олимпиадах и занимали призовые места. Так что это задание не выходит за рамки их интеллекта, возможно, только за пределы их знаний о питоне.

Прошлой ночью у меня была Эврика! момент. Я еще не реализовал это, но сделаю это в течение выходных, а затем опубликую свои результаты здесь. Это может быть несколько грубо, но я думаю, что это сделает работу.

Извините, что мне потребовалось так много времени, чтобы ответить, мой лимит интернета был достигнут, и мне пришлось ждать до 1-го числа, чтобы его сбросить. Что напоминает мне, всем счастливой весны (для тех из вас, кто живет в Южном полушарии).

Еще раз спасибо за ваш вклад. Я выберу лучший ответ после выходных. С Уважением!