|
p align="left">ПРИМЕР: Использование типизированных констант program typed_const; var N:integer; procedure Test; const k:integer=1; begin if k<N then begin writeln(k,'-й вызов процедуры'); k:=k+1; Test; end else writeln('последний вызов процедуры'); end; begin read(N); if N>0 then Test; end. МОДУЛИ Модуль (Unit) в паскале - это специальным образом оформленная библиотека определений типов, констант, переменных, а также процедур и функций. Модуль компилируется отдельно, в результате чего создается файл с расширением tpu (turbo pascal unit). Он не может быть запущен на выполнение самостоятельно, а может использоваться только из других программ. Для этого в программах указывается список имен используемых модулей в разделе Uses, после чего программа может использовать константы, типы и переменные, описанные в этих модулях. В Турбо Паскале существует несколько стандартных модулей: System, Crt, Dos, Printer, Overlay, которые составляют библиотеку Турбо Паскаля: файл turbo.tpl (turbo pascal library). К числу стандартных модулей также относится модуль Graph. Существует возможность создавать новые модули. Файл модуля имеет следующую структуру: UNIT <имя модуля>; INTERFACE <раздел объявлений> IMPLEMENTATION <раздел реализации> Begin <раздел инициализации> End. Имя модуля должно совпадать с именем файла, в котором он хранится. Раздел объявлений или интерфейсная часть содержит объявления всех глобальных объектов модуля (типов, констант, переменных и подпрограмм), которые будут доступны программам, использующим этот модуль. Подпрограммы в этом разделе объявляются только заголовками. В интерфейсной части модулей нельзя использовать опережающее описание, т.е. директиву forward. Раздел реализации или исполняемая часть модуля содержит описание локальных объектов модуля: типов, констант, переменных и подпрограмм. Здесь же содержится описание подпрограмм, объявленных в интерфейсной части. Для этих подпрограмм заголовок может указываться либо без параметров, либо с параметрами, которые в точности повторяют описание из раздела объявлений. Локальные объекты модуля доступны в пределах модуля, но не доступны программам, использующим модуль. Раздел инициализации может отсутствовать. В этом случае можно даже не писать слово Begin, а сразу завершать модуль, написав End. В раздел инициализации входят операторы, которые будут выполняться при запуске программы, использующей модуль, перед выполнением основной программы. Разделы инициализаций выполняются в том порядке, в котором подключаются модули. ПРИМЕР: Модуль для работы с одномерными массивами до 100 целых чисел. {модуль описаний, глобальных для основной программы и всех модулей} Unit Globals; Interface const Len=100; type Vector = array[1..Len] of integer; Implementation End. Unit Vectors; Interface uses Globals; {находит максимальный элемент массива} function Max_V(A:Vector; n:byte):integer; {поэлементное сложение двух векторов} procedure Add_V(A,B:Vector; n:byte; var C:Vector); {скалярное произведение векторов} function Scal_V(A,B:Vector; n:byte):integer; Implementation function Max_V; {заголовок без параметров} var i,max:integer; begin max:=A[1]; for i:=2 to n do if A[i]>max then max:=A[i]; Max_V:=max; end; procedure Add_V; var i:integer; begin for i:=1 to n do C[i]:=A[i]+B[i]; end; function Scal_V(A,B:Vector; n:byte):integer; {заголовок из interface} var s:integer; i:byte; begin s:=0; for i:=1 to n do s:=s+A[i]*B[i]; Scal_V:=s; end; End. {раздел инициализации модуля отсутствует} АЛГОРИТМЫ ПОИСКА Алгоритмы поиска применяются для нахождения, например, в массиве элемента с нужными свойствами. Обычно различают постановки задачи поиска для первого и последнего вхождения элемента. Во всех ниже изложенных алгоритмах будем считать, что производится поиск в массиве A из N целых чисел элемента, равного X. ЛИНЕЙНЫЙ ПОИСК Линейный поиск осуществляется циклом (while или repeat - until) с двойным условием. Первое условие контролирует индекс на принадлежность массиву, например, (i<=N). Второе условие - это условие поиска. В нашем случае в цикле while это условие продолжения поиска: (A[i]<>X), а в цикле repeat - until это условие завершения поиска: (A[i]=X). В теле цикла обычно пишется только один оператор: изменение индекса в массиве. После выхода из цикла необходимо проверить, по какому из условий мы вышли. В операторе if обычно повторяют первое условие цикла. Можно говорить об успешном поиске с циклом while при выполнении этого условия, а с циклом repeat - until при его нарушении. ПРИМЕР: Линейный поиск program Poisk1; var A:array[1..100] of integer; N, X, i:integer; begin read(N); {N<=100} for i:=1 to N do read(A[i]); read(X); i:=1; {i:=0;} while (i<=N) and (A[i]<>X) do i:=i+1; {repeat i:=i+1; until (i>N) or (A[i]=X);} if i<=N then write('первое вхождение числа ',X,' в массив A на ',i,' месте') else write('не нашли'); end. При поиске последнего вхождения после ввода должны идти операторы: i:=N; {i:=N+1;} while (i>=1) and (A[i]<>X) do i:=i-1; {repeat i:=i-1; until (i<1) or (A[i]=X);} if i>=1 then write('последнее вхождение числа ',X,' в массив A на ',i,' месте') else write('не нашли'); ПОИСК С БАРЬЕРОМ Идея поиска с барьером состоит в том, чтобы не проверять каждый раз в цикле условие, связанное с границами массива. Это можно обеспечить, установив в массив так называемый барьер: любой элемент, который удовлетворяет условию поиска. Тем самым будет ограничено изменение индекса. Выход из цикла, в котором теперь остается только условие поиска, может произойти либо на найденном элементе, либо на барьере. Таким образом, после выхода из цикла проверяется, не барьер ли мы нашли? Вычислительная сложность поиска с барьером меньше, чем у линейного поиска, но также является величиной того же порядка, что и N - количество элементов массива. Существует два способа установки барьера: дополнительным элементом или вместо крайнего элемента массива. ПРИМЕР: Поиск с барьером program Poisk2a; var A:array[1..101] of integer; N,X,i:integer; begin read(N); {N<=100} for i:=1 to N do read(A[i]); read(X); A[N+1]:=X; {установка барьера дополнительным элементом} i:=1; {i:=0;} while A[i]<>X do i:=i+1; {repeat i:=i+1; until A[i]=X;} if i<=N then write('первое вхождение числа ',X,' в массив A на ',i,' месте') else write('не нашли'); end. program Poisk2b; var A:array[1..100] of integer; N,X,i,y:integer; begin read(N); {N<=100} for i:=1 to N do read(A[i]); read(X); y:=A[N]; {сохранение последнего элемента} A[N]:=X; {установка барьера на последнее место массива} i:=1; {i:=0;} while A[i]<>X do i:=i+1; {repeat i:=i+1; until A[i]=X;} if (i<N) or (y=X) then write('первое вхождение числа ',X,' в массив A на ',i,' месте') else write('не нашли'); A[N]:=y; {восстановление последнего элемента массива} end. ДВОИЧНЫЙ (БИНАРНЫЙ) ПОИСК Алгоритм двоичного поиска можно использовать для поиска элемента с заданным свойством только в массивах, упорядоченных по этому свойству. Так при поиске числа с заданным значением необходимо иметь массив, упорядоченный по возрастанию или по убыванию значений элементов. А, например, при поиске числа с заданной суммой цифр массив должен быть упорядочен по возрастанию или по убыванию сумм цифр элементов. Идея алгоритма состоит в том, что массив каждый раз делится пополам и выбирается та часть, где может находиться нужный элемент. Деление продолжается пока часть массива для поиска больше одного элемента, после чего остается проверить этот оставшийся элемент на выполнение условия поиска. Существуют две модификации этого алгоритма для поиска первого и последнего вхождения. Все зависит от того, как выбирается средний элемент: округлением в меньшую или большую сторону. В первом случае средний элемент относится к левой части массива, а во втором - к правой. В процессе работы алгоритма двоичного поиска размер фрагмента, где этот поиск должен продолжаться, каждый раз уменьшается примерно в два раза. Это обеспечивает вычислительную сложность алгоритма порядка логарифма N по основанию 2, где N - количество элементов массива. ПРИМЕР: Поиск в упорядоченном по возрастанию массиве первого вхождения числа X. program Poisk3a; var A:array[1..100] of integer; N,X,left,right:integer; begin read(N); {N<=100} write('введите упорядоченный по возрастанию массив'); for i:=1 to N do read(A[i]); read(X); left:=1; right:=N; {левая и правая граница фрагмента для поиска} while left<right do begin c:=(left + right) div 2; {середина с округлением в меньшую сторону} if X>A[c] then {если массив упорядочен по убыванию, то if X<A[c]} left:=c+1 {выбираем правую половину без середины, меняя left} else right:=c; {выбираем левую половину с серединой, меняя right} end; if X=A[left] then {здесь left = right, но не всегда = c} write('первое вхождение числа ',X,' в массив A на ',left,' месте') else write('не нашли'); end. ПРИМЕР: Поиск в массиве, упорядоченном по возрастанию сумм цифр элементов массива, последнего числа с суммой цифр равной X. program Poisk3b; var A:array[1..100] of integer;
Страницы: 1, 2, 3, 4, 5, 6, 7
| 
