Ctrl →

Nikita_PyCharm · Июль 30, 2020 12:21:10

Решил задачу Эйлера # № 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()

Эта программа работает по типу рекурсии (вложенные циклы), но когда я пытаюсь взять минимум и запихнуть ёё в рекурсию нечего не выходит, есть предложения?

Прикреплённый файлы:
tesk_18.py (4,2 KБ)

FishHook · Июль 30, 2020 13:45:03

Nikita_PyCharm
Только затронул тему рекурсии.

В каком конкретно месте вашей программы вы как вам кажется осуществляете рекурсивный вызов?

Nikita_PyCharm · Июль 30, 2020 14:10:16

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 · Июль 30, 2020 14:27:43

моя программа работает по перебору

 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 · Июль 30, 2020 14:42:32

Nikita_PyCharm
Я предполагаю

Вы молодец, но давайте вместе вслух прочитаем определение рекурсии

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

Теперь покажите мне функцию, которая вызывает саму себя

FishHook · Июль 30, 2020 14:44:21

Nikita_PyCharm
Читать до просветления
http://www.tvd-home.ru/recursion

Nikita_PyCharm · Июль 30, 2020 14:56:50

FishHook
Nikita_PyCharmЧитать до просветленияhttp://www.tvd-home.ru/recursion

Да я знаю что такое рекурсия, я не правильно выразился сказав “моя программа работает по типу рекурсии” я имел в виду что вложенный for в for очень похож по действию рекурсии только не проваливается сам в себя а как бы весь стек прописан циклами снаружи.

 def ar (a)
    a += 1
    return ar(a)

Отредактировано Nikita_PyCharm (Июль 30, 2020 14:57:44)

Nikita_PyCharm · Июль 30, 2020 14:59:37

я тут немного изменил подход вместо

 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 · Июль 30, 2020 15:00:50

Nikita_PyCharm
я тут немного изменил подход вместо

так можно будет идти по строкам используя увеличивающийся индекс

Nikita_PyCharm · Июль 30, 2020 15:08:25

FishHook
Nikita_PyCharmЧитать до просветленияhttp://www.tvd-home.ru/recursion

Хм возможно я рановато залез в рекурсию для начала почитаю руководство, Спасибо

Python-сообщество

Уведомления

#1 Июль 30, 2020 12:21:10

Проект Эйлера задача 18, оптимизация

#2 Июль 30, 2020 13:45:03

Проект Эйлера задача 18, оптимизация

#3 Июль 30, 2020 14:10:16

Проект Эйлера задача 18, оптимизация

#4 Июль 30, 2020 14:27:43

Проект Эйлера задача 18, оптимизация

#5 Июль 30, 2020 14:42:32

Проект Эйлера задача 18, оптимизация

#6 Июль 30, 2020 14:44:21

Проект Эйлера задача 18, оптимизация

#7 Июль 30, 2020 14:56:50

Проект Эйлера задача 18, оптимизация

#8 Июль 30, 2020 14:59:37

Проект Эйлера задача 18, оптимизация

#9 Июль 30, 2020 15:00:50

Проект Эйлера задача 18, оптимизация

#10 Июль 30, 2020 15:08:25

Проект Эйлера задача 18, оптимизация

Board footer