Основы визуальной алгоритмизации. Афанасьева Т.В. - 39 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

3
9
Второе деление S=8, А(8)=30 А(8)>Х), исключаем правую половину.
Элементы массива А (2,3,4,6,10,12,20,30,35,45).
Номера элементов 1234 5 6 7 8910.
Третье деление S=6, А(6)=12 А(6)=Х), элемент Х=12 найден.
Рис.30. Иллюстрация применения метода бинарного поиска
На рис.31 представлен алгоритм, реализующий метод бинарного поиска в
упорядоченном массиве.
Рис.31.Алгоритм поиска методом бинарного поиска
Задания для самостоятельного выполнения
Составить визуальные циклические алгоритмы для следующих задач обра-
ботки упорядоченных одномерных массивов.
1. Ввести упорядоченный по неубыванию массив Х(1) < = Х(2) < =…Х(n).
Найти количество различных чисел среди элементов этого массива.
2. Ввести два упорядоченных по возрастанию числовых массива
Х(1)<Х(2)<Х(3) <…Х(n) и Y(1)<Y(2)<…Y(m). Найти количество общих элементов в этих массивах, то
есть количество К таких чисел X( i )= Y( j ).
3. Известно, что некоторое число содержится в каждом из трех целочисленных неубывающих массивов
Х(1) < = Х(2) < =…Х(n), Y(1)< =Y(2)< =…Y(m) и
Z(1)<=Z(2)<=…Z(k).Найтиодноизэтихчисел.
4. Вставить значение Р в упорядоченный неубыванию массив Х(1) < = Х(2) < =…Х(n) так, чтобы упорядо-
ченность не нарушилась.
5. Удалить значение Р в упорядоченный неубыванию массиве Х(1) < = Х(2) < =…Х(n).
6. Соединить два упорядоченных массива Х(1) < = Х(2) < =…Х(n) и Y(1)< =Y(2)< =…Y(m) в массив Z(1) <
=Z(2)<=…Z(k),при этом каждый элемент должен входить в массив Z столько раз, сколько раз он
входит в массивы
ХиY.
+
+
+
НАЧАЛО
ВВОД N,X
A(1..N)
P=1, Q = N
Р
<
Q
S=(P+Q) DIV 2
КОНЕЦ
A(S)=X
A(S)<X
P=S+1
НАЙДЕ-
НО,S
Q=S+1
В этом алгоритме Х - искомое значение,
P, Q - номера первого и последнего эле-
мента усеченного
массива. S=(P+Q) DIV 2 - операция деле-
ния нацело массива пополам.S-резуль-
тат, номер совпавшего элемента массива
ЗНАЧЕНИЕ НЕ
НАЙДЕНО

Страницы