Тема: Не зрозумів жарту

def game(x, a, b):
    count1, count2, xsum = 0, 0, 0
    a2 = a
    b2 = b
    print(a2, b2) 
    while(xsum + b[0] <= x):

        if a != [] and (xsum + a[0]) <= x:
            xsum += a.pop(0)
            

        elif b != []:
            xsum += b.pop(0)
        count1 += 1
            
    print(a2, b2)   
    xsum = 0
    while(xsum + a2[0] <= x):

        if b2 != [] and (xsum + b2[0]) <= x:
            xsum += b2.pop(0)

        elif a2 != []:
            xsum += a2.pop(0)
            
        count2 += 1
            
       
    return max(count1, count2)

x = 10
a = [4, 2, 4, 6, 1]
b = [2, 1, 8, 5]

Не розумію чому змінні a2 і b2 змінюють свої значення після першого циклу, адже вони там жодним чином не використовуються. І тут немає рекурсії. Чи це якась особливість виконання циклу while?

2

Re: Не зрозумів жарту

Бо в пітоні присвоювання не копіює масив чи список, а просто записує в нову змінну вказівник на нього. Щоб так було як вихочете требе функцію copy вживати.

Подякували: ping, koala, Vitaliy_Danmer, leofun014

3

Re: Не зрозумів жарту

проілюструю:

d = {1:2}
f = d
f_copy  = d.copy()
print('f before changing d', f)
d[1] = 4
print('f after changing d',f)
print('f_copy after changing d',f_copy)
Python 3.6.1 (default, Dec 2015, 13:05:11)
[GCC 4.8.2] on linux
   
f before changing d {1: 2}
f after changing d {1: 4}
f_copy after changing d {1: 2}   
Подякували: koala, Vitaliy_Danmer, leofun013

4

Re: Не зрозумів жарту

Програма неефективна і падатиме ще з багатьох причин.
Може, умовою поділитеся?

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

5 Востаннє редагувалося Vitaliy_Danmer (16.10.2018 10:31:05)

Re: Не зрозумів жарту

koala написав:

Програма неефективна і падатиме ще з багатьох причин.
Може, умовою поділитеся?

Це завдання з HackerRank.com, називається "Game of two stacks".
Дано два стеки і деяке число х. Треба прибирати числа зі стеків, верхівкою яких є нульовий елемент, доки їхня сума не стане більшою за число х. Максимальна кількість прибраних таким чином чисел і є відповіддю.

6 Востаннє редагувалося koala (16.10.2018 11:51:58)

Re: Не зрозумів жарту

Так у вас навряд щось вийде. Ви намагаєтеся по максимуму захопити один стек, а потім подобирати з іншого, я правильно зрозумів? Ось вам приклад, коли це не спрацює:
a=[3,1,1,1,3]
b=[3,1,1,1,3]
x=10
Відповідь тут 6: дві перші трійки з обох стеків і 4 одинички (2:2 чи 1:3 у будь-якому порядку). А ваш алгоритм буде давати 5, бо збере або що може з a, або що може з b, а потім його не пустить трійка.
Тут потрібен розумний перебір: починаємо зі стану "якомога більше з a, якщо ще можна - то трохи з b" і намагаємося по одному елементу "викидати" з a і по максимуму набирати з b (приблизно як на малюнку). Якщо нове значення краще, запам'ятовуємо. Коли з a не буде чого викидати - маємо відповідь.
Звісно, насправді не треба нічого викидати - треба пам'ятати позиції в a та b та поточну суму.
http://narodna-osvita.com.ua/uploads/7_klas_fizika_sirotjuk_2015/204.jpg

Подякували: Vitaliy_Danmer, leofun01, Vasil.Kolomiets3

7

Re: Не зрозумів жарту

Ось, що з цього вийшло, кому цікаво:

def game(x, a, b):

    a.reverse()
    b.reverse()
    count = 0
    sum1 = 0
    sum2 = 0
    stack = []

    while(a):
        if sum1 + a[-1] <= x:
            stack.append(a.pop())
            sum1 += stack[-1]
            count += 1
        else:
            break

    while(b):
        if sum2 + b[-1] <= x:
            if sum1 + b[-1] <= x:
                y = b.pop()
                sum1 += y
                sum2 += y
                count += 1
            else:
                y = b.pop()
                sum1 += y - stack.pop()
                sum2 += y
        else:
            break

    return count

x = 10
a = [4, 2, 4, 6, 1]
b = [2, 1, 8, 5]

Хтось може зауважити, що не варто було реверсувати a i b, а просто скористатися pop(0).
Проте pop(0) має швидкість виконання O(n), а не O(1), як у випадку з просто pop(), тому що доводиться проходити усю довжину списку до початку. Тому для швидшого виконання програми краще використати реверсування.

Подякували: koala, Vasil.Kolomiets2

8

Re: Не зрозумів жарту

Тобто ви замість того, щоб тримати індекси, робите перетворення масивів, і кажете, що це для оптимізації? Ню-ню.

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