Лекции по информатике (1113418), страница 5
Текст из файла (страница 5)
Для определения правила вычисления значения используется понятие <описание фукции>. Это описание размещается в разделе роцелур и функций того блока, где они используются.
<описание фукции>::=<заголовок функции>;<блок>
<заголовок функции>::=function<имя функции> :<имя типа>
<список формальных параметров>
Подобно процедурам функции могут быть без параметров, могут иметь параметры-значения и параметры-переменные. Имя типа в заголовке функции необходимо по двум причинам:
- для определения типа выражения, надо знать типы операндов;
- для контроля правиольности использования функции в программе.
Подобно поцедуре тело функции - блок. Как же определить какой из результатов, получаемых в теле функции - значение функции? Для этого в теле функции обязятельно должен быть хотя бы один выполняемый оператор присваивания вида <имя функции>::=<выражение>.
Итак, основные отличия описания процедуры от описания функции:
- служебное слово function в заголоаке;
- имя типа значений функции в заголоаке;
- в теле должен быть оператор присваивания с именем функции в правой части.
Вызов функции.
Для инициации выполнения тела функции служит оператор вызова функции, который часто мы и будем называть функцией. За исключением того, что вызов функции может использоваться только в выражениях, кроме уже перечисленных дугих отличий функции от процедуры нет. Т.о., функцию всегда можно описать как процедуру и наоборот. Что и когда надо использовать?
Дело втом, что функция должна иметь один результат - значение. Процедура - несколько. Поэтому, если именуемая последоватедьность действий создается ради неоднократного вычисления значения с разными данными, то это - функция, если кроме этого предполагается изменение значений нескольких объектов в программе - процедура.
Побочный эффект.
Функция имеет единственный эффект - вычисление значения. Вообще говоря, не должно быть в программе других эффектов от вызова функции. Pascal однако, допускает функции, в теле которых может изменяться значения глобальных объектов. Подобные действия называются побочным эффектом.
Побочный эффект опасен уже тем, что из текста программы не возможно усмотреть, что кроме выработки значения функция меняет значения каких-то объектов программы.
(Рассматриваются примеры побочных эффектов.)
Параметры-функции, параметры-процедуры.
Рассмативается реализация на Pascal алгоритма нахождения нулей функции методом деления отрезка пополам. Ясно, что если этот алгоритм надо применять к разным функциям в программе, то разумно было бы оформить его как функцию. Для этого надо уметь передавать функцию, для которой надо вычислить нули, как параметр.
Pascal допускает использование процедур и функций в качестве параметров. Единственное ограничение на функции и процедуры, передаваемые как параметр - они не должны иметь параметров-переменных.
program Fork (input, output);
const eps = 1E-14;{точность вычислений}
var x,y:real;
function zero (function f(x:real):real; a,b:real):real;
var x,y:real; s:boolean;
begin
s:=f(a)<0;{a - левая граница отрезка}
repeat
ищем нули}
if (z<0)=s then a:=x else b:=x {b - правая граница oтрезка}
until abs(a-b)<eps; zero:=x
end
Также обращается внимание, что в случае параметров функций и процедур их значения передаются по имени.
Рекурсия
Рекурсия вводится, опираясь на опыт синтаксических определений, для которых при их построениях, она отмечалась всякий раз особо. Приводятся примеры рекурсивных определений факториала, чисел Фиббоначи, нечетных чисел.
Процедура ( везде далее подразумевается также и функция ) называется рекурсивной, если в процессе своего выполнения процедуры она обращается к самой себе прямо или косвенно. Обращение назывется косвенным (неявным), елси в теле процедуры есть обращение к другой процедуре, в которой ( возможно через цепочку вызово) есть обращение к исходной процедуре.
Каждое обращение к процедуре вызывает независимую активацию. Совокупность данных, используемых при одной активации, назовем фреймом активации. Фрейм активации содержит значения всех локальных переменных и формальных параметров. Если процедура несколько раз обращалась к себе и ни одно обращение не завершилось, то сществует несколько фреймов.
Рассматривается пример процедуры, распечатывающей строку символов в обратном порядке.
procedure Backprint;
var символ:char;
begin read (символ);
if символ=EOL then writeln{перед началом вывода}
else begin Backprint; write (символ) end
end.
Итерация и рекурсия.
На примерах программ вычисления факториала, наибольшего общего делителя (все они уже встречались), строятся иерационный и рекурсивный их варианты. Затем на ниже следующем примере сведения цикла while к рекурсии ставится вопрос о взаимоотношении итерации и рекурсии.
while УловиеЦикла do | procedure РекурЦикл
Телоцикла | begin
end | then
| begin ТелоЦикла;
| РекурсЦикл
| end
| end
1. Каждая итерация может быть заменена рекурсией.
2. Рекурсия не всегда может быть заменена итерацией.
Примером последнего утверждения может служить функция Аккермана:
A(m, n) = n+1 если m=0,
A(m-1, 1) если n=0,
A(m-1, A(m, n-1)) в противном случае.
Лекция 15.
Применеие рекурсии в алгоритмах с возвратом.
Файловый тип. Ввод/вывод.
Есть широкий спектр алгоритмов когда вычисления идут не по фиксированным правилам, а методом проб и ошибок. Примером таких алгоритмов могут служить алгоритм игры чет-нечет; алгоритм поиска пути в лабиринте в задаче об Ариадне и Тезее. Теперь рассмотрим применение рекурсии для решения таких задач.
Применение рекурсии рассматривается на примере задачи обхода шахматной доски ходом коня. Наряду с демонстрацией применения рекурсии еще раз демонтрируется пошагавая, структурная разработка пограммы.
procedure попытка следующего хода;
begin
repeat
if ход преемлем? then
begin
if доска не заполнена? then
begin
if неудача? then стирание предыдущего хода;
end
end
until (ход был удачным?) or (нет других возможных ходов)
end.
В итоге выписывается полный текст программы на Pascal.
Файловый тип. Ввод/вывод.
Все рассмотренные ранее типы данных обладали одним общим свойством - число их компонентов конечно и заранее фиксировано. Однако, существует достаточно широкий класс задач, когда количество компонент данных заранее не известно. Пример - задача кодирования текста поступающего на вход в реальном времени, ввод текста, длина которого заранее не известна и т.п.
В Pascal существует тип данных, множество элементов которого есть последовательности однотипных элементов, длина этих последовательностей не фиксируется заранее. Важной характеристикой этого типа, называемого файловым, является то, что доступ к его компонентам строго последовательный. Это означает, чтобы получить доступ к i-му компоненту, необходимо пройти i-1-ый.
Файловый тип - это единственный тип, обладающий тем свойством, что данные этого типа могут иметь время жизни более времени выполнения программы! Поэтому этот тип часто используют, чтобы сохранить результаты работы программы для последующей обработки; либо ввести данные извне. Примеры файлового типа, с которыми мы уже много раз встречались мног раз - input и output.
Файлы и работа с ними.
<тип файл>::= file of <тип компонент>
Тип компонент - любой, не содержащий файлового. Файлы бывают внутренние и внешние. Внешние файлы описываются в заголовке программы, в скобках, после имени программы:
program <имя программы>(<список внешних файлов>);
В списке внешних файлов указываются те файлы, чье время жизни больше времени выполнения программы. Если файл не указан в этом списке - он внутренний, т.е. время его жизни равно времени выполнения программы.
Над файлами не определено никаких операций, для них не определен даже оператор присваивания.
Для доступа к компонентам файла в Pascal предопределены специальные процедуры : rewrite(f); reset(f); append(f); read(f); write(f); get(f); put(f); и специальная переменная, так назывемая буферная переменная f^.
На примерах излагаются правила работы и использования перечисленных выше средств работы с файлами. Также рассматривается текстовый файл. выше средств работы с файлами. Также рассматривается текстовый файл.
Лекция 16
Ссылочный тип данных. Динамические объекты.
1. Природа динамических объектов и способы их реализации.
Все объекты, представляющие данные в программе и которые рассматривали до сих пор, были статические в том смысле, что все их параматры, размеры были известны до выполнения программы. Следовательно, ресурсы для их можно было заранее спланировать и выделить.
Существуют задачи, для которых характерно наличие данных: - фактичское появление которых возможно, но не обязательно; - время жизни этих объектов меньше времени исполнения программы. Такие объекты называют динамическими объектами.
Например, если нам надо выбрать из входного потока данных, совокупности данных, обладающих определенными свойствами. Встретим или нет мы такие совокупноси это вопрос. Поэтому выделение ресурсов для их хранения заранее вряд ли разумно. Более того мы не знаем как велика будет такая совокупность. Затем, если собранную совокупность мы должны передать по линиям связи, например, на другую машину, то в нашей программе логично было бы ресурсы, занимаемые переданной совокупностью, освободить для других нужд. (Ресурсов нехватает всегда - это закон.)
Для работы со статическими объектами в языках программирования используется хорошо известный механизм имен. Pascal здесь не исключение. Однако, этот механизм вряд ли нам подходит для представления и манипуляции с динамическими объектами. Дело в том, что имя должно быт известно до выполнения программы - это во-первых. Во вторых, порождение всякого именованного объекта связано с выделением памяти. Раз объекты возникают динамически, то заранее мы не знаем сколько их будет. Следовательно не можем заранее выделить(породить, написать, придумать) нужное количество имен. Далее, не ясно чему соответствует в памяти имя не существующего объекта. Когда объект стал не нужен мы не можем уничтожить имя. Нет таких средств в языке. С другой стороны,уже при написании программы нам надо как-то описывать действия над динамическими объектами.
Для решения этой проблемы в программировании был предложен механизм ссылок. Идея его состоит в том, что данамические объекты представлены не явно, а через некоторую статическую переменную, которая указывает на место расположения динамического объекта, если он существует, либо содержит специальное значение - объект отсутствует. Что значит указывает? Это значит что ее значение - "имя" динамического объекта. Это специальное имя, называемое ссылкой (саму переменную, при этом, часто называют указателем) и которое указывает где размещается, как найти объект и получить доступ к значению.
В случае Pascal такми именем является адрес в памяти где размещается динамический объект. Каждый раз, когда порождается динамический объект ему выделяется место в памяти. Адрес начала выделенной области памяти полагается в качестве значения ссылочной переменной, представляющей динамический объект. При уничтожении динамического объекта занимаемая им память считается свободной, а соответствующая ссылочная переменная принимает специальной значение - нет объекта. Все действия над динамическими объектами в программе описываются как действия над значениями ссылочных переменных. Каждая ссылочная переменная указыает, представляет всегда только один динамический объект.
К недостаткам такого решения можно отнести следующее. Если значение ссылочной переменной (ссылка на динамический объект) будет утеряно - этот объект будет безвозвратно утерян. Ведь его "имени" мы явно не знаем. Оно есть значение ссылочной переменной. Если несколько ссылочных переменных указывают на один и тот же объект и этот объект будет уничтожен с помощью одной из них, то все манипуляции с другими ссылочными переменными станут не корректными.
2. Описание ссылочных переменных и их семантика
Синтаксис задания ссылочного типа:
<задание ссылочного типа>::= ^<имя типа>
^ - признак ссылочного типа, имя типа - имя стандартного либо описанного ранее типа. Это тип динамических объектов, которые может представлять переменная ссылочного типа. Надо подчеркнуть , что здесь может быть только имя типа.
Сами переменнаые ссылочного типа вводятся обычным образом.
type
массив = array [1..100]of integer;
массивссылок= array [1..100]of ^integer;
var
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
