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

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

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

В основном программа берет (в качестве ввода) строка, состоящей из целых чисел от 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)

Обратите внимание, что целые числа не меняют положение. Они все еще в том же порядке, что они были в исходной строке.

Теперь я знаю, как решить эту проблему, используя рекурсию. Но разочаровывающая часть состоит в том, что Мне не разрешено использовать рекурсию.

Это должно быть решено с использованием только «пока» и «для» петель. и очевидно, а также в порядке.

Ниже приведен некоторый код, который у меня есть до сих пор:

Мой код:

                                         #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 года

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

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

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

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