DjangoBB LoFi version

Полная версия: Максимум неполного массива

Начало » Python для новичков » Максимум неполного массива

1 2

graf

Фев. 19, 2020 15:53:06

Добрый день!
Решаю задачку Хирьянова:
В некотором физическом эксперименте показания прибора снимались с частотой 5 измерений в секунду. Эксперимент проводился в течение довольно большого времени, и в результате накопилось очень много данных. Ученых, которые проводили данный эксперимент, очень интересует, какое максимальное значение измеряемой величины достигалось во время измерения. Но вот беда: на остановку установки также требуется секунда времени, и в течение этого времени с установки могут приходить совершенно любые значения величины. В связи с этим, показания последних 5 измерений учитывать при поиске максимального значения не следует.

Вам необходимо написать программу, которая в данном потоке чисел заранее неизвестной длины находит максимальное значение, отбрасывая при этом последние 5 измерений.

Формат входных данных
На вход вашей программе передается последовательность натуральных чисел – результаты измерений. Каждое новое число передается с новой строки. Гарантируется, что длина входной последовательности не меньше 6 и не превосходит 10 9 . На конце последовательности передается число 0.

Формат выходных данных
Программа должна вывести на экран одно число – максимальное значение входной последовательности за исключением последних 5 элементов.

Сначала решил так:

 A = []
k = int(input())
A.append(k)
for i in A:
    k = int(input())
    if k == 0:
        for i in range(5):
            A.pop(-1)
        break
    A.append(k)
    i += 1
print (max(A))

Прошли все тесты кроме одного с самым большим объемом данных. Выпала ошибка:
====== Тест #10 =======
— Входные данные: файл слишком велик, размер 9889191 —
— Результат работы: размер 0 —

— Поток ошибок: размер 86 —
Traceback (most recent call last):
File “./002583”, line 8, in <module>
MemoryError

Перерешал так (мысль была уменьшить список):

 A = []
k = int(input())
A.append(k)
for i in range(10000000000):
    k = int(input())
    if k == 0:
        for i in range(5):
            A.pop(-1)
        break
    A.append(k)
    i += 1
    if i > 10:
        x = max(A[0:4])
        A = A[1:]+A[:1]
        A.pop(-1)
        A.append(x)
        A = A[-1:]+A[:-1]
        
print (max(A))

Опять ошибка. Только в этот раз превышение времени реальной работы.
Подскажите, пожалуйста, есть еще какой-нибудь метод (более оптимальный)?

Rodegast

Фев. 19, 2020 18:06:50

 >>> s = list(range(25))
>>> s
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]
>>> max(s[:-5])
19

py.user.next

Фев. 20, 2020 02:22:30

graf
Подскажите, пожалуйста, есть еще какой-нибудь метод (более оптимальный)?

У тебя должен быть буфер на пять элементов. Когда он заполнен и приходит новый элемент, первый элемент надо вытолкнуть из буфера и сравнить этот первый элемент с текущим максимальным элементом. При этом новый элемент добавляется в конец буфера. На следующем новом элементе повторяется всё то же самое.

Думаю, тут нужно два цикла: первый цикл заполняет весь буфер изначально; второй цикл проектируется с инвариантом и выполняет всю работу по запоминанию текущего максимального элемента.

Вариант от Rodegast неправильный, так как в задаче речь идёт о “бесконечной” последовательности с маркером её конца, а range() , в свою очередь, требует изначального знания, сколько элементов будет в последовательности. В реальных задачах данные вообще бесконечно поступают и там просто нет никакого известного заранее объёма.

graf

Фев. 20, 2020 08:22:24

py.user.next
Про буфер я догадался и реализовал во втором варианте решения (может кривовато):

        if i > 10:
        x = max(A[0:4])
        A = A[1:]+A[:1]
        A.pop(-1)
        A.append(x)
        A = A[-1:]+A[:-1]

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

py.user.next

Фев. 20, 2020 09:44:38

graf
Про буфер я догадался и реализовал во втором варианте решения (может кривовато):

Я тебе написал, как нужно делать. Не надо применять функцию max() и тем самым перебирать весь буфер на каждом шаге. Для миллиона элементов это приведёт к миллиону переборов буфера. В том алгоритме, который я описал, сравнение элемента с последним максимальным элементом на данный момент происходит после выталкивания элемента из буфера. А буфер используется только для хранения последних пяти элементов.

Если не догоняешь, как это сделать, я тебе могу написать. Но лучше будет, если ты сам подумаешь, потому что мне этот код ничего нового не даст в плане опыта.

Rafik

Фев. 20, 2020 10:32:33

py.user.next, дополню немного. Перед чтением из буфера и записью в него надо бы проверить полученный элемент на 0, “конец последовательности”. Если 0, то выдать результат.

graf

Фев. 20, 2020 12:55:39

py.user.next
Rafik
Всем спасибо!
Решил так:

 A = []
x = 0
k = int(input())
A.append(k)
for i in range(1000000000):
    k = int(input())
    if k == 0:
        break
    A.append(k)
    if i > 4:
        A.pop(0)
    if A[0] > x:
        x = A[0]
    i += 1
print (x)

Rodegast

Фев. 20, 2020 14:13:19

> Вариант от Rodegast неправильный, так как в задаче речь идёт о “бесконечной” последовательности

Где написано что последовательность бесконечная?

> а range() , в свою очередь, требует изначального знания, сколько элементов будет в последовательности.

Ну и причём тут range?

> Решил так:

Решил ты её не правильно, нужно использовать цикл while

graf

Фев. 20, 2020 15:02:17

Rodegast
Мое решение тоже работает, но если подскажешь как красивее это реализовать, буду благодарен

Немного подумал. Так?:

 A = []
x = 0
i = 0
k = int(input())
A.append(k)
while k != 0:
    k = int(input())
    A.append(k)
    if i > 5:
        A.pop(0)
    if A[0] > x:
        x = A[0]
    i += 1
print (x)

Rodegast

Фев. 20, 2020 16:36:01

> Мое решение тоже работает

Оно у тебя работает пока в списке менее 1000000000 элементов

> но если подскажешь как красивее это реализовать, буду благодарен

Можно сначала прочитать весь список, а потом использовать функцию max (см. моё первое сообщение).
Если хочешь это делать сразу, тогда как то так:

 res = 0
cache = []
x = int(input())
while x:
	cache.append(x)
	if len(cache) >= 5:
		x = cache.pop(0)
	res = res if res > x else x
	x = int(input())
print(res)