Эффективные алгоритмы

Приветствую всех. Есть ли у кого-то информация о том, как решать 27 задание ЕГЭ по информатике эффективно по времени и по памяти? Практически не нашел бесплатного контента по этой теме

что за задание?

ты бы скинул сюда пример задания хотябы

Chaiok сказал(а):↑

ты бы скинул сюда пример задания хотябы

Нажмите, чтобы раскрыть...

https://inf-ege.sdamgia.ru/test?theme=402

Что-то вроде такого

Мне кажется это просто на логику

смотри готовые решения, там все подробно рассказывается

забил бы, какая разница?

kid cudi bich сказал(а):↑

забил бы, какая разница?

Нажмите, чтобы раскрыть...

2 первичных балла - слишком много

Цитата:

По каналу связи передаются положительные целые числа, не превышающие 1000, – результаты измерений, полученных в ходе эксперимента (количество измерений известно заранее). После окончания эксперимента передаётся контрольное значение – наибольшее число R, удовлетворяющее следующим условиям:

1) R — сумма двух различных переданных элементов последовательности («различные» означает, что нельзя просто удваивать переданные числа, суммы различных, но равных по величине элементов допускаются);

2) R — нечётное число.

Если чисел, соответствующих приведённым условиям, нет, считается, что R = –1. В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены.

Нажмите, чтобы раскрыть...

Отмороженное существо писало задачу.

- различных переданных - это каких?

- причем тут удваивать - уже ж написали различных?

- наибольшее число R - по отношению к чему?

- каких помех? насколко искажены? как должна программа реагировать?

жаль школяров, прям до глубины души, но я бы просто уринотерапию приписал бы творцам сего шедевра.

Цитата:

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

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

Максимальная оценка за выполнение задания А – 2 балла.

Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик).

Программа считается эффективной по времени, если время работы программы пропорционально количеству элементов последовательности N, т.е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.

Нажмите, чтобы раскрыть...

Ответ на вопрос ТС, лежит в самом вопросе, но:

А. сохранение в массив задача ЗАВЕДОМО проигрышная по памяти, а учитывая что в масиве прийдется вести поиск, или фортировку, то она так же проигрышная по сложности - О(N log N), и это в лучшем случае.

Б. очевидно программа должна последовательно обрабатывать входящие данные, то есть на каждый елемент, в таком случае мы получим O (n), причем абсолютно стабильный.

Решение:

функция счетчкик, принимает на вход стек-массив (можно использовать замыкания например), текущее значение.

R = -1, Max_1 = 1, Max_2 = 1

сравниваем текущее значение, с нулевым R (изначально -1), если больше. Max_1 = текущему,

сравниваем max_1 и max_2, если меньше (не строго) max_2 не трогаем - иначе перезаписываем.

По концу у нас будет максимальное и предыдущее значение.

Сравниваем с контрольной R, (ну там четность проверям и т.п.)

UPD. только посмотрев видео понял, что нормальное человеческое предложение "программа должна вернуть результат", ЕГЕ даунята написали "передаётся контрольное значение"...

OrangeTank сказал(а):↑

Приветствую всех. Есть ли у кого-то информация о том, как решать 27 задание ЕГЭ по информатике эффективно по времени и по памяти? Практически не нашел бесплатного контента по этой теме

Нажмите, чтобы раскрыть...

https://www.youtube.com/watch?v=KkhgWixJ2V8
Все 5 видосов из цикла

Nightling сказал(а):↑

https://www.youtube.com/watch?v=KkhgWixJ2V8
Все 5 видосов из цикла

Нажмите, чтобы раскрыть...

Спасибо!

OrangeTank сказал(а):↑

https://inf-ege.sdamgia.ru/test?theme=402

Что-то вроде такого

Нажмите, чтобы раскрыть...

там же решения есть, всё что тебе надо это правильно составлять условия.

saw_tooth сказал(а):↑

Отмороженное существо писало задачу.

- различных переданных - это каких?

- причем тут удваивать - уже ж написали различных?

- наибольшее число R - по отношению к чему?

- каких помех? насколко искажены? как должна программа реагировать?

жаль школяров, прям до глубины души, но я бы просто уринотерапию приписал бы творцам сего шедевра.

Ответ на вопрос ТС, лежит в самом вопросе, но:

А. сохранение в массив задача ЗАВЕДОМО проигрышная по памяти, а учитывая что в масиве прийдется вести поиск, или фортировку, то она так же проигрышная по сложности - О(N log N), и это в лучшем случае.

Б. очевидно программа должна последовательно обрабатывать входящие данные, то есть на каждый елемент, в таком случае мы получим O (n), причем абсолютно стабильный.

Решение:

функция счетчкик, принимает на вход стек-массив (можно использовать замыкания например), текущее значение.

R = -1, Max_1 = 1, Max_2 = 1

сравниваем текущее значение, с нулевым R (изначально -1), если больше. Max_1 = текущему,

сравниваем max_1 и max_2, если меньше (не строго) max_2 не трогаем - иначе перезаписываем.

По концу у нас будет максимальное и предыдущее значение.

Сравниваем с контрольной R, (ну там четность проверям и т.п.)

UPD. только посмотрев видео понял, что нормальное человеческое предложение "программа должна вернуть результат", ЕГЕ даунята написали "передаётся контрольное значение"...

Нажмите, чтобы раскрыть...

Это задания и я также решал. Там есть намного сложнее задания на нахождение максимальный суммы среди всех пар, которая делится на какое-то число

В эти задания льют слишком много воды, чтобы как можно дольше времени уходило только на формулировку задачи. Насколько я понимаю нужно просто перебирать все варианты пар чисел, суммировать их, если сумма нечетная сравнивать с R?

Ну это самое очевидное что в голову пришло, можно придумать еще приколов чтобы меньше действий ушло на перебор. (ну не факт)