Структура данных - массив. Часть 1 - 13 стр.

UptoLike

ВУЗ: 

ЮФУ | Ростов-на-Дону

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

Рубрика: 

13
Выходные данные
: если a[i]=x, то i является найденным но-
мером, в противном случае
x∈(a[i];a[i+1]), 1≤i<n,
Метод решения.
Приведем математическое определение упорядоченности по не-
убыванию элементов массива
a[1..n]:
(∀i:1≤i<n:a[i]≤a[i+1])
Для упорядоченного массива удобно ввести ограничение:
a[1]≤ x <a[n].
Тогда то значение x, которое требуется найти удовлетворяет условию:
(1≤i<n)and(a[i]≤x<a[i+1]).
Это значит, что если a[i]=x, то i является найденным номером,
в
противном случае x∈(a[i];a[i+1]), 1≤i<n,
то есть пока (i+1<n)and(a[i+1]≤x), продолжаем поиск i:=i+1.
Условие a[i+1]≤x использует упорядоченность массива, ограниче-
ние a[1]≤ x <a[n] позволяет упростить логическое выражение в заго-
ловке цикла, тогда получим : пока
a[i+1]≤x , продолжаем поиск.
Описание алгоритма.
if (a[1]≤x) and (x<a[n]) then
begin
i:=1;
while (a[i+1]≤x) do
i:=i+1;
end;
Опишем алгоритм в виде функции search_Lin.
сonst n_max=20;
type vect=array[1..n_max] of integer;
function search_Lin(n:integer; const a:vect;
x:integer):integer;
var i:integer;

Страницы