1 Тема від tragical Востаннє редагувалося koala (11.09.2020 19:50:20)

  • tragical
  • Новий користувач
  • Поза форумом
  • Дата реєстрації: 11.09.2020
  • Повідомлень: 1
    • Репутація: 0

Тема: Проект Ейлера, Задача11 https://projecteuler.net/problem=11

Ось код, все працює, але код не оптимізований, підкажіть як можна оптимізувати його

from array import * 
tmp1=1
tmp=1
tmp2=1
tmp3=1
suma=1
suma2=1
suma1=1
suma3=1

masiv=[8, 2, 22, 97, 38, 15, 0 , 40, 0, 75, 4, 5, 7, 78, 52, 12, 50, 77, 91, 8, 49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 4, 56, 62,0,81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40 ,67 ,53, 88, 30 ,3 ,49, 13 ,36, 65,52, 70 ,95, 23, 4 ,60, 11 ,42, 69, 24 ,68, 56, 1 ,32 ,56, 71, 37, 2, 36, 91,22, 31, 16 ,71, 51 ,67, 63, 89, 41, 92 ,36 ,54 ,22 ,40 ,40 ,28, 66, 33, 13, 80,24, 47, 32 ,60 ,99, 3 ,45, 2 ,44 ,75, 33, 53 ,78 ,36 ,84 ,20, 35, 17, 12, 50,32, 98, 81 ,28, 64, 23, 67 ,10, 26, 38, 40, 67, 59, 54, 70, 66 ,18 ,38 ,64, 70,67 ,26 ,20 ,68 ,2 ,62, 12, 20, 95, 63, 94 ,39, 63, 8 ,40 ,91 ,66 ,49, 94, 21,24, 55, 58 ,5 ,66, 73, 99, 26, 97, 17, 78, 78 ,96 ,83, 14 ,88 ,34 ,89 ,63, 72,21, 36 ,23 ,9 ,75 ,0 ,76, 44, 20, 45 ,35, 14, 0 ,61, 33, 97, 34, 31, 33, 95,78, 17, 53, 28 ,22, 75, 31, 67, 15, 94 ,3 ,80, 4, 62, 16, 14, 9 ,53, 56, 92,16 ,39 ,5 ,42, 96 ,35 ,31 ,47 ,55, 58, 88 ,24 ,0 ,17 ,54, 24 ,36, 29, 85, 57,86, 56, 0, 48, 35, 71, 89, 7, 5, 44, 44, 37, 44, 60 ,21, 58 ,51, 54, 17, 58,19, 80, 81, 68, 5 ,94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77 ,89, 55, 40,4, 52, 8, 83, 97 ,35 ,99, 16, 7, 97 ,57 ,32 ,16, 26, 26, 79, 33 ,27, 98, 66,88, 36, 68, 87, 57, 62 ,20, 72, 3 ,46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69,4 ,42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 8, 46, 29, 32, 40, 62, 76, 36,20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82 ,67, 59, 85, 74, 4 ,36, 16,20, 73, 35, 29, 78, 31 ,90 ,1 ,74 ,31, 49, 71, 48, 86 ,81, 16, 23, 57, 5, 54,1 ,70, 54, 71, 83 ,51, 54, 69, 16 ,92 ,33 ,48 ,61 ,43 ,52, 1 ,89 ,19 ,67, 48]
for r in range(0,336):
    j=-21
    j=-21+r
    tmp=1     
    #print('')
    for i in range(1,5):
        j+=21
        #print(masiv[j])
        tmp*=masiv[j]
        #print(tmp)
        if suma<tmp:
            suma=tmp

for r1 in range(0,339):
    j=-20
    j=-20+r1
    tmp1=1     
    #print('')        
    for i in range(1,5):
        j+=20
        #print(masiv[j])
        tmp1*=masiv[j]
        #print(tmp1)
        if suma1<tmp1:
            suma1=tmp1
for r2 in range(0,339):
    j=-19
    j=-19+r2
    tmp2=1     
    print('')
    for i in range(1,5):
        j+=19
        print(masiv[j])
        tmp2*=masiv[j]
        #print(tmp)
        if suma2<tmp2:
            suma2=tmp2
for r3 in range(0,396):
    j=-1
    j=-1+r3
    tmp3=1     
    #print('')
    for i in range(1,5):
        j+=1
        #print(masiv[j])

        tmp3*=masiv[j]
        #print(tmp)
        if suma3<tmp3:
            suma3=tmp3

print(suma)
print(suma2)
print(suma1)
print(suma3)


if suma>suma1:
    rez=suma
else:
    rez=suma1
if suma2>suma3:
    rez1=suma2
else:
    rez1=suma3
if rez1>rez:
    print(rez1)
else:
    print(rez)

2 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 620
    • Репутація: 13333

Re: Проект Ейлера, Задача11 https://projecteuler.net/problem=11

Оптимізувати, перепрошую, за яким параметром?
Тут у будь-якому разі буде десь така сама обчислювальна складність. Тут радше можна про читаність поговорити.
Ну, хоча одну ідею я можу подати, але вона не дуже певна. Якщо ви маєте рядок чисел і добуток чисел (x1,x2,x3,x4), позначимо цей добуток tmp, то добуток чисел (x2,x3,x4,x5) можна обчислити як tmp/x1*x5. Втім, операція ділення повільна, не факт, що це буде швидше за пряме множення. Це можна ще пришвидшити, якщо логарифмувати всю таблицю - додавання та віднімання точно швидші, навіть з рухомою комою; але тоді вийде... гм... порахуєемо.
Якщо сторона квадрата N, то нам треба обчислити по N*(N-3) потрійних добутків по горизонталі і вертикалі та по (N-3)*(N_3) по діагоналях. Разом 3*(2*N*(N-3)+2*(N-3)*(N-3))=6*(N-3)*(2*N-3) множень. Якщо замінити це на ділення, то (ліньки думати, скільки по діагоналях) хай буде 2*(N-3)*(2*N-3) множень і стільки ж ділень. А якщо замінити на додавання-віднімання, то буде стільки додавань і віднімань, скільки зараз множень і ділень, і ще N*N логарифмів. У будь-якому разі маємо складність O(N2). Не думаю, що тут є що шукати.
Є одна дрібниця: немає сенсу перевіряти значення часткових добутків у внутрішньому циклі, можна винести на рівень вище.

Ну і ваш код не спрацює, якщо, наприклад, masiv[18:22] = [1000]*4, бо він знайде ці тисячі - а вони, насправді, розбиті між рядками.

Подякували: tragical, leofun012

koala вебсайт

3 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 620
    • Репутація: 13333

Re: Проект Ейлера, Задача11 https://projecteuler.net/problem=11

Ще раджу використовувати функцію max. І reduce з functools.
Ну і я посилання виправив.

Подякували: tragical1

koala вебсайт

4 Відповідь від koala Востаннє редагувалося koala (11.09.2020 22:12:13)

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 620
    • Репутація: 13333

Re: Проект Ейлера, Задача11 https://projecteuler.net/problem=11

Ось по суті ваш код, але значно читаніший:

from functools import reduce

def euler11(array, span=4):
    height = len(array) #висота масиву
    width = len(array[0]) #ширина масиву

    best = 0
    #горизонталі
    for row in range(height):
        for col in range(width-span):
            tmp = reduce(int.__mul__, (array[row][col+i] for i in range(span)))
            best = max(best, tmp)
    #вертикалі
    for row in range(height-span):
        for col in range(width):
            tmp = reduce(int.__mul__, (array[row+i][col] for i in range(span)))
            best = max(best, tmp)
    #діагоналі паралельні головній
    for row in range(height-span):
        for col in range(width-span):
            tmp = reduce(int.__mul__, (array[row+i][col+i] for i in range(span)))
            best = max(best, tmp)
    #діагоналі паралельні допоміжній
    for row in range(height-span):
        for col in range(width-span):
            tmp = reduce(int.__mul__, (array[row+span-i-1][col+i] for i in range(span)))
            best = max(best, tmp)
    return best

if __name__ == '__main__':
    DATA = '''08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
    49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
    81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
    52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
    22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
    24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
    32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
    67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
    24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
    21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
    78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
    16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
    86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
    19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
    04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
    88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
    04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
    20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
    20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
    01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48'''
    ARRAY = [[int(x) for x in line.split()] for line in DATA.splitlines()]
    
    print(euler11(ARRAY))
Подякували: tragical1

koala вебсайт

5 Відповідь від /KIT\

  • /KIT\
  • Меломан
  • Поза форумом
  • Звідки: Україна
  • Дата реєстрації: 25.09.2015
  • Повідомлень: 1 397
    • Репутація: 804

Re: Проект Ейлера, Задача11 https://projecteuler.net/problem=11

koala написав:

Ось по суті ваш код, але значно читаніший:

from functools import reduce

def euler11(array, span=4):
    height = len(array) #висота масиву
    width = len(array[0]) #ширина масиву

    best = 0
    #горизонталі
    for row in range(height):
        for col in range(width-span):
            tmp = reduce(int.__mul__, (ARRAY[row][col+i] for i in range(span)))
            best = max(best, tmp)
    #вертикалі
    for row in range(height-span):
        for col in range(width):
            tmp = reduce(int.__mul__, (ARRAY[row+i][col] for i in range(span)))
            best = max(best, tmp)
    #діагоналі паралельні головній
    for row in range(height-span):
        for col in range(width-span):
            tmp = reduce(int.__mul__, (ARRAY[row+i][col+i] for i in range(span)))
            best = max(best, tmp)
    #діагоналі паралельні допоміжній
    for row in range(height-span):
        for col in range(width-span):
            tmp = reduce(int.__mul__, (ARRAY[row+span-i-1][col+i] for i in range(span)))
            best = max(best, tmp)
    return best

if __name__ == '__main__':
    DATA = '''08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
    49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
    81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
    52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
    22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
    24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
    32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
    67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
    24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
    21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
    78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
    16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
    86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
    19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
    04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
    88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
    04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
    20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
    20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
    01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48'''
    ARRAY = [[int(x) for x in line.split()] for line in DATA.splitlines()]
    
    print(euler11(ARRAY))

Функція euler11 має параметр array, але все одно використовує глобальну змінну ARRAY

Подякували: koala1

6 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 620
    • Репутація: 13333

Re: Проект Ейлера, Задача11 https://projecteuler.net/problem=11

Дякую, виправив.

koala вебсайт