Основы программирования — Осенний семестр; Михалкович С.С.; 2008; III — различия между версиями

Материал из Вики ИТ мехмата ЮФУ
Перейти к: навигация, поиск
(Новая: Категория:Конспекты ==Подпрограммы== ===Вспомогательные алгоритмы=== '''Вспомогательный алгоритм''' — ...)
 
(Примеры использования циклов)
 
(не показано 9 промежуточных версий 3 участников)
Строка 1: Строка 1:
[[Категория:Конспекты]]
+
[[Категория:Основы программирования]]
==Подпрограммы==
+
[[Страница курса Основы программирования|К основной странице курса]]
===Вспомогательные алгоритмы===
+
== Циклы ==
'''Вспомогательный алгоритм''' — это алгоритм, который используется для реализации другого алгоритма.
+
=== Циклы с предусловием (while) и постусловием (repeat) ===
 +
<xh4> Синтаксис цикла while </xh4>
 +
'''while''' <условие> '''do'''   <'''''заголовок цикла'''''
 +
  <оператор>  <— '''''тело цикла'''''
 +
 +
<условие>::= <логическое выражение>
  
Вспомогательные алгоритмы имеют:
+
<xh4> Семантика цикла while </xh4>
*'''''имя'''''
+
[[Изображение:Цикл_while_м.png]]
*'''''список параметров'''''
 
:некоторые параметры являются ''входными'', а некоторые — ''выходными''
 
  
Если один из ''выходных'' параметров возвращается особым образом, так что алгоритм можно использовать в выражении, то такой алгоритм называется '''алгоритмом-функцией'''.
+
<xh4> Синтаксис цикла repeat </xh4>
 +
'''repeat'''
 +
  <операторы>
 +
'''until''' <условие>
  
В программировании вспомогательные алгоритмы называются '''подпрограммами''' и делятся на:
+
<xh4> Семантика цикла repeat </xh4>
*'''''процедуры'''''
+
[[Изображение:Цикл_repeat_м.png]]
*'''''функции'''''
 
  
 +
=== Зацикливание ===
 +
'''Зацикливание''' происходит, если:
 +
* условие цикла с ''предусловием'' всегда ''истинно''
 +
''<u>Пример</u>.''
 +
<source lang="Pascal">
 +
while true do
 +
  <оператор>
 +
</source>
  
'''Важно.''' Подпрограммы позволяют избежать дублирования кода при решении однотипных задач.  
+
* условие цикла с ''постусловием'' всегда ''ложно''
Алгоритм один раз описывается, а затем может быть многократно вызван с различным набором параметров из другого алгоритма.
+
''<u>Пример</u>.''
 +
<source lang="Pascal">
 +
repeat
 +
  <операторы>
 +
until false
 +
</source>
  
<small>'''Лекция 9'''</small>
+
'''Итерация''' — однократное повторение тела цикла.
  
===Процедуры===
+
<xh4> Отличия между циклами while и repeat </xh4>
'''Пример.'''
+
'''''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>
 
называется '''заголовком процедуры'''.
 
  
Теперь можем многократно использовать описанную процедуру в основной программе:
+
<xh4> Примеры </xh4>
<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) ===
Если функция возвращает результат и выполняет дополнительное действие, которое сказывается вне функции, то такие действия называются '''побочным рузультатом вызова функции.'''
+
<xh4> Синтаксис </xh4>
 +
<заголовок цикла>
 +
  <тело цикла>
  
'''Правило.'''
+
<заголовок цикла> ::= '''for''' <переменная>:=<выражение1> <направление> <выражение2> '''do'''
:В подавляющем большинстве случаев функция не должна иметь побочный эффект.
+
<тело цикла> ::= <оператор>
 +
<направление> ::= to | downto
  
===Оператор exit===
+
<xh4> Семантика </xh4>
Оператор '''<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;      //Можно
+
while <переменная> <> e do
 
'''procedure''' p(i: integer);        //НЕЛЬЗЯ
 
'''var''' i: integer;
 
 
function f(Result: real): real; //НЕЛЬЗЯ
 
<small>'''Лекция 10'''</small>
 
==Область видимости и время жизни объекта==
 
'''Время жизни переменной''' — время, в течение которого существует отведенная ей память.
 
*для глобальных переменных это время работы программы
 
*для локальных — с момента описания до конца работы блока, где они описаны
 
 
 
'''Область видимости переменной''' — область в программе, в которой можно обратиться к переменной по имени.
 
==Побочный эффект==
 
'''Побочным эффктом подпрограммы''' называется также любое изменение глобальных переменных (или параметров для функции).
 
 
 
'''Пример.'''
 
<source lang="Pascal">var n: integer;
 
procedure p;
 
 
begin
 
begin
   n += 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
+
Табулирование функции<xh4>
  <еще больше кода; n не используется>
+
</xh4>Дана 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;
 +
var x:real:=h;
 +
</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);
+
==== Погрешность при работе с вещественными числами ====
begin
+
'''Замечание.''' Вещественные числа в памяти компьютера представлены приближенно. Ошибка, которая возникает при ''представлении'' вещественного числа в памяти, называется '''ошибкой округления'''
  var t := a;
+
Ошибка, которая возникает в результате ''вычислений'' с вещественными числами, называется '''вычислительной погрешностью'''.
  a := b;
 
  b := t;
 
end;</source>
 
Таким образом, в одном пространстве имен можно описать несколько подпрограмм с одним именем, но разными типами или количеством формальных параметров.
 
<br>При вызове такой подпрограммы на ''этапе компиляции'' типы фактических параметров сравниваются с типами формальных для всех версий этой подпрограммы и выбирается наиболее подходящая.
 
 
 
'''Замечание 1.''' Тип возвращаемого значения функции не участвует в операции разрешения перегрузки.
 
 
 
Версии подпрограммы с одним именем называются '''перегруженными''', а определение того, какую версию выбрать — '''разрешением перегрузки'''.
 
  
'''Замечание 2.''' Разрешить перегрузку можно не всегда.
+
Вещественные хранятся в памяти компьютера в виде M*10<sup>p</sup>, где M называется мантиссой, p - порядком. Вещественное типа real занимает 64 бита (8 байт), из которых первый бит отводится под знак
<br>'''Пример.'''
+
порядка, следующие 11 бит хранят значение порядка, затем идет бит для знака мантиссы и оставшиеся 51 бит отводятся для хранения мантиссы.
<source lang="Pascal">procedure p(i: integer; r: real);
 
...
 
  
procedure p(r: real; c: char);
+
Минимальное положительное вещественное число называется '''машинным эпсилон''' и задается константой real.Epsilon<br />
...
 
 
 
procedure p(r: real; i: integer);
 
...
 
  
 
begin
 
begin
   p(1, 2); //неоднозначность
+
   writeln(real.Epsilon);
end.</source>
+
end.
'''Замечание 3.''' В процессе разрешения перегрузки происходит ''неявное преобразование типов''.
 
<small>'''Лекция 11'''</small>
 
  
==Параметры по умолчанию==
 
<source lang="Pascal">procedure DoOp(a, b: integer; var res: integer; op: char := '+');
 
begin
 
  case op of
 
    '+': res := a + b;
 
    '-': res := a - b;
 
    '*': res := a * b;
 
  end;
 
end;
 
...
 
DoOp(1,2, res, '-'); // res = -1
 
DoOp(3,4, res1);    // res1 = 7</source>
 
'''Параметры по умолчанию''' обязательно должны находиться последними в списке параметров. Если при вызове не указывать этот параметр, будет использовано значение по умолчанию.
 
  
'''Замечание.''' Параметры по умолчанию корректно сочетаются с перегрузкой.
+
'''Вывод.''' Вещественные числа нельзя сравнивать на равенство, можно только на ''больше/меньше''.
==Предварительное объявление подпрограмм==
 
<source lang="Pascal">procedure p;
 
begin
 
  q;
 
end;
 
  
procedure q;
+
<xh4> Рекуррентные соотношения </xh4>
begin
+
Говорят, что последовательность данных
  ...
+
x<sub>1</sub>, x<sub>2</sub>, x<sub>3</sub>,..., x<sub>n</sub>
end;</source>
+
является '''рекуррентной''', если
Такое описание вызовет ошибку компиляции, т.к. в '''<tt>p</tt>''' используется еще не известная процедура. Чтобы таких ошибок не возникало, нужно использовать ''предварительное объявление подпрограммы'':
+
x<sub>k + 1</sub> = f( x<sub>k</sub> ), k = 1, 2, 3...
<source lang="Pascal">procedure q; forward;
 
  
procedure p;
+
<xh4> Вывод степеней двойки </xh4>
 +
<source lang="Pascal">
 +
var x := 1;
 +
for var i := 1 to 10 do
 
begin
 
begin
   q;
+
   writeln(x);
 +
  x *= 2;
 
end;
 
end;
 +
</source>
  
procedure q;
+
<xh4> Последовательность Фибоначчи </xh4>
  ...</source>
+
<math>\begin{cases} x_1 = 1, x_2 = 1 \\ x_{k+1} = x_k + x_{k-1}\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 := 1;
  BinOpType = procedure(a, b: real; var res: real);
+
var b := 1;
 
+
write(a, ' ', b, ' ');
var
+
for var i := 3 to 20 do
  pr: BinOpType;
 
 
 
procedure AddOp(a, b: real; var res: real);
 
 
begin
 
begin
   res := a + b;
+
   c := a + b;
end;
+
  write(c, ' ');
procedure MultOp(a, b: real; var res: real);
+
  a := b;
begin
+
   b := c;
   res := a * b;
 
 
end;
 
end;
 +
</source>
  
begin
+
<xh4> Вычисление НОД (алгоритм Евклида) </xh4>
  pr := AddOp;
+
<math>\begin{cases} x_1 = a \\ x_2 = b \\ x_{k+1} = x_{k-1} mod  x_k\end{cases}</math>
  var r: real;
 
  pr(1,2, r);  //вызов процедуры через процедурную переменную
 
  
  pr := MultOp;
+
<source lang="Pascal">
  pr(3,4, r);
+
var a, b: integer;
end.</source>
+
read(a, b);
После присваивания процедурной переменной имени процедуры, эта процедура может быть вызвана через переменную:
+
assert((a > 0) and (b > 0));
<имя процедурной переменной>( <список параметров> );
+
repeat
Такой способ вызова процедуры является чрезвычайно гибким, поскольку позволяет менять вызываемое действие в процессе работы программы.
+
  c := a mod b;
 +
  a := b;
 +
  b := c;
 +
until c = 0;
 +
writeln(a);
 +
</source>
  
'''Замечание.''' До первого присваивания процедурная переменная имеет тип <tt>'''nil'''</tt>. В этот момент вызывать процедуру через переменную нельзя — будет ошибка выполнения.
+
<xh4> Суммирование рядов (конечных и бесконечных) </xh4>
 +
* <math>\sum_{i=1}^n  \frac{a^i}{i!}</math>
  
===Функции обратного вызова (callback)===
+
Найдем рекуррентную связь между <tt>a<sub>i</sub></tt>:
<source lang="Pascal">type ActionType = procedure;
+
x<sub>1</sub> = a
 +
x<sub>i</sub> = x<sub>i-1</sub> * a / i, i = 2, 3..
  
procedure DoActions(Action1, Action2, Action3: ActionType);
+
<source lang="Pascal">
 +
read(a, n);
 +
x := a;
 +
s := x;
 +
for var i := 2 to n do
 
begin
 
begin
   Action1;
+
   x *= a / i;
   Action2;
+
   s += x;
  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>
  
'''Пример.''' Вычисление определённого интеграла методом прямоугольников.
+
<xh4> Нахождение max в последовательности чисел </xh4>
<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>
  
===Вызов нескольких процедур через процедурную переменную===
+
<xh4> Разложение целого числа на простые множители </xh4>
<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);
+
<xh4> Поиск заданного значения среди введенных </xh4>
var x := 3;
+
<u>Решение 1</u>. С использованием оператора ''break''
while x <= 1000 do
+
<source lang="Pascal">
begin
+
var exists: boolean := false;
  if IsPrime(x) then
+
for var i:=1 to n do
    writeln(x);
 
  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
 
begin
  goto 1;
+
  read(x);
  <100 операторов>
+
   if x = k then
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> "поднимается на размер ЗА.
+
<xh4> Обработка последовательности, завершающейся нулем </xh4>
<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;
+
<xh4> Вычисление значения многочлена. Схема Горнера </xh4>
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);
+
<xh4> Поиск нуля функции на отрезке </xh4>
  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<=1000, 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| Первая часть конспекта]]
 
*[[Конспекты|Другие конспекты]]
 

Текущая версия на 14:00, 21 сентября 2013

К основной странице курса

Циклы

Циклы с предусловием (while) и постусловием (repeat)

<xh4> Синтаксис цикла while </xh4>

while <условие> do   <— заголовок цикла
  <оператор>   <— тело цикла

<условие>::= <логическое выражение>

<xh4> Семантика цикла while </xh4> Цикл while м.png

<xh4> Синтаксис цикла repeat </xh4>

repeat
  <операторы>
until <условие>

<xh4> Семантика цикла repeat </xh4> Цикл repeat м.png

Зацикливание

Зацикливание происходит, если:

  • условие цикла с предусловием всегда истинно

Пример.

while true do
  <оператор>
  • условие цикла с постусловием всегда ложно

Пример.

repeat
  <операторы>
until false

Итерация — однократное повторение тела цикла.

<xh4> Отличия между циклами while и repeat </xh4> while

тело может не выполниться ни разу

repeat

тело выполнится хотя бы один раз

<xh4> Примеры </xh4> Пример 1. Сумма нечетных двузначных чисел

С использованием while

s := 0; 
x := 11;
while x < 100 do
begin
  s += x;
  x += 2;
end;

С использованием repeat

s := 0; x := 11;
repeat
  s += x;
  x += 2;
until x = 99;

Пример 2. Факториал

С использованием repeat

var n: integer;
read(n);
var x := n;
var p := 1;

repeat
  p *= x;
  x -= 1;
until x = 1;

С использованием while

var n: integer;
read(n);
var x := n;
var p := 1;

while x > 1 do
begin
  p *= x;
  x -= 1;
end;

Моделирование repeat с помощью while

repeat             Op
  Op       ——>     while not A do
until A;           begin
                     Op
                   end;

Моделирование while с помощью repeat

while A do         if A then
  Op         ——>     repeat
                       Op
                     until not A

Оператор цикла с параметром (for)

<xh4> Синтаксис </xh4>

<заголовок цикла>
  <тело цикла>
<заголовок цикла> ::= for <переменная>:=<выражение1> <направление> <выражение2> do
<тело цикла> ::= <оператор> 
<направление> ::= to | downto

<xh4> Семантика </xh4>

var b := <выражение1>;
var e := <выражение2>;
  <переменная> := b;
 
while <переменная> <> e do
begin
  <оператор>
  <получить следующее значение переменной>
end;
<получить следующее значение переменной> ::= <переменная> += 1; | <переменная> -= 1;

<xh4> Ограничения: </xh4>

  • выражения 1 и 2 должны быть совместимы по присваиванию с переменной
  • переменная должна иметь порядковый тип (такой же, как и в case — целый, символьный или перечислимый)
  • переменная цикла for не должна меняться внутри цикла for
  • переменная цикла for должна быть описана в той же п/п, где используется цикл

Дополнительные возможности PascalABC.NET

Возможно описание переменной цикла в его заголовке:

for [var] i: integer := 1 to 5 do
  <оператор>

Возможно автоопределение типа при описании:

for var i := 1 to 5 do
  <оператор>

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

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

Табулирование функции<xh4>

</xh4>Дана f(x) на [a; b], разбитая на N частей. 

Выдать таблицу значений в точках разбиения.

var a, b: real;
var N: integer;
read(a, b, N);

assert(N <> 0);
assert(b > a);
var h := (b - a) / N;
var x:real:=h;

Дальнейшее решение с помощью for:

for var i := 0 to N do
begin
  writelnFormat('{0,6:f2} {1,9:f4}', x, f(x));
  x += h;
end;

Дальнейшее решение с помощью while:

var eps := h / 2;
while x < (b + eps) do
begin
  writelnFormat('{0,6:f2} {1,9:f4}', x, f(x));
  x += h;
end;

Погрешность при работе с вещественными числами

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

Вещественные хранятся в памяти компьютера в виде M*10p, где M называется мантиссой, p - порядком. Вещественное типа real занимает 64 бита (8 байт), из которых первый бит отводится под знак порядка, следующие 11 бит хранят значение порядка, затем идет бит для знака мантиссы и оставшиеся 51 бит отводятся для хранения мантиссы.

Минимальное положительное вещественное число называется машинным эпсилон и задается константой real.Epsilon

begin

 writeln(real.Epsilon);

end.


Вывод. Вещественные числа нельзя сравнивать на равенство, можно только на больше/меньше.

<xh4> Рекуррентные соотношения </xh4> Говорят, что последовательность данных

x1, x2, x3,..., xn

является рекуррентной, если

xk + 1 = f( xk ), k = 1, 2, 3...

<xh4> Вывод степеней двойки </xh4>

var x := 1;
for var i := 1 to 10 do
begin
  writeln(x);
  x *= 2;
end;

<xh4> Последовательность Фибоначчи </xh4> <math>\begin{cases} x_1 = 1, x_2 = 1 \\ x_{k+1} = x_k + x_{k-1}\end{cases}</math>

var a := 1;
var b := 1;
write(a, ' ', b, ' ');
for var i := 3 to 20 do
begin
  c := a + b;
  write(c, ' ');
  a := b;
  b := c;
end;

<xh4> Вычисление НОД (алгоритм Евклида) </xh4> <math>\begin{cases} x_1 = a \\ x_2 = b \\ x_{k+1} = x_{k-1} mod x_k\end{cases}</math>

var a, b: integer;
read(a, b);
assert((a > 0) and (b > 0));
repeat
  c := a mod b;
  a := b;
  b := c;
until c = 0;
writeln(a);

<xh4> Суммирование рядов (конечных и бесконечных) </xh4>

  • <math>\sum_{i=1}^n \frac{a^i}{i!}</math>

Найдем рекуррентную связь между ai:

x1 = a
xi = xi-1 * a / i, i = 2, 3..
read(a, n);
x := a;
s := x;
for var i := 2 to n do
begin
  x *= a / i;
  s += x;
end;
  • <math>\sum_{i=1}^\infty (-1)^i\frac{a^i}{i}</math>

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

задается некоторый малый eps и сумма <math>\sum_{i=1}^\infty x_i</math> вычисляется, пока <math>|x_i| >\ eps</math>
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;

<xh4> Нахождение max в последовательности чисел </xh4>

max := - real.MaxValue; // или max := real.MinValue;
for var i := 1 to n do
begin
  read(x);
  if x > max then
    max := x;
end;

<xh4> Разложение целого числа на простые множители </xh4> Будем делить x на p, начиная с p = 2. Если делится нацело, то p — множитель, если не делится, то увеличиваем p на 1, пока x <> 1.

read(x);
p := 2;
repeat
  if x mod p = 0 then
  begin
    write(p, ' ');
    x := x div p;
  end
  else
    p += 1;
until x = 1;

Операторы break и continue

break — оператор досрочного завершения цикла.

Break м.png

continue — оператор досрочного завершения текущей итерации цикла.

Continue м.png

Примеры использования циклов (продолжение)

<xh4> Поиск заданного значения среди введенных </xh4> Решение 1. С использованием оператора break

var exists: boolean := false;
for var i:=1 to n do
begin
  read(x);
  if x = k then
  begin
    exists := true;
    break;
  end;
end;

Решение 2.

var i := 1;
var exists: boolean:= false;
repeat
  read(x);
  if x = k then
    exists := true;
  i += 1;
until (i > n) or exists;

<xh4> Обработка последовательности, завершающейся нулем </xh4> Вводятся числа. Конец ввода — ноль.
Найти сумму и произведение положительных чисел.

s := 0;
p := 1;
while True do
begin
  read(x);
  if x = 0 then
    break; 
  if x < 0 then
    continue;  //фильтр
  s += x;
  p *= x;
end;

<xh4> Вычисление значения многочлена. Схема Горнера </xh4> Необходимо вычислить <math>\ a_0x^n + a_1x^{n-1} + ... + a_{n-1}x + a_n</math> если

a0...an известны
x дано

Решение 1.

var p := 1.0;
var s := 0.0;
for var i := 0 to n do
begin
  read(a);
  s += p * a;
  p *= x;
end;

Это решение использует 2(n + 1) умножений.

Однако есть и другое решение — схема Горнера. Оно основана на том, что
<math>\ a_0x^2 + a_1x + a_2 = ((a_0)x + a_1)x + a_2</math>

Решение 2.

read(a);
var res: real := a;
for var i:=1 to n do
begin
  read(a);
  res *= x;
  res += a;
end;

Итого — всего n умножений.

<xh4> Поиск нуля функции на отрезке </xh4> Требуется найти корень уравнения f( x ) = 0

  • на отрезке [a; b]
  • с заданной точностью eps
  • f(x) непрерывна на этом отрезке
  • имеет на нем ровно 1 корень, т.е. f(a ) * f( b ) < 0

Эта задача решается методом половинного деления.

assert(b > a);
var fa := f(a);
var fb := f(b);
assert(fa * fb < 0);

while b - a > eps do
begib
  var x := (b + a) / 2;
  var fx := f(x);
  if fx * fa > 0 then
  begin
    a := x;
    fa := fx;
  end
  else
    b := x;
end;

Вложенные циклы

Метод последовательной детализации

Задача. Вывести все простые числа <= n

writeln(2);
x := 3;
while x <= n do
begin
  Если число x — простое, то
    writeln(x);
  x += 2;
end;

Метод окаймления

Задача. Вывести Ak, A = 2..10

Метод окаймления заключается в том, что что мы окаймляем данный алгоритм внешним циклом, "размораживая" некоторый параметр.

Итак, пусть A — фиксировано( "заморожено" ).

var p := 1.0;
for var i:=1 to k do
  p *= A;
write(p);

Теперь размораживаем A:

for A:=2 to 10 do
begin
  ...
end;

Переборные задачи

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

Задача. Дано равенство: a2 + b2 = c2, a,b,c — целые
Вывести все такие тройки (a, b, c), что: a<=1000, b<=1000, c<=1000;

Решение.

for var a:=1 to 1000 do
for var b:=1 to 1000 do
for var c:=1 to 1000 do
  if a*a + b*b = c*c then
    writeln(a, b, c);

Однако, ясно, что

a2 + b2 = c2 <=> b2 + a2 = c2

Кроме того, c можно вычислять.

Оптимизация.

for var a:=1 to 1000 do
  for var b:=1 to a-1 do
  begin
    var c := round(sqrt(a*a + b*b));
    if a*a + b*b = c*c then
    begin
      writeln(a, b, c);
      writeln(b, a, c);
    end;
  end;

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