Н. Вирт - Программирование на языке Модула-2 (1160777), страница 9
Текст из файла (страница 9)
приусловии, что а[i-1] <= a[i] для всех i = 1... N-l. Лучший метод - это так называемый двоичныйпоиск: проверить средний элемент массива, а затем применить этот же метод к левой или правой37половине. Этот алгоритм реализует следующий далее фрагмент программы (предполагается, что N> 0). Инвариантами цикла являются условия (а[к] < х для всех к = 0...i-1) и (а[к] > х для всех к j+1...N-1)1 := 0; j := N-1; найден := FALSE;REPEAT центр := (i + j) DIV 2;IF x < а[центр] THEN j := центр - 1ELSIF x > а[центр] THEN i := центр + 1ELSE найден := TRUEENDUNTIL (i > j) OR найденПоскольку каждый шаг делит интервал поиска пополам, то число необходимых сравненийравно всего лишь los2(N). Приведем другую, более эффективную версию, исключающуюсоставное условие завершения.i := 0; j := N-1;REPEAT центр := (1 + J) DIV 2:IF x <+ а[центр] THEN j := центр - 1 END;IF x >= а[центр] THEN i := центр + 1 ENDUNTIL i > j; IF i > j+1 THEN найден ELSE не найден ENDНиже приведена еще более изощренная версия.
Ее основная идея - не прекращать поисксразу, как только элемент найден, поскольку это довольно редкое событие по сравнению с числомбезуспешных проверок.1 : = 0; j := N-1;REPEAT центр := (i + j) DIV 2;IF x < а[центр] THEN j := центрELSE i := центр + 1ENDUNTIL i >= jНа этом завершим список примеров использования простых массивов. Все элементымассива имеют одинаковый тип, однако сам элемент может быть в свою очередь массивом(фактически, как мы увидим далее, это может быть любой структурированный тип). Массивмассивов называется многомерным массивом или матрицей, поскольку можно, считать, чтокаждый индекс соответствует одному измерению в декартовом пространстве. Вот примерыдвумерных массивов:a: ARRAY [l.
.N], [t. .N] OF REALT: ARRAY [0. .M-1], [0. .N-1] OF CHARпредставляющие собой сокращение следующих полных Форм:a: ARRAY [1..N] OF38ARRAY [1..N] OFREALT: ARRAY [0..М-1] OFARRAY [0. .N-1] OFCHARОтступы используются, чтобы отразить иерархическую структуру описания. Общийсинтаксис типа массив таков:$ ТипМассив = "ARRAY" ПростойТип {"," ПростойТип}$"OF" Тип.Здесь простой тип, обозначающий диапазон индексов, имеет либо вид"[" КонстВыражение ".." КонстВыражение "]"либо является идентификатором. Например, описание массиваmap: ARRAY[" ".."~"] OF CARDINALвводит массив из 95 чисел типа CARDINAL, причем каждый элемент индексируетсяграфической литерой, как это показано в следующих операторах:map["А"] := 0; k := map["+"]Синтаксис обозначений допускает сокращение, аналогичное сокращениям в описаниях:можно писать a[i,j] вместо a[i][j].
Однако последняя Форма отчетливее выражает тот Факт, что [J]является индексом массива а[i]. Синтаксис обозначения элемента массива:$ Обозначение - КвалИдент {"[" СписВыражений "]"}.$ СписВыражений - Выражение {"," Выражение}.При работе с матрицами оператор цикла с шагом демонстрирует все свои преимущества,особенно в числовых применениях. Канонический пример - перемножение двух матриц, гдекаждый элемент произведения с - а*Ь определяется какc[i,j] = a[i,1]*b[l,j] + a[i,2]*b[2,j] + ......
+ a[i,N]*b[N,j]Пусть имеются описанияa: ARRAY [1..М], [1..К] OF REAL:b: ARRAY [1..K],[1..N] OF REAL:с: ARRAY [1..Ml,I1..N] OF REALАлгоритм умножения состоит из трех вложенных друг в друга цикловFOR i := 1 ТО М DOFOR j := 1 ТО N DOсумма := 0.0;39FOR k := 1 ТО К DOсумма := a[i,k]*b[k,j] + суммаEND;c[i,j] := суммаENDENDВо втором примере мы демонстрируем поиск слова в таблице. Каждое слово в таблице массив литер.
Предполагаем, что таблица Т описана так же, как в одном из приведенных вышепримеров, а х задан следующим образом:х: ARRAY [0..N-1] OF CHARНаше решение использует типичный линейный поиск:i := 0; найден := FALSE; WHILE ~найден&(1 < М) DOнайден := "Т[i] равен х"ji := i + 1ENDЕсли определить равенство двух слов х и у как x[j] = у[i] для всех j = 0...N-1, то можновыразить "внутренний" поиск в таком виде:j := 0; равно := TRUE;WHILE равно&(j < N) DOравно := T[i,j] = x[j]; j := j + 1END;найден := равноЭто решение выглядит довольно неуклюжим, однако в случае М > 0 и N > 0 его можнопреобразовать в более простую Форму. Окончательный вариант алгоритма поиска в таблицеможно записать так:i := 0:REPEAT j := 0;REPEAT В := T[i,j] # x[j]; j := j + 1UNTIL В OR (j = N);i := i+lUNTIL NOT В OR (i = M)Значение логической переменной В в конца фрагмента имеет следующий смысл: "слово хне найдено". Мы провели достаточную подготовительную работу для разработки содержательныхзавершенных программ.
Здесь будет представлено три примера полностью завершенныхпрограмм, причем все они содержат массивы. В первом примере задача состоит в печати спискастепеней40двойки, причем каждая строка должна содержать величины 2^i, i, 2^(-i). Эта задача былабы очень простой, если использовать тип REAL. Тогда ядро программы выглядело бы так:d := 1; f := 1.0;FOR exp := 1 ТО N DOd := 2*d; печать(d); (* d = 2^exp *)печать(ехр);f := f/2.0; печать(f) (* f = 2^(-exp) *)ENDОднако мы хотим получить точные результаты с тем количеством цифр, котороепотребуется.
По этой причине мы представляем и целое число d = 2^ехр, и дробь f = 2^(-ехр)массивами "цифр", каждая из которых лежит в диапазоне 0...9. Для представления f нампотребуется N иифр, для d - только логарифм от N. Отметим, что удвоение d производится справаналево, а деление f пополам - слева направо. Таблица результатов приведена ниже.MODULE СтепениДвойки:FROM InOuL IMPORT Write,WriteLn,WriteString,WriteCard;CONST M = 11; N = 32; (* M ~ N*log(2) *)VAR i,j,k,exp: CARDINAL;c,r,t: CARDINAL:d: ARRAY [0..M] OF CARDINAL:f: ARRAY [0..N] OF CARDINAL:BEGINd[0] := 1; k := 1;FOR exp := 1 TO N DO(* вычислить d = 2^exp операциями d := 2*d *)с := 0; (* перенос *)FOR i := 0 TO k-1 DOt := 2*d[i] + c:IF t >= 10 THENd[i] := t - 10; с := 1ELSEd[i] := t; c := 0ENDEND;41IF с > О THENd[k] := 1; k := k + 1END:(* вывод d[k-1]...d[0] *) i := М;REPEAT i := i - 1; Write(" ") UNTIL i = k;:REPEAT i := i - 1; Write(CHR(d[i]+ORD("0")))UNTIL i = 0;WriteCard(exp,4);(* вычисление f = 2^(-exp) операциями f := f DIV 2и его вывод *)WriteString(" 0."); r : = 0; (* остаток *)FOR j := 1 ТО ехр-1 DOr := 10*r + f[j]; f[j] := r DIV 2:r := r MOD 2; Write(CHR(f[j]+ORD("0")))END;f[ехр] := 5; Write("5"); WriteLnENDEND СтепениДвойки.Вывод программы СтепениДвойки.21 0.542 0.2583 0.125164 0.0625325 0.03125646 0.0156251287 0.00781252568 0.003906255129 0.001953125102410 0.0009765625204811 0.00048828125409612 0.00024414062542819213 0.00012207031251638414 0.000061035156253276815 0.0000305175781256553616 0.000015258789062513107217 0.0000076293945312526214418 0.00000381469726562552428819 0.0000019073486328125104857620 0.00000095367431640625209715221 0.000000476837158203125419430422 0.ООО0ОО2384185791О15625838860823 0.0000001192092895507812516777216 24 0.00000005960464477539062533554432 25 0.000000029802322387695312567108864 26 0.00000001490116119384765625134217728 27 0.000000007450580596923828125268435456 28 0.0000000037252902984619140625536870912 29 0.000000001862645149230957031251073741824 30 0.0000000009313225746154785156252147483648 31 0.00000000046566128730773925781254294967296 32 0.00000000023283064365386962890625Наш второй пример имеет аналогичную природу.
Задача - точно вычислить десятичныедроби d - 1/1. Трудность заключается, конечно, в представлении дробей, которые являютсябесконечными последовательностями цифр (например, 1/3 = 0.333...). К счастью, все дроби имеютповторяющийся период, и было бы разумно и полезно отмечать начало периода и завершатьвычисление в его конце.
Но как находить начало и конец периода? Рассмотрим сначала алгоритмвычисления цифр дроби.Начиная с остатка ост = 10, мы повторяем умножение его на 10 и делим произведение на i.Частное от деления нацело - это новое значение для ост. Этот алгоритм в точности воспроизводитстандартный метод деления, что иллюстрируется следующим Фрагментом программы и числовымпримером при i = 7.1.000000 / 7 = 0.142857103020604043501ОСТ :- 1;REPEAT ост := 10*ост;СледЦиФра := ост DIV i;ост : = ост MOD 1UNTIL ...Мы знаем, что период завершится, как только получится остаток, который встречалсяранее.
Поэтому наш способ - запоминать остатки и их индексы. Индексы обозначают то место,откуда начинается период. Обозначим массив индексов через х и дадим его элементам начальныезначения 0. Индексация массива ведется по значениям остатков. В рассмотренном выше примеределения на 7 величины индексов следующие: х[1]=1, х[2]=3, х[3]=2, х[4]=5, х[5]=6, х[6]=4.MODULE Дроби;FROM InOut IMPORT Write,WriteLn,WriteString,WriteCard;CONST Основание = 10; N = 32;VARост: CARDINAL;i,j,m:CARDINAL;d:ARRAY[1..N]OFCARDINAL;(*цифры*)x:ARRAY[0..N]OFCARDINAL;(*индекс*)BEGINFORi:=2TONDOFORj:=0TOi-1DOx[j]:=0END;m:=0;ост:=1;REPEATm:=m+1;х[ост]:=m;ост:=Основание*ост;d[m]:=остDIVi;ост:=остMODiUNTIL х[ост] # 0;WriteCard(i,6);WriteString("FOR j := 1 TO х[ост]-1 DO Write(CHR(d[j]+ORD("0"))) END;0.");Write("'");FORWriteLnENDEND Дроби.j:=х[ост]TOmDOWrite(CHR(d[j]+ORD("0")))END;Вывод программы Дроби.2 0.5'0 З 0.'З4 0.25'05 0.2'0446 0.1'67 0.'1428578 0.125'09 0.'1 10 0.1'0 11 0.0812 0.08'313 0.'07692314 0.0'71428515 0.0'616 0.0625'017 0.'058823529411764718 0.0'519 0.'05263157894736842120 0.05'0 21 0.'04761922 0.0'4523 0.'043478260869565217391324 0.041'625 0.04'026 0.0'38461527 0.'03728 0.03'57142829 0.'034482758620689655172413793130 0.0'331 0.'03225806451612932 0.03125'0В последнем примере рассмотрим программу печати списка простых чисел.
Онаосновывается на проверке делимости последовательных целых чисел. Проверяемые целые числаполучаются увеличением предыдущего числа по очереди на 2 и на 4. тем самым сразу отсекаютсячисла, кратные 2 и 3. Необходимо проверять делимость только на простые числа, которые былиуже ранее вычислены и запомнены.MODULEFROM InOut IMPORT WriteLn,WriteCard;CONSTN=250;M=LL = 8; (* сколько простых чисел печатать на строке *)ПростыеЧисла:16;(*M^2~N*)45VARшаг,граница,квадрат,L:простое:P,V:ARRAYBEGINLx:=1;шаг:=4;FORi:=(*найтиследующееREPEATx:=x+IF квадрат <= х THENграницаквадратEND;k:-[0..M]граница3простоешаг;граница:-:=простое:=V[k]:=WHILEkIFV[k]ENDi,k,x:+1;2;&OF:=:=1:TOчислошаг:=V[гpaница]:квадрат;Р[граница+1]*Р[граница+1]простое(k:=граница)<k<V[k]простоеCARDINAL;CARDINAL;BOOLEAN;CARDINAL;0;квадрат:=9;NDOР[i]*)6шаг;+x+:=x#TRUE;DO1;THEN2*P[klV[k]ENDUNTIL простое:IFiWriteCard(x,6);IFWriteLn;ENDENDEND ПростыеЧисла.<=MLLTHEN:=Р[i]L:=LL:=Lх+END;1:THEN0Вывод программы ПростыеЧисла.57111317 19 23293137414347 53 59616771737983 89 97101103107109113127 131137139149151157163167 173179181191193197199211 223227229233239241251257 263269271277281283293307 311313317331337347349353 359367373379383389397401 409419421431433439443449 457461463467479487491499 50350952146523541547557563 569571577587593599601607 613617619631641643647653 659661673677683691701709 719727733739743751757761 769773787797809811821823 827829839853857859863877 881883887907911919929937 941947953967971977983991 9971009101310191021103110331039 10491051106110631069108710911093 10971103110911171123112911511153 11631171118111871193120112131217 12231229123112371249125912771279 12831289129112971301130313071319 13211327136113671373138113991409 14231427142914331439144714511453 14591471148114831487148914931499 15111523153115431549155315591567 15711579158315971601Эти примеры завершают первую часть книги.Они показывают, что массивыявляются фундаментальным средством, используемым в большинстве программ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
