Язык программирования Pascal. Регулярные типы данных. Васильев В.В - 12 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

12
writeln('Искомый элемент найден под номером ',k)
end
else writeln('Искомый элемент не найден :(');
readkey;
End.{Bin_search}
Рассмотрим задачу, для решения которой потребуется упорядочить часть
массива исходных данных .
Задача 6. Пусть даны вещественные числа
aaa
n122
,,...,
. Эти точки опре-
деляют n интервалов числовой оси
(
)
aa
12
,
,
(
)
aa
34
,
, … ,
(
)
aa
nn212−
,
. Является ли
интервалом объединение этих интервалов? Если да, то указать концы объеди -
ненного интервала.
♣ При решении задачи будем считать , что
∀
<
++
iaa
ii2122
,
in
=
−
011,,...,
(у любого интервала левый конец меньше правого ). Переставим в массиве A,
состоящем из
aaa
n122
,,...,
, интервалы так, чтобы все левые концы интервалов
были расположены по возрастанию . Упорядочивать левые концы будем мето-
дом выбора с отысканием минимальных элементов и перестановки их в начало
неупорядоченной части массива.
Интервал
(
)
de,
будем считать объединенным интервалом. На первом шаге
положим, что
de,
=
(
)
~
,
~
aa
12
- первый отрезок частично упорядоченного мас-
сива А . Попробуем объединить
(
)
de,
со вторым интервалом. Для этого прове-
рим, что начало второго интервала не выходит за конец первого, т.е.
ae
3
<
(в
противном случае объединение интервалов не является интервалом). В каче-
стве конца объединенного интервала выберем наибольший из концов первого
и второго интервалов, т.е.
eea
=
max(,)
3
. Затем пробуем объединить
(
)
de,
со
третьим интервалом и т. д.
Для реализации описанной идеи нам потребуется цикл , в котором для 2-
го, 3-го, ..., n-го интервалов мы проверим, что их левые концы не выходят за
правый конец объединенного интервала (в противном случае объединение ин-
тервалов не является интервалом), т.е.
∀
=
−
<
inae
i
3521,,...,
. Правым кон -
цом объединенного интервала будем считать наибольший из правых концов
интервалов, т.е. наибольшее из чисел
e
и
a
i+1
.
Переменные i, j используются как параметры циклов. n – количество ин -
тервалов. а – массив из 2n вещественных чисел, концов интервалов. m – номер
очередного минимального элемента. min – значение очередного минимального
элемента. f – переменная логического типа, используемая для хранения ответа
на вопрос: “Является ли интервалом объединение данных интервалов? ” . ♣
Program Interval;
Uses crt;
Const n=5;
Var a:array[1..2*n] of real; f:boolean;

Страницы