Алгоритм 13. Поиск заданного элемента в упорядоченном по возрастанию массиве.

Нужно в массиве М определить индекс C элемента равного заданному K.

Идея: заданное число K сравнивается со средним элементом в массиве M, индекс которого C = (A+B)/2, где A и B нижняя и верхняя границы индексов в точках A =1 B=N.

Если M(C) ≠ K, то далее поиск идет в одной из половин массива M(C) в зависимости от результатов сравнения. Для этого изменяется значение или A на (C+1), или B на (C-1). Затем K сравнивается со средним элементом в соответствующей половине и т.д.

A = 1: B = N: L = 0

20 IF B < A GOTO 90

C = INT((A+B)/2)

IF M(C) = K GOTO 80

IF M(C) > K GOTO 70

A = C+1: GOTO20

70 B = C-1: GOTO 20

80 L = 1: B = A-1: GOTO 20

90 RETURN

Задача 3.

Вводится информация о 6-ти отелях с количеством посадочных мест в ресторане в каждом. Вывести название отеля с максимальным количеством посадочных мест в ресторане.

Описание алгоритма:

1. объявляем два массива: массив названий отелей NO$(6) и массив количеств посадочных мест в ресторанах в каждом K(6);

2. переменной Кmax присваиваем начальное значение, которое д.б. заведомо меньше самого малого среди заданных (в данном случае возьмем –1);

3. открываем цикл, в котором:

§ вводим название отеля и количество мест в нем;

§ ищем максимальное количество Кmax и его индекс imax, сравнивая в каждом цикле введенное значение К с Кmax - если K(g)> Kmax, то Kmax присваивается значение K(g), а его индексу gmax значение g;

§ цикл будет выполняться 6 раз;

4. после завершения цикла выводится результат - ”Максимальное количество посадочных мест ” Kmax “ в отеле ” NO$(gmax)

Рис.11. Блок-схема алгоритма решения задачи 3.

Программа

Dim NO$(6), K(6)

Kmax= -1

For g=1 To 6

Input “Отель, кол-во мест”, NO$(g), K(g)

If K(g)> Kmax Then Kmax=K(g): gmax=g

Next

Print”Максимальное количество посадочных мест ”, Kmax, “ в отеле ”, NO$(gmax)

End