shpory

32. Оператор безусловного перехода goto.

Оператор безусловного перехода goto имеет следующую форму:

goto метка

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

label1: оператор

Метки должны быть описаны в разделе меток с использованием служебного слова label:

label 1,2,3;

Например, в результате выполнения программы

label 1,2; begin

var i := 5;

2: if i<0 then goto 1; write(i);

Dec(i); goto 2; 1:

end.

будет выведено 543210.

Метка должна помечать оператор в том же блоке, в котором описана. Метка не может помечать несколько операторов.

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

Использование оператора безусловного перехода в программе считается признаком плохого стиля программирования. Для основных вариантов использования goto в язык Паскаль введены специальные процедуры: break - переход на оператор, следующий за циклом, exit - переход за последний оператор процедуры, continue - переход за последний оператор в теле цикла.

Единственный пример уместного использования оператора goto в программе - выход из нескольких вложенных циклов одновременно. Например, при поиске элемента k в двумерном массиве:

var a: array [1..10,1..10] of integer;

...

var found := False; for var i:=1 to 10 do for var j:=1 to 10 do if a[i,j]=k then begin

found := True; goto c1;

end;

c1: writeln(found);

26. Реализация ветвления в ЯП. Оператор условного перехода

Оператор условного перехода в Турбо Паскаль имеет вид:

if условие then оператор 1 else оператор 2;

условие - это логическое выражение, в зависимости от которого выбирается одна из двух альтернативных ветвей алгоритма. Если значение условия истинно (TRUE), то будет выполняться оператор 1, записанный после ключевого слова then. В противном случае будет выполнен оператор 2, следующий за словом else, при этом оператор 1 пропускается. После выполнения указанных операторов программа переходит к выполеннию команды, стоящей непосредственно после оператора if.

Необходимо помнить, что перед ключевым словом else точка с запятой никогда не ставится!

else - часть в операторе if может отсутствовать:

if условие then оператор 1;

Тогда в случае невыполнения логического условия управление сразу передается оператору, стоящему в программе после конструкции if.

Следует помнить, что синтаксис языка допускает запись только одного оператора после ключевых слов then и else, поэтому группу инструкций обязательно надо объединять в составной оператор (окаймлять операторными скобками begin ... end). В противном случае возникает чаще всего логическая ошибка программы, когда компилятор языка ошибок не выдает, но программа тем не менее работает неправильно.

9. Логический тип

Базовый тип данных - данные логического типа.

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

Другое название Булевый. Допустимые значения ["истина", "ложь"]. Данные этого типа хранят значения всевозможных условий, пори помощи которых образуются ветвления и циклы (вспомните урок про структуры алгоритмов).

Способы представления (хранения).

BASIC	PASCAL	C
не	<им.пер.>:b	не
выделен	oolean;	выделен,
, но	"истина"=t	но
"истина	rue	"истина
"=-1	"ложь"=fal	"= 1
"ложь"	se	"ложь"=
= 0		0
целого		целого
типа		типа

Основные операции. (Образование сложных условий.)

При работе с логическими данными используются операции:

унарная – отрицание. Как выполняются логические операции нетрудно разобраться с помощью таблиц истинности. В этих таблицах 1 соответствует истине, 0 обозначает ложь.

отрицание │ A │not A│

─┼───┼─────┼

│ 0 │ 1 │

│ 1 │ 0 │

Имеются бинарные (с двумя аргументами) операции:

not a	not a	отрицание
a and b	a and b	логическое И
a or b	a or b	логическое ИЛИ
a xor b	a xor b	исключающее ИЛИ

Эти операции реализованы и в бейсике, и в паскале.

Операции

a imp b	-	импликация (следование)
a eqv b	-	эквивалентность

имеются только в бейсике.

Специалисты по математической логике знают, как любую логическую формулу представить в виде набора операций, состоящих из конъюнкций (логическое «И»), дизъюнкций (логическое «ИЛИ») и отрицаний (логическое «НЕ»).

таблицы истинности бинарных операций

A │ B │and│ or│xor│eqv│imp

──┼───┼───┼───┼───┼───┼───

0 │ 0 │ 0 │ 0 │ 0 │ 1 │ 1

0 │ 1 │ 0 │ 1 │ 1 │ 0 │ 1

1 │ 0 │ 0 │ 1 │ 1 │ 0 │ 0

1 │ 1 │ 1 │ 1 │ 0 │ 1 │ 1

BASIC	PASCAL
not a	not a	отрицание
a and b	a and b логическое И
a or b	a or b логическое ИЛИ
a xor b	a xor b исключающее ИЛИ
a imp b	-	импликация (следование)
a eqv b	-	эквивалентность

Образуются данные логического типа при сравнении данных одинакового типа на совпадение (равны, не равны).

Если тип упорядочен, допустимы сравнения: > , >= , < , >= .

Вязыке PASCAL есть функция определения четности числа:

odd(x) = true , если аргумент четный,

=false , если аргумент нечетный.

Вязыке BASIC можно перемешивать данные числовых и логического типа:

функция y=F(x) при x>a

=G(x) при x<=a

может быть записана y=-F(x)*(x>a)-G(x)*(x<=a).

34. Переменные.

Переменная – это область оперативной памяти компьютера, которая может хранить данные во время работы программы.

Переменная имеет:Имя (x, text, bm,), значение (число, текст, символ ) ,тип (целый, вещественный, символьный, строковый)

Имя переменной (идентификатор): начинается с буквы, содержит буквы (лучше лат) и цифры, длина имени не должна превышать 255 символов, нельзя использовать зарезервированные слова, не должно содержать пробелов и специальных символов.

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

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

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

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

Определение переменной заключается в указании ее имени (идентификатора) и типа.

Имя и тип разделяются двоеточием.

После объявления и описания переменной должен стоять символ ";".

Концом блока описания будет начало какого-либо другого блока программы или описание процедур и функций.

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

Тип переменной

Целый тип (Byte, Integer)– для использования целых чисел

Вещественный тип (Real)– для использования дробных чисел

Символьный тип (Char)– это любые буквы алфавита, символы и цифры 0-9 (один символ). Использование отдельных символов, заключаются в знаки апострофов, например 'а', '4', '+', '-', либо код символа #126

Строковый тип (составной) (String)– для использования наборов символов, заключенных в знаки апострофов, например 'тип', '123'

Напомним, что каждый модуль (процедура, функция, программа) состоит из заголовка (procedure…, function…, program…) и блока.

Если блок какой-либо процедуры p1 содержит внутри процедуру p2, то говорят, что p2 вложена в p1.

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

Константы, переменные, типы, описанные в блоке program, называются глобальными. Казалось бы, проще иметь дело вообще только с глобальными переменными, описав их все в program. Но использование локальных переменных позволяет системе лучше оптимизировать программы, делать их более наглядными и уменьшает вероятность появления ошибок.

27. Реализация выбора в ЯП. Оператор выбора

Часто возникают ситуации, когда приходится осуществлять выбор одного из нескольких альтернативных путей выполнения программы. Несмотря на то, что такой выбор можно организовать с помощью оператора if .. then, удобнее воспользоваться специальным оператором выбора. Его формат:

case выражение of

вариант : оператор;

...

вариант : оператор;

end;

или

case выражение of

вариант : оператор;

...

вариант : оператор;

else оператор

end;

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

31. Процедуры и функции пользователя в ЯП.

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

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

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

Различают формальные параметры – параметры, определенные в заголовке подпрограммы, и фактические параметры – выражения, задающие конкретные значения при обращении к подпрограмме. При обращении к подпрограмме ее формальные параметры замещаются фактическими, переданными из главной программы.

Процедуры

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

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

procedure <имя> (Формальные параметры);

const ...;

type ...;

var ...;

begin

<операторы процедуры>

end;

Функции

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

function <имя> (Формальные параметры) : тип результата;

const ...;

type ...;

var ...;

begin

<операторы функции>

end;

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

Обращение к функции осуществляется по имени с необязательным указанием списка аргументов. Каждый аргумент должен соответствовать формальным параметрам, указанным в заголовке, и иметь тот же тип.

2)«Алгоритм и его свойства»

Понятие алгоритма

Из отсутствия четкого определения алгоритма делаем вывод, что алгоритм - неопределяемое понятие и, как и для неопределяемых понятий в других науках, применяется Аксиоматическое построение: выбирается система аксиом, и любые объекты, которые будут удовлетворять этой системе и будут алгоритмами.

Такой системой аксиом являются основные свойства алгоритмов.

Основные свойства алгоритмов

*ДВА СПОСОБА ИСПОЛЬЗОВАНИЯ АЛГОРИТМА

- алгоритм можно

1)записать по определенным правилам

2)исполнить

Вязыке BASIC имеются две отдельные команды: LIST – показать текст записи программы,

RUN – исполнить программу

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

* НАЛИЧИЕ ИСПОЛНИТЕЛЯ

- алгоритм может быть выполнен (это система команд для кого-то или чего-то)

Исполнитель может ничего не знать о цели алгоритма. Исполнитель должен понимать отдельные команды.

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

* РЕЗУЛЬТАТИВНОСТЬ

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

* ОДНОЗНАЧНОСТЬ

- применение алгоритма к одним и тем же данным дает один и тот же результат.

* ДЕТЕРМИНИРОВАННОСТЬ

- строгая определенность, однозначность, непротиворечивость правил

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

фиксируется начальный и заключительный шаги алгоритма.

* МАССОВОСТЬ

- алгоритм дает решение не одной, а целого набора задач.

*ДВА СПОСОБА ИСПОЛЬЗОВАНИЯ АЛГОРИТМА

*НАЛИЧИЕ ИСПОЛНИТЕЛЯ

*РЕЗУЛЬТАТИВНОСТЬ

*ОДНОЗНАЧНОСТЬ

*ДЕТЕРМИНИРОВАННОСТЬ

*МАССОВОСТЬ

Основы программирования

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

* Однородность памяти И данные, и команды представляются одинаково. Компьютер не различает, что находится в ячейке памяти: команда, число или текст.

* Адресность Основная память состоит из пронумерованных ячеек

* Двоичность Информация кодируется двоичным числом.

.Оформление программ

С развитием компьютерной информатики все более четко выделяются

ДАННЫЕ - все объекты, с которыми может работать ЭВМ и КОМАНДЫ - средства, которые при этом используются.

Данные, это материалы, определяют, с чем работает компьютер, Команды, это инструменты (операторы, процедуры, функции), определяют, как поступать с данными, а иногда и с самими командами.

При работе ЭВМ данные могут менять свои значения. Для обеспечения такой возможности служат ПЕРЕМЕННЫЕ. Переменная - это выделенная для хранения определенной информации область памяти, соответственно имеет адрес начала в памяти и размер. Для удобства использования и отличий между собой переменные снабжаются ИДЕНТИФИКАТОРОМ, проще говоря каждая переменная получает ИМЯ. Информацию, хранящуюся в переменной в момент обращения к этой переменной называют ЗНАЧЕНИЕМ переменной.

Занесение значения в память называется операцией присваивания.

6 рекурсия

Подпрограммы в Паскале могут обращаться сами к себе. Такое обращение называется рекурсией.

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

Пример.Рассмотрим математическую головоломку из книги Ж. Арсака «Программирование игр и головоломок».

Построим последовательность чисел следующим образом: возьмем целое число i>1. Следующий член последовательности равен i/2, если i четное, и 3 i+1, если i нечетное. Если i=1, то последовательность останавливается.

Математически конечность последовательности независимо от начального i не доказана, но на практике последовательность останавливается всегда.

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

Пример программы с использованием рекурсии

Program Arsac;

Var first: word;

Procedure posledov (i: word);

Begin

Writeln (i);

If i=1 then exit;

If odd(i) then posledov(3*i+1) else posledov(i div 2);

End;

Begin

Write (‘ введите первое значение ’); readln (first);

Posledov (first);

Readln ;

End.

Виды рекурсий

1.Простая а) Хвостовая рекурсия — специальный случай рекурсии, при котором рекурсивный вызов функцией самой себя является её последней операцией. б) Если в процедуре рекурсивный вызов не является завершающей инструкцией, то такая рекурсия называется

вложенной.

2.Сложная или косвенная :Функция A вызывает функцию B, а функция B — функцию A.

Рекурсия и цикл Что такое цикл?

Цикл – разновидность управляющей конструкции. Управляет она, очевидно, выполнением кода (как например, конструкция if (условие) [then] оператор, где оператор выполняется, только если условие истинно).

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

На псевдокоде цикл с предусловием обычно обозначается так:

while (условие) do{оператор1; оператор2; … } Здесь в круглых скобках записано условие цикла, а в фигурных – тело цикла. Например, так можно распечатать все числа от nдо 1:

while (n > 0) do{// на каждом шаге цикла проверяем, не стало ли n <= 0, т.е. не выполнилось ли условие выхода из цикла print(n);// печатаем текущее значение n n = n — 1;// уменьшаем значение n, чтобы оно в конце концов стало меньше 0 и мы вышли из цикла }

Этот фрагмент кода делает следующее: на каждом шаге цикла сначала проверяется условие, что n > 0, т.к. если оно не выполнено, нам будет необходимо прекратить выполнение дальнейших действий, связанных с поставленной задачей. Если условие оказалось ложно, т.е. n уже меньше либо равно нулю, тело цикла не выполняется и работа этого кода заканчивается. Если же оно окажется истинно, и n все еще больше нуля, т.е. его можно печатать, то выполняется тело цикла: n печатается и уменьшается на единицу, чтобы перейти к следующему значению n. Затем снова выполняет проверка условия, т.е. делается следующий шаг цикла.

При чем здесь рекурсия?

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

dec_print(n) {if (n > 0) then { // проверка условия, как в циклеprint(n); // печать очередного значения n dec_print(n-1); // вызов функции от следующего значения n } }

На каждом шаге рекурсии проверяется условие n > 0. Если оно не выполнится, ничего больше происходить не будет, т.к. нет ветки else, точно так же, как и в цикле. Если же оно истинно, будут выполнены операторы во вторых фигурных скобках: сначала напечатано очередное значение n, а потом вызвана та же функция от уменьшенного значения n – последнее равносильно выполнению оператора n = n — 1; в цикле и переходу к следующему шагу. Этот вызов функции снова запустит выполнение аналогичных действий: сначала проверка истинности условия, а затем выполнение действий в зависимости от результатов проверки. Заметим, все ровно так же, как и в цикле, только записано иначе, но все равно очень похоже.

Теперь попробуем задать такое преобразование в общем виде. Цикл с предусловием, как сказано выше, имеет следующий вид: while (условие) do{оператор1; оператор2; … }

Его можно заменить такой рекурсивной функцией:

cycle(...) { // параметры зависят от того, что происходит в циклеif (условие) then {// проверка такого же условия, как в циклеоператор1; // операторы из тела циклаоператор2; … cycle(...); // рекурсивный вызов функции } }

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

30.Реализация цикла с параметром в ЯП Цикл – это многократно повторяющиеся фрагменты программ. Алгоритм циклической структуры – это алгоритм, содержащий циклы. В ТР существует три оператора цикла:цикл с предусловием, цикл с постусловием, цикл с параметром. Для всех циклов характерны следующие особенности:значения переменных используемых в цикле, и не изменяющиеся в нем д.б. определены до входа в цикл;вход в цикл

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

Формат записи:

1.For P:=Pn to Pk do OP;

2.For P:=Pk downto Pn do OP;

где: For - для;to – до;downto – уменьшая до;do – выполнить;OP – тело цикла; оператор (простой или составной); P - параметр цикла, переменная порядкового типа; Pn, Pk – начальное и конечное значение параметра. Работа оператора: Вычисляется начальное значение параметра цикла Pn и присваивается параметру P. Проверяется условие P?Pk, и если оно Trueвыполняются операторы тела цикла OP . После чего наращивается значение P на единицу и опять проверяется условие P?Pk . Если

условие False осуществляется выход из цикла.
В операторе с downto шаг изменения параметра цикла равен –1.	Примеры записи:	For i:=1 to n
do n:=sqr(i)+1;
For s:=’A’ to ‘Z’ do R:=R+ord(s)/127;
For L:=False to True do H:= (False or L) And Not (L);
Пример. Составить программу вычисления функции y для заданного значения n.

где: C=2,7; a=0.5; t=0,1; 0<n<10; Dn=1.

Program Ex_3;
Uses crt;
Var y, C, a, t :real; n	:integer;
Begin
clrscr;
Writeln('Введите C, a,	t');
Read(C, a, n);
Writeln('Результат:');
Writeln(‘n’:5,’y’:15);
For n:=1 to 10 do
Begin

y:=C*exp(a*t)*cos(n*t); Writeln(n:4,’ ‘:5, y:10); end; End.

12)Строковый (литерный).

К базовым, с некоторой натяжкой, можно отнести тип данных «строка».

Способ хранения и набор операций со строками компьютеру известны, но, фактически, строка – это упорядоченный набор знаков. По умолчанию, для хранения строки выделено 256 байт, но при желании можно длину строк уменьшить, память сэкономить.

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

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

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

Тип строка в языке pascal отмечается словом string, в языке basic, после имени переменной пишут знак доллара ’$’, в некоторых версиях вместо знака доллара используется знак «солнышко» - круг поверх косого креста.

0	1	2	3	4	5	6	...	255
	б	у	к	в	ы
код 5	код б	код у	код к	код в	код ы

Первый знак строки занимает 1 байт, второй – второй, ...

Нулевой байт хранит длину строки.

pascal basic

var s:string;

s$=”буквы”

begin s:=’буквы’; end. (s¤=”буквы”)

К операциям преобразования строк относим:

Выделение части строки (с указанного места указанной длины).

Конкатенация, соединение (склейка) двух строк в одну. (Часто операция обозначается знаком ‘+’ между аргументами.)

Удаление части строки.

Вставка одной строки внутрь другой.

Не реализованные в некотором языке операции вполне заменимы набором имеющихся.

Например, удалить часть строки можно путем склейки кусочка слева и кусочка справа. Средняя часть будет потеряна.

BASIC PASCAL

выполняем вырезку из строки =mid$(s$,m,l) =copy(s,m,l)

=left$(s,l)
=right$(s,l)
склеиваем две строки	=s1$+s2$	=concat(s1,s2)
удаляем часть строки	delete(s,m,l)
вставляем строку в строку		insert(p,s,m)
замена фрагмента строки	mid$(a$,m,x)=

О строке можно извлечь информацию:

Число – длину строки.

Номер места, начиная с которого одна строка находится внутри другой (поиск подстроки в строке).

Имеются просто команды преобразования числа в строку цифр и, обратно, строки цифр в число.

BASIC	PASCAL
определяем длину строки	=len(s$)	=length(s)
ищем подстроку в строке	=instr(s$,p$)	=pos(p,s)
преобразуем число в строку =str$(x)		str(n,s)
=bin$(x)
=oct$(x)
=hex$(s)
преобразуем строку в число	=val(x$)	val(s,n,c)

15. Указатели. Выделение и возвращение памяти. ДИНАМИЧЕСКАЯ ПАМЯТЬ

Динамическая память -- это оперативная память ПК, предоставляемая программе при ее работе, за вычетом сегмента данных (64 Кбайт), стека (обычно 16 Кбайт) и собственно тела программы. Размер динамической памяти можно варьировать в широких пределах. По умолчанию этот размер определяется всей доступной памятью ПК и, как правило, составляет не менее 200...300 Кбайт. АДРЕСА И УКАЗАТЕЛИ Оперативная память ПК представляет собой совокупность элементарных ячеек для хранения информации -- байтов, каждый из которых имеет собственный номер. Эти номера называются адресами, они позволяют обращаться к любому байту памяти. .Указатель -- это переменная, которая в качестве своего значения содержит адрес байта памяти. В ПК адреса задаются совокупностью двух шестнадцатиразрядных слов, которые называются сегментом и смещением. Сегмент -- это участок памяти, имеющий длину 65536 байт (64 Кбайт) и начинающийся с физического адреса, кратного 16 (т.е. 0, 16, 32, 48 и т.д.). Смещение указывает, сколько байт от начала сегмента необходимо пропустить, чтобы обратиться к нужному адресу. Адресное пространство ПК составляет 1 Мбайт (речь идет о так называемой стандартной памяти ПК; на современных компьютерах с процессорами 80386 и выше адресное пространство составляет 4 Гбайт, однако в Турбо Паскале нет средств, поддерживающих работу с дополнительной памятью; при использовании среды Borland Pascal with Objects 7.0 такая возможность имеется). Для адресации в пределах 1 Мбайта нужно 20 двоичных разрядов, которые получаются из двух шестнадцатиразрядных слов (сегмента и смещения) следующим образом: содержимое сегмента смещается влево на 4 разряда, освободившиеся правые разряды заполняются нулями, результат складывается с содержимым смещения.

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

Таким образом, по своей внутренней структуре любой указатель представляет собой совокупность двух слов (данных типа WORD), трактуемых как сегмент и смещение. С помощью указателей можно размещать в динамической памяти любой из известных в Турбо Паскале типов данных. Лишь некоторые из них (BYTE, CHAR, SHORTINT, BOOLEAN) занимают во внутреннем представлении один байт, остальные -- несколько смежных. Поэтому на самом деле указатель адресует лишь первый байт данных.ВЫДЕЛЕНИЕ И ОСВОБОЖДЕНИЕ ДИНАМИЧЕСКОЙ ПАМЯТИ Вся динамическая память в Турбо Паскале рассматривается как сплошной массив байтов, который называется кучей. Физически куча располагается в старших адресах сразу за областью памяти, которую занимает тело программы. Начало кучи хранится в стандартной переменной HEAPORG, конец - в переменной HEAPEND. Текущую границу незанятой динамической памяти указывает указатель HEAPPTR.

Расположение кучи в памяти ПК

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

var

i, j: ^integer;

r: ^real;

begin

New(i);

. . . . .

end. После выполнения этого фрагмента указатель i приобретет значение, которое перед этим имел указатель кучи HEAPPTR, а сам HEAPPTR увеличит свое значение на 2, так как длина внутреннего представления типа INTEGER, с которым связан указатель i, составляет 2 байта (на самом деле это не совсем так: память под любую переменную выделяется порциями, кратными 8 байтам). Оператор

new(r);вызовет еще раз смещение указателя HEAPPTR, но теперь уже на 6 байт, потому что такова длина внутреннего представления типа REAL. Аналогичным образом выделяется память и для переменной любого другого типа. После того как указатель приобрел некоторое значение, т.е. стал указывать на конкретный физический байт памяти, по этому адресу можно разместить любое значение соответствующего типа. Для этого сразу за указателем без каких-либо пробелов ставится значок ^, например:

i^ := 2; {В область памяти i помещено значение 2}

r^ := 2*pi; {В область памяти r помещено значение 6.28}

Таким образом, значение, на которое указывает указатель, т.е. собственно данные, размещенные в куче, обозначаются значком ^, который ставится сразу за указателем. Если за указателем нет значка ^, то имеется виду адрес, по которому размещены данные. Имеет смысл еще раз задуматься над только что сказанным: значением любого указателя является адрес, а чтобы указать, что речь идет не об адресе, а о тех данных, которые размещены по этому адресу, за указателем ставится ^. Если Вы четко уясните себе это, у Вас не будет проблем при работе с динамической памятью.

Динамически размещенные данные можно использовать в любом месте программы, где это допустимо для констант и переменных соответствующего типа, например:

r^ := sqr(r^) + i^ - 17;

Разумеется, совершенно недопустим оператор

r := sqr(r^) + i^ - 17;

так как указателю R нельзя присвоить значение вещественного выражения. Точно так же недопустим оператор

r^ := sqr(r);

поскольку значением указателя R является адрес, и его (в отличие от того значения, которое размещено по этому адресу) нельзя возводить в квадрат. Ошибочным будет и такое присваивание:

r^ := i;

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

Динамическую память можно не только забирать из кучи, но и возвращать обратно. Для этого используется процедура DISPOSE. Например, операторы

dispose(r);

dispose(i);

вернут в кучу 8 байт, которые ранее были выделены указателям I и R.

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

const

р: ^real = NIL;

begin

. . . . .

if р = NIL then

new(p);

. . . . .

dispose(p);

p := NIL;

. . . . .

end.

Никакие другие операции сравнения над указателями не разрешены. Приведенный выше фрагмент иллюстрирует предпочтительный способ объявления указателя в виде типизированной константы с одновременным присвоением ему значения NIL. Следует учесть, что начальное значение указателя (при его объявлении в разделе переменных) может быть произвольным. Использование указателей, которым не присвоено значение процедурой NEW или другим способом, не контролируется системой и может привести к непредсказуемым результатам. Чередование обращений к процедурам NEW и DISPOSE обычно приводит к ╚ячеистой╩ структуре памяти. Дело в том, что все операции с ней выполняются под управлением особой подпрограммы, которая называется администратором кучи. Она автоматически пристыковывается к нашей программе компоновщиком Турбо Паскаля и ведет учет всех сводных фрагментов в куче. При очередном обращении к процедуре NEW эта подпрограмма отыскивает наименьший свободный фрагмент, в котором еще может разместиться требуемая переменная. Адрес начала найденного фрагмента возвращается в указателе, а сам фрагмент или его часть нужной длины помечается как занятая часть кучи.

Другая возможность состоит в освобождении целого фрагмента кучи. С этой целью перед началом выделения динамической памяти текущее значение указателя HEAPPTR запоминается в переменной-указателе с ющью процедуры MARK. Теперь можно в любой момент освободить фрагмент кучи, начиная от того адреса, который запомнила процедура MARК, и до конца динамической памяти. Для этого используется процедура RELEASE. Например:

var

p,p1,p2,р3,р4,р5: ^integer;

begin

new(p1);

new(p2);

mark(p);

new(p3);

new(p4);

new(p5);

. . . . .

release(p);

end.

В этом примере процедурой MARK(P) в указатель Р было помещено тукущее значение HEAPPTR, однако память под переменную не резервировалась. Обращение RELEASE(P) освободило динамическую память от помеченного места до конца кучи. Пирведенный ниже рисунок иллюстрирует механизм работы процедур NEW-DISPOSE и NEW-MARK-RELEASE для рассмотренного примера и для случая, когда вмемто оператора RELEASE(P) используется, например, DISPOSE(P3).

а)

б)

в)

Состояние динамической памяти:

а) перед освобождением; б) после Dispose(p3); в) после Release(p)Следует учесть, что вызов RELEASE уничтожает список свободных фрагментов в куче, созданных до этого процедурой DISPOSE, поэтому совместное использование обоих механизмов освобождения памяти в рамках одной программы не рекомендуется.

22. язык программирования алфавит, синтаксис ,лексема, семантика.Комментарии , пространство имен,ключевые слова. Основными элементами любого языка программирования являются его алфавит, синтаксис и семантика. Алфавит – совокупность символов, отображаемых на устройствах печати и экранах и/или вводимых с клавиатуры терминала. Лексика – совокупность правил образования цепочек символов (лексем), образующих идентификаторы (переменные и метки), операторы, операции и другие лексические компоненты языка. Сюда же включаются зарезервированные (запрещенные, ключевые) слова языка программирования, предназначенные для обозначения операторов, встроенных функций и пр. Иногда эквивалентные лексемы, в зависимости от языка программирования, могут обозначаться как одним символом алфавита, так и несколькими. Например, операция присваивания значения в языке Си обозначается как «=», а в языке Паскаль – «:=». Операторные скобки в языке Си задаются символами «{» и «}», а в языке Паскаль – begin и end. Граница между лексикой и алфавитом, таким образом, является весьма условной, тем более что компилятор обычно на фазе лексического анализа заменяет распознанные ключевые слова внутренним кодом (например, begin – 512, end – 513) и в дальнейшем рассматривает их как отдельные символы. Синтаксис – совокупность правил образования языковых конструкций, или предложений языка программирования – блоков, процедур, составных операторов, условных операторов, операторов цикла и пр. Особенностью синтаксиса является принцип вложенности (рекурсивность) правил построения конструкций. Это значит, что элемент синтаксиса языка в своем определении прямо или косвенно в одной из его частей содержит сам себя. Например, в определении оператора цикла телом цикла является оператор, частным случаем которого является все тот же оператор цикла.Необходимо строгое соблюдение правил правописания (синтаксиса) программы. В частности, в Паскале однозначно определено назначение знаков пунктуации. Точка с запятой (;) ставится в конце заголовка программы, в конце раздела описания переменных, после каждого оператора. Перед словом End точку с запятой можно не ставить. Запятая (,) является разделителем элементов во всевозможных списках: списке переменных в разделе описания, списке вводимых и выводимых величин.В БНФ(формула Бекуса – Наура) всякое синтаксическое понятие описывается в виде формулы, состоящей из правой и левой части, соединенных знаком ::=, смысл которого эквивалентен словам «по определению есть». Слева от знака ::= записывается имя определяемого понятия (метапеременная), которое заключается в угловые скобки <>, а в правой части записывается формула или диаграмма, определяющая все множество значений, которые может принимать метапеременная. Синтаксис языка описывается путем последовательного усложнения понятий: сначала определяются простейшие (базовые), затем все более сложные, включающие в себя предыдущие понятия в качестве составляющих.

В записях метаформул приняты определенные соглашения. Например, формула БНФ, определяющая понятие «двоичная цифра», выглядит следующим образом: <двоичная цифра>::=0|1 Значок «|» эквивалентен слову «или».В диаграммах стрелки указывают на последовательность расположения элементов синтаксической конструкции; кружками обводятся символы, присутствующие в конструкции.Понятие «двоичный код» как непустую последовательность двоичных цифр БНФ описывает так:<двоичный код>::=<двоичная цифра>|<двоичныйкод><двоичная цифра>Определение, в котором некоторое понятие определяется само через себя, называется рекурсивным. Рекурсивные определения характерны для БНФ.Возвратная стрелка обозначает возможность многократного повторения. Очевидно, что диаграмма более наглядна, чем БНФ.Синтаксические диаграммы были введены Н. Виртом и использованы для описания созданного им языка Паскаль.Семантика – смысловое содержание конструкций, предложений языка, семантический анализ – это проверка смысловой правильности конструкции. Например, если мы в выражении используем переменную, то она должна быть определена ранее по тексту программы, а из этого определения может быть получен ее тип. Исходя из типа переменной, можно говорить о допустимости операции с данной переменной. Семантические ошибки возникают при недопустимом использовании операций, массивов, функций, операторов и пр. Пространство имён — некоторое множество, под которым подразумевается модель, абстрактное хранилище или окружение, созданное для логической группировки уникальных идентификаторов (то есть имён). Идентификатор, определенный в пространстве имён, ассоциируется с этим пространством. Один и тот же идентификатор может быть

независимо определён в нескольких пространствах. Таким образом, значение, связанное с идентификатором, определённым в одном пространстве имён, может иметь (или не иметь) такое же значение, как и такой же идентификатор, определённый в другом пространстве. Языки с поддержкой пространств имён определяют правила, указывающие, к какому пространству имён принадлежит идентификатор (то есть его определение). Например, Андрей работает в компании X, а ID (сокр. от англ. Identifier — идентификатор) его как работника равен 123. Олег работает в компании Y, а его ID также равен 123. Единственное (с точки зрения некой системы учёта), благодаря чему Андрей и Олег могут быть различимы при совпадающих ID, это их принадлежность к разным компаниям. Различие компаний в этом случае представляет собой систему различных пространств имён (одна компания — одно пространство). Наличие двух работников в компании с одинаковыми ID представляет большие проблемы при их использовании, например, по платёжному чеку, в котором будет указан работник с ID 123, будет весьма затруднительно определить работника, которому этот чек предназначается. В больших базах данных могут существовать сотни и тысячи идентификаторов. Пространства имён (или схожие структуры) реализуют механизм для сокрытия локальных идентификаторов. Их смысл заключается в группировке логически связанных идентификаторов в соответствующих пространствах имён, таким образом делая систему модульной. Ограничение видимости переменных может также производиться путём задания класса её памяти. Операционные системы, многие современные языки программирования обеспечивают поддержку своей модели пространств имён: используют каталоги (или папки) как модель пространства имён. Это позволяет существовать двум файлам с одинаковыми именами (пока они находятся в разных каталогах). В некоторых языках программирования

(например, C++, Python) идентификаторы имён пространств сами ассоциированы с соответствующими пространствами. Поэтому в этих языках пространства имён могут вкладываться друг в друга, формируя дерево пространств имён. Корень такого дерева называется глобальным пространством имён.

4)Линейный алгоритм

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

Алгоритм назовем линейным, если:1) выполняется каждый его шаг, и 2) только один раз.

Такого определения вполне достаточно. В некоторых учебниках используются слова «шаги выполняются последовательно, друг за другом», но эти слова означают наличие некоторого порядка. А порядков имеется два!

Одним из свойств алгоритма является, что его можно использовать двояко: либо исполнить, либо записать по определенным правилам. Таким образом первый порядок – порядок исполнения команд, второй – порядок написания. Эти порядки могут не совпадать.

На рисунке слева – случай, когда порядок написания и порядок исполнения совпадают, справа – эти порядки различны. Может показаться, что на рисунке справа алгоритм не линеен, так как команды выполняются не «друг за другом», а сначала вторая, потом первая. Но если определить линейный алгоритм как указано выше - Алгоритм линейный, если выполняется каждый его шаг, и только один раз – то эта проблема снимается.

Линеен алгоритм обмена, алгоритмы деления угла или отрезка пополам и многие другие.

Ветвление неполное

Вернемся к нашему определению линейного алгоритма и попытаемся определить остальные алгоритмические структуры.

Для начала, откажемся от требования 1), обязательности выполнения каждого шага алгоритма.

Имеем алгоритм, в котором некоторые шаги могут не выполняться.

Получившаяся структура алгоритма называется. НЕПОЛНОЕ ВЕТВЛЕНИЕ

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

Если условие истинно – шаг алгоритма выполняется, иначе – нет.

Всевозможные условия являются объектом работы, то есть ДАННЫМИ, которые могут иметь либо значение истина, либо значение ложь. Образуются эти значения при сравнении двух переменных или выражений одного типа.

A=B;A<>B;X<>5;A>5;B<3;C<=A+B

Значения этих выражений «истинно» (true) или «ложно» (false) зависит от значений используемых переменных.

На языке блок-схем блок ветвления обозначается ромбом, имеет один вход и два выхода. Однако любой алгоритм должен обладать свойством результативности, то есть у него должен быть конец и только один. Обе ветви, для достижения конца соединяются, место соединения называется УЗЕЛ и на блок-схеме отмечается кружком.

Наличие двух выходов так же представляет собой проблему. Выходы должны быть разными. Поэтому они маркируются словами «да» и «нет» или знаками «+» и «-». Согласно первому выходу алгоритм продолжаем при истинности условия, которое вписывается в ромб, иначе – продолжаем согласно второму выходу. Лентяи просто ставят около выхода «да» точку. Этого достаточно для однозначного определения дальнейших шагов алгоритма.

Цикл

Ветвление - один из случаев нарушения линейности алгоритма.

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

Однако ветви могут соединиться и перед блоком условия!

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

Такая организация алгоритма называется ЦИКЛ.

Шаги, которые могут выполняться несколько раз подряд образуют ТЕЛО цикла. Выполнять или нет тело еще раз решает УСЛОВИЕ цикла.

Итак, любой цикл имеет ТЕЛО и УСЛОВИЕ ВЫХОДА.

Снова вспоминаем свойство алгоритма, что его можно исполнить и его можно записать.

Две составных части цикла – тело и условие – можно записать по разному: либо сначала условие, потом тело, либо сначала тело, потом условие.

В первом случае цикл называется циклом типа «пока», во втором – циклом типа «до».

Так выглядит оформление цикла с предусловием (цикла «пока») в разных языках программирования.

basi				pascal		C
c
10 if
<
усл.>
then
40
20
<тело
цикла
"ПОК
А">
30
goto
10
40
while
<усл.>
<тел
о
цикла
"ПОК
А">
wend
А так
выглядит
оформле
ние
цикла с
постусло
вием
(цикла
«до») в
языках
програм
мирован
ия.
basic
10 rem				repeat		do
начало
цикла				<тел		{<тел
20 <тело
цикла				о		о
«ДО»>				цикла		цикла
						"ДО">
						}