Статья Автор: Лебедев Дмитрий

Вопросы_Линейный поиск

Вопрос 1
Линейный алгоритм.  Решение задачи о поиске максимальной разности.
Задача. Дан массив a0, a1,…an−1. Необходимо выбрать в нём два элемента ai и aj такие, что:

  • i<j  

  • разность (aj−ai) максимальна.
Ссылка на видеоразбор
https://youtu.be/tmoyNffkc1g

Вопрос 2.
Линейный алгоритм. Префиксные суммы. Решение задачи о запросе суммы на отрезке.
Задача.
Пусть дан массив a0, a1, … an−1. В элементах массива записано количество осадков,
выпавших в моменты времени 0, 1, ..,n−1.
Необходимо ответить на m запросов о количестве осадков, выпавших с i-го по j-й момент времени (1≤i≤j≤n).
Формулируя задачу более строго, необходимо уметь отвечать на запросы суммы элементов массива на отрезке c [i;j].
Ссыллка на разбор задачи
https://youtu.be/4cATnSzX3F0
 

Вопрос 3.
Линейный поиск. Использование двух указателей. Решение задачи поиска отрезка с максимальной суммой.
Задача. "Отрезок с максимальной суммой"
Дан массив a0, a1, .... an−1. Требуется найти отрезок массива с индексами с i по j (i≤j) такой, что
сумма элементов ai+ai+1+...+aj максимально возможная.
Ссылка на разбор задачи
https://youtu.be/5gm6HkYzws0
Ссылка на задачу
https://www.silvertests.ru/OlympTask.aspx?Id=42853

Вопрос 4.
Линейный поиск. Метод двух указателей. Отрезок с заданной суммой.
Задача.
Необходимо найти непрерывный отрезок массива a0, a1, ... an−1,
сумма элементов на котором равна k. Элементы массива неотрицательны.
Ссылка на разбор задачи
https://youtu.be/TC2XhiKV9Mc

Вопрос 5
Линейные структуры данных. Стек как абстрактный тип данных.
Задача о правильной скобочной последовательности.
Задача. Правильная скобочная последовательность
Пусть нам дана последовательность из трёх видов скобок: (), [], {}.
Необходимо проверить, является ли она правильной. Правильной является последовательность,
которая может возникнуть при записи некоторого арифметического выражения.
Пример правильной последовательности: ([]())[]
Ссылка на разбор вопроса
https://youtu.be/4cATnSzX3F0
Ссылка на задачу
https://www.silvertests.ru/OlympTask.aspx?Id=38597
 

Вопрос 6.
Линейные структуры данных. Стек как абстрактная структура данных.

Стек с поддержкой минимального элемента
Реализовать стек, который будет содержать ещё одну операцию — "узнать значение наименьшего элемента во всём стеке".
Это так называемый "стек с минимумом".

Задача «Шарики». В одной компьютерной игре игрок выставляет в линию шарики разных цветов.
Когда образуется непрерывная цепочка из трех и более шариков одного цвета, она удаляется из линии.
Все шарики при этом сдвигаются друг к другу, и ситуация может повториться.
Напишите программу, которая по данной ситуации определяет,
сколько шариков будет "уничтожено". Естественно, непрерывных цепочек из трех и
более одноцветных шаров в начальный момент может быть не более одной.
Входные данные
Сначала вводится количество шариков в цепочке (не более 1000) и
цвета шариков (от 0 до 9, каждому цвету соответствует свое целое число).
Выходные данные
Требуется вывести количество шариков, которое будет "уничтожено".
Ссылка на теорию
https://youtu.be/Th3gt1Ox35E
Ссылка на задачу
https://www.silvertests.ru/OlympTask.aspx?Id=44039

Вопрос 7
Линейные структуры данных. Очередь как абстрактная структура данных.
Возможные способы реализации очереди.
Задача «Раздача подарков».
Громозека раздавал N земным детям, стоящим по кругу, привезенные подарки.
Чтобы не было никому обидно, Громозека решил, что будет каждый раз давать подарок K-му ребенку.
Ребенок, получивший подарок с радостью выбегал из круга, а все остальные смыкали круг. 
Определите, в каком порядке дети получали подарки.
Входные данные
Входная строка содержит натуральные числа N и K, разделённые пробелом.
Выходные данные
Программа должна вывести в одну строку, через пробел, номера ребят в том порядке, как они получают подарок.

Ссылка на теорию
https://youtu.be/Mki8RRLciXI
Ссылка на задачу
https://www.silvertests.ru/OlympTask.aspx?Id=39396
Пропустить Навигационные Ссылки.
Чтобы оставить комментарий нужна авторизация
Печать