Однопроходные алгоритмы

Содержание

Слайд 2

План работы

Лекция , задачи
Контест (solomon.mesi.ru)
Дорешивание
Зачет

План работы Лекция , задачи Контест (solomon.mesi.ru) Дорешивание Зачет

Слайд 3

Что же лучше???

Что же лучше???

Слайд 4

Суть программирования

Суть программирования

Слайд 5

Однопроходные алгоритмы

Если последовательность можно не хранить – ее хранить не нужно!

Однопроходные алгоритмы Если последовательность можно не хранить – ее хранить не нужно!

Слайд 6

Простая задача

Определите среднее арифметическое элементов последовательности, завершающейся числом 0.

Простая задача Определите среднее арифметическое элементов последовательности, завершающейся числом 0.

Слайд 7

Задача А

Для настольной игры используются карточки с номерами от 1 до N.

Задача А Для настольной игры используются карточки с номерами от 1 до
Одна карточка потерялась. Найдите ее, зная номера оставшихся карточек.
Дано число N, далее N-1 номер оставшихся карточек (различные числа от 1 до N). Программа должна вывести номер потерянной карточки.

Слайд 8

Задача B

У меня в прихожей стоят в ряд 20 тапочек –

Задача B У меня в прихожей стоят в ряд 20 тапочек –
10 левых и 10 правых. Приходя домой, я переобуваюсь и выбираю два тапочка – левый и правый, в которые мне удобнее всего засунуть ноги. Естественно, что левый тапочек должен стоять левее правого, и расстояние (количество других тапочек) между ними должно быть как можно меньше.
Напишите программу, которая вычисляет, сколько же тапочек стоит между теми, которые мне удобнее всего надеть.
Вводится последовательность из 10 нулей и 10 единиц, записанных в некотором порядке. Единица соответствует левому тапочку, 0 – правому тапочку. Числа разделены пробелами.
Программа должна вывести количество тапочек между самыми удобными тапочками, или -1, если таких нет.

Слайд 9

Задача C

Спортсмен Василий участвовал в соревнованиях по хоккейболу и получил в

Задача C Спортсмен Василий участвовал в соревнованиях по хоккейболу и получил в
личном зачете серебряную медаль. Известно, что участники, получившие одинаковое количество очков, награждаются одинаковыми наградами. Известно, что были разыграны золотые, серебряные и бронзовые медали. В задаче не спрашиваются правила хоккейбола. Необходимо только определить, сколько очков набрал Василий. Формат входного файла
На первой строке дано число N (2 ≤ N ≤ 1000) количество спортсменов, участвовавших в соревнованиях, на второй N целых чисел – результаты через пробел.
Требуется вывести одно число – результат Василия

Слайд 10

Задача D. Праздничные дни

5 - + + + -
0 3 0 0

Задача D. Праздничные дни 5 - + + + - 0 3 0 0 0
0

Слайд 11

Задача D

Дано N целых чисел. Требуется выбрать из них три таких числа,

Задача D Дано N целых чисел. Требуется выбрать из них три таких
произведение которых максимально.
Во входном файле записано сначала число N— количество чисел в последовательности
(3≤N≤10^6). Далее записана сама последовательность: N целых чисел, по модулю не превышающих 30000.
В выходной файл выведите три искомых числа в любом порядке. Если существует несколько различных троек чисел, дающих максимальное произведение, то выведите любую из них.

Слайд 12

Задача E

Дана последовательность целых чисел. Найти отрезок этого массива с максимальной суммой.

Задача E Дана последовательность целых чисел. Найти отрезок этого массива с максимальной

Входные данные В первой строке дано натуральное число n (1 ≤ n ≤ 10^5 ) — размер массива. Во второй строке через пробел перечислены элемента массива. Числа не превышают 10^4 .
Выходные данные. Выведите три числа — индекс начала отрезка, индекс конца и саму максимальную сумму. Массив индексируется с единицы. Если ответов несколько — выведите любой.
Имя файла: Однопроходные-алгоритмы.pptx
Количество просмотров: 38
Количество скачиваний: 0