Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

для т

.pdf
Скачиваний:
6
Добавлен:
14.05.2015
Размер:
557.02 Кб
Скачать

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

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}

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

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

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]