Лекции по информатике (1113418), страница 4

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

Текст из файла (страница 4)

N = ....;{количество площадок в лабиринте}

type коридор = (Ардна,Мнтвр,Никого,Жлт,Злн,Крс);

var движение:boolean {логический признак выхода из основного цикла};

ищи:boolean{логический признак для определения типа площадки};

S,K,I,J,C:integer;{S - длина пройденного пути,

K - вспомогательная переменная,

I - номер площадки;

J - номер коридора;

C - число жлт коридоров}

ЛБРНТ:array [1..N,0..N] of коридор;

{ ЛБРНТ[I,0] - указывает есть ли кто на площадке;

ЛБРНТ[I,J] - указывает цвет коридора J}

ПУТЬ:array [1..N] of 1..N;

{площадка идентифицируется своим номером}

типлщдки:(минотавр,петля,злнулица,ариадна,проч);

begin

for I:=1 to N do

for J:=0 to N do {read (ЛБРНТ[I,J]); - Ввод лабиринта}

{Надо иметь ввиду, что ЛБРНТ[I,J]- перечислимого типа}

{поэтому просто read проблему ввода не решит}

I:=I0; J:=J0; {начальное размещение Тезея; ЛБРНТ[I,0]=Ардна}

{I0,J0 - могут быть введены из вне}

движение := true;

while движение do

begin

{определение типа площадки};

case типлщдки of

минотавр: движение:=false;

{нашли Минотавра}

петля : {наматывай};

злнулица: {разматывай}

ариадна : движение:=false;

{Минотавр не достижим}

проч : {наматывай}

end {case}

end{while}

end{program}.

{определение типа площадки}

типлщдки:=Минотавр;

Ищи:=true;

while ищи do

begin C:=0;

case типлщдки of

Минотавр: if ЛБРНТ[I,0] = мнтвр then ищи:=false

else типлщдки:= succ(типлщдки);

Петля: begin K:=1; while K<=N do

begin

if ЛБРНТ[I,K]=Жлт then

begin J:=K; C:=C+1 end;

K:=K+1;

end;

if C>=2 then ищи:=false

else типлщдки:= succ(типлщдки);

end{Петля}

Злнулица: begin К:=1;

while(К<=N)AND(ЛБРНТ[I,K]<>Злн) do К:=К+1;

if К<=N then begin J:=K; ищи:=false end

else типлщдки:= succ(типлщдки);

end{Злнулица};

Ариадна: if ЛБРНТ[I,0]=Ариадна then ищи:=false

else типлщдки:= succ(типлщдки);

Проч: begin if NOT(C=1)AND NOT(ЛБРНТ[I,J]=Жлт)

{Это условие должно выполяться после Петля}

then begin writeln('Ошибка в лабиринте');

движение:=false

end;

ищи:=fasle

end{Проч}

end {case};

end;

{Наматывай} ЛБРНТ[I,J]:=Крс; K:=I; I:=J; J:=K; ЛБРНТ[I,J]:=Крс;S:=S-1;

{Разматывай} ЛБРНТ[I,J]:=Жлт; K:=I; I:=J; J:=K; ЛБРНТ[I,J]:=Жлт;

S:=S+1; ПУТЬ[S]:=I;

Следует обратить внимание на следующие моменты:

- процесс абстракции при выборе структуры (математической) для описания понятия лабиринт;

- выбор способа представления выбранной структуры средствами языка программирования;

- ЛБРНТ[I,0] и ЛБРНТ[I,J] имеют разный тип, но мы вынуждены определять их одного типа;

- способ работы с перечислимым типом в цикле;

- способ выхода из цикла.

Лекция 11-12.

Комбинированный и множественные типы данных.

Здесь продолжается изучение производных типов данных.

Производные типы

Регулярный Комбинированный Множественный

Комбинрованный тип данных

Элементы этого множества есть наборы фиксированного числа поименованных компонентов разного типа. Зачение этого типа называются записью. Компоненты записи называются полями. Каждое поле имеет имя, уникальное на своем уровне внутри записи. На разных уровнях внутри записи могут быть однаковые имена. Эти имена "видимы" только внутри записи. На тип поля ограничений нет.

комбинированный тип::=record <список полей> end

список полей::= <секция записи>{;<секция записи>}

секция записи::=<имя поля>{,<имя поля>:<тип>}

Доступ к значению поля осуществляется через частичную переменную записи. Каждая заптсь имеет столько частичных переменных, сколько полей в записи. Имя частичной переменной строится как перечисление вершин в дереве записи, от крня до вершины представляющей нужное поле.

Курс

Админчст Группы

Нач.крс Испктр Стрст Стрст Студент

имя фмлия пол г/р адрс

грд улца д кв

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

- При определении кимбинированного типа порядок перечисления полей не важен.

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

- нельзя использоватть имени поля без имени полной переменной.

Для полных переменных в Pascal определен только оператор присваивания.

Оператор присоединения.

Этот оператор позволяет сократить длину имени частичной переменной там где эта переменная интенсивно используется.

with <список переменных комбинированного типа> do <любой оператор Pascal>

При использовании этого оператора могут возникать два вида коллизий имен:

1.У переменных, перечисленных в списке комбинированного типа, есть поля с одинаковыми именами;

2.В программе есть переменная с тем же именем как и имя поля переменной из списка переменных комбинированного типа.

Первая коллизия разрешается так: это имя поля трактуется как имя поля той полной переменной, которая перечислена в списке переменных комбинированного типа позже.

Вторая коллизия разрешается в пользу имени поля, т.е. при совпадении имен переменной и поля, это имя трактуется как имя поля, а не имя переменной.

Множественный тип.

Множественный тип - это не упрядоченный набор конечного числа однотипных элементов, среди которых нет повторяющихся. Тип элемента - базовый тип множества. Базовым типом может быть любой скалярный тип, кроме real. Значение мноежественного типа задается через коструктор множества:

[{список значений базового типа через запятую}]

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

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

Операции над значениями множественного типа.

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

Рассматриваются операции отношения на значениях множественного типа: включение (in), сравнения (<,>,=).

Рассматривается пример программы, реализующий решето Эратосфена, для выбора из множества натуральных чисел от 2 до 201 всех простых чисел.

(Замечение. В книге Абрамова, Трифонов, Трифонова в этом примере опечатка! Переменная k не может иметь тип 2..N, т.к. в этом случае вложенный repeat работать не будет (условие k>N - не будет выполнено никогда)). никогда)).

Лекция 13.

П р о ц е д у р ы .

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

С другой стороны процедура рассматривается как поименованная последовательность действий. Благодаря наличию имени эту последовательность можно неоднократно использовать и инициировать.

Аппарат процедур позволяет:

- упростить реализацию, за счет компактности записи программы;

- упростить процесс отладки программы, за счет ясности текста программы;

- упростить процесс разработки программы за счет срутктуризации программы;

- ускорить разработку программы за счет многократного использования заготовок.

Описание процедуры вводит и именует последоательность действий. Оператор процедуры инициирует выполенение ранее описанной оследовательность действий.

описание П ::= заголовок П ; блок заголовок::= procedure имя П (список форм.парм.) оператор П ::= имя П | имя П ( список факт.парм.)

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

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

Процедуры с параметрами.

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

Параметры-переменные

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

Разъясняется синтаксис и семантика передачи параметров по ссылке.

Параметры-значения прозводных типов.

На примерах показывается что если значение производного типа передается как значение, то происходит копированние этого значения в теле процедуры. Это может привести к значительным накладным расходам.

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

Type

procedure Mult (var x,y,z: matrix);

var i,j,k,s: integer;{i,j,k - параметры циклов;

s - для промежуточных сумм}

begin

for i :=1 to N do

for j :=1 to N do

begin s:=0;for k :=1 to N do

s:=s+x[i,k]*y[k,j];

z[i,j]:=s

end

end{procedure}

A =... B =...

Если рассмотреть результаты обращений Mult(A,B,C), Mult(A,B,A),Mult(A,B,B), то получим следующие результаты: ...

Причина этого в том что параметры-переменные связаны между собой в теле процедуры.

Синтаксис списка формальных параметров.

Здесь рассматриваются правила спецификации формальных параметров, объединения их в секции и т.д. Разъясняется важность порядка перечисления параметров в списке. Отмечается что здесь при спецификации формального параметра может быть только имя типа, но не его описание. Это приводит, в частности, к тому, что нельзя написать процедуру для обработки массивов переменной длины.

Область действия имен. (Принцип локализации имени.)

Здесь разъясняются понятия локального, глобального объектов и объектов-параметров. Объясняется как их различать. Как разрешаются коллизия имен между ними.

Оператор процедуры.

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

1.Если у процедуры нет параметров, то оператор состоит только из имени.

2.Число фактических параметров должно в точности совпадать с числом формальных параметов.

3.Тип фактического параметра должен соотвествовать типу формального.

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

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

var i:integer;

a:array [1..2]of integer;

procedure P(x:integer);

begin i:=i+1; x:=x+2 end

begin a[1]:=10; a[2]:=20; i:=1; P(a[i])end

по значению x:=10; a[1]:=10; a[2]:=20;

по ссылке x=a[1];a[1]:=10; a[2]:=20;

по имени x=a[i];a[1]:=10; a[2]:=22;

Лекция 14.

Ф у н к ц и и

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

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

Описание процедуры-функции.

Характеристики

Список файлов лекций