2Б /. Фундаментальные с-гууму^

. . . >

же базовому типу В, мы получим

сагШпа1иу(Л) = (саг(1таШу(В)) (1.1(

где и = cardinality(/), а / - тип индексов массива,

В следующем небольшом фрагменте программы показан использование селектора для массива. Цель этой nporpat мы - найти наименьший индекс i компоненты со значением, Поиск выполняется с помощью последовательного просмотр массива а, описанного как

var а: аггау[1..Л'] of Т\ {iV > 0}

repeat i := i + luntil (a [/] = x) V (/ = Щ\

-- if j3LijMhen e a нет такого элемента

В другом варианте этой программы применяется распре страненный прием фиктивного элемента, или барьера, распс ложенного в конце массива. Использование барьера позвв i ляет упростить условие окончания цикла:

varo;: array[l..iV+ 1] of Г;

a[N+\]:x; repeat г :=/+1 until аИ = д;; \

if i> N then e a нет такого элемента

Присваивание а(Л'+1]:=д: является примером выбора ного изменения, т. е. изменения отдельной компоненты a ставной переменной. В обеих версия.х (1.15) и (1.16) ochoi* ным условием, выполняющимся вне зависимости от тог сколько раз выполняется оператор г:=/+1, является

[/] ¥= X для / = 1 ... / - I

Поэтому оно называется инвариантом цикла.

Разумеется, поиск можно значительно ускорить, если ко; поненты уже упорядочены (рассортированы). В этом слуФ чаще всего применяется метод повторного деления попола интервала, в котором ищется нужный элемент. Такой прие называется методом деления пополам или бинарным пои ком, он показан в программе (1.17). При каждом noBTopefii просматриваемый интервал между индексами i и / делиТ1 пополам. Поэтому максимальное число требующихся сра нений равно Ilog2(A)].

repeat к (i+J) div 2; ц f

if л: > a[k] then i k+l elsey := k~l mtil ia[k]x) V Q>J)

Соответствующим инвариантным условием выхода из цикла (Ляется a[h]<x для ~ а[1г]X для h = j+l ... Л'

ледовательно, если программа заканчивается при а [h] Ф *, ) не существует a[h] - х для 1 Л Л'.)

Компоненты массива могут в свою очередь быть составами. Переменная-массив, компоненты которой являются ассивами, называется матрицей. Например,

М:аггау[1 .. lO]oiRow

-это массив, состоящий из десяти компонент (строк), каж-ая из которых состоит из пяти компонент вещественного та. Этот массив называется матрицей 10X5 с веществен-ыми компонентами. Селекторы могут соответствующим об-азом следовать один за другим, так что

М [/][/]

бозначает j-ю компоненту строки M[i], являющейся i-й ком-онентой М. Обычно это записывается короче, как

M[i,j]

точно так же описание

М: array [I .. 10] of array [I .. 5] of real

южно записать проще, как

М:array[1 .. 10, 1 .. 5]ofreaZ .

Если нужно выполнить некоторое действие со всеми ком-юнентами массива или с расположенными подряд компонеи-ами какой-то части массива, то для этого удобно использовать оператор цикла, как показано в следующем примере.

Пусть дробь / представляется с помощью массива d, так,

/==Е rf/*io-

- е. в десятичном виде с k-l цифрами. Теперь пусть f УЖно разделить на 2. Для этого обычную операцию деления Производят, со всеми k-1 цифрами di, начиная с / = 1. При том деление цифры на 2 выполняется с учетом возможного Переноса из предыдущей, позиции, и. на следующий шаг

80 1. Фундаментальные структуры vuhhmx

.------ s

передается возможный остаток (см. 1.18)

г := 10*r+d[iy,

4,]:= г div 2; (11

г := r-2*d[i]

Этот процесс используется в программе 1.1 для получени; таблицы отрицательных степеней 2. Оператор цикла удобН| использовать также и для деления пополам при вычислени 2-\ 2-2, 2- ; таким образом получается вложенносц двух операторов цикла.

prtrampower (output);

{десятичное представление отрицательных степеней двойки]

eeastM = 10; --

type digit = О.. 9; таг i,k,r: integer;

d: array [1 .. n] of digit; .

begin for A: := 1 to и do bin wnYe(.); r := 0; fori := 1 tofc-1 do begin 10*r+d[i]; di\: r div 2;

r := r-2*d[i]; write{chr{d{i]-\-ordQ(f)))

end;

dik\ := 5; writeh{Ъ')

end end .

Программа 1.1. Вычисление степеней двойки.

Результат для п = 10 имеет вид

- .25

.125 .0625

.03125 ...

.015625 . .

.0078125

.00390626

.001953126

.0009765626

1.7. ЗАПИСИ

Самый общий метод получения составных типов - at объединение компонент, принадлежащих к произвольны^ возмодкно, тоже составным тша.щ в один составной тип. При