Введение в процедурное программирование

Бухараев Н.Р.

Введение в процедурное программирование

Методическое пособие для подготовки к

Государственному экзамену по информатике

для студентов специальности «Прикладная математика».

Казанский государственный университет

Факультет вычислительной математики и кибернетики
От составителя - студенту.

Предлагаемое пособие - не конспект готовых ответов (или же, попросту - набор шпаргалок) к государственному экзамену, но призванный придать импульс к своей собственной работе связанный и замкнутый текст. Это означает, что посвященный каждому вопросу программы параграф использует понятия, введенные в предыдущих ответах, а решение задач - ссылки на решение задач из предыдущих ответов. Теоретически можно и практически нужно (в идеале, фактически же – лишь по требованию экзаменатора) уметь "разворачивать" ответ до базовых общематематических понятий из первого параграфа. Потому, не удивляйтесь - при приблизительно равном фактическом объеме (после такого развертывания), более поздние разделы выглядят компактнее более ранних.

 

Что оценивается на государственном экзамене? Не ваша программистская интуиция, и не знание конкретных языков или систем программирования - но ваша квалификация как программистов, закачивающих университетский курс обучения по математической специальности. По факту, это означает умение уверенно создавать пусть не идеально эффективные, но всегда понятные, «грамотные» и лишь потому правильные и надежные программы. Последнее обязательно предполагает свободное владение технологией решения достаточно сложных задач - невозможного без фундаментальной общематематической подготовки, умения формулировать вне синтаксиса конкретного языка программирования точную семантику используемых понятий в терминах классических понятий.

 

При том вполне очевидно, что задача экзаменатора - не в том, чтобы "завалить" вас на отдельных формулировках, но в том, чтобы оценить вашу программистскую и общематематическую культуру в целом. Потому - не старайтесь заучивать приведенные формулировки наизусть - поздно и бесполезно! Лучше задумайтесь - как бы вы сами точно и полезно сформулировали содержание используемых в вашей программистской практике понятий. Надеюсь - ваши формулировки будут близки к моим. Успеха!

 

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

 

© Н. Р. Бухараев, КТК ВМК КГУ, 2002 -2008

Основные понятия процедурного программирования.

Ключевые понятия: состояние, оператор, спецификация, трасса. Структурное программирование – композиция, условные и итерационные (циклические) определения операторов. Рекуррентные определения.

 

Умения и навыки: Преобразование неструктурных алгоритмов в структурные. Нахождение рекуррентных определений кратных числовых функций. Преобразование рекуррент в итерацию.

При моделировании реальных объектов мы выделяем описание статики (одновременности) – допустимого положения, характеристики, состояния объекта на некоторый фиксированный момент времени - и динамики - изменения объекта во времени, допустимых преобразований его состояний. Формально-математическим средством такого описания служит понятие области (модели, домена, системы, пространства) или, в программистской терминологии, (абстрактного) типа данных - пары <A,F>. Здесь A - некоторое основное множество значений, отражающее совокупность допустимых состояний объекта, а F, FÍAàA, - класс функций, описывающих совокупность его допустимых преобразований во времени. (Здесь и далее XàY - класс функций f с областью определения Dom(f)=X и областью значений Val(f)=Y, не обязательно - всюду определенных). Сам термин «тип» указывает на то, что на деле такое описание не задает конкретный, содержательно богатый объект однозначно, но описывает некоторое зависящее от цели моделирования обеднение, математическую абстракцию объекта.

 

Помимо формулирования цели программирования как создания компьтерных моделей, понятие типа используется и для описания языка программирования как основного средства такого моделирования. Здесь для программиста явное выделение класса функций F особенно важно, поскольку оно задает класс доступных для использования преобразований. В отличие от обычной математической практики, класс таких исходных, предопределенных функций, равно как и способы определения новых функций в программировании крайне ограничены.

 

Понятие типа помогает нам точнее сформулировать и задачу самого программирования как перевод, описание допустимого в терминах доступного.

 

В наиболее простом случае элементы множества А считаются "атомами", не имеющими, в контексте данного языка описания, внутренней структуры - возможных/допустимыхзначений некоторой единственной характеристики объекта, отождествляемой с ним самим. Такие типы называют простыми или скалярными.

 

Классические примеры типов, традиционно воспринимаемых нами как скалярные - арифметика целых Z, рациональных Q и вещественных D чисел, т.е. соответствующие числовые множества, рассматриваемые совместно с 4 арифметическими операциями и отношениями сравнения. Универсальность математических понятий позволяет использовать одни и те же пространства для описания содержательно различных характеристик объекта - так, вещественные числа могут пониматься как значения скорости, ускорения, веса, температуры и прочих характеристик объекта.

 

В отличие от классического разделения «скаляры-векторы», в программировании понятие простого и сложного относительны. Тип, считающийся скалярным в одном языке программирования, может трактоваться как структурный – в другом.

 

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

 

Т.е. некоторого множества n-ок p=<p₁,..,p_n>, p_iÎ A_i, p_i - значение i-ой характеристики (как правило, числовое). В этом случае основное множество типа – n-местное отношение, подмножество декартового произведения A₁´…´A_n (множества всех n-ок p=<p₁,..,p_n>, p_iÎ A_i, i Î [1..n]). Так, множество точек плоскости можно описать как декартово произведение D²=D´D={<x,y>, xÎ D, yÎ D}, где x,y - декартовы координаты точки, любую фигуру на плоскости - как некоторое подмножество D². Другой способ описания того же пространства - задание точек парой значений их полярных координат.

 

В программировании вместо позиционного принципа, требующего предварительной, часто неявной, нумерации характеристик, обычно используется принцип именования - сопоставления значений не номерам, но именам характеристик. В этом случае в качестве основного множества типа выступает подмножество именованного декартового произведения множеств A₁,…,A_n- класса всех функций значения, т.е. определенных на некотором множестве имен Name всех функций f таких, что f(k)ÎA_i(k), k Î Name.

 

Пример. Множество точек плоскости можно описать как именованное декартово произведение - множество всех функций f на множестве имен {'X-координата', 'Y-координата'}, где f('X-координата') Î D, f('Y-координата') Î D. При задании точек полярными координатами мы, по всей видимости, выберем уже другое множество имен - например, {'радиус', 'угол'}, что помогает явно различить разные представления понятий.

 

Отметим, что хотя в качестве имен обычно используются слова (последовательности символов), наше определение позволяет понимать под именами любое множество значений - например, снова - целые числа (индексы). В случае использования таких "нетрадиционных" имен обычно предпочитают говорить не об именах, а об указателях или ссылках на значение. На практике различие между именованным и "просто" декартовым произведениями довольно условно. Как правило, мы стараемся описать объект как упорядочиваемый (по меньшей мере, одним способом) набором "координат", т.е. независимых линейных характеристик (см. "Классификация типов").

 

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

 

Итак, в общем случае типа данных <A,F> в качестве множества состояний A выступает некоторое множество функций, а F - некоторый класс функций над А, FÍAàA. Функции "высших порядков", аргументами и значениями которых являются функции, называют операторами, а их определение на некотором формально-математическом языке называют - спецификацией. Классический способ спецификации – задание областей определения («дано») и значений («требуется найти/вычислить») оператора парой предикатов, называемых ее пред- и пост-условием.

Примеры см. далее. На практике мы часто подразумеваем тривиальные предусловия, не формулируя их явно.

Как следует из названия, процедурное программирование изначально ориентировалось на функциональное описание динамики - сложных преобразований, имеющих «вход» и «выход», начало и конец, аргументы и результаты – в операторных терминах.

 

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

 

Язык процедурного программирования - язык формального описания реальных процессов и объектов в терминах задаваемых этим языком способов определения типов данных и процедур их преобразования.

 

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

 

Это существенно отличает их от языков аксиоматической математики и рекурсивного (функционального и логического) программирования, оперирующих косвенными определениями понятий указанием их свойств, в частности – в терминах рекурсивных определений.

 

Базовый рекуррентный принцип ("новое" определяем через "старое") отражается в основном для таких языков общем способе обозначения операторов – операторе кратного или векторного присваивания вида s:=e(s'). Здесь s, s' - списки имен переменных, а e - выражение, задающее функциональную зависимость новых значений переменных (с именами из s) от старых значений переменных (с именами из s'). Существенно, что имена в s, s' могут совпадать.

 

Важные частные случаи присваивания, используемые (в отличие от кратного присваивания) в реальных языках программирования:

a) s:=s', где s, s' - произвольные списки имен переменных (такое присваивание соответствует табличному определению некоторой функции, в частном случае - перестановке значений)

b) простое присваивание вида v:=e(s), v - (единственное) имя переменной

c) бинарное присваивание вида v:=[vf]v', v,v' - имена переменных, f - имя (знак) функции двух аргументов.

 

В контексте процедурного программирования, программа трактуется как процедура, итоговое определение оператора на заданном языке программирования по спецификации – определению этого оператора на некотором формальном языке, а программирование - такое определение как происходящий во времени процесс.

 

Как отмечено выше, с абстрактной, обематематической точки зрения и значения (из А), и их преобразования (из F) - это одни и те же объекты (функции), с одними и теми же способами их определения. С другой, для программиста определение типов как пары <данные, преобразования> также отражает фундаментальное разделение хранимой и выводимой информации.

 

В программировании значения переменных трактуются как содержимое ячеек памяти, с существенным разделением на память внутреннюю и внешнюю по отношению к устройству вычисления. Это - быстрая, но малоемкая оперативная память и файлы – более медленная, но емкая память, связанные с внешними (периферийными) устройствами ввода-вывода. Более точно, программа - определение файловой процедуры (или как процедуру обработки внешних потоков данных - что еще точнее, но требует явного уточнения интерактивного подхода).

 

Классическим примером конструктивного построения языка являются языки структурного программирования, выделяющие в качестве основных три общематематических способа (структуры, схемы) определения новых процедур:

a) композиция – (S1;S2, в синтаксисе языка Паскаль), соответствующая описанию последовательного вычисления процедур S1 и S2 как функций на состояниях: (S1;S2)(s)=S2(S1(s))

В школьных терминах – определение «сложной функции» подстановкой (суперпозицией).

 

b) структуру условного оператора (в Паскале - if B then S1 else S2), соответствующую определению функции разбором случаев

ì S1(s), B(s)=true

(if B then S1 else S2)(s)= í

î S2(s), B(s)=false

В классических терминах – условное определение функции.

 

c) структуру оператора цикла с предусловием (в Паскале - while B do S), соответствующую итогу вычисления первого члена рекуррентно определяемой последовательности s, не обладающим заданным свойством B. Точнее:

a) если s₀=s, s_i+1=S(s_i) и k=min {i: B(s_i)=false}, то (while B do S)(s)=s_k

b) если {i: B(s_i)=false}=Æ, то значение (while B do S)(s) неопределено,

 

В классических терминах – итерационное определение функции.

 

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

 

Пример структурирования программ

Задача линейного поиска значения в последовательном файле. Неформальная постановка – выяснить (found), есть ли заданное значение x в заданной последовательности a. Спецификация: предусловие AÎNàT and XÎT, постусловие found:=$ iÎ Dom(A)(X=A_i):

Здесь и далее мы обозначаем значения большими буквами, чтобы явно отличить их от имен значений.

read(x); found:=false; while not eof() do begin read(a); if a=x then begin found:=true; goto 1 end; 1:»

read(x); found:=false; while not eof() and not found do begin read(a); if a=x then begin found:=true; end;

 

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

 

 

Нетрудно увидеть за этими определениями хорошо знакомое различие между двумя определениями последовательности – реккурентным (зависимость от предыдущего члена) и формулой общего члена, задающей зависимость члена последовательности от номера (и первого члена).

 

Пример трассировки для доказательства корректности программ. Задача обмена значений (вещественных) переменных, спецификация x,y:=y,x.

 

Программа Трасса Программа Трасса Программа Трасса

x y x y z x y

X Y X Y Æ X Y

x:=y; Y Y z:=x; X Y X x:=x+y; X+Y Y

y:=x Y Y x:=y; Y Y X y:=x-y; X+Y X

y:=z Y X X x:=x-y Y X неверно верно верно

 

Примеры обратного перехода от непосредственного определения последовательностей (как функций на N, т.е. "формулы общего члена") к итерационным определениям.

 

Спецификация Итерационное определение Программа

 

m:=max (a₁,…,a_n) m₁= a₁ ì a_i, m_i<a_i read(m);

m_i+1= max(m_i,a_i)=í while not eof() do

î m_i, m_{i ³} a_i if m<a then m:=a

 

s:=S {a_i: iÎ [1..k]} s₀=0 s:=0; read(eps);

k=min {i: abs(a_i)<eps } read(a); go:= true;

s_i+1= s_i+a_i while not eof() and go do

begin read(a);

if abs(a)>=eps

then s:=s+a else go:=false

end

Общую теорию приближения числовых функций суммами (теорию рядов) - ищи в курсе мат. анализа.

b:=a₀xⁿ+…+a_nx⁰ b₀= a₀ read(b);

b_i+1=b_ix+a_i while not eof() do

(схема Горнера) begin read(a); b:=b*x+a end

Замечательный - и достаточно редкий - случай наилучшего решения проблемы заданными средствами (здесь - с наименьшим количеством вычисления арифметических операций)

 

Пример построения модифицированного тела процедуры.

 

{процедура линейного поиска значения в массиве}

{спецификация: found:=x Îa» $ iÎ [1..LenA] (x=a_i) }

procedure poisk(x:T;A:tArray;LenA:tIndex; var found:boolean);

var i:tIndex;

begin

found:=false; i:=1;

while (i<=LenA) and not found do if A[i]=x then found:=true else inc(i)

end;

 

Построим обращение для poisk(2*i,X,10,b)»?

1) (Избавление от коллизии имен)

found:=false; i1:=1; while (i1 <=LenA) and not found do if A[ i1 ]= x1 then found:=true else inc(i1)

2) (Присваивание значений параметров-значений)

x1:=2*i; a:=x;LenA:=10; found:=false; i1:=1; while (i1<=LenA) and not found do if A[i1]=x1 then found:=true else inc(i1)

3) (Замена имен параметров-переменных)

4) x1:=2*i; a:=x;LenA:=10; b:=false; i1:=1; while (i1<=LenA) and not found do if A[i1]=x1 then b:= true else inc(i1)

т.е. poisk(2*i,X,10,b)» x1:=2*i; a:=x; LenA:=10; b:=false; i1:=1; while (i1<=LenA) and not found do if A[i1]=x1 then b:=true else inc(i1)

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

Пример побочного эффекта. Пусть процедура линейного поиска теперь реализована так

procedure poisk(x:T;A:tArray; var found:boolean);

{found:=$iÎ[1..LenA](x=a_i)}

{var i:tIndex; - сэкономили память!}

begin

found:=false; while (LenA>=0) and not found do if A[i]=x then found:=true else dec(Len)

end;

 

В отличие от параметров процедуры, глобальные объекты никак не участвуют в модификации тела процедуры, потому обращение вида poisk(x,a,b) не только найдет правильное значение b, но и обнулит значение глобальной переменной LenA, содержащую по смыслу фактическую длину массива а и тем самым "закроет" его элементы для дальнейшей обработки.

 

Потому - либо а) (правило полной локализации) вообще не используй локально (т.е. в теле процедуры) глобальные объекты, либо, как минимум б) не изменяй их значений в теле процедуры. В любом случае использования глобальных объектов помечай такое использование синтаксически (в виде комментария).

 

 

Классификация типов данных.

(Начни с определения понятия абстрактного типа данных как области - пары <A,F>, FÍAàA – см. § 1).

 

Примеры базовой семантики конкретных типов языка Паскаль (в реальности, как мы хорошо знаем, каждый тип обогащен множеством других функций)

Real, integer - арифметика вещественных и целых чисел,

string - полугруппа слов относительно операции конкатенации (сцепления слов),

 

array[I] of T - множество всех функций IàT, c операцией App применения (аппликации) функции к аргументу, App(a,i)=a[i],

record n₁:T₁;…;n_m:T_m end - именованное декартово произведение (определение см. § 1) основных множеств типов T₁,…,T_m с конечным множеством имен {n₁,…,n_m}, с операцией аппликации, App(r,n)=r.n,

file of T - множество всех последовательностей NàT, c операторами:

reset(f)» маркер(f)=0; режим(f):=чтение;

read(f,x)» inc(маркер(f));x:=f(маркер(f))

область определения: (режим(f)=чтение)& (маркер(f)Î Dom(f))

rewrite(f)» маркер(f)=0; режим(f):=запись;f:=<> (пустая последовательность)

write(f,e)» inc(маркер(f));f(маркер(f)):=e;

область определения: (режим(f)=запись)

eof(f)» маркер(f)Î Dom(f)» компонента f(маркер(f)) определена

где маркер(f), режим(f) - некоторые вспомогательные системные (т.е. предопределенные, не определяемые пользователем) переменные.

 

(В отличие от объектного подхода), классический процедурный стиль склоняется к раздельному описанию

а) способов определения основного множества значений А, при фиксированном классе функций F (собственно, и относимых к определению типа) и

б) способов определения класса F - преобразований значений типа (см. § 2).

 

Это определяет и соответствующую классификацию типов по способу определений значений основного множества.

1) Разделение между скалярными и производными типами уже проведено в §1. В последнем случае, значения структурированы. Общая схема такой структуры - именованное декартово произведение, т.е. некоторый класс функций. Различие производных типов - в конкретных областях определения и значений этих функций, и (фиксированных для каждого типа) операторов их обработки. Примеры скалярных типов в Паскале - integer, real, char, boolean, перечислимый, ограниченный, производных типов - string, text, array, file, record, set.

 

2) Стандартные и пользовательские типы. В первом случае множество значений преопределено, во втором (до)определяется программистом. Примеры стандартных типов - integer, real, char, boolean, string, text; пользовательских типов - перечислимый, ограниченный, array, file, record, set.

 

3) Порядковые и непорядковые типы. Понятие перебора (перечисления, пересчета) является одним из наиболее фундаментальных в программировании. Порядковые типы - те множества значений X, на которых определен (хотя бы один) порядок перебора, т.е. сравнение (линейный порядок) <, x<x' - "x' следует позже в переборе, чем x". Однако, не любое сравнение определяет порядок перебора, а лишь такое, для которого определены (доступны)

- функция следования (прямого перебора) succ, succ(x)=min{x': x'>x} и

- функции предшествования (обратного перебора) pred, pred(x)=max{x’:x’<x}

 

Примеры порядковых типов Паскаля -

integer - succ(n)=n+1,

char, - succ(c_i)= c_i+1 (c_{i -} - i-ый символ в предопределенном языком фиксированном алфавите, таблице символов)

Boolean - false<true

 

Значения производных типов (array T1 of T2, record, file of T) обычно не считаются порядковыми, но нужный порядок можно (до)определить, если соответствующие базовые типы - порядковые (см. перечисление последовательностей в §10 и §11). Очень интересны примеры

- типа real, на котором определено обычное сравнение чисел, но из теоретических «мощностных» соображений не может быть определена соответствующая функция следования - не существует наименьшего вещественного числа, большего данного.

- множества всех бесконечных последовательностей, с теми же свойствами. (см. "Перечисление последовательностей").

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

 

4) Динамические и статические производные типы. Значения производных типов - функции. Область их определения может быть фиксирована (статический тип) - пример - множество всех функций [1,n]àT для фиксированного n, либо нет (динамический тип), пример - множество всех функций [1,n]àT для произвольного n. Примеры статических типов - record, статический array (в стандартном Паскале); динамических - file, string, динамический array (в Object Pascal).

 

В последнем случае определение типа предполагает явное или неявное наличие соответствующих операторов расширения и сужения области определения. Примеры - оператор Паскаля SetLength явного установления области определения динамических массивов; оператор write увеличивает длину файла неявно.

 

Практический интерес представляют типы, которые можно назвать псевдодинамическими. Это функции, область определения которых не фиксирована, но содержится в некотором фиксированном множестве значений. Пример: множество всех последовательностей f с длиной менее заданной, f:[1..n]àT, n<nMax. В практическом программировании необходимо учитывать конечность памяти - в реальности, все динамические типы являются псевдодинамическими!

5) Абстрактные типы. Совершенно иной смысл имеет условное разделение абстрактных и конкретных типов. Абстрактные типы - типы, точно определяемые как математические объекты (объекты некоторого языка спецификаций), но не как объекты данного языка программирования. Пример - комплексные числа и точки плоскости не есть тип Паскаля, тип record x,y: real end - тип Паскаля. Установление соответствия между (значениями и операциями) абстрактного и конкретного типов называется реализацией (определением, моделированием или представлением) абстрактного типа.

6) Тесно связано с понятием реализации (как способа определения) деление типов по способам доступа. На практике, программисту важен именно способ определения, задания объекта/функции. Другое дело, что такие определения можно снова точно сформулировать в терминах функций/операторов. Существует три важных вида таких определений: реккурентное (данные последовательного доступа, пример - файлы и списки, язык описания - функции следования), явное (данные прямого доступа, пример - массивы и записи, язык описания - оператор аппликации) и рекурсивное (пример - деревья и графы, язык описания - функции на последовательностях)

 

Пояснить классификацию типов на конкретном примере.

Задача: найти длину lmax самого длинного слова w (в текстовом файле f) и само это слово w; (слова представлены символьным списком.)

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

type

{список - абстрактный динамический пользовательский тип последовательного доступа}

slovo=^component;

component=record letter:char;next:slovo end;

{аналогично - найди место в каждой классификации для остальных типов, используемых в спецификации и реализации программы}

 

procedure P(var f:text; var lmax:integer; var w:slovo);

var v:slovo;

begin

lmax:=0;

w:=ПустоеСлово;

stop:= КончилисьСлова(f); v:=Oчередное слово(f); l:= Длина(v);

while not stop do

begin

if l>lMax then begin lmax:=l; Копировать(w,v) end;

{подготовка переменных к следующему проходу}

Уничтожить(v);

stop:= КончилисьСлова(f); v:=Oчередное слово(f); l:= Длина(v);

end;

Внимание - хитрость примера - обратное влияние или "побочный" эффект реализации - независимое определение функции КончилисьСлова (» остаток файла содержит хотя бы одно слово» хотя бы один не пробел) делает практически невозможным (точнее, сильно неэффективным) реализацию процедур OчередноеСлово и Длина. Отдельные, с точки зрения логики, операторы, могут быть реализованы только совместно.

 

procedure P(var f:text; var lmax:integer; var w:slovo);

var v:slovo;

begin

lmax:=0;

w:=nil; {w:=ПустоеСлово}

ОпределиКончилисьСловаЕслиНетОпределиОчередноеСловоИЕгоДлину(f,stop,v,l);

{читай файл до непробела/начала слова, если таковое есть - читай все непробелы в список v, одновременно подсчитывая их число в l}

while not stop do

begin

if l>lMax then begin lmax:=l; Копировать(w,v) end;

{подготовка переменных к следующему проходу}

Уничтожить(v);

ОпределиКончилисьСловаЕслиНетОпределиОчередноеСловоИЕгоДлину(f,stop,v,l);

end;

 

Замечание. Если есть трудности с реализацией порождения, уничтожения и копирования списков - см. "Абстрактные линейные типы данных"

Вычисление предикатов.

Предикат (свойство, условие) - произвольная функция с областью определения Boolean={true,false}. Пример (двуместных) предикатов - бинарные отношения, в частности, отношения сравнения <,>,=,<>.

 

Вычисление предикатов облегчается тем, что существует общематематический язык логики (исчисления предикатов) - исключительно выразительный и одновременно компактный - содержащий бинарные операции & (and, в синтаксисе Паскаля), Ú (or), Ø (not) - их относят к операциям алгебры логики, а также два квантора (оператора над множествами) " и $ (отсутствуют в Паскале). Перевод формулы из языка ИП в программу на структурном языке программирование - техническая задача, при учете следующих основных моментов.

 

1. Написание (спецификация) формул может быть само по себе достаточно сложной задачей. Математическая логика располагает множеством стратегий таких спецификаций в виде алгоритмов записи любого предиката в некоторой канонической (нормальной) форме. Наиболее простые из таких форм для бескванторных формул - днф (дизъюнкция элементарных коньюнкций), кнф (конъюнкция элементарных дизъюнкций); по определению, элементарные формулы могут содержать отрицание, но не знаки бинарных логических операций.

2. Для кванторных формул канонической является т.н. предваренная нормальная форма вида Q₁x₁… Q_n x_n B(x_1,…,x_n,z) (где Q_i - либо $ либо ", причем каждые два соседних квантора можно считать различными, а B уже не содержит кванторов).

Пример. Определить принадлежность точки p(x,y) к фигуре, составленной из 4 колец. Каждое кольцо задаваемется центром и длинами внутреннего и внешнего радиусов.

Решение - стратегия днф.

а) Точка принадлежит к фигуре, если она принадлежит одному из колец.

type

tPoint=record x,y:real end;

tRing=?

tFigure=array[1..n] of tRing;

 

function ПринадлежитФигуре(p: tPoint; figure:tFigure):boolean;

begin

ПринадлежитФигуре:=

ПринадлежитКольцу(p,figure[1]) or

ПринадлежитКольцу(p,figure[2]) or

ПринадлежитКольцу(p,figure[3])

end

b) Точка принадлежит кольцу, если она находится одновременно внутри внешнего и вне внутреннего окружностей кольца.

type

tRing =record center:tPoint; radius1,radius2:real end;

function ПринадлежитКольцу(p:tPoint; Ring:tRing):boolean;

begin

ПринадлежитКольцу:=

ПринадлежитОкружности(p,Ring.center,Ring.radius1) and

not ПринадлежитОкружности(p,Ring.center,Ring.radius2)

end;

d) Принадлежность точки P с заданными координатами Px,Py к окружности O c центром Ox,Oy и радиусом Oradius описывается атомарной формулой

(Px-Ox)²+(Py-Oy)²£ Oradius²

function ПринадлежитОкружности(p:tPoint,center:tPoint; radius:real):boolean;

begin

ПринадлежитОкружности:= sqr(P.x-Center.x)+sqr(P.y-Center.y)<=sqr(radius)

end;

3. Алгоритмическое определение операций алгебры логики.

a) y:=not b» if b=true then y:=false else y:=true

b) y:=b1 and b2» 1) y:=false; if b1=true then if b2=true then y:=true;» 2) y:=true; if b1=false then y:=false; if b2=false then y:=false;

c) y:=b1 or b2» 1) y:=true; if b1=false then if b2=false then y:=false 2) y:=false; if b1=true then y:=true; if b2=true then y:=true

Внимание - указанные эквивалентности верны лишь для определенных значений b1,b2. Программы 1) определенные значения y при неопределенном значении b2, программы 2) - нет. Семантика 1) соответствует т.н. быстрому означиванию операций и определяют т.н. условные коньюнкцию и дизъюнкции - строго говоря, отличных от классических (семантика 2). В Паскале эта неоднозначность ("темное" место языка) разрешается директивой компилятора $B. Разные значения директивы может сделать одну и ту же программу верной или неверной!

Задача (линейный поиск)

type

tIndex=1..MaxLen;

ArrayOfT=array[tIndex] of T;

procedure Poisk(x:T; a:ArrayOfT; LenA:tIndex; var found:boolean; var index:tIndex);

begin

index:=1;

while (index<=LenA) and (x<>a[index]) do inc(index);

found:= index<=LenA

end;

При быстром означивании формула (index<=LenA) and (x<>a[index]) при index=LenA+1 дает false (программа верна), при классическом - значение неопределено (программа неверна). Совет: желательно избегать неопределенных значений -

index:=1; found:=false;

while (index<=LenA) and not found do if x=a[index] then found:=true else inc(index);

4. Вычисление кванторных формул.

a) y:=$ xÎ X (B(x))

Рассмотрим частный (для классической логики), но наиболее важный для программирования (и конструктивной логики) случай. X - множество значений порядкового динамического типа, для которого определены функция следования (перебора) и предикат конца перебора значений - заданный, например, в виде сравнения. Тогда $ xÎ X (B(x)) - это кратная дизъюнкция, а y есть первый true в реккурентной последовательности y₀=false, y_i+1= y_i or B(x_i) (либо false, если такового нет). Поэтому, можно воспользоваться общей схемой вычисления членов реккурентных последовательностей:

y:= $ xÎ X (B(x))»

y:=false; i:=1; while (i<=LenX) and not y do if B(x_i) then y:=true else inc(i)

Точно также можно определить формулу " xÎ X (B(x)) как кратную конъюнкцию:

y:= " xÎ X (B(x))»

y:=true; i:=1; while (i<=LenX) and y do if B(x_i) then y:=false else inc(i)

 

Пример вычисления кванторной формулы. Последовательность A длины LenA (строго) периодическая (или, попросту - кратная), если оно состоит из двух или более одинаковых "сцепленных" подпоследовательностей некоторой длины k, называемой в этом случае периодом A. Выяснить, является ли данная последовательность строго периодической.

Спецификация

b:=A - строго периодическая»

b:=$ k Î [1,LenA div 2] (k - период A)»

b:=$ k Î [1,LenA div 2] (LenA mod k =0 à " iÎ [1..LenA-k] (A[i]=A[i+k]))

type

tIndex:1..MaxLen;

tArray:array[tIndex] of T;

 

function Period(k:tIndex; a:tArray; LenA:tIndex):boolean;

var b2:boolean; UpperLimit2:tIndex; {= LenA-k }

begin

b2:=LenA mod k; UpperLimit2:= LenA-k; i:=1;

while (i<= UpperLimit2) and b do

if A[i]<>A[i+k] then b2:=false else inc(i)

Period:=b2

while

 

end;

function Periodic(a:tArray; LenA:tIndex):boolean;

var UpperLimit1:tIndex; {=LenA div 2} b1:boolean;

begin

b:=false; k:=1; UpperLimit:=LenA div 2;

while (k<=UpperLimit) and not b do

if period(k,A.LenA) then b:=true else inc(k);

Periodic:=b;

end;

 

§ 5. Поиск.

Основной интуитивный смысл структур данных - "хранилище" данных, обеспечивающее операции доступа (чтения) и записи, что, при формальном определении этих структур как функций соответствует вычислению следующих основных операторов

- аппликация (по хранилищу f и указателю/имени x определить значение f(x)),

- (пере)определению значения функции f в точке x новым значением y, и

- (для динамических типов) расширению/сужению области определения функции.

 

Понятие хранилища данных тесно связано по смыслу, но существенно шире по объему понятия структуры (производного типа). В качестве хранилища, при фиксации кодирования, могут выступать и скалярные значения. Так, например, по основной теореме арифметики, любое n,nÎ N, есть некоторое произведение степеней простых чисел P p(i) ^a(i) (p(i) i-е простое число). Следовательно, его можно р