Найти - Пользователи
Полная версия: Проект Эйлера задача 18, оптимизация
Начало » Python для новичков » Проект Эйлера задача 18, оптимизация
1 2
Nikita_PyCharm
Решил задачу Эйлера # № 18 через brute force, теперь хочу её уменьшить рекурсией но не могу понять как это можно сделать!
Только затронул тему рекурсии.
 a = [95, 64]
a1 =[17, 47, 82]
a2 =[18, 35, 87, 10]
a3 =[20, 4, 82, 47, 65]
a4 =[19, 1, 23, 75, 3, 34]
a5 =[88, 2, 77, 73, 7, 63, 67]
a6 =[99, 65, 4, 28, 6, 16, 70, 92]
a7 =[41, 41, 26, 56, 83, 40, 80, 70, 33]
a8 =[41, 48, 72, 33, 47, 32, 37, 16, 94, 29]
a9  =[53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14]
a10 =[70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57]
a11 =[91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48]
a12 =[63, 66, 4, 68, 89, 53, 67, 30,73, 16, 69, 87, 40, 31]
a13 =[4, 62, 98, 27, 23, 9, 70, 98,73, 93, 38, 53, 60, 4, 23]
def pep():
    lis = []
    lis1 = []
    for i in range(0, 2):
        if len(lis) >= 1:
            lis.pop(0)
        lis.insert(0, a[i])
        for i1 in range(i, i + 2):
            if len(lis) >= 2:
                lis.pop(1)
            lis.insert(1, a1[i1])
            for i2 in range(i1, i1 + 2):
                if len(lis) >= 3:
                    lis.pop(2)
                lis.insert(2, a2[i2])
                for i3 in range(i2, i2 + 2):
                    if len(lis) >= 4:
                        lis.pop(3)
                    lis.insert(3, a3[i3])
                    for i4 in range(i3, i3 + 2):
                        if len(lis) >= 5:
                            lis.pop(4)
                        lis.insert(4, a4[i4])
                        for i5 in range(i4, i4 + 2):
                            if len(lis) >= 6:
                                lis.pop(5)
                            lis.insert(5, a5[i5])
                            for i6 in range(i5, i5 + 2):
                                if len(lis) >= 7:
                                    lis.pop(6)
                                lis.insert(6, a6[i6])
                                for i7 in range(i6, i6 + 2):
                                    if len(lis) >= 8:
                                        lis.pop(7)
                                    lis.insert(7, a7[i7])
                                    for i8 in range(i7, i7 + 2):
                                        if len(lis) >= 9:
                                            lis.pop(8)
                                        lis.insert(8, a8[i8])
                                        for i9 in range(i8, i8 + 2):
                                            if len(lis) >= 10:
                                                lis.pop(9)
                                            lis.insert(9, a9[i9])
                                            for i10 in range(i9, i9 + 2):
                                                if len(lis) >= 11:
                                                    lis.pop(10)
                                                lis.insert(10, a10[i10])
                                                for i11 in range(i10, i10 + 2):
                                                    if len(lis) >= 12:
                                                        lis.pop(11)
                                                    lis.insert(11, a11[i11])
                                                    for i12 in range(i11, i11 + 2):
                                                        if len(lis) >= 13:
                                                            lis.pop(12)
                                                        lis.insert(12, a12[i12])
                                                        for i13 in range(i12, i12 + 2):
                                                            if len(lis) >= 14:
                                                                lis.pop(13)
                                                            lis.insert(13, a13[i13])
                                                            if sum(lis) >= 998:
                                                                lis.insert(0, 75)
                                                                print(lis,"\nсреди всех вариантов, максимальный -",sum(lis))
                                                                lis.pop(0)
                                                            lis1.append(sum(lis))
    print(len(lis1), ' вариантов\n',"max - ",max(lis1) + 75, 'среди всех sum')
pep()
input()
Эта программа работает по типу рекурсии (вложенные циклы), но когда я пытаюсь взять минимум и запихнуть ёё в рекурсию нечего не выходит, есть предложения?
FishHook
Nikita_PyCharm
Только затронул тему рекурсии.
В каком конкретно месте вашей программы вы как вам кажется осуществляете рекурсивный вызов?
Nikita_PyCharm
FishHook
Я предполагаю
 for i in range(0, 2):
        if len(lis) >= 1:
            lis.pop(0)
        lis.insert(0, a[i])
только не могу добиться переноса данных как происходит между
 for i in range(0, 2):
        if len(lis) >= 1:
            lis.pop(0)
        lis.insert(0, a[i])
        for i1 in range(i, i + 2):
            if len(lis) >= 2:
                lis.pop(1)
            lis.insert(1, a1[i1])
Nikita_PyCharm
моя программа работает по перебору
 a =    [95, 64]
a1 =  [17, 47, 82]
a2 =[18, 35, 87, 10]
def pep():
    lis = []
    lis1 = []
    for i in range(0, 2):
        if len(lis) >= 1:
            lis.pop(0)
        lis.insert(0, a[i])
        for i1 in range(i, i + 2):
            if len(lis) >= 2:
                lis.pop(1)
            lis.insert(1, a1[i1])
            for i2 in range(i1, i1 + 2):
                if len(lis) >= 3:
                    lis.pop(2)
                lis.insert(2, a2[i2])
когда программа доходит до последнего for, в первый раз, в lis уже находится список
 [95,17,18]
, сумма этого списка добавляется в lis1 дальше в for i2 (заменяется lis(2)) на 35 и также сумма добавляется в lis1, мы выходим из for i2 и переходим for i1 (в нём мы заменяем lis(1)) на 47 и снова обращаемся к for i2 который также подменяет смежные значения a2, в итоге перебираются все 8 вариантов.
Вот как этот процес можно сделать одним циклом или рекурсией?
FishHook
Nikita_PyCharm
Я предполагаю
Вы молодец, но давайте вместе вслух прочитаем определение рекурсии

Реку́рсия — определение, описание, изображение какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя. Термин «рекурсия» используется в различных специальных областях знаний — от лингвистики до логики, но наиболее широкое применение находит в математике и информатике.
Рекурси́вная фу́нкция (от лат. recursio — возвращение) — это числовая функция числового аргумента, которая в своей записи содержит себя же.

Теперь покажите мне функцию, которая вызывает саму себя
FishHook
Nikita_PyCharm
Читать до просветления
http://www.tvd-home.ru/recursion
Nikita_PyCharm
FishHook
Nikita_PyCharmЧитать до просветленияhttp://www.tvd-home.ru/recursion
Да я знаю что такое рекурсия, я не правильно выразился сказав “моя программа работает по типу рекурсии” я имел в виду что вложенный for в for очень похож по действию рекурсии только не проваливается сам в себя а как бы весь стек прописан циклами снаружи.
 def ar (a)
    a += 1
    return ar(a)
Nikita_PyCharm
я тут немного изменил подход вместо
 a =    [95, 64]
a1 =  [17, 47, 82]
a2 =[18, 35, 87, 10]
лучше использовать
 a = [
    [75],
    [95, 64],
    [17, 47, 82],
    [18, 35, 87, 10],
]
Nikita_PyCharm
Nikita_PyCharm
я тут немного изменил подход вместо
так можно будет идти по строкам используя увеличивающийся индекс
Nikita_PyCharm
FishHook
Nikita_PyCharmЧитать до просветленияhttp://www.tvd-home.ru/recursion
Хм возможно я рановато залез в рекурсию для начала почитаю руководство, Спасибо
This is a "lo-fi" version of our main content. To view the full version with more information, formatting and images, please click here.
Powered by DjangoBB