Упражнения. 1. На основании приведенных в лекции функций реализуйте алгоритмы последовательного и бинарного поиска

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

2. В связи с визитом Императора Палпатина было решено обновить состав дроидов в ангаре 32. Из-за кризиса было решено новых дроидов не закупать, но выкинуть пару старых. Как известно, Палпатин не переносит дроидов с маленькими серийными номерами, так что все, что требуется – найти среди них двух, у которых серийные номера наименьшие.

Формат входного файла

Первая строка входного файла содержит целое число N – количество дроидов. (2 ≤ N ≤ 1000), вторая строка – N целых чисел, по модулю не превышающих – номера дроидов.

Формат выходного файла

Выведите два числа: первым – последний по величине из номеров дроидов (такого следует утилизировать в первую очередь), а вторым – предпоследний.

Пример входного файла

49 100 23 -100 157

Пример выходного файла

-100 23

Пример входного файла

99 1 5 1

Пример выходного файла

1 1

3. Некто загадал число от 1 до N. За какое наименьшее количество вопросов (на которые он отвечает «да» или «нет») можно угадать задуманное число?

Формат входных данных

Вводится одно число N (1 < N < 10001).

Формат выходных данных

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

Пример входного файла

Пример выходного файла

4. Задана матрица K, содержащая n строк и m столбцов. Седловой точкой этой матрицы назовем элемент, который одновременно является минимумом в своей строке и максимумом в своем столбце. Найдите количество седловых точек заданной матрицы.

Формат входного файла

Первая строка входного файла содержит целые числа n и m (1 ≤ n, m ≤ 750). Далее следуют n строк по m чисел в каждой. j -ое число i -ой строки равно . Все по модулю не превосходят 1000.

Формат выходного файла

В выходной файл выведите ответ на задачу.

Пример входного файла

2 2

0 0

0 0

Пример выходного файла

Пример входного файла

2 2

1 2

3 4

Пример выходного файла

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

Формат входного файла

На первой строке дано число N (2 ≤ N ≤ 1000) количество спортсменов, участвовавших в соревнованиях, на второй N целых чисел – результаты через пробел.

Формат выходного файла

Требуется вывести одно число – результат Василия.

Пример входного файла

4 3 3 1 2

Пример выходного файла

Пример входного файла

1 2 5 3 5 1 1 6

Пример выходного файла

Литература

1. Ахо А., Хопкрофт Дж., Ульман Д. Структуры данных и алгоритмы. Уч. пособие. — М.: Вильямс, 2000. – 384с.

2. Кнут Д.Э. Искусство программирования. Том 3. Сортировка и поиск, 3-е изд.: Пер. с англ.: Уч. пос. – М.: Вильямс, 2000. – 832 с.

3. Кормен Т., Леверсон Ч.., Ртвест Р. Алгоритмы. Построение и анализ. — М.: МЦНМО, 1999. – 960 с.

4. Подбельский, В.В. Программирование на языке Си: учеб. пособие / В.В. Подбельский, С.С. Фомин. – М.: Финансы и статистика, 2004. – 600 с.

5. Подбельский, В.В. Язык Си++: учеб. пособие / В.В. Подбельский. – М.: Финансы и статистика, 2005. – 560 с.

6. Сэджвик Р. Фундаментальные алгоритмы на С++. Части 1-4. Анализ, структуры данных, сортировка, поиск. — М.: Диасофт, 2001. – 687 с.

7. Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си. Учебное пособие. – М.: Финансы и статистика, 2004. – 464 с.

Дата добавления: 2014-01-04