|
|
| Строка 1: |
Строка 1: |
| | [[Категория:Конспекты]] | | [[Категория:Конспекты]] |
| − | ==Подпрограммы== | + | [[Категория:Основы программирования]] |
| − | ===Вспомогательные алгоритмы=== | + | == Циклы с предусловием (while) и постусловием (repeat) == |
| − | '''Вспомогательный алгоритм''' — это алгоритм, который используется для реализации другого алгоритма. | + | === Синтаксис цикла while === |
| | + | '''while''' <условие> '''do''' <— '''''заголовок цикла''''' |
| | + | <оператор> <— '''''тело цикла''''' |
| | + | |
| | + | <условие>::= <логическое выражение> |
| | | | |
| − | Вспомогательные алгоритмы имеют:
| + | === Семантика цикла while === |
| − | *'''''имя'''''
| + | [[Изображение:Цикл_while_м.png]] |
| − | *'''''список параметров'''''
| |
| − | :некоторые параметры являются ''входными'', а некоторые — ''выходными'' | |
| | | | |
| − | Если один из ''выходных'' параметров возвращается особым образом, так что алгоритм можно использовать в выражении, то такой алгоритм называется '''алгоритмом-функцией'''.
| + | === Синтаксис цикла repeat === |
| | + | '''repeat''' |
| | + | <операторы> |
| | + | '''until''' <условие> |
| | | | |
| − | В программировании вспомогательные алгоритмы называются '''подпрограммами''' и делятся на:
| + | === Семантика цикла repeat === |
| − | *'''''процедуры'''''
| + | [[Изображение:Цикл_repeat_м.png]] |
| − | *'''''функции'''''
| |
| | | | |
| | + | === Зацикливание === |
| | + | '''Зацикливание''' происходит, если: |
| | + | * условие цикла с ''предусловием'' всегда ''истинно'' |
| | + | ''<u>Пример</u>.'' |
| | + | <source lang="Pascal"> |
| | + | while true do |
| | + | <оператор> |
| | + | </source> |
| | | | |
| − | '''Важно.''' Подпрограммы позволяют избежать дублирования кода при решении однотипных задач. | + | * условие цикла с ''постусловием'' всегда ''ложно'' |
| − | Алгоритм один раз описывается, а затем может быть многократно вызван с различным набором параметров из другого алгоритма.
| + | ''<u>Пример</u>.'' |
| | + | <source lang="Pascal"> |
| | + | repeat |
| | + | <операторы> |
| | + | until false |
| | + | </source> |
| | | | |
| − | <small>'''Лекция 9'''</small>
| + | '''Итерация''' — однократное повторение тела цикла. |
| | | | |
| − | ===Процедуры===
| + | <h4> Отличия между циклами while и repeat </h4> |
| − | '''Пример.''' | + | '''''while''''' |
| − | :Даны 3 пары положительных чисел. | + | :тело может не выполниться ни разу |
| − | :Найти их среднее арифметическое и среднее геометрическое.
| + | '''''repeat''''' |
| − | Очевидно, удобно сделать подпрограмму, которой бы на вход подавались два числа, а выходными параметрами являлись их среднее арифметическое и среднее геометрическое соответственно.
| + | :тело выполнится хотя бы один раз |
| − | <source lang="Pascal">procedure CalcSrASrG(a, b: real; var SA, SG: real);
| |
| − | begin
| |
| − | SA := (a + b) / 2;
| |
| − | SG := sqrt(a * b);
| |
| − | end;</source>
| |
| − | ''Строка'' | |
| − | <source lang="Pascal">procedure CalcSrASrG(a, b: real; var SA, SG: real); </source>
| |
| − | называется '''заголовком процедуры'''.
| |
| | | | |
| − | Теперь можем многократно использовать описанную процедуру в основной программе:
| + | <h4> Примеры </h4> |
| − | <source lang="Pascal">begin //основной программы | + | ''<u>Пример 1</u>.'' Сумма нечетных двузначных чисел |
| − | for var i:=1 to 3 do
| |
| − | begin
| |
| − | var a, b: real;
| |
| − | readln(a, b);
| |
| − | var SA, SG: real;
| |
| − | CalcSrASrG(a, b, SA, SG);
| |
| − | writeln(SA, '|', SG);
| |
| − | end;
| |
| − | end.</source>
| |
| − | ''Оператор'' | |
| − | <source lang="Pascal">CalcSrASrG(a, b, SA, SG);</source> | |
| − | называется '''оператором вызова процедуры'''.
| |
| | | | |
| − | <xh4>Синтаксис описания процедуры</xh4>
| + | ''С использованием while'' |
| − | '''procedure''' <имя> [( <список формальных параметров> )];
| + | <source lang="Pascal"> |
| − | <раздел описаний>
| + | s := 0; |
| − | '''begin'''
| + | x := 11; |
| − | <операторы и внутриблочные переменные>
| + | while x < 100 do |
| − | '''end;'''
| |
| − | '''Замечание.''' Pascal допускает ''внутренне описание'' п/п (''вложенность'' процедур)
| |
| − | <список формальных пар-ов> ::= <секция ф.п.> | <секция ф.п.>; <список ф.п.>
| |
| − | <секция ф.п.> ::= ['''var'''] <список имен>: <тип>
| |
| − | <xh4>Синтаксис вызова процедуры</xh4>
| |
| − | <имя процедуры> [( [<список фактических параметров>] )]
| |
| − | | |
| − | <список фактических пар-ов> ::= <список выражений>
| |
| − | (<список выражений> ::= <выражение>{, <выражение>})
| |
| − | <xh4>Семантика вызова процедуры</xh4>
| |
| − | *имя должно быть именем процедуры, описанной ранее (или именем текущей процедуры)
| |
| − | *количество фактических параметров должно совпадать с количеством формальных параметров
| |
| − | *фактические '''''параметры-переменные''''' должны быть именами переменных, типы которых совпадают с типами соответствующих формальных параметров
| |
| − | *фактические '''''параметры-значения''''' должны быть выражениями, типы которых совместимы по присваиванию с типами соответствующих формальных параметров
| |
| − | | |
| − | ===Входно-выходные параметры===
| |
| − | Параметр x называется '''входно-выходным''', если его значение необходимо в начале алгоритма, оно модифицируется алгоритмом и возвращается в вызывающую программу.
| |
| − | | |
| − | ''Входно-выходные'' параметры описываются с ключевым словом '''var''', как и ''выходные''.
| |
| − | | |
| − | '''Пример 1.''' Увеличение значения переменной на заданное число.
| |
| − | <source lang="Pascal">procedure Inc(var x: integer; n: integer); | |
| | begin | | begin |
| − | x += n; | + | s += x; |
| − | end;</source>
| + | x += 2; |
| − | Вызов процедуры:
| |
| − | <source lang="Pascal">var x: integer; //неинициализированная переменная
| |
| − | x := 1; //x инициализировано | |
| − | Inc(x, 2);</source>
| |
| − | | |
| − | '''Пример 2.''' Перемена местами значений двух переменных.
| |
| − | <source lang="Pascal">procedure Swap(var x,y: integer);
| |
| − | begin
| |
| − | var v := x;
| |
| − | x := y;
| |
| − | y := v;
| |
| | end; | | end; |
| | + | </source> |
| | | | |
| − | begin
| + | ''С использованием repeat'' |
| − | var a := 5;
| + | <source lang="Pascal"> |
| − | var b := 3; | + | s := 0; x := 11; |
| − | Swap(a,b); | + | repeat |
| − | end.</source>
| + | s += x; |
| | + | x += 2; |
| | + | until x = 99;</source> |
| | | | |
| − | ===Функции===
| + | ''<u>Пример 2</u>.'' Факториал |
| − | '''Функции''' являются др. разновидностью подпрограмм. Это п/п, возвращающая одно значение особым образом так, что ее вызов можно использовать в выражении. | |
| − | Точнее, — вызов процедуры является оператором, а вызов функции — выражением.
| |
| | | | |
| − | '''Пример'''. Функция sgn(x) — знак числа | + | ''С использованием repeat'' |
| − | <source lang="Pascal">function Sign(x: real): integer; | + | <source lang="Pascal"> |
| − | begin
| + | var n: integer; |
| − | if x > 0 then
| + | read(n); |
| − | Result := 1
| + | var x := n; |
| − | else if x < 0 then
| + | var p := 1; |
| − | Result := -1
| |
| − | else
| |
| − | Result := 0;
| |
| − | end;</source>
| |
| | | | |
| − | Строка <source lang="Pascal">function Sign(x: real): integer;</source>
| + | repeat |
| − | называется '''заголовком функции''', а <tt>integer</tt> — это '''тип возвращаемого значения'''.
| + | p *= x; |
| | + | x -= 1; |
| | + | until x = 1; |
| | + | </source> |
| | | | |
| − | В каждой функции неявно определена переменная <tt>'''result'''</tt>, хранящая возвращаемое значение функции и имеющая тот же тип.
| + | ''С использованием while'' |
| − | Присваивание значения Result в теле функции ''обязательно по всем ветвям'' алгоритма.
| + | <source lang="Pascal"> |
| | + | var n: integer; |
| | + | read(n); |
| | + | var x := n; |
| | + | var p := 1; |
| | | | |
| − | '''Пример ''неправильной (!!!)''''' функции.
| + | while x > 1 do |
| − | <source lang="Pascal">function f(x: integer): integer;
| |
| | begin | | begin |
| − | if x > 0 then | + | p *= x; |
| − | Result := 777;
| + | x -= 1; |
| | end; | | end; |
| | + | </source> |
| | | | |
| − | begin
| + | === Моделирование repeat с помощью while === |
| − | writeln(f(0)); | + | '''repeat''' ''Op'' |
| − | end.</source> | + | '' Op'' ——> '''while''' '''not''' A '''do''' |
| − | Выведется непредсказуемое значение, находящееся в этот момент в памяти, т.к. по ветке x = 0 переменная Result не инициализируется.
| + | '''until''' A; '''begin''' |
| | + | ''Op'' |
| | + | '''end;''' |
| | | | |
| − | '''Пример.''' Считывание значения с клавиатуры.
| + | === Моделирование while с помощью repeat === |
| − | <source lang="Pascal">function ReadInteger: integer;
| + | '''while''' A '''do''' '''if''' A '''then''' |
| − | begin
| + | ''Op'' ——> '''repeat''' |
| − | read(Result);
| + | '' Op'' |
| − | end;</source>
| + | '''until not''' A |
| − | '''''Сравнение использования процедуры и функции''''' | |
| − | процедура функция
| |
| − | var x: integer; var x := ReadInteger();
| |
| − | read(x);
| |
| − | '''Пример.''' Сумма первых N натуральных чисел. | |
| − | <source lang="Pascal">function SumN(N: integer): integer;
| |
| − | begin
| |
| − | Result := 0;
| |
| − | for var i:=1 to N do
| |
| − | Result += i;
| |
| − | end;</source>
| |
| − | <xh4>Синтаксис описания функции</xh4>
| |
| − | '''function''' <имя>[( [<список формальных параметров>] )]: <тип возвращаемого значения>;
| |
| − | <раздел описаний>
| |
| − | '''begin'''
| |
| − | <операторы и внутриблочные описания> | |
| − | '''end''';
| |
| − | <xh4>Синтаксис вызова функции</xh4>
| |
| − | <имя>[( [<список формальных параметров>] )];
| |
| − | <xh4>Семантика</xh4>
| |
| − | '''Замечание.''' Формальные параметры функции ''не'' рекомендуется делать '''параметрами-переменными'''. | |
| | | | |
| − | Считается, что функция должна вычислять и возвращаеть результат, и более ничего не делать.
| + | == Оператор цикла с параметром (for) == |
| − | Если функция возвращает результат и выполняет дополнительное действие, которое сказывается вне функции, то такие действия называются '''побочным рузультатом вызова функции.'''
| + | === Синтаксис === |
| | + | <заголовок цикла> |
| | + | <тело цикла> |
| | | | |
| − | '''Правило.''' | + | <заголовок цикла> ::= '''for''' <переменная>:=<выражение1> <направление> <выражение2> '''do''' |
| − | :В подавляющем большинстве случаев функция не должна иметь побочный эффект. | + | <тело цикла> ::= <оператор> |
| | + | <направление> ::= to | downto |
| | | | |
| − | ===Оператор exit=== | + | === Семантика === |
| − | Оператор '''<tt>exit</tt>''' — оператор досрочного завершения подпрограммы.
| + | <source lang="Pascal"> |
| − | | + | var b := <выражение1>; |
| − | '''Пример'''. Поиск числа k среди n введенных.
| + | var e := <выражение2>; |
| − | <source lang="Pascal">function Find(n: integer; k: integer): boolean; | + | <переменная> := b; |
| − | begin
| |
| − | for var i:=1 to n do
| |
| − | begin
| |
| − | var x := ReadInteger;
| |
| − | if x = k then
| |
| − | begin
| |
| − | result := true;
| |
| − | exit;
| |
| − | end;
| |
| − | end;
| |
| − | result := false;
| |
| − | end;</source>
| |
| − | '''Замечание.''' Оператор <tt>'''exit'''</tt>, в отличие от <tt>'''break'''</tt>, позволяет завершить подпрограмму и выйти сразу из нескольких вложенных циклов. При вызове его в теле основной программы программа завершается.
| |
| − | | |
| − | ==Локальные и глобальные переменные==
| |
| − | <source lang="Pascal">var | |
| − | n: integer;
| |
| − | m: integer;
| |
| − | | |
| − | function f(x: integer): integer;
| |
| − | var n: integer;
| |
| − | begin
| |
| − | writeln(n);
| |
| − | writeln(m); | |
| − | n := 5;
| |
| − | end;</source>
| |
| − | '''Замечание.''' '''Локальная''' переменная, описанная в процедуре или функции, может иметь то же имя, что и '''глобальная''' переменная.
| |
| − | Если глобальная описана ранее, то её имя внутри процедуры становится недоступным.
| |
| − | | |
| − | Глобальные переменныя по умолчанию инициализируются '''0''', а локальные по умолчанию не инициализируются.
| |
| − | Локальная переменная <tt>'''Result'''</tt> в функции по умолчанию также не инициализируется.
| |
| − | | |
| − | В данном примере:
| |
| − | :writeln(n) выведет непредсказуемый результат; | |
| − | :writeln(m) выведет 0;
| |
| − | | |
| − | ==Пространство имен==
| |
| − | Область программы, в которой не может быть описано двух объектов с одинаковыми именем, называется '''пространством имен'''.
| |
| − | | |
| − | Различают:
| |
| − | *'''''глобальное''''' пространство имен
| |
| − | *пространство имен '''''каждой п/п'''''
| |
| − | | |
| − | ''Формальные'' параметры п/п являются ''локальными'' по отношению к эти п/п.
| |
| − | | |
| − | '''Примеры''' допустимых и недопустимых описаний:
| |
| − | '''procedure''' p(p: integer); //Можно
| |
| − |
| |
| − | '''function''' Result: integer; //Можно
| |
| | | | |
| − | '''procedure''' p(i: integer); //НЕЛЬЗЯ
| + | while <переменная> <> e do |
| − | '''var''' i: integer;
| |
| − |
| |
| − | function f(Result: real): real; //НЕЛЬЗЯ
| |
| − | <small>'''Лекция 10'''</small> | |
| − | ==Область видимости и время жизни объекта==
| |
| − | '''Время жизни переменной''' — время, в течение которого существует отведенная ей память.
| |
| − | *для глобальных переменных это время работы программы
| |
| − | *для локальных — с момента описания до конца работы блока, где они описаны
| |
| − | | |
| − | '''Область видимости переменной''' — область в программе, в которой можно обратиться к переменной по имени.
| |
| − | ==Побочный эффект==
| |
| − | '''Побочным эффктом подпрограммы''' называется также любое изменение глобальных переменных (или параметров для функции).
| |
| − | | |
| − | '''Пример.'''
| |
| − | <source lang="Pascal">var n: integer;
| |
| − | procedure p;
| |
| | begin | | begin |
| − | n += 1; | + | <оператор> |
| | + | <получить следующее значение переменной> |
| | + | <переменная> += 1; | <переменная> -= 1; |
| | end; | | end; |
| | + | </source> |
| | | | |
| − | begin
| + | <получить следующее значение переменной> ::= <переменная> '''+'''= 1; | <переменная> '''-'''= 1; |
| − | n := 5;
| + | <xh4> Ограничения: </xh4> |
| − | p;
| + | * выражения 1 и 2 должны быть совместимы по присваиванию с переменной |
| − | write(p);
| + | * переменная должна иметь порядковый тип (такой же, как и в case — целый, символьный или перечислимый) |
| − | end.</source>
| + | * переменная цикла for не должна меняться внутри цикла for |
| | + | * переменная цикла for должна быть описана в той же п/п, где используется цикл |
| | | | |
| − | '''Замечание.''' Если подпрограмма желает изменить глобальную переменную, то в большинстве случаев эту переменную следует передать как параметр. | + | === Дополнительные возможности PascalABC.NET === |
| | + | Возможно '''''описание переменной цикла в его заголовке''''': |
| | + | <source lang="Pascal"> |
| | + | for [var] i: integer := 1 to 5 do |
| | + | <оператор> |
| | + | </source> |
| | | | |
| − | ==Принцип локальности==
| + | Возможно '''''автоопределение типа при описании''''': |
| − | Рассмотрим пример:
| + | <source lang="Pascal"> |
| − | <source lang="Pascal">var n: integer; | + | for var i := 1 to 5 do |
| | + | <оператор> |
| | + | </source> |
| | | | |
| − | procedure p;
| + | Переменная цикла, описанная в заголовке цикла, определена только внутри цикла. <br /> |
| − | begin
| + | '''Замечание.''' Значение переменной цикла после завершения цикла не определено. Именно поэтому рекомендуется ''описывать переменную цикла в заголовке цикла''. |
| − | <много кода; n не используется>
| |
| − | end;
| |
| | | | |
| − | procedure p1;
| + | == Примеры использования циклов == |
| − | begin
| + | === Табулирование функции === |
| − | <еще больше кода; n не используется>
| + | Дана f(x) на [a; b], разбитая на N частей. <br /> |
| − | end;
| + | Выдать таблицу значений в точках разбиения. |
| | | | |
| − | begin
| + | <source lang="Pascal"> |
| − | <10 операторов>
| + | var a, b: real; |
| − | n := 1;
| + | var N: integer; |
| − | <еще операторы>
| + | read(a, b, N); |
| − | end.</source>
| |
| − | '''Принцип локальности''' — эмпирический принцип, по которому переменную следует описывать и впервые инициализировать в том месте алгоритма, где она начинает впервые использоваться.
| |
| | | | |
| − | Обычно входные и выходные данные описываются, как глобальные переменные, после всех подпрограмм (если эти подпрограммы их не используют).
| + | assert(N <> 0); |
| − | В начале текста программы обычно используются переменные и константы, инициализируемые каким-то значением, которое легко поменять при следующих запусках этой подпрограммы.
| + | assert(b > a); |
| | + | var h := (b - a) / N; |
| | + | </source> |
| | | | |
| − | '''Пример.''' Вычислить произведениe целых чисел от a до b. | + | ''Дальнейшее решение с помощью '''for''''': |
| − | '''Решение 1.''' | + | <source lang="Pascal"> |
| − | <source lang="Pascal">var
| + | for var i := 0 to N do |
| − | p := 1;
| |
| − | a, b: integer;
| |
| − | i: integer;
| |
| − | begin
| |
| − | read(a, b);
| |
| − | for i:=a to b do
| |
| − | p *= i;
| |
| − | writeln(p);
| |
| − | writeln(i); //от компилятора зависит, будет i = b или (b + 1)
| |
| − | end.</source>
| |
| − | Внесем изменения:
| |
| − | *опишем i в заголовке цикла
| |
| − | :при описании переменной в заголовке цикла её область видимости и время жизни ограничены телом цикла
| |
| − | *инициализируем p непосредственно перед циклом, вычисляющим произведение
| |
| − | '''Решение 2.'''
| |
| − | <source lang="Pascal">var | |
| − | p: integer;
| |
| − | a, b: integer;
| |
| − | begin
| |
| − | read(a, b);
| |
| − | p := 1;
| |
| − | for var i:=a to b do
| |
| − | p *= i;
| |
| − | writeln(p);
| |
| − | end.</source>
| |
| − | Второе решение является более ''масштабируемым'', чем первое, поскольку алгоритм вычисления произведения расположен непрерывно в тексте программы и его можно легко превратить в подпрограмму.
| |
| − | | |
| − | ==Внутренний механизм передачи параметра-переменной==
| |
| − | <source lang="Pascal">procedure MyInc(var a: real; n: integer);
| |
| | begin | | begin |
| − | a += n; | + | writelnFormat('{0,6:f2} {1,9:f4}', x, f(x)); |
| | + | x += h; |
| | end; | | end; |
| | + | </source> |
| | | | |
| − | var | + | ''Дальнейшее решение с помощью '''while''''': |
| − | b: real;
| + | <source lang="Pascal"> |
| − | i: integer;
| + | var eps := h / 2; |
| | + | while x < (b + eps) do |
| | begin | | begin |
| − | b := ReadReal; | + | writelnFormat('{0,6:f2} {1,9:f4}', x, f(x)); |
| − | i := ReadInteger;
| + | x += h; |
| − | MyInc(b, i);
| |
| − | writeln(b);
| |
| − | end.</source>
| |
| − | Здесь
| |
| − | :b, i: фактические параметры при вызове MyInc
| |
| − | :a, n: формальные параметры (a — параметр-переменная; n — параметр-значение)
| |
| − | | |
| − | При передаче параметра-значения i в соответствующий формальный параметр копируется '''значение i'''.
| |
| − | А вот механизм передачи параметра-переменной называется '''передачей по ссылке'''.
| |
| − | | |
| − | '''Ссылкой''' обычно называют другое имя некоторого объекта.
| |
| − | | |
| − | Для параметра-переменной имя соответствующего формального параметра выступает в роли ссылки переменной-фактического параметра.
| |
| − | Все, что происходит со ''ссылкой'' внутри подпрограммы происходит и с ''самим объектом'' вне подпрограммы, поскольку это один и тот же объект.
| |
| − | | |
| − | При передаче параметра ''по ссылке'' в подпрограмму передается не сама переменная, а её '''адрес''':
| |
| − | MyInc(var a: real; i: integer);
| |
| − | |
| |
| − | '''@'''b ('''адрес''' b)
| |
| − | '''Замечание 1.''' В 32-битных ОС размер адреса — 4 байта, это позволяет адресовать примерно 4 Гб операционной памяти.
| |
| − | <br>'''Замечание 2.''' Размер адреса не зависит от размера переменной, поэтому при передаче параметров большого размера их предпочитают передавать по ссылке.
| |
| − | | |
| − | ==Перегрузка имен подпрограмм==
| |
| − | Предположим, у нас описана процедура:
| |
| − | <source lang="Pascal">procedure Swap(a, b: integer);
| |
| − | begin
| |
| − | var t := a;
| |
| − | a := b;
| |
| − | b := t;
| |
| − | end;</source>
| |
| − | Возможно ли описать процедуру с таким же именем, параметры которой были бы вещественными? Да, возможно:
| |
| − | <source lang="Pascal">procedure Swap(a, b: integer);
| |
| − | begin
| |
| − | var t := a;
| |
| − | a := b;
| |
| − | b := t; | |
| | end; | | end; |
| | + | </source> |
| | | | |
| − | procedure Swap(a, b: real);
| + | '''Замечание.''' Вещественные числа в памяти компьютера представлены приближенно. Ошибка, которая возникает при ''представлении'' вещественного числа в памяти, называется '''ошибкой округления'''. <br /> |
| − | begin
| + | Ошибка, которая возникает в результате ''вычислений'' с вещественными числами называется '''вычислительной погрешностью'''. |
| − | var t := a;
| |
| − | a := b;
| |
| − | b := t;
| |
| − | end;</source>
| |
| − | Таким образом, в одном пространстве имен можно описать несколько подпрограмм с одним именем, но разными типами или количеством формальных параметров.
| |
| − | <br>При вызове такой подпрограммы на ''этапе компиляции'' типы фактических параметров сравниваются с типами формальных для всех версий этой подпрограммы и выбирается наиболее подходящая.
| |
| | | | |
| − | '''Замечание 1.''' Тип возвращаемого значения функции не участвует в операции разрешения перегрузки. | + | '''Вывод.''' Вещественные числа нельзя сравнивать на равенство, можно только на ''больше/меньше''. |
| | | | |
| − | Версии подпрограммы с одним именем называются '''перегруженными''', а определение того, какую версию выбрать — '''разрешением перегрузки'''.
| + | === Рекуррентные соотношения === |
| | + | Говорят, что последовательность данных |
| | + | x<sub>1</sub>, x<sub>2</sub>, x<sub>3</sub>,..., x<sub>n</sub> |
| | + | является '''рекуррентной''', если |
| | + | x<sub>k + 1</sub> = f( x<sub>k</sub> ), k = 1, 2, 3... |
| | | | |
| − | '''Замечание 2.''' Разрешить перегрузку можно не всегда.
| + | === Вывод степеней двойки === |
| − | <br>'''Пример.'''
| + | <source lang="Pascal"> |
| − | <source lang="Pascal">procedure p(i: integer; r: real);
| + | var x := 1; |
| − | ...
| + | for var i := 1 to 10 do |
| − | | |
| − | procedure p(r: real; c: char);
| |
| − | ...
| |
| − | | |
| − | procedure p(r: real; i: integer);
| |
| − | ...
| |
| − | | |
| − | begin
| |
| − | p(1, 2); //неоднозначность
| |
| − | end.</source>
| |
| − | '''Замечание 3.''' В процессе разрешения перегрузки происходит ''неявное преобразование типов''.
| |
| − | <small>'''Лекция 11'''</small>
| |
| − | | |
| − | ==Параметры по умолчанию== | |
| − | <source lang="Pascal">procedure DoOp(a, b: integer; var res: integer; op: char := '+'); | |
| | begin | | begin |
| − | case op of | + | writeln(x); |
| − | '+': res := a + b;
| + | x *= 2; |
| − | '-': res := a - b;
| |
| − | '*': res := a * b;
| |
| − | end;
| |
| | end; | | end; |
| − | ...
| + | </source> |
| − | DoOp(1,2, res, '-'); // res = -1
| |
| − | DoOp(3,4, res1); // res1 = 7</source>
| |
| − | '''Параметры по умолчанию''' обязательно должны находиться последними в списке параметров. Если при вызове не указывать этот параметр, будет использовано значение по умолчанию.
| |
| | | | |
| − | '''Замечание.''' Параметры по умолчанию корректно сочетаются с перегрузкой.
| + | === Последовательность Фибоначчи === |
| − | ==Предварительное объявление подпрограмм== | + | <math>\begin{cases} x_1 = 1, x_2 = 1 \\ x_{k+1} = x_k + x_{k-1}\end{cases}</math> |
| − | <source lang="Pascal">procedure p; | |
| − | begin | |
| − | q;
| |
| − | end; | |
| | | | |
| − | procedure q;
| + | <source lang="Pascal"> |
| | + | var a := 1; |
| | + | var b := 1; |
| | + | write(a, ' ', b, ' '); |
| | + | for var i := 3 to 20 do |
| | begin | | begin |
| − | ... | + | c := a + b; |
| − | end;</source>
| + | write(c, ' '); |
| − | Такое описание вызовет ошибку компиляции, т.к. в '''<tt>p</tt>''' используется еще не известная процедура. Чтобы таких ошибок не возникало, нужно использовать ''предварительное объявление подпрограммы'':
| + | a := b; |
| − | <source lang="Pascal">procedure q; forward;
| + | b := c; |
| − | | |
| − | procedure p;
| |
| − | begin
| |
| − | q; | |
| | end; | | end; |
| | + | </source> |
| | | | |
| − | procedure q;
| + | === Вычисление НОД (алгоритм Евклида) === |
| − | ...</source>
| + | <math>\begin{cases} x_1 = a \\ x_2 = b \\ x_{k+1} = x_{k-1} mod x_k\end{cases}</math> |
| − | '''forward-объявление''' делается для подпрограмм, которые ''обязательно'' будут описаны ниже. Если программа не будет описана в этом же файле, то, в конце компиляции этого файла, мы получим ошибку компилятора о <tt>'''forward'''</tt>, который был объявлен, но не описан.
| |
| | | | |
| − | ==Процедурные переменные==
| |
| − | ===Процедурный тип и переменные===
| |
| − | <source lang="Pascal">var pr: procedure(a, b: real; var res: real);</source>
| |
| − | Переменная называется '''процедурной''' если ей можно присваивать процедуры или функции указанного типа.
| |
| | <source lang="Pascal"> | | <source lang="Pascal"> |
| − | type
| + | var a, b: integer; |
| − | BinOpType = procedure(a, b: real; var res: real); | + | read(a, b); |
| | + | assert((a > 0) and (b > 0)); |
| | + | repeat |
| | + | c := a mod b; |
| | + | a := b; |
| | + | b := c; |
| | + | until c = 0; |
| | + | writeln(a); |
| | + | </source> |
| | | | |
| − | var
| + | === Суммирование рядов (конечных и бесконечных) === |
| − | pr: BinOpType;
| + | * <math>\sum_{i=1}^n \frac{a^i}{i!}</math> |
| | | | |
| − | procedure AddOp(a, b: real; var res: real);
| + | Найдем рекуррентную связь между <tt>a<sub>i</sub></tt>: |
| − | begin
| + | x<sub>1</sub> = a |
| − | res := a + b;
| + | x<sub>i</sub> = x<sub>i-1</sub> * a / i, i = 2, 3.. |
| − | end;
| |
| − | procedure MultOp(a, b: real; var res: real);
| |
| − | begin
| |
| − | res := a * b;
| |
| − | end;
| |
| | | | |
| | + | <source lang="Pascal"> |
| | + | read(a, n); |
| | + | x := a; |
| | + | s := x; |
| | + | for var i := 2 to n do |
| | begin | | begin |
| − | pr := AddOp; | + | x *= a / i; |
| − | var r: real;
| + | s += x; |
| − | pr(1,2, r); //вызов процедуры через процедурную переменную
| |
| − | | |
| − | pr := MultOp;
| |
| − | pr(3,4, r); | |
| − | end.</source>
| |
| − | После присваивания процедурной переменной имени процедуры, эта процедура может быть вызвана через переменную:
| |
| − | <имя процедурной переменной>( <список параметров> );
| |
| − | Такой способ вызова процедуры является чрезвычайно гибким, поскольку позволяет менять вызываемое действие в процессе работы программы.
| |
| − | | |
| − | '''Замечание.''' До первого присваивания процедурная переменная имеет тип <tt>'''nil'''</tt>. В этот момент вызывать процедуру через переменную нельзя — будет ошибка выполнения.
| |
| − | | |
| − | ===Функции обратного вызова (callback)===
| |
| − | <source lang="Pascal">type ActionType = procedure;
| |
| − | | |
| − | procedure DoActions(Action1, Action2, Action3: ActionType);
| |
| − | begin
| |
| − | Action1;
| |
| − | Action2;
| |
| − | Action3;
| |
| | end; | | end; |
| | + | </source> |
| | | | |
| − | procedure Eat;
| + | * <math>\sum_{i=1}^\infty (-1)^i\frac{a^i}{i}</math> |
| − | begin
| |
| − | writeln('Студент ест');
| |
| − | end;
| |
| − | procedure Think;
| |
| − | begin
| |
| − | writeln('Студент думает');
| |
| − | end;
| |
| − | procedure Sleep;
| |
| − | begin
| |
| − | writeln('Студент спит');
| |
| − | end;
| |
| | | | |
| − | begin
| + | Для вычисления суммы ''бесконечного ряда'' в простейшем случае используют следующий метод: |
| − | DoActions(Sleep, Eat, Sleep); // Первый алгоритм подготовки к сессии
| + | :задается некоторый малый <tt>'''eps'''</tt> и сумма <math>\sum_{i=1}^\infty x_i</math> вычисляется, пока <math>|x_i| >\ eps</math> |
| − | DoActions(Think, Eat, Sleep); // Второй алгоритм подготовки к сессии
| |
| − | DoActions(Sleep, Sleep, Think); // Третий алгоритм подготовки к сессии
| |
| − | end.</source>
| |
| − | Процедурные переменные могут являться параметрами других процедур.
| |
| − | При вызове этих процедур им на вход в качестве параметров передаются имена процедур, котоые будут вызваны позже внутри основной процедуры.
| |
| − | <br>Другими словами, мы передаем в процедуру действие, которое должно быть вызвано (будет вызвано) в определенный момент в этой процедуре. | |
| | | | |
| − | Такой вызов называется '''обратным вызовом (callback)'''.
| + | <source lang="Pascal"> |
| − | <br>''Примечание.'' Прямой вызов — это передача процедуры в качестве параметра. | + | assert((a > 0) and (a < 1)); |
| | + | i := 1; |
| | + | s := 0; |
| | + | y := -a; |
| | + | repeat |
| | + | s += y / i; |
| | + | i += 1; |
| | + | y *= -a; |
| | + | until abs(y / i) < eps; |
| | + | </source> |
| | | | |
| − | '''Пример.''' Вычисление определённого интеграла методом прямоугольников.
| + | === Нахождение max в последовательности чисел === |
| − | <source lang="Pascal">type func = function(x: real): real; | + | <source lang="Pascal"> |
| − | function Integral(a, b: real; N: integer; f: func);
| + | max := - real.MaxValue; // или max := real.MinValue; |
| | + | for var i := 1 to n do |
| | begin | | begin |
| − | assert(a < b); | + | read(x); |
| − | var h := (b - a) / N;
| + | if x > max then |
| − | result := 0; | + | max := x; |
| − | var x := a;
| |
| − | for var i:=0 to N-1 do
| |
| − | begin
| |
| − | result += f(x);
| |
| − | x += h;
| |
| − | end;
| |
| − | result *= h;
| |
| | end;</source> | | end;</source> |
| | | | |
| − | ===Вызов нескольких процедур через процедурную переменную=== | + | === Разложение целого числа на простые множители === |
| − | <source lang="Pascal">type ActionType = procedure; | + | Будем делить <tt>x</tt> на <tt>p</tt>, начиная с <tt>''p = 2''</tt>. Если делится нацело, то <tt>p</tt> — множитель, если не делится, то увеличиваем <tt>p</tt> на 1, пока <tt>''x <> 1''</tt>. |
| | | | |
| − | procedure Eat;
| + | <source lang="Pascal"> |
| − | begin
| + | read(x); |
| − | ...
| + | p := 2; |
| − | end;
| + | repeat |
| − | procedure Think;
| + | if x mod p = 0 then |
| − | begin
| + | begin |
| − | ... | + | write(p, ' '); |
| − | end;
| + | x := x div p; |
| − | procedure Sleep;
| + | end |
| − | begin
| + | else |
| − | ... | + | p += 1; |
| − | end;
| + | until x = 1;</source> |
| | | | |
| − | var pr: ActionType;
| + | === Операторы break и continue === |
| − | begin
| + | '''break''' — оператор ''досрочного завершения цикла''. |
| − | pr += Sleep;
| + | [[Изображение:break_м.png|none]] |
| − | pr += Eat;
| |
| − | pr += Think;
| |
| − | pr;
| |
| − | pr -= Eat;
| |
| − | pr;
| |
| − | end.</source>
| |
| − | '''Замечание 1.''' Такое возможно только в .NET; | |
| − | <br>'''Замечание 2.''' Подобный механизм не имеет смысла использовать для функций;
| |
| | | | |
| − | <small>'''Лекция 12'''</small>
| + | '''continue''' — оператор ''досрочного завершения текущей итерации'' цикла. |
| − | ==Методы разработки подпрограмм==
| + | [[Изображение:continue_м.png|none]] |
| − | '''Пример.''' Вывести таблицу простых чисел <= 1000.
| |
| − | ===Метод разработки ''сверху вниз''===
| |
| − | Метод разработки '''сверху вниз''' начинается с записи основного алгоритма в предположении,
| |
| − | что все подпрограммы уже написаны, т.е. код пишется ''в крупных командах''.
| |
| | | | |
| − | '''Решение.'''
| + | === Поиск заданного значения среди введенных === |
| − | <source lang="Pascal">writeln(2); | + | <u>Решение 1</u>. С использованием оператора ''break'' |
| − | var x := 3; | + | <source lang="Pascal"> |
| − | while x <= 1000 do
| + | var exists: boolean := false; |
| | + | for var i:=1 to n do |
| | begin | | begin |
| − | if IsPrime(x) then | + | read(x); |
| − | writeln(x);
| + | if x = k then |
| − | x += 2; | |
| − | end;</source>
| |
| − | После этого реализуем функцию IsPrime;
| |
| − | | |
| − | Этот метод используется, когда:
| |
| − | *основной алгоритм понят, и его можно сразу записать
| |
| − | *задача четко поставлена
| |
| − | *имеется ровно одна задача, которую необходимо решить
| |
| − | | |
| − | '''Замечание.''' В коде главной программы имеются вызовы других подпрограмм, которые реализуются позже (возможно, другими разработчиками);
| |
| − | <br>На период, пока они не написаны, вместо них могут использоваться "'''заглушки'''" (подпрограммы с тривиальными телами)
| |
| − | | |
| − | Код каждой разрабатываемой подпрограммы также может разрабатываться методом сверху вниз.
| |
| − | ===Метод разработки ''снизу вверх''===
| |
| − | Вначале составляется "нижняя" подпрограмма, она всесторонне тестируется, и, потом,
| |
| − | пишется основная программа или подпрограмма.
| |
| − | | |
| − | Метод используется, когда:
| |
| − | *на момент начала решения задача нечетко поставлена
| |
| − | *когда задача — большая
| |
| − | *нет ясно выраженного главного алгоритма, а есть множество взаимосвязанных задач (примером может служить программа, реализующая деятельность университета)
| |
| − | | |
| − | '''Замечание 1.''' Написание самых "нижних" подпрограмм позволяет лучше войти в предметную область;
| |
| − | <br>'''Замечание 2.''' С какого-то момента разработка хотя бы упрощенного главного алгоритма становится необходимой;
| |
| − | | |
| − | Если между главным алгоритмом и "нижними" подпрограммами имеется несколько уровней,
| |
| − | то имеет смысл '''сочетать оба метода разработки'''.
| |
| − | ==Оператор goto==
| |
| − | ===Синтаксис===
| |
| − | '''goto''' <метка>
| |
| − | ...
| |
| − | <метка>: <оператор>
| |
| − | '''Метка''' представляет собой идентификатор или целое положительное число.
| |
| − | <br>Метка должна описываться в '''''разделе описаний меток''''' в виде:
| |
| − | '''label''' <метка1>, <метка2>...;
| |
| − | === Семантические ограничения ===
| |
| − | *метка должна использоваться в той же подпрограмме, в которой описана;
| |
| − | *нельзя, используя goto, перейти внутрь какой-нибудь конструкции (цикла или условного оператора);
| |
| − | <xh4>Пример плохого кода</xh4>
| |
| − | <source lang="Pascal">label 1, 2, 3;
| |
| − | begin
| |
| − | goto 1;
| |
| − | <100 операторов>
| |
| − | 2: write(2);
| |
| − | goto 3;
| |
| − | <100 операторов>
| |
| − | 1: write(1);
| |
| − | goto 2;
| |
| − | <100 операторов>
| |
| − | 3: write(3);
| |
| − | end.</source>
| |
| − | Однако, бывают ситуации, когда удобно использовать оператор <tt>'''goto'''</tt>, например, чтобы ''выйти из нескольких циклов''.
| |
| − | | |
| − | '''Пример.'''
| |
| − | :найти a, b, c:
| |
| − | :a<sup>2</sup> + b<sup>2</sup> = c<sup>2</sup>, 50 <= a,b,c <= 100
| |
| − | <source lang="Pascal">label fin;
| |
| − | var aa, bb, cc: integer;
| |
| − | var flag := false;
| |
| − | | |
| − | for var a:=50 to 100 do
| |
| − | for var b:=50 to 100 do
| |
| − | for var c:=50 to 100 do
| |
| − | if a*a + b*b = c*c then
| |
| | begin | | begin |
| − | flag := true; | + | exists := true; |
| − | aa := a; | + | break; |
| − | bb := b;
| |
| − | cc := c;
| |
| − | goto fin;
| |
| | end; | | end; |
| | + | end;</source> |
| | | | |
| − | fin: if flag then
| + | <u>Решение 2</u>. |
| − | writeln(aa, bb, cc);</source>
| + | <source lang="Pascal"> |
| − | == Вызов подпрограммы на этапе выполнения == | + | var i := 1; |
| − | С каждой выполняющейся программой связан блок памяти, выделяющийся ей в начале работы и называемый '''программным стеком'''.
| + | var exists: boolean:= false; |
| − | <br>Программный стек используется для хранения значений всех переменных, констант, а также промежуточных значений в процессе выполнения.
| + | repeat |
| − | <здесь будет рисунок>
| + | read(x); |
| − | При в ходе в подпрограмму в процессе выполнения, на программном стеке для нее выделяется специальный участок памяти, называемый '''записью активации''' ('''ЗА''') этой подпрограммы.
| + | if x = k then |
| | + | exists := true; |
| | + | i += 1; |
| | + | until (i > n) or exists;</source> |
| | | | |
| − | Данный участок выделяется на вершине стека, после чего вершина стека <tt>'''top'''</tt> "поднимается на размер ЗА.
| + | === Обработка последовательности, завершающейся нулем === |
| − | <br>После окончания работы подпрограммы ее ЗА снимается со стека и вызывающая программа выполняется дальше.
| + | Вводятся числа. Конец ввода — ноль. <br /> |
| − | | + | Найти сумму и произведение положительных чисел. |
| − | '''Пример.'''
| + | <source lang="Pascal"> |
| − | <br>[[Изображение:Работа_стека.gif]]
| + | s := 0; |
| − | === Устройство ЗА подпрограммы ===
| + | p := 1; |
| − | [[Изображение:ЗА.png]]<br>
| + | while True do |
| − | Штриховкой отмечены поля, заполняемые до запуска п/п.
| |
| − | | |
| − | === Алгоритм входа в подпрограмму ===
| |
| − | # Увеличить '''<tt>top</tt>''' стека на размер ЗА п/п, вычесленного на этапе компиляции: '''<tt>top += r<sub>ЗА</sub></tt>'''
| |
| − | # Вычислить '''адрес возврата''' ('''АВ''') и '''адрес конца ЗА''' вызывающей п/п
| |
| − | # Вычислить значения всех фактических параметров и подставить их на место формальных.
| |
| − | # Перейти в коде программы на начало выполнения п/п
| |
| − | === Алгоритм выхода из подпрограммы ===
| |
| − | # Уменьшить<tt>'''top'''</tt> стека, переместив его на '''адрес конца ЗА''' вызывающей подпрограммы
| |
| − | # В коде программы перейти по '''АВ'''
| |
| − | <small>'''Лекция 13'''</small>
| |
| − | === Пример ===
| |
| − | <здесь будет рисунок>
| |
| − | | |
| − | После запуска программы ОС записывает код этой программы в оперативную память и выделяет дополнительный участок памяти для данных, называемый '''программным стеком'''.
| |
| − | | |
| − | При перемещении <tt>top</tt> на программном стеке накапливается мусор, потом в этот мусор опять записывается ЗА.
| |
| − | <br />Коды <tt>top</tt> и <tt>current</tt> хранятся в специальных регистрах.
| |
| − | | |
| − | '''Вывод 1.''' Если подпрограмма — маленькая, то накладные расходы на её вызов могут существенно превысить время работы самой подпрограммы.
| |
| − | <br />'''Вывод 2.''' Если локальные переменные или формальные параметры, передаваемые по значению имеют большой размер, то ЗА соответствующей подпрограммы будет большой. В результате при нескольких вложенных вызовах таких подпрограмм может произойти '''переполнение программного стека''' ('''Stack overflow'''), т.к. программный стек не увеличивается в размерах, а память под него выделяется один раз. | |
| − | :'''''Выход.''''' Большие параметры по этой причине рекомендуется передавать не по значению, а ''по ссылке'', при этом на стек копируется не содержимое параметра, а его адрес.
| |
| − | | |
| − | '''Замечание.''' Адреса глобальных переменных, используемых в подпрограммах вычисляются по некоторому алгоритму ''на этапе выполнения'', следовательно, обращение к глобальным переменным происходит дольше, чем к локальным.
| |
| − | | |
| − | ==Модули==
| |
| − | === Введение ===
| |
| − | '''Модуль''' — это совокупность взаимосвязанных процедур, функций, типов, переменных и констант,
| |
| − | предназначенных для решения ряда однотипных задач, и помещенных в специальным образом оформленный файл.
| |
| − | | |
| − | Модули разбивают большой проект на относительно независимые части, при этом, каждая часть "живет своей жизнью": модуль, написанный для одного программного проекта может быть использован в другом программном проекте.
| |
| − | | |
| − | Различают модули в виде '''''исходных текстов''''' и '''''откомпилированные модули'''''.
| |
| − | <br>Откомпилированные модули уменьшают суммарное время компиляции и позволяют ''скрывать программный код от модификации''.
| |
| − | | |
| − | '''Пример.'''
| |
| − | :Модуль ''MyLib''
| |
| − | <source lang="Pascal">unit MyLib; | |
| − | | |
| − | interface // раздел интерфейса
| |
| − | const
| |
| − | MyPi = 3.14;
| |
| − | var
| |
| − | size: integer := 10;
| |
| − | | |
| − | function AddSquares(a, b: real): real;
| |
| − | procedure InvertPrint(a, b: integer);
| |
| − | | |
| − | implementation // раздел реализации
| |
| − | var i: integer;
| |
| − | | |
| − | function MySqr(a: real): real;
| |
| | begin | | begin |
| − | result := a * a; | + | read(x); |
| | + | if x = 0 then |
| | + | break; |
| | + | if x < 0 then |
| | + | continue; //фильтр |
| | + | s += x; |
| | + | p *= x; |
| | end; | | end; |
| | + | </source> |
| | | | |
| − | function AddSquares(a, b: real): real;
| + | === Вычисление значения многочлена. Схема Горнера === |
| − | begin
| + | Необходимо вычислить |
| − | result := MySqr(a) + MySqr(b);
| + | <math>\ a_0x^n + a_1x^{n-1} + ... + a_{n-1}x + a_n</math> |
| − | end;
| + | если |
| | + | :a<sub>0</sub>...a<sub>n</sub> известны |
| | + | :x дано |
| | | | |
| − | procedure InvertPrint(a, b: integer);
| + | <u>Решение 1</u>. |
| | + | <source lang="Pascal"> |
| | + | var p := 1.0; |
| | + | var s := 0.0; |
| | + | for var i := 0 to n do |
| | begin | | begin |
| − | write(b, ' ', a); | + | read(a); |
| | + | s += p * a; |
| | + | p *= x; |
| | end; | | end; |
| − |
| |
| − | end. // конец модуля</source>
| |
| − |
| |
| − | :Программа, подключающая модуль ''MyLib''
| |
| − | <source lang="Pascal">uses MyLib;
| |
| − |
| |
| − | var
| |
| − | n: integer;
| |
| − |
| |
| − | begin
| |
| − | writeln(size);
| |
| − | writeln(AddSquares(3, 4));
| |
| − | InvertPrint(3,4);
| |
| − | end.</source>
| |
| − |
| |
| − |
| |
| − | Модуль в языке Object Pascal состоит из двух разделов:
| |
| − | *раздел '''интерфейса'''
| |
| − | *раздел '''реализации'''
| |
| − |
| |
| − | В разделе '''интерфейса''' описываются все
| |
| − | <br>''переменные, константы, типы, заголовки подпрограмм'',
| |
| − | <br>которые можно будет использовать в других модулях, подключающих данный.
| |
| − |
| |
| − | В разделе '''реализации''' содержится
| |
| − | <br>''реализация подпрограмм'',
| |
| − | <br>заголовки которых приведены в разделе интерфейса, а также
| |
| − | <br>описание ''вспомогательных констант, переменных, типов и подпрограмм'',
| |
| − | <br>которые нужны для реализации подпрограмм из раздела интерфейса и не видны из других модулей.
| |
| − |
| |
| − | Данный принцип получил название '''принципа сокрытия информации'''.
| |
| − | <br>Его ''преимущества'':
| |
| − | *уменьшение количества информации, необходимой для понимания работы модуля;
| |
| − | *сокрытие реализации от клиентов;
| |
| − | *возможность легкого изменения реализации в следующих версиях без изменения интерфейса, т.е. без затрагивания интерфейса клиентов;
| |
| − | *возможность скрыть программный код от клиентов, предоставив им лишь откомпилированную версию модуля;
| |
| − |
| |
| − | <small>'''Лекция 14'''</small>
| |
| − | === Синтаксис модуля ===
| |
| − | '''unit''' <имя модуля>;
| |
| − |
| |
| − | '''interface'''
| |
| − | ['''uses''' <список модулей>;]
| |
| − | <раздел описаний модуля: для п/п — только заголовки>
| |
| − |
| |
| − | '''implementation'''
| |
| − | ['''uses''' <список модулей>;]
| |
| − | <раздел описаний, где даны реализации п/п из раздела interface>
| |
| − |
| |
| − |
| |
| − | ['''initialization'''
| |
| − | <операторы>] ''' begin'''
| |
| − | | <операторы>
| |
| − | ['''finalization''' '''end'''.
| |
| − | <операторы>]
| |
| − |
| |
| − | === Семантические ограничения ===
| |
| − | *Модули, перечисленные в секции <tt>'''uses'''</tt> в разделах интерфейса и реализации не должны пересекаться;
| |
| − | *''циклическая зависимость'' между модулями в разделе интерфейса '''запрещена''':
| |
| − | '''unit''' A; '''unit''' B;
| |
| − | '''interface''' '''interface'''
| |
| − | '''uses''' B; '''uses''' A;
| |
| − | :тем не менее, если A ссылается на B в разделе ''интерфейса'', а B ссылается на A в разделе ''реализации'', то это '''допустимо''':
| |
| − | '''unit''' A; '''unit''' B;
| |
| − | '''interface''' '''interface'''
| |
| − | '''uses''' B; '''implementation'''
| |
| − | '''uses''' A;
| |
| − | :потому что модули '''''компилируются в два этапа''''':
| |
| − | :*интерфейс
| |
| − | :*реализация
| |
| − |
| |
| − | === Разделы инициализации и финализации модуля ===
| |
| − | '''unit''' A; <u>основная программа</u>
| |
| − | ...
| |
| − | '''initialization''' '''uses''' A;
| |
| − | <операторы<sub>1</sub>>
| |
| − | '''finalization ''' '''begin'''
| |
| − | <операторы<sub>2</sub>> <операторы<sub>3</sub>>
| |
| − | '''end'''. '''end'''.
| |
| − |
| |
| − | Операторы в разделе '''<tt>initialization</tt>''' модуля выполняются ''раньше'' тела основной программы,
| |
| − | <br /> а операторы в разделе <tt>'''finalization'''</tt> выполняются''после'' основной программы.
| |
| − |
| |
| − | Т.е. последовательность выполнения будет такой:
| |
| − | <операторы<sub>1</sub>>
| |
| − | <операторы<sub>3</sub>>
| |
| − | <операторы<sub>2</sub>>
| |
| − | '''Примечание.''' В разделе ''инициализации'' обычно инициализируются глобальные переменные из раздела интерфейса.
| |
| − |
| |
| − | <u>Пример</u>.
| |
| − | <source lang="Pascal">unit A;
| |
| − |
| |
| − | interface
| |
| − | var
| |
| − | RandomNumber: integer;
| |
| − |
| |
| − | implementation
| |
| − | ...
| |
| − | initialization
| |
| − | RandomNumber := Random(100);
| |
| − | end.
| |
| | </source> | | </source> |
| | + | Это решение использует <tt>2(n + 1)</tt> умножений. |
| | | | |
| − | === Схема компиляции программы с модулями === | + | Однако есть и другое решение — '''схема Горнера'''. |
| − | <Здесь будет рисунок>
| + | Оно основана на том, что <br /> |
| | + | <math>\ a_0x^2 + a_1x + a_2 = ((a_0)x + a_1)x + a_2</math> |
| | | | |
| − | 1. Компилируется файл основной программы.
| + | <u>Решение 2</u>. |
| − | <br />2. Если в нем встречена секция <tt>'''uses'''</tt>, то компилируются модули из этой секции ''слева направо''.
| + | <source lang="Pascal"> |
| − | <br />3. Каждый модуль компилируется так же, как и основная программа по пунктам 1-2:
| + | read(a); |
| − | :Если в модуле подключаются другие модули, то компилируются они,
| + | var res: real := a; |
| − | :и так происходит до тех пор, пока компилятор не дойдет до модулей, не содержащих подключения других модулей.
| + | for var i:=1 to n do |
| − | 4. По окончании компиляции модуля его откомпилированный вариант (.'''pcu''' в PascalABC.NET) записывается на диск.
| |
| − | <br />5. После записи откомпилированного модуля на диск компилятор возвращается к основному модулю (вызывающему) или программе, и докомпилирует его до конца. Основная программа после компиляции хранится в оперативной памяти.
| |
| − | <br />6. ''Первый этап компиляции закончен''. Начинается заключительный этап компиляции — '''линковка''' ('''компоновка'''). Специальная программа — '''линковщик''' — собирает из откомпилированных модулей единый исполняемый файл (.'''exe''' в Windows).
| |
| − | | |
| − | '''Замечание 1.''' Ошибки могут происходить как на этапе компиляции, так и на этапе, собственно, линковки.
| |
| − | <br />'''Замечание 2.''' Наличие откомпилированного файла модуля существенно ускоряет процесс компиляции (сводя его к процессу линковки).
| |
| − | <br />'''Замечание 3.''' Если есть откомпилированные файлы модулей, то исходные тексты модулей можно удалить. При этом компилятор проанализирует, что данный модуль откомпилирован, и продолжит компиляцию дальше.
| |
| − | <br />'''Замечание 4.''' Если файл модуля <tt>.pas</tt> создан после откомпилированного файла модуля (<tt>.pcu</tt>), то произойдет его перекомпиляция.
| |
| − | <br />'''Замечание 5.''' При работе в интегрированной среде компилятор в первую очередь берет тексты модулей из открытых файлов и только затем смотрит файлы на диске.
| |
| − | | |
| − | '''Примечание 1.''' Файлы модулей могут храниться в другом каталоге относительно файла исходной программы. Тогда надо вместе с именем модуля указывать, в каком каталоге он хранится (тогда имя модуля и имя файла модуля могут не совпадать):
| |
| − | — Main ——————————— MyPr.pas
| |
| − | |
| |
| − | |— Modules | — a.pas
| |
| − | | — b. pas
| |
| − | | |
| − | <u>MyPr.pas</u>
| |
| − | '''program''' MyPr;
| |
| − | '''uses'''
| |
| − | A '''in''' 'Modules\a.pas';
| |
| − | B '''in''' 'Modules\b.pas';
| |
| − | '''Примечание 2.''' Откомпилированные файлы модулей по умолчанию создаются:
| |
| − | *в каталоге основной программы
| |
| − | *если установлен специальный путь в среде программирования для выходных файлов, то по этому пути
| |
| − | Кроме этого, стандартные откомпилированные модули хранятся в специальной папке, например, в PascalABC.NET — в папке '''\LIB'''. Если модуль претендует на звание стандартного, его можно туда поместить.
| |
| − | | |
| − | === Упрощенная структура модуля ===
| |
| − | В PascalABC.NET можно использовать упрощенную структуру модуля:
| |
| − | '''unit''' <имя модуля>;
| |
| − | <раздел описаний>
| |
| − | ['''begin'''
| |
| − | <операторы>]
| |
| − | '''end'''.
| |
| − | | |
| − | В <разделе описаний> описываются типы, константы, переменные и подпрограммы.
| |
| − | <br />Раздел <tt>'''begin''' + <операторы></tt> соответствует разделу ''инициализации''.
| |
| − | | |
| − | === Алгоритм поиска имен в модулях ===
| |
| − | В разных модулях могут находиться объекты с одинаковыми именами, т.к. модуль является ''пространством имен''.
| |
| − | <br />Как же осуществляется поиск имен в модулях?
| |
| − | | |
| − | '''Правило 1'''. Имя вначале ищется в текущем модуле. Если не найдено, то в подключенных модулях секции <tt>'''uses'''</tt> ''справа налево''.
| |
| − | <br />'''Правило 2'''. Если нужно явно указать переменную из какого-то модуля, то перед ней ставится <tt>'''<имя модуля>.'''</tt>
| |
| − | | |
| − | ''<u>Пример</u>''.
| |
| − | <source lang="Pascal">unit A; | |
| − | uses B;
| |
| − | var n, m: integer; | |
| − | ...
| |
| − | end.</source>
| |
| − | | |
| − | <source lang="Pascal">unit B;
| |
| − | var n, k, m: integer; | |
| − | ...
| |
| − | end.</source>
| |
| − | | |
| − | <source lang="Pascal">program MyPr;
| |
| − | uses A, B;
| |
| − | | |
| − | var n: integer;
| |
| | begin | | begin |
| − | n := 5; // из основной программы | + | read(a); |
| − | k := 6; // из B | + | res *= x; |
| − | m := 7; // из B | + | res += a; |
| − | A.n := 8; // из A
| + | end; |
| − | B.n := 9; // из B
| |
| − | A.m := 10; // из A
| |
| − | end.</source> | |
| − | | |
| − | === Стандартный системный модуль PABCSystem ===
| |
| − | <xh4></xh4>
| |
| − | <source lang="Pascal"></source>
| |
| − | | |
| − | <small>'''Лекция 15'''</small>
| |
| − | | |
| − | Документирующие комментарии ///
| |
| − | | |
| − | Библиотеки. Отличие библиотек от модулей. Подключение библиотек в PascalABC.NET.
| |
| − | | |
| − | Перечислимый и диапазонный типы. Стандартные функции Ord Pred Succ. Стандартные процедуры Inc Dec.
| |
| − | | |
| − | Использование перечислимого типа в for и case.
| |
| − | | |
| − | ==Массивы==
| |
| − | | |
| − | Понятие структурированного типа данных.
| |
| − | | |
| − | Определение массива.
| |
| − | | |
| − | Описание массивов. Тип массива. Тип индексов массива. Понятие порядкового типа.
| |
| − | | |
| − | <small>'''Лекция 16'''</small>
| |
| − | | |
| − | Обращение к элементам массивов.
| |
| − | | |
| − | Выход за границы диапазона. Контроль выхода в Delphi и PascalABC.NET.
| |
| − | | |
| − | Динамические массивы. Хранение в памяти.
| |
| − | | |
| − | Инициализация массивов.
| |
| − | | |
| − | Присваивание массивов. Сравнение массивов.
| |
| − | | |
| − | Присваивание a := nil для динамических массивов.
| |
| − | | |
| − | Цикл foreach.
| |
| − | | |
| − | Именная и структурная эквивалентность типов.
| |
| − | | |
| − | <small>'''Лекция 17'''</small>
| |
| − | <H3>Массивы как параметры подпрограмм</H3>
| |
| − | | |
| − | При передаче статического массива должна соблюдаться именная эквивалентность
| |
| − | <source lang="delphi">
| |
| − | procedure xxx(a: array [1..100] of integer); // неверно
| |
| − |
| |
| − | type IArr = array [1..100] of integer;
| |
| − | procedure yyy(a: IArr);
| |
| | </source> | | </source> |
| − | Передавать массив по значению крайне неэффективно (т.к.происходит копирование всех элементов на стек). Его следует передавать по ссылке: для этого есть специальное ключевое слово <tt>const</tt>, которое также запрещает изменять данные внутри п/п.
| + | Итого — всего <tt>n</tt> умножений. |
| − | <source lang="delphi">
| |
| | | | |
| − | procedure zzz(const a: IArr);
| + | === Поиск нуля функции на отрезке === |
| − | procedure sss(var a: IArr);
| + | Требуется найти корень уравнения <tt>f( x ) = 0</tt> |
| | + | * на отрезке <tt>[a; b]</tt> |
| | + | * с заданной точностью <tt>eps</tt> |
| | + | *<tt>f(x)</tt> непрерывна на этом отрезке |
| | + | * имеет на нем ровно 1 корень, т.е. <tt>f(a ) * f( b ) < 0</tt> |
| | | | |
| − | </source>
| + | Эта задача решается '''методом половинного деления'''. |
| − | Динамический массив
| + | <source lang="Pascal"> |
| − | можно передавать в виде <tt>array of integer</tt>, т.к. для него определена структурная эквивалентность типов.
| + | assert(b > a); |
| − | <source lang="delphi"> | + | var fa := f(a); |
| − | procedure ttt(a: array of integer);
| + | var fb := f(b); |
| − | </source> | + | assert(fa * fb < 0); |
| − | Передавать массив по ссылке необходимо только если внутри п/п нужно изменить длину массива.
| |
| − | Иначе можно передавать по значению, т.к. при вызове п/п на программный стек кладется только адрес участка памяти, хранящего значения элементов массива, а значит все изменения формального массива-параметра внутри п/п меняют соответствующий ему фактический параметр.
| |
| − | Массивы как возвращаемые значения функции
| |
| | | | |
| − | Часто требуется использовать массив как возвращаемое значение функции, для этого удобно использовать динамический массив, который хранит свою длину.
| + | while b - a > eps do |
| − | | + | begib |
| − | <h3>Переменное число параметров подпрограмм</h3>
| + | var x := (b + a) / 2; |
| − | | + | var fx := f(x); |
| − | П/п можно создавать с переменным количеством параметров.
| + | if fx * fa > 0 then |
| − | Для этого исп. ключевое слово params.
| + | begin |
| − | При этом такие параметры, перечисленные через запятую, на этапе выполнения упаковываются в динамический массив, и п/п внутри работает именно с ним.
| + | a := x; |
| − | Пар-р params может быть только один и должен находиться последним в списке пар-ов.
| + | fa := fx; |
| − | | + | end |
| − | <small>'''Лекция 18'''</small>
| + | else |
| − | ==Шаблоны подпрограмм==
| + | b := x; |
| − | | + | end; |
| − | Часто требуется выполнять одно и то же действие для разных типов данных.
| |
| − | В этом случае неудобно использовать перегрузку, т.к. п/п отличаются только заголовками.
| |
| − | | |
| − | Выход - шаблоны.
| |
| − | | |
| − | Пример:
| |
| − | | |
| − | procedure Print<T> (array of T); | |
| − | | |
| − | В момент вызова п/п происходит:
| |
| − | | |
| − | * выведение типов шаблона по фактическим параметрам
| |
| − | * инстанцирование - подстановка конкретных типов шаблонов и генерация кода подпрограммы с этими конкретными типами.
| |
| − | | |
| − | Если для такого типа код уже инстанцировался, то повторно действие не выполняется.
| |
| − | | |
| − | ==Задачи на одномерные массивы== | |
| − | | |
| − | * инвертирование массива (шаблон)
| |
| − | * поиск элемента в массиве - найти и вернуть индекс (шаблон)
| |
| − | | |
| − | можно с for и break,
| |
| − | | |
| − | можно и другим способом - с while
| |
| − | | |
| − | * поиск с барьером (шаблон). Его преимущества
| |
| − | * минимальный элемент массива и его индекс
| |
| − | * слияние двух упорядоченных массивов в один упорядоченный (барьер)
| |
| − | * сдвиг элементов массива влево (шаблон)
| |
| − | | |
| − | знакомство со значением default(T), Т - тип
| |
| − | | |
| − | <small>'''Лекция 19'''</small>
| |
| − | | |
| − | <h3>Задачи на одномерные массивы</h3>
| |
| − | | |
| − | pas-файл с задачами
| |
| − | | |
| − | doc-файл
| |
| − | | |
| − | используется тип IArr = array [1..size] of integer
| |
| − | | |
| − | * сдвиг элементов массива вправо (ShiftRight)
| |
| − | | |
| − | [ два варианта определения граничных значений цикла (от n-1 до 1; от n до 2) ]
| |
| − | | |
| − | * циклический сдвиг элементов массива вправо (CycleShiftRight)
| |
| − | * удаление элемента по заданному индексу (Delete)
| |
| − | * вставка элемента по заданному индексу (Insert)
| |
| − | | |
| − | <H3>Задачи с процедурными переменными в качестве параметров</H3>
| |
| − | | |
| − | Определяется тип IUnPred = function (x: integer): boolean
| |
| − | | |
| − | * поиск элемента по заданному условию (Find)
| |
| − | * количество элементов, удовлетворяющих условию (Count)
| |
| − | * условный минимум (MinElem) | |
| − | * удаление всех элементов, удовлетворяющих условию (DeleteAll)
| |
| − | | |
| − | '''Примечание.''' Для проверки выхода индекса за границы диапазона (внутри цикла) следует проверять граничные значения счетчика, подставляя их во все индексы
| |
| − | | |
| − | <small>'''Лекция 20'''</small>
| |
| − | | |
| − | ==Сортировки==
| |
| − | | |
| − | * '''Выбором''' (нахождение минимального элемента в неупорядоченной части массива и перемещение его на первую после уже отсортированного участка позицию)
| |
| − | | |
| − | * '''Пузырьковая'''
| |
| − | | |
| − | Это самый компактный алгоритм сортировки. Его можно оптимизировать, проверяя случай "холостого" прохода по элементам массива. Т.е. если за проход ни один элемент не изменил позицию, значит массив уже отсортирован и проверять дальше нет смысла.
| |
| − | | |
| − | * '''Вставками''' (вставка элемента из еще не упорядоченного участка массива в "нужную" позицию отсортированного, для чего сдвиг части элементов вправо и вставка нового в освободившуюся позицию)
| |
| − | | |
| − | '''Замечание.''' Рассмотренные виды сортировки не являются самыми эффективными.
| |
| − | Асимптотическая сложность алгоритмов
| |
| − | | |
| − | '''Определение.''' Число шагов алгоритма асимптотически равно Θ(f(n)) если, существуют такие N, с1, с2>0 (c1<c2), что для любых n ≥ N выполняется:
| |
| − | | |
| − | c1*f(n) ≤ число шагов ≤ c2*f(n) | |
| − | | |
| − | '''Замечание 1.''' Для рассмотренных алгоритмов сортировки асимптотическая сложность = Θ(n<sup>2</sup>).
| |
| − | | |
| − | '''Замечание 2.''' Существуют алгоритмы сортировки с асимптотической сложностью = Θ(n*logn) (они будут рассмотрены в следующем семестре).
| |
| − | | |
| − | <small>'''Лекция 21'''</small>
| |
| − | ==Алгоритм бинарного поиска в отсортированном массиве== | |
| − | | |
| − | Его асимптотическая сложность - Θ(logn).
| |
| − | Двумерные массивы
| |
| − | | |
| − | Двумерный массив как матрица (соответствие индексов строкам и столбцам)
| |
| − | | |
| − | Элементы строки. Элементы столбца (рисунки)
| |
| − | | |
| − | Понятие замороженного индекса
| |
| − | | |
| − | <H3>Задачи на двумерные массивы</H3>
| |
| − | | |
| − | * Вывод матрицы
| |
| − | ** внешний цикл по строкам
| |
| − | ** если внешним сделать цикл по столбцам будет выведена транспонированная матрица
| |
| − | | |
| − | * Сумма элементов в j-том столбце
| |
| − | | |
| − | * Сумма элементов в каждом столбце
| |
| − | ** использование функции для нахождения суммы в j-ом столбце
| |
| − | * Минимальный элемент в каждой строке
| |
| − | ** в отличие от предыдущей задачи, для реализации не создается дополнительная п/п.
| |
| − | | |
| − | '''Замечание.''' Решать такие задачи можно и реализуя алгоритм полностью, и создавая для этого дополнительные п/п. Если задача несложная, то вполне можно пользоваться первым способом, однако если решение не очевидно, лучше выносить часть алгоритма в п/п, иначе код будет очень трудно читать.
| |
| − | | |
| − | * Квадратные матрицы и элементы выше-ниже главной (побочной) диагонали.
| |
| − | | |
| − | <small>'''Лекция 22'''</small>
| |
| − | | |
| − | * Поиск элемента в матрице
| |
| − | | |
| − | если для поиска используется функция, то при нахождении элемента выходить из циклов с помощью exit,
| |
| − | | |
| − | иначе удобно использовать goto КОНЕЦ_ВНЕШНЕГО_ЦИКЛА
| |
| − | | |
| − | ==Записи==
| |
| − | === Введение ===
| |
| − | <source lang="delphi">
| |
| − | type <имя записи>= record
| |
| − | <поля записи>
| |
| − | end;
| |
| | </source> | | </source> |
| | | | |
| − | Поля записей
| + | == Вложенные циклы == |
| − | | + | === Метод последовательной детализации === |
| − | Инициализация записей при описании (на примере Student)
| + | ''<u>Задача</u>.'' Вывести все простые числа <= n |
| − | | + | <source lang="Pascal"> |
| − | Доступ к полям записей. Точечная нотация.
| + | writeln(2); |
| − | | + | x := 3; |
| − | '''Замечание.''' Для записей имеет место именная эквивалентность типов.
| + | while x <= n do |
| − | | + | begin |
| − | === Передача записей в подпрограммы. Записи как возвращаемые значения функции === | + | Если число x — простое, то |
| − | | + | writeln(x); |
| − | Передача записей в п/п (Print(s)). Запись как возвращаемое значение функции (s := ReadStudent;).
| + | x += 2; |
| − | | + | end; |
| − | Передавать записи по значению неэффективно, т.к. копируются все поля. Поэтому следуют передавать их по ссылке (с ключевым словом const - если значения полей не изменяются, и var - если внутри п/п их требуется изменить.
| |
| − | | |
| − | Оператор with.
| |
| − | | |
| − | <source lang="delphi"> | |
| − | with <переменная типа запись> do
| |
| − | begin
| |
| − | <поле>:=<значение>
| |
| − | end;
| |
| | </source> | | </source> |
| | | | |
| − | Оператор удобен, когда нужно выполнить достаточное количество операций с одной и той же переменной (имя этой переменной и точка добавляются неявно перед всеми полями)
| + | === Метод окаймления === |
| | + | ''<u>Задача</u>.'' Вывести A<sup>k</sup>, A = 2..10 |
| | | | |
| − | === Методы в записях ===
| + | '''Метод окаймления''' заключается в том, что что мы окаймляем данный алгоритм внешним циклом, "''размораживая''" некоторый параметр. |
| | | | |
| − | На примере Student.Print.
| + | Итак, пусть A — фиксировано( "''заморожено''" ). |
| − | | + | <source lang="Pascal"> |
| − | Запись как пространство имен
| + | var p := 1.0; |
| − | | + | for var i:=1 to k do |
| − | Запись выступает для своих полей и методов в качестве модуля (поскольку является набором данных и связанных с ними процедур и функций, оформленных как единое целое).
| + | p *= A; |
| − | | + | write(p); |
| − | Методы работают в некотором окружении, в роли которого выступают поля записи и другие методы.
| |
| − | | |
| − | Т.о. возникает понятие ''инкапсуляции'':
| |
| − | :'''Инкапсуляция''' — хранение в записи одновременно данных и методов (запись представляет собой «капсулу»). <br />Инкапсуляция тесно связана с защитой данных: лишь некоторые члены в этой «капсуле» являются открытыми.
| |
| − | | |
| − | Создается окружение при описании переменной типа запись.
| |
| − | | |
| − | * Сравнение s.Print и Print(s)
| |
| − | | |
| − | '''s.Print''' - объектно-ориентированный подход, доминирует объект, который сам выполняет над собой действие.
| |
| − | | |
| − | '''Print(s)''' - процедурно-ориентированный подход, главным является действие, выполняющееся над переменной.
| |
| − | | |
| − | * Метод Init - инициализатор полей записи.
| |
| − | | |
| − | <small>'''Лекция 23'''</small>
| |
| − | | |
| − | ==Создание простейших графических объектов==
| |
| − | | |
| − | <source lang="delphi"> | |
| − | RPoint = record x, y: integer end;
| |
| − | RRectangle = record p1,p2: RPoint end;
| |
| | </source> | | </source> |
| | | | |
| − | Для каждого типа определяются методы Print, Draw, MoveOn
| + | Теперь ''размораживаем'' A: |
| − | | + | <source lang="Pascal"> |
| − | <H3>Записи как средство упаковки параметров</H3>
| + | for A:=2 to 10 do |
| − | | |
| − | '''Пример.''' | |
| − | Используем определенные типы записей для создания перегруженных версий процедур Rectangle и Line:
| |
| − | | |
| − | <source lang="delphi"> | |
| − | Rectangle(x1,y1, x2,y2: integer)
| |
| − | Rectangle(p1,p2: RPoint)
| |
| − | Rectangle(r: RRectangle)
| |
| − | | |
| − | Line(x1,y1, x2,y2: integer)
| |
| − | Line(p1,p2: RPoint)
| |
| − | Line(r: RRectangle)
| |
| − | </source>
| |
| − | | |
| − | <H3>Переменная типа запись как объект</H3>
| |
| − | | |
| − | В модуле можно выносить реализацию методов записи в раздел реализации. При этом в разделе интерфейса внутри определения типа запись описываются только заголовки методов, а в разделе реализации перед именем метода необходимо писать <Имя записи>.
| |
| − | | |
| − | Поля записи как состояние объекта.
| |
| − | | |
| − | Методы записи как действия, воздействующие на состояние объекта.
| |
| − | | |
| − | Методы делятся на две категории
| |
| − | * меняющие состояние объекта (MoveOn для RPoint)
| |
| − | * осуществляющие доступ к состоянию объекта на чтение (Draw для RPoint)
| |
| − | | |
| − | Сортировка массива записей.
| |
| − | | |
| − | <small>'''Лекция 24'''</small>
| |
| − | ==Индексная сортировка==
| |
| − | | |
| − | Часто физически переставлять элементы массива или вообще невозможно, или долго (в силу достаточно большого размера, например).
| |
| − | В этом случае удобно использовать ''перестановку индексов'' вместо перестановки самих элементов.
| |
| − | | |
| − | Идея заключается в том, чтобы описать '''индексный массив''' index, который взаимооднозначно сопоставляет ''реальным'' индексам элемента ''виртуальные'' таким образом, чтобы относительно ''виртуальных'' массив оказался упорядоченным.
| |
| − | | |
| − | ----
| |
| − | | |
| − | '''Пример.'''
| |
| − | | |
| − | Дан массив целых (с реальными индексами):
| |
| − | '''5'''[1] '''15'''[2] '''3'''[3] '''1'''[4] '''9'''[5] '''8'''[6] '''20'''[7] '''12'''[8]
| |
| − | | |
| − | А так выглядит отсортированный массив по виртуальным индексам:
| |
| − | '''1'''[1] '''3'''[2] '''5'''[3] '''8'''[4] '''9'''[5] '''12'''[6] '''15'''[7] '''20'''[8]
| |
| − | | |
| − | Т.е.
| |
| − | index[1] = 4
| |
| − | index[2] = 3
| |
| − | index[3] = 1
| |
| − | index[4] = 6
| |
| − | index[5] = 5
| |
| − | index[6] = 8
| |
| − | index[7] = 2
| |
| − | index[8] = 7
| |
| − | | |
| − | ----
| |
| − | Соответственно, алгоритм сортировки меняется таким образом, что вместо перемены местами самих элементов упорядочиваемого массива меняется '''содержимое элементов index'''.
| |
| − | | |
| − | Вначале удобно положить элементы index соответствующими '''тождественной''' подстановке (т.е. a[i] = i).
| |
| − | <source lang="delphi">
| |
| − | type CmpFunc = function (const s1,s2: Student): boolean;
| |
| − | | |
| − | procedure BubbleIndexStudentSort(const a: StArr; var Index: IArr; n: integer; Cmp: CmpFunc);
| |
| | begin | | begin |
| − | for var i:=1 to n do | + | ... |
| − | Index[i] := i;
| |
| − | for var i:=n downto 2 do
| |
| − | for var j:=1 to i-1 do
| |
| − | if Cmp(a[Index[j+1]],a[Index[j]]) then
| |
| − | Swap(Index[j+1],Index[j]);
| |
| − | end;
| |
| − | | |
| − | procedure WriteArrByIndex(const a: StArr; const Index: IArr; n: integer);
| |
| − | begin
| |
| − | for var i:=1 to n do
| |
| − | writeln(a[Index[i]].name,' ',a[Index[i]].course,' ',a[Index[i]].group);
| |
| | end; | | end; |
| | </source> | | </source> |
| | | | |
| − | ==Множества== | + | === Переборные задачи === |
| | + | Класс задач, в которых требуется перебрать множество вариантов и выбрать несколько оптимальных по каким-то критериям. |
| | | | |
| − | Описание множеств. Множества-константы. Пустое множество.
| + | ''<u>Задача</u>''. |
| | + | Дано равенство: a<sup>2</sup> + b<sup>2</sup> = c<sup>2</sup>, a,b,c — целые <br /> |
| | + | Вывести все такие тройки (a, b, c), что: a<=100, b<=1000, c<=1000; |
| | | | |
| − | Операции над множествами:
| + | <u>Решение</u>. |
| − | s1+s2 - объединение
| + | <source lang="Pascal"> |
| − | s1*s2 - пересечение
| + | for var a:=1 to 1000 do |
| − | s1-s2 - разность
| + | for var b:=1 to 1000 do |
| − | s += s1
| + | for var c:=1 to 1000 do |
| − | s -= s1
| + | if a*a + b*b = c*c then |
| − | s *= s1
| + | writeln(a, b, c); |
| − | s1<s2 - строгое вложение
| + | </source> |
| − | s1<=s2 - нестрогое вложене
| |
| − | s1>s2 - строгое вложение
| |
| − | s1<=s2 - нестрогое вложене
| |
| − | i in s - принадлежность
| |
| − |
| |
| − | Include(s,i);
| |
| − | Exclude(s,i);
| |
| − | Вывод множеств.
| |
| | | | |
| − | Цикл foreach по множеству.
| + | Однако, ясно, что |
| | + | a<sup>2</sup> + b<sup>2</sup> = c<sup>2</sup> <=> b<sup>2</sup> + a<sup>2</sup> = c<sup>2</sup> |
| | + | Кроме того, <tt>c</tt> можно вычислять. |
| | | | |
| − | Пример использования множеств: решето Эратосфена.
| + | <u>Оптимизация</u>. |
| − | Алгоритм.
| + | <source lang="Pascal"> |
| − | | + | for var a:=1 to 1000 do |
| − | <small>'''Лекция 25'''</small> | + | for var b:=1 to a-1 do |
| − | <H3>Алгоритм Эратосфена</H3>
| + | begin |
| − | | + | var c := round(sqrt(a*a + b*b)); |
| − | Код алгоритма Эратосфена
| + | if a*a + b*b = c*c then |
| − | <source lang="delphi"> | + | begin |
| − | const n = 10000;
| + | writeln(a, b, c); |
| − | var primes: set of byte; | + | writeln(b, a, c); |
| − | begin | + | end; |
| − | primes := [2..n];
| + | end; |
| − | for var i:=2 to round(sqrt(n)) do
| |
| − | begin
| |
| − | if not (i in primes) then
| |
| − | continue;
| |
| − | var x := 2*i;
| |
| − | while x<=n do
| |
| − | begin
| |
| − | Exclude(primes,x);
| |
| − | x += i;
| |
| − | end;
| |
| − | end;
| |
| − | for var i:=0 to n do
| |
| − | if i in primes then
| |
| − | write(i,' ');
| |
| − | end.
| |
| | </source> | | </source> |
| | | | |
| − | <H3>Статические методы записей</H3>
| + | '''Вывод.''' При наличии нескольких вложенных циклов, в первую очередь, нужно оптимизировать ''самый внутренний''. |
| − | <source lang="delphi">
| |
| − | type RRectangle = record
| |
| − | class function EqualSquare(const r1,r2: RRectangle): boolean;
| |
| − | class function CreateRandom: RRectangle;
| |
| − | end;
| |
| − | </source>
| |
| − | | |
| − | <H3>Символы</H3>
| |
| − | | |
| − | Коды символов. Однобайтовые и двухбайтовые кодировки.
| |
| − | ASCII - стандарт на символы с кодами 0..127.
| |
| − | Unicode.
| |
| − | Однобайтовые кодировки: Windows, DOS (CP866), Koi8
| |
| − | | |
| − | Литеральные константы-символы:
| |
| − | #13 - символ возврата "каретки"
| |
| − | #10 - символ перехода на следующую строку
| |
| − | #9 - символ табуляции
| |
| − | | |
| − | <H4>Стандартные подпрограммы работы с символами</H4>
| |
| − | OrdUnicode(c)
| |
| − | ChrUnicode(i)
| |
| − | Succ(c)
| |
| − | Pred(c)
| |
| − | Inc(c,5)
| |
| − | Dec(c,5)
| |
| − | Ord(c)
| |
| − | Chr(i)
| |
| − | UpperCase(c)
| |
| − | LowerCase(c)
| |
| − | | |
| − | Для символов с кодами 0..127
| |
| − | OrdUnicode(c)=Ord(c)
| |
| − | ChrUnicode(i)=Chr(i)
| |
| − | | |
| − | char - тип, содержащий ряд статических методов:
| |
| − | | |
| − | char.IsDigit(c)
| |
| − | char.IsLetter(c)
| |
| − | char.IsLetterOrDigit(c)
| |
| − | char.IsLower(c)
| |
| − | char.IsUpper(c)
| |
| − | char.ToLower(c)
| |
| − | char.ToUpper(c)
| |
| − | | |
| − | <small>'''Лекция 26'''</small>
| |
| − | ==Строки==
| |
| − | | |
| − | Тип string
| |
| − | | |
| − | Отводится память (до 2 Гб), равная длине строки, плюс некоторая дополнительная информация
| |
| − | | |
| − | Строки - массивы символов, индексируемые с 1: s[i] - i - тый символ строки.
| |
| − | var s := 'IT'; // s[1]='I', s[2]='T'
| |
| − | | |
| − | Операции со строками:
| |
| − | | |
| − | s1+s2
| |
| − | s1 += s2
| |
| − | s1<s2
| |
| − | ...
| |
| − | | |
| − | <H3>Основные подпрограммы работы со строками</H3>
| |
| − | | |
| − | '''Length(s)''' - функция, возвращающая длину строки s
| |
| − | | |
| − | '''SetLength(s,n)''' - процедура, устанавливающая длину строки s равной n
| |
| − | | |
| − | '''Copy(s,from,len)''' - функция, возвращающая подстроку s с позиции from длины len
| |
| − | | |
| − | '''Insert(subs,s,form)''' - процедура, вставляющая подстроку subs в строку s с позиции from
| |
| − | | |
| − | '''Delete(s,from,len)''' - процедура, удаляющая из строки s len символов с позиции from
| |
| − | | |
| − | '''Pos(subs,s)''' - функция, возвращающая позицию первого вхождения подстроки subs в строку s или 0, если подстрока не найдена
| |
| − | | |
| − | '''PosEx(subs,s,from=1)''' - функция, возвращающая позицию первого вхождения подстроки subs в строку s, начиная с позиции from, или 0, если подстрока не найдена
| |
| − | | |
| − | '''TrimLeft(s)''' - функция, возвращающая строку s, в которой удалены все начальные пробелы
| |
| − | | |
| − | '''TrimRight(s)''' - функция, возвращающая строку s, в которой удалены все заключительные пробелы
| |
| − | | |
| − | '''Trim(s)''' - функция, возвращающая строку s, в которой удалены все удаляет все начальные и заключительные пробелы | |
| − | | |
| − | <h4>Преобразование строка ↔ число</h4>
| |
| − | | |
| − | '''Str(x,s)''' - процедура, преобразующая целое или вещественное выражение x к строковому представлению и записывающая результат в строку s
| |
| − | | |
| − | '''Val(s,x,errcode)''' - процедура, преобразующая строку s к целому или вещественному значению и записывающая результат в целую или вещественную переменную x. Переменная errcode - целая; если преобразование невозможно, то в errcode содержится номер первого символа, вызвавшего ошибку
| |
| − | | |
| − | '''IntToStr(i)''' - функция, преобразующая целое x в строку | |
| − | | |
| − | '''StrToInt(s)''' - функция, преобразующая строку s к целому; может генерировать исключение
| |
| − | | |
| − | '''FloatToStr(i)''' - функция, преобразующая вещественное x в строку
| |
| − | | |
| − | '''StrToFloat(s)''' - функция, преобразующая строку s к вещественному; может генерировать исключение
| |
| − | | |
| − | <H3>Некоторые задачи на строки</H3>
| |
| − | | |
| − | Посимвольная обработка
| |
| − | | |
| − | * Строка 'ABCD...XYZ'
| |
| − | * Сумма всех цифр в строке s
| |
| − | | |
| − | Использование стандартных подпрограмм
| |
| − | | |
| − | * Вывести индексы всех вхождений подстроки s1 в s (на Delete, PosEx)
| |
| − | | |
| − | ==Ссылки==
| |
| − | *[[Основы программирования — Осенний семестр; Михалкович С.С.; 2008; I| Первая часть конспекта]]
| |
| − | *[[Конспекты|Другие конспекты]]
| |
Переменная цикла, описанная в заголовке цикла, определена только внутри цикла.
Замечание. Значение переменной цикла после завершения цикла не определено. Именно поэтому рекомендуется описывать переменную цикла в заголовке цикла.
Дана f(x) на [a; b], разбитая на N частей.
Выдать таблицу значений в точках разбиения.
<math>\begin{cases} x_1 = 1, x_2 = 1 \\ x_{k+1} = x_k + x_{k-1}\end{cases}</math>
<math>\begin{cases} x_1 = a \\ x_2 = b \\ x_{k+1} = x_{k-1} mod x_k\end{cases}</math>
Вводятся числа. Конец ввода — ноль.
Найти сумму и произведение положительных чисел.
Необходимо вычислить
<math>\ a_0x^n + a_1x^{n-1} + ... + a_{n-1}x + a_n</math>
если
Класс задач, в которых требуется перебрать множество вариантов и выбрать несколько оптимальных по каким-то критериям.
