Форум программистов, компьютерный форум, киберфорум
Python: Решение задач
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.83/6: Рейтинг темы: голосов - 6, средняя оценка - 4.83
0 / 0 / 0
Регистрация: 03.07.2023
Сообщений: 4

Поиск максимального числа в каждых К числах N потока данных

03.07.2023, 11:00. Показов 1282. Ответов 18

Студворк — интернет-сервис помощи студентам
Добрый день, друзья.
Прохожу курс питона, тема линейное программирование. Несколько дней уже бьюсь, не могу решить следующую задачу:

Напиште решение задачи на Python. Условие задачи: пользователь вводит числа N и K, (K < N), затем вводит последовательно N чисел. Нужно вывести числа, которые отвечали бы условиям: первое число - это сумма первых K чисел из вводимых N. Второе число - это сумма K чисел из вводимых N со смещением 1 и так далее.
Пример: Вводятся числа N равное 5 и K равное 3. Затем вводятся 5 чисел 1, 2, 3, 1, 4 ( В ответе будут числа: 6, 6, 8 (т.е 1+2+3, 2+3+1, 3+1+4))
Найти максимальное число среди каждых K чисел.
Решить задачу без использования списков, т.е. работать в потоке, памяти нет, чисел много.
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
03.07.2023, 11:00
Ответы с готовыми решениями:

Поиск максимального потока
Дали задание по поиску максимального потока, посмотрите пожалуйста файл, может есть какой то алгоритм решения. Наткнулся на онлайн...

Поиск максимального потока в графе
Прошу напишите код программы для поиска максимального потока в графе на паскале

Алгоритм Гомори-Ху. Поиск максимального потока
Помогитите, пожалуйста, разобраться с одной деталью в алгоритме Гомори-Ху. Вот здесь в пункте 2.3.3. есть пример с задачей, подробно,...

18
Эксперт PythonЭксперт Java
19530 / 11067 / 2931
Регистрация: 21.10.2017
Сообщений: 23,294
03.07.2023, 14:20
Цитата Сообщение от AlexM19 Посмотреть сообщение
Решить задачу без использования списков
А куда вы будете складывать входящие данные, позвольте спросить? Даже если их обрабатывать последовательно, то после каждого очередного введенного числа будет выведен результат.
Или тут максимально по упоротому добавлять результаты к одной и той же строке?

Добавлено через 5 минут
Хотя не, даже так не получится. Сдается мне, условие про отсутствие списков надуманное.
1
0 / 0 / 0
Регистрация: 03.07.2023
Сообщений: 4
03.07.2023, 14:57  [ТС]
- А куда вы будете складывать входящие данные, позвольте спросить?
Полагаю, что подразумевалось использование только числовых переменных.

-Или тут максимально по упоротому добавлять результаты к одной и той же строке?
Я думал насчёт строк, но тогда, если их можно использовать, то не вижу особого смысла в ограничении на списки.

Сегодня ближе к 18:00 приложу ссылку на само видео с урока, на случай, если я не так понял.
0
Эксперт Python
 Аватар для dondublon
4648 / 2068 / 366
Регистрация: 17.03.2012
Сообщений: 10,168
Записей в блоге: 6
03.07.2023, 15:13
Пмм, k последних чисел тут всё равно придётся хранить, в каком-то виде. Все n. конечно, не нужно.
1
5514 / 2867 / 571
Регистрация: 07.11.2019
Сообщений: 4,750
03.07.2023, 17:41
Не совсем верно, т.к. первое значение надо сохранять, но идея, думаю, понятная..
Python
1
2
f=sum(a[:k])
max(f:=f-a[i]+a[i+k] for i in range(n-k))


Добавлено через 1 час 18 минут
Что-то подобное:
Python
1
2
3
4
5
6
7
a = [1, 2, 3, 1, 6, 9, 8]
n = len(a)
k = 3
s1 = sum(a[:k])
s = s1
result = max(s1, max(s := s+a[i+k]-a[i] for i in range(n-k)))
print(result)
1
0 / 0 / 0
Регистрация: 03.07.2023
Сообщений: 4
03.07.2023, 17:50  [ТС]
Цитата Сообщение от AlexM19 Посмотреть сообщение
Сегодня ближе к 18:00 приложу ссылку на само видео с урока, на случай, если я не так понял.
https://youtu.be/EgrQac43aXk
0
Эксперт Python
 Аватар для dondublon
4648 / 2068 / 366
Регистрация: 17.03.2012
Сообщений: 10,168
Записей в блоге: 6
03.07.2023, 20:06
Мне кажется, это невозможно. Вырисовывается примерно такой подход, в качестве наиболее экономного - мы храним сумму, с каждым новым числом его прибавляем к сумме и должны вычесть первое. Но эти первые надо хранить.

Поясню. Я думаю о сложном случае, когда числа подаются в виде последовательности (а не списка) и мы не можем помнить много "прошлых". Решение от u235 опирается на то, что сами числа нам поступили в виде списка (а не последовательности), и не заводим новый список.
0
1956 / 874 / 352
Регистрация: 05.09.2021
Сообщений: 1,387
03.07.2023, 20:28
dondublon, Почему-то мне кажется, что когда ТС выложит решение (если выложит), то в нем все равно будет в той или иной форме присутствовать список.

Если бы К было задано фиксировано, то мы могли бы сделать (захардкодить) буфер в виде number_1, number_2 .... number_k, и дальше проводить какую-то ротацию, чтобы заменяя "ушедшие" значения новыми, но т.к. К неизвестно, то по любому понадобится какая-то структура размер которой можно задать динамически. Можно конечно реализовать свой "список", но это "такое".
0
Вирусоборец
 Аватар для thyrex
14432 / 7474 / 1579
Регистрация: 06.09.2009
Сообщений: 27,111
03.07.2023, 20:36
Видимо все же подразумевалось, что на входе числа не пишутся в список, а выходные данные как раз можно и в список оформить.
0
Эксперт PythonЭксперт Java
19530 / 11067 / 2931
Регистрация: 21.10.2017
Сообщений: 23,294
03.07.2023, 20:44
Как ни крути, К чисел нужно запоминать.
1
32 / 24 / 11
Регистрация: 03.06.2023
Сообщений: 56
03.07.2023, 20:49
Хм, можно ли как-то создать второй генератор, не вводя данные повторно? (отметил комментарием нужное место)

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
n = int(input())
k = int(input())
 
gen1 = (int(input()) for _ in range(n))
gen2 = ...  # Нужно как-то создать генератор, не вводя данные второй раз
 
c = 0
s = 0
mx = 0
 
while True:
    try:
        right = next(gen1)
        s += right
 
        if c == k:
            left = next(gen2)
            s -= left
        else:
            c += 1
 
        if s > mx:
            mx = s
 
    except (RuntimeError, StopIteration):
        break
 
print(mx)
0
Вирусоборец
 Аватар для thyrex
14432 / 7474 / 1579
Регистрация: 06.09.2009
Сообщений: 27,111
03.07.2023, 21:18
Цитата Сообщение от iSmokeJC Посмотреть сообщение
Как ни крути, К чисел нужно запоминать.
Интересно потом будет посмотреть, как сам преподаватель из foxford решит это задание без списков
1
0 / 0 / 0
Регистрация: 03.07.2023
Сообщений: 4
03.07.2023, 22:47  [ТС]
UPD! Нашёл преподавателя в VK (Гуровиц Владимир Михайлович). Он подтвердил Ваши предположения:

"имелось в виду, что N большое, и N памяти у нас нет, а К - маленькое, и К памяти использовать можно"

Добавлено через 42 минуты
Получилось так:
Python
1
2
3
4
5
6
7
8
9
N, K = map(int, input('Введите через пробел N, K: ').split())
print('NK = ', N, K)
list_k = []  # меняющийся список K чисел
for i in range(N):
    list_k.append(int(input('Введите число ')))
    if len(list_k) == K:
        print('Сумма K чисел: ', sum(list_k))
        print('Максимальное из K чисел: ', max(list_k))
        list_k.pop(0)
Спасибо всем, прошу прощения, что потратили время на ерунду. Я вернусь с вопросами поинтереснее.
0
 Аватар для s_t_r_a_j
526 / 179 / 58
Регистрация: 12.02.2023
Сообщений: 641
05.07.2023, 23:29
Цитата Сообщение от AlexM19 Посмотреть сообщение
Получилось так:
Python
1
2
3
4
5
6
7
8
9
N, K = map(int, input('Введите через пробел N, K: ').split())
print('NK = ', N, K)
list_k = []  # меняющийся список K чисел
for i in range(N):
    list_k.append(int(input('Введите число ')))
    if len(list_k) == K:
        print('Сумма K чисел: ', sum(list_k))
        print('Максимальное из K чисел: ', max(list_k))
        list_k.pop(0)
что-то не так мне кажется получилось
может так:
Python
1
2
3
4
5
6
7
8
9
N, K = map(int, input('Введите через пробел N, K: ').split())
list_k = []
for i in range(N):
    list_k.append(int(input('Введите число ')))
for j in range(0,N,K):
    for u in range(K):
        t = list_k[(j+u):(j+u+K)]
        if len(t) >= K:
            print(f'Сумма чисел: {t} = {sum(t)}. Максимальное из чисел: {max(t)}')
0
Вирусоборец
 Аватар для thyrex
14432 / 7474 / 1579
Регистрация: 06.09.2009
Сообщений: 27,111
05.07.2023, 23:34
s_t_r_a_j, написано же
Цитата Сообщение от AlexM19 Посмотреть сообщение
имелось в виду, что N большое, и N памяти у нас нет
1
Эксперт Python
 Аватар для dondublon
4648 / 2068 / 366
Регистрация: 17.03.2012
Сообщений: 10,168
Записей в блоге: 6
07.07.2023, 12:15
Используйте collections.deque, чтобы выглядело по-взрослому.
1
5514 / 2867 / 571
Регистрация: 07.11.2019
Сообщений: 4,750
07.07.2023, 12:40
Если нужна скорость, то можно так:
Python
1
2
3
4
5
6
import numpy as np
a=np.array([1,2,3,1,4])
n=a.shape[0]
k=3
w=np.ones(k)
print(np.convolve(w, a, 'valid').max())
Или можно использовать scipy.signal.fftconvolve для свертки.
0
3750 / 1944 / 612
Регистрация: 21.11.2021
Сообщений: 3,707
07.07.2023, 14:02
Цитата Сообщение от dondublon Посмотреть сообщение
Используйте collections.deque, чтобы выглядело по-взрослому
Толковая мысль. Вот так можно:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
from collections import deque
k = int(input('k = '))
deq = deque(maxlen=k)
try:
    while True:
        x = int(input('Введите число (для выхода нажмите Enter:) '))
        deq.append(x)
        if len(deq) == deq.maxlen:
            print()
            print(f'sum = {sum(deq)}, max = {max(deq)}')
            print()
except:
    pass
0
Эксперт Python
 Аватар для dondublon
4648 / 2068 / 366
Регистрация: 17.03.2012
Сообщений: 10,168
Записей в блоге: 6
09.07.2023, 15:49
Я имел в виду как-то так:
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from collections import deque
 
 
def get_sum(seq, k):
    q = deque()
    sum_ = 0
    iterator = iter(seq)
    # Заполняем первые k штук
    for i in range(k):
        v = next(iterator)
        q.append(v)
        sum_ += v
    yield sum_
    
    # Далее до упора, соответственно меняем очередь и сумму, сумму возвращаем. 
    for v in iterator:
        first_k = q.popleft()
        q.append(v)
        sum_ = sum_ + v - first_k
        yield sum_
 
 
lst = range(11)
for s in get_sum(lst, 3):
    print(s)
Добавлено через 3 минуты
Для суммы норм, для максимума чисто не сделаешь, но можно сократить число проходов по очереди в k раз в среднем, оставить только для случая, когда попнутый элемент является максимальным.
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
09.07.2023, 15:49
Помогаю со студенческими работами здесь

Поиск максимального потока методом проталкивания предпотока
объясните прогу пожалуйста.Код не мой, а сдать надо // {поиск максимального потока методом проталкивания предпотока в его реализации...

Поиск максимального потока методом Форда-Фалкерсона
Здрасвуйте помогите мне пожалуйста найти поиск максимального потока методом Форда-Фалкерсона; для поиска дополняющего пути используется...

Задача на нахождение максимального потока и потока минимальной
Помогите с задачей ! Найти максимальный поток, который может протекать по сети из узла s в узел t, если для каждой дуги задана ее...

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

Поиск максимального числа
PROGRAM Lab_3; {Лабораторная работа №3 Вариант №11} const=9999; Var N, A, i:word; Label metka; Begin while A&lt;&gt;C Do ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
19
Ответ Создать тему
Новые блоги и статьи
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
Фото: Daniel Greenwood
kumehtar 13.11.2025
Расскажи мне о Мире, бродяга
kumehtar 12.11.2025
— Расскажи мне о Мире, бродяга, Ты же видел моря и метели. Как сменялись короны и стяги, Как эпохи стрелою летели. - Этот мир — это крылья и горы, Снег и пламя, любовь и тревоги, И бескрайние. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru