Перейти к содержимому

Переменная цикла for должна описываться в том же блоке что и цикл for

  • автор:

Научный форум dxdy

Написал процедуру, не хочет запускать, пишет что:
slonim.pas(26) : Переменная цикла for должна описываться в том же блоке, что и цикл for.

uses
crt, graphABC;

var
n, m, i, j, max1, max2, n1, n2: integer;
a: array[1..3, 1..25] of integer;
z: char;

procedure menu(var w: char);
begin
clrscr;
writeln(‘выберите пункт меню:’);
writeln(‘Y — условие’);
writeln(‘V — ввод данных’);
writeln(‘R — вывод данных’);
writeln(‘Q — выход’);
readln(w);
end;

procedure yslovie;
begin
HideCursor;
write(‘Приводится рост учеников 3 параллельных классов, где колличество n<=25 в каждом классе. Определить номера двух самых высоких учеников в каждом классе.’);writeln;
writeln;
writeln(‘Автор работы : ‘);
for i := 1 to 18 do writeln;
writeln(‘ Для выхода в меню нажмите Enter’);
readln;
end;

procedure vvod;
begin
randomize;
n := random(25 — 15) + 14; //ввод
for i := 1 to 3 do
for j := 1 to n do
a[i, j] := random(195 — 141) + 140;

for i := 1 to 3 do //вывод
begin
for j := 1 to n do
write(a[i, j]:4);
write(‘ — класс №’, i);
writeln;
end;
for i := 1 to 17 do writeln;
writeln(‘ Для выхода в меню нажмите Enter’);
readln;
end;

procedure vivod;
begin
if a[1, 1] = 0 then writeln(‘Что ты как не человек. Данные введи сначало :)’)
else begin
for i := 1 to 3 do //вывод
begin
for j := 1 to n do
write(a[i, j]:4);
write(‘ — класс №’, i);
writeln;
end;

max1 := a[1, 1];
for i := 1 to 3 do
begin
max1 := 0;
n1 := 0;
n2 := 0;
for j := 1 to n do
if max1 < a[i, j] then begin
n2 := n1;
max2 := max1;
n1 := j;
max1 := a[i, j];
end
else if max2 < a[i, j] then begin
max2 := a[i, j];
n2 := j;
end;
writeln(‘В ‘, i, ‘ классе, ученики под номером ‘, n1:2, ‘ и ‘, n2:2, ‘ самые высокие’);
end;
end;
for i := 1 to 14 do writeln;
writeln(‘ Для выхода в меню нажмите Enter’);
readln;
end;

begin
repeat
clrscr;
menu(w);
case upcase(w) of
‘Y’:
begin
clrscr;
yslovie;
end;
‘V’:
begin
clrscr;
vvod;
end;
‘R’:
begin
clrscr;
vivod;
end;
‘Q’: closewindow;
end;
until upcase(w) = ‘Q’;
end.

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

Чтобы отступы в коде не пропадали (надеюсь, они были? а то вряд ли кто-то станет приглядываться к нему внимательно, если предыдущих мер окажется всё-таки недостаточно), вставьте его заново внутри [syn tax lang=»pascal»]…[/syntax] , пока можете редактировать пост.

Это делается вот так:

uses
crt , graphABC;

var
n , m , max1 , max2 , n1 , n2 : integer ;
a : array [ 1 .. 3 , 1 .. 25 ] of integer ;
z : char ;

procedure menu ( var w : char ) ;

begin
clrscr;
writeln ( ‘выберите пункт меню:’ ) ;
writeln ( ‘Y — условие’ ) ;
writeln ( ‘V — ввод данных’ ) ;
writeln ( ‘R — вывод данных’ ) ;
writeln ( ‘Q — выход’ ) ;
readln ( w ) ;
end ;

procedure yslovie;
var
i : integer ;
begin
HideCursor;
write ( ‘Приводится рост учеников 3 параллельных классов, где колличество n<=25 в каждом классе. Определить номера двух самых высоких учеников в каждом классе.’ ) ; writeln ;
writeln ;
writeln ( ‘Автор работы : ‘ ) ;
for i := 1 to 18 do writeln ;
writeln ( ‘ Для выхода в меню нажмите Enter’ ) ;
readln ;
end ;

procedure vvod;
var
i , j : integer ;
begin
clrscr;
randomize;
n := random ( 25 — 15 ) + 14 ; //ввод
for i := 1 to 3 do
for j := 1 to n do
a [ i , j ] := random ( 195 — 141 ) + 140 ;

for i := 1 to 3 do //вывод
begin
for j := 1 to n do
write ( a [ i , j ] : 4 ) ;
write ( ‘ — класс №’ , i ) ;
writeln ;
end ;
for i := 1 to 17 do writeln ;
writeln ( ‘ Для выхода в меню нажмите Enter’ ) ;
readln ;
end ;

procedure vivod; var
i , j : integer ;
begin
clrscr;
if a [ 1 , 1 ] = 0 then writeln ( ‘Что ты как не человек. Данные введи сначало :)’ )
else begin
for i := 1 to 3 do //вывод
begin
for j := 1 to n do
write ( a [ i , j ] : 4 ) ;
write ( ‘ — класс №’ , i ) ;
writeln ;
end ;

max1 := a [ 1 , 1 ] ;
for i := 1 to 3 do
begin
max1 := 0 ;
n1 := 0 ;
n2 := 0 ;
for j := 1 to n do
if max1 < a [ i , j ] then begin
n2 := n1;
max2 := max1;
n1 := j;
max1 := a [ i , j ] ;
end
else if max2 < a [ i , j ] then begin
max2 := a [ i , j ] ;
n2 := j;
end ;
writeln ( ‘В ‘ , i , ‘ классе, ученики под номером ‘ , n1 : 2 , ‘ и ‘ , n2 : 2 , ‘ самые высокие’ ) ;
end ;
end ;
for i := 1 to 14 do writeln ;
writeln ( ‘ Для выхода в меню нажмите Enter’ ) ;
readln ;
end ;

begin
repeat
clrscr;
menu ( w ) ;
case upcase ( w ) of
‘Y’ :
begin
clrscr;
yslovie;
end ;
‘V’ :
begin
clrscr;
vvod;
end ;
‘R’ :
begin
clrscr;
vivod;
end ;
‘Q’ : closewindow;
end ;
until upcase ( w ) = ‘Q’ ;
end .

Переменная цикла for должна описываться в том же блоке что и цикл for

Ограничения использования оператора FOR

Ограничения в использовании оператора цикла с параметром естественным образом вытекают из описания этого оператора. Рассмотрим еще раз по пунктам описание оператора For и вытекающие из этого следствия.

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

(неправильный параметр цикла FOR).

2. Параметр должен быть описан в том же блоке, где находится сам оператор цикла.
Нарушение этого требования может привести к серьезным ошибкам при использовании подпрограмм т.к. использование глобальных переменных в п/п не рекомендуется!

V. Использование переменных, описанных снаружи блока с циклом FOR может быть оправдано в нескольких относительно редких случаях, где необходимо обработать часть элементов массива по отличающемуся алгоритму, но в общем это неправильный стиль программирования.

3. Выражения, определяющие начальное и конечное значения параметра ("Выражение 1" и "Выражение 2"), должны быть ординального типа, совместимого с типом самого параметра цикла.
Параметру цикла перед выполнением цикла присваивается значение выражения 1, в конце каждого цикла текущее значение параметра сравнивается со значением выражения 2, что и определяет требование совместимости типов параметра цикла и значений выражений 1 и 2. В случае нарушения данного требования при трансляции программы генерируется сообщение

4. Шаг изменения параметра цикла равен +1 или -1.
Если в программе шаг изменения параметра должен отличаться от значений +1 и -1, то нужно применить один из следующих способов:
— вместо оператора For использовать операторы While или Repeat;
— в цикле For задать соответствующий алгоритм изменения индексов.

Пример 1. Для массива просуммировать отдельно элементы с четными и нечетными индексами.

Основы программирования — первый семестр 08-09

Алгоритм — набор команд, определяющих порядок действий для решения поставленной задачи.

С алгоритмом всегда связан исполнитель алгоритма — устройство, имеющее систему команд.

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

Свойства алгоритма

  • Дискретность — алгоритм представляет собой последовательность элементарных шагов (команд исполнителя).
  • Детерминированность (определённость) — при одних и тех же входных данных получается один и тот же результат.
  • Завершаемость (конечность) — каждый алгоритм завершается за конечное число шагов при любом наборе исходных данных.
  • Результативность — после выполнения алгоритма известно, что считать результатом.
  • Массовость — применимость алгоритма ко множеству исходных данных.

Пример алгоритма.

Алгоритм 1. (словесное описание)

Алгоритм 2. (псевдокод)

Эквивалентными называются алгоритмы, имеющие одинаковые наборы исходных данных и выдающие одинаковый результат при одинаковых исходных данных. Алгоритмы 1 и 2 являются эквивалентными. Однако, они отличаются по скорости выполнения и по читаемости.

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

Способы описания алгоритмов

1. Словесный

2. Псевдокод

3. Блок-схемы

Пример. А.2., представленный блок-схемой.

Max flowchart.png

4. Язык программирования (ЯП)

Для языка программирования команды алгоритма называются операторами или инструкциями.

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

  • правильность работы
  • скорость выполнения
  • объем занимаемой памяти
  • сложность написания
  • возможность распараллеливания

Основные характеристики программы

Те же, что и у алгоритма, а также:

  • понятность при чтении
  • модифицируемость (легкость изменения кода)
  • масштабируемость (возможность изменения кода для решения родственной или более общей задачи)
  • безопасность

Если два алгоритма эквивалентны, то какой из них лучше? Тот же вопрос можно задать о программах, реализующих эти алгоритмы. Как правило, не существует однозначного ответа на этот вопрос. Лучшие по скорости алгоритмы как правило более сложны, труднее для понимания и могут требовать больше памяти. Часто для решения задачи не нужна самая быстрая программа — достаточно простой и понятной программы.

Обзор современных языков программирования

(самостоятельно на форуме)

Язык программирования PascalABC.NET

Правила записи программ на PascalABC.NET

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

Структура программы на языке Паскаль

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

Система программирования PascalABC.NET

Общая характеристика PascalABC.NET.

Отличия языка PascalABC.NET от обычного языка Паскаль.

Компиляторы и интерпретаторы

Схема компиляции в машинный код

Схема компиляции в промежуточный код. JIT-компиляция

Ошибки времени компиляции (синтаксические и семантические) и ошибки времени выполнения

Синтаксис — правила записи конструкций, семантика — смысл конструкций.

Синтаксис и семантика ЯП

// В программе 2013-14 гг. этот пункт будет сокращен и размыт по следующим темам когда будут вводиться основные операторы языка.

Определения

Синтаксис — формальные правила описания конструкций ЯП.

Семантика — описывает смысл конструкций ЯП, а также задает ряд ограничений.

Способы описания синтаксиса

  • БНФ (Бэкуса-Наура формы, 1960, Алгол-60).

называют терминалами (лексемами) — это «конечные символы», т.е. по умолчанию известные в ЯП.

  • РБНФ (Расширенные БНФ)
  • Синтаксические диаграммы (Вирт, Паскаль)

Грамматика языка — совокупность всех синтаксических правил данного ЯП, обычно заданных в форме БНФ.

Грамматика не учитывает все виды ошибок, в ЯП формулируются дополнительные семантические правила.

Замечание 1. Способы 1-3 эквивалентны.

Замечание 2. Синтаксис определяет лексемы языка.

Лексемы Паскаля

  1. спецсимволы::= += *
  2. ключевые слова (begin, end, if, for)
  3. идентификаторы (a, b1)
  4. константы (2, 'ABC', #5)
  5. комментарии (3 вида)

Переменные и их описание

Основные сведения

Переменная — это ячейка памяти компьютера, имеющая имя и тип.

Тип определяет размер переменной и множество принимаемых ею значений.

В языке Pascal любая переменная перед использованием должна быть описана.
Обычно переменные описываются в разделе описаний.

<xh4> Синтаксис в виде РБНФ </xh4>

Пример секции описания переменных.

Внутриблочные переменные

В PascalABC.NET возможно внутриблочное описание переменных:

В последнем случае происходит автоопределение типов.

Основные типы

  • Целые
  • Вещественные
  • Символьные
  • Строковые
  • Логический

Основные операторы

Оператор присваивания :=

Пример использования оператора присваивания.

<xh4> Семанитика </xh4> Вычисляется выражение в правой части, при этом, вместо имен переменных подставляются их значения.
Затем результат вычисления записывается в переменную в левой части.

Ограничение. Тип выражения должен быть совместим по присваиванию с переменной.
Например:

  • одинаковые типы совместимы.
  • выражение типа integer можно присвоить переменной типа real. Обратное неверно.

<xh4> Операторы присваивания += и *= </xh4> Пример.

<xh4> Примеры использования := </xh4> Пример 1. Перемена местами двух значений. Дано: x, y;

Это стандартное решение. В PascalABC.NET на основе этого алгоритма определена стандартная процедура Swap(x, y).

Однако, существуют и другие решения. Например:

Пример 2. Использование промежуточных переменных в вычислениях Дано: x: real; Найти: x 15 ;

Заметим, что в первом решении используется 6 операций умножения, в во 2м и 3м — 5. Возникает задача: найти x n за минимальное число умножений.
Об этом читай тему.

Оператор ввода

<xh4> Семантика </xh4> Происходит считывание данных с клавиатуры и запись их в переменные из <списка переменных>. Вводить данные нужно либо через пробел, либо по нажатию <Enter>, при этом программа не перейдет к выполнению следующего оператора, пока не будут считаны все данные.

Имеются также стандартные функции ReadInteger, ReadReal, ReadlnInteger, ReadlnReal:

С процедурой ввода связан ряд ошибок времени выполнения (например, если переменная используется в качестве делителя, и вводится 0, или, если должно быть получено целое число, а вводится 'ABC'). Эти ошибки нужно уметь обрабатывать.

Оператор try/except и обработка ошибок ввода

Операторы, которые могут получать ошибку, заключаются специальный охранный блок — оператор try.

<xh4> Семантика </xh4> Если внутри блока try происходит ошибка выполнения, то все последующие операторы в блоке игнорируются, и выполнение программы переходит к блоку except. По выходе из except программа продолжает работу.

Если ошибки не происходит, то выполняются все операторы в блоке try, блок except не выполняется, и программа продолжает работу.

Оператор вывода

<xh4> Семантика </xh4> Выражения в списке вычисляются, и их значения выводятся на экран.
В случае writeln после вывода осуществляется переход на новую строку.

<xh4> Форматы вывода </xh4> После каждого выражения в списке вывода можно использовать формат вывода в виде :a, где a — выражение целого типа.
После вещественного типа — :a:b (a задает ширину поля вывода (выравнивание по правому краю), b — количество знаков в дробной части).

<xh4> Вывод с помощью write[ln]Format </xh4>

Пример вывода с использованием форматной строки.

В форматной строке тоже можно использовать формат вывода.
: 10 — это ширина поля вывода
: 3 — это количество знаков в дробной части для вещественного числа (показывает это спецификатор f).
— экспоненциальный формат.

Арифметические выражения

Основные сведения

Каждое выражение имеет тип. Выражение называется арифметическим, если его тип — числовой.
Выражение строится посредством операций (унарных или бинарных) и операндов.

В арифметических выражениях если a и b — одного типа, то и a op b принадлежит к тому же типу. Исключением является операция "/":

a / b — вещественное.

Если a и b принадлежат к различным типам, то выражение принадлежит к "старшему" типу.
Например:

Стандартные функции

В арифметические выражения могут входить стандартные функции:

<xh4> Порядок выполнения операций в арифметических выражениях </xh4>

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

<xh4> Операции div и mod для целых </xh4> x div y = x / y, округленное до ближайшего целого по направлению к нулю. Это результат от целочисленного деления.
x mod y = x - (x div y) * y. Это остаток от целочисленного деления.

Пример использования
Целочисленные операции часто применяются для определения четности числа:

Логические выражения

<xh4> Основные сведения </xh4> Выражение назывется логическим, если оно имеет тип boolean.
Пример.

Это простые логические выражения. Однако, с помщью логических операций можно составлять сложные.

<xh4> Таблицы истинности логических операций </xh4>

<xh4> Сокращение вычислений логических выражений </xh4> Большинство современных компиляторов, в т.ч. PascalABC.NET производит сокращенное вычисление логических выражений.
Это означает, что в выражении

если a — ложно, то b не вычисляется, а в

если a — истинно, b не вычисляется.

Это очень полезно при вычислении таких выражений, как, например,

Логически здесь все верно, однако, если бы не использовалось сокращенное вычисление, в случае равенства нулю y'а возникала бы ошибка деления на ноль.

<xh4> Логические переменные </xh4> Можно описывать логические переменные (тип boolean). Им можно присваивать логические выражения.
Эти переменные принимают одно из двух возможных значений:

true (истина) false (ложь)

Пример использования логических переменных
Дано: прямоугольник со сторонами, параллельными осям координат, задан координатами абсцисс вертикальных сторон (x1, x2) и ординатами горизонтальных (y1, y2); точка M( x, y );
Найти: находится ли точка внутри прямоугольника, снаружи, или лежит на границе;

Побитовые операции

<xh4> Побитовые операции and, or, xor, not </xh4> Замечание. Работают только с целыми.

Соответствующая операция применяется к каждому биту двоичного представления числа.
Пример.

<xh4> Операции shl и shr </xh4> Побитовый сдвиг влево и сдвиг вправо соответственно.

Сдвигает двоичное представление x на n позиций влево.

Сдвигает двоичное представление x на n позиций вправо.

Таблица приоритетов операций языка Object Pascal

  1. унарные + - not
  2. имеющие смысл умножения* / div mod and shl shr
  3. имеющие смысл сложения+ - or xor
  4. операции отношения<> <= >= < > in

Условный оператор

If.jpg

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

Примеры использования для решения задач

Пример 1. Нахождение минимума
Дано: x, y
Найти: min

Пример 2. Упорядочение a, b по возрастанию.
Ясно, что если a > b, — нужно поменять их местами.
Но тут одним оператором не обойтись. Для этого можно использовать составной оператор — один или больше операторов, заключенных в операторные скобки begin - end;:

Пример 3. Вычисление функции по взаимоисключающим веткам
<math>y = \begin x, & x < 2 \\ x^2, & 2 < x < 3 \\ 1-x, & x \ge\; 3 \end</math>

Замечание. Если по ветви else располагается другой оператор if, то говорят, что возникает цепочка вложенных операторов if.

Координаты средней точки

Пример 4. Даны координаты трех точек на прямой a, b, c (a, b, c попарно не равны). Найти m - координаты средней точки

Достаточно рассмотреть случай, когда координаты точек равны 1,2 и 3

Рассмотрим все возможные ситуации распределения этих значений между a,b,c:

При a<b возможны три варианта, в двух из которых a<c. При a>b возможны три варианта, в двух из которых a>c.

Решение представляется вложенными операторами if с уровнем вложенности 3.

По количеству операций (3 сравнения, одно присваивание) это - самое лучшее решение

То же решение, записанное с помощью функции min:

Данное решение менее эффективно по числу сравнений и присваиваний (посчитайте самостоятельно), но по понятности может восприниматься лучше предыдущего.

Самостоятельные задания
  • Даны координаты вершин треугольника и точка M, не лежащая на границе треугольника. Принадлежит ли M треугольнику.
  • Является ли 4-угольник ABCD корректно заданным.

Оператор case выбора варианта

<xh4> Семантика </xh4> Вначале вычисляется выражение-<переключатель>, после чего его значение ищется в одном из <списков выбора>.
Если значение попадает в какой-то <список выбора>, то выполняется соответствующий ему оператор, иначе, если есть ветвь else, то выполняется оператор по ветке else.

  • выражение-переключатель должно иметь так называемый порядковый тип:

НО НЕ строковый или вещественный.

  • значения в <списках выбора> не должны пересекаться.

<xh4> Примеры использования оператора выбора </xh4> Пример 1. День недели

Пример 2. Цифра или буква

Циклы

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

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

Цикл while м.png

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

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

Цикл repeat м.png

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

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

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

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

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

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

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

repeat

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • <math>\sum_^n \frac</math>

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

  • <math>\sum_^\infty (-1)^i\frac</math>

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

задается некоторый малый eps и сумма <math>\sum_^\infty x_i</math> вычисляется, пока <math>|x_i| >\ eps</math>

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

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

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

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

Break м.png

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

Continue м.png

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Подпрограммы

Вспомогательные алгоритмы

Вспомогательный алгоритм — это алгоритм, который используется для реализации другого алгоритма.

Вспомогательные алгоритмы имеют:

  • имя
  • список параметров

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

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

  • процедуры
  • функции

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

Процедуры

Пример.
Даны 3 пары положительных чисел.
Найти их среднее арифметическое и среднее геометрическое.

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

называется заголовком процедуры.

Теперь можем многократно использовать описанную процедуру в основной программе:

называется оператором вызова процедуры.

<xh4> Синтаксис описания процедуры </xh4>

Замечание. Pascal допускает внутренне описание подпрограмм (вложенность подпрограмм)

<xh4> Синтаксис вызова процедуры </xh4>

<xh4> Семантика вызова процедуры </xh4>

  • имя должно быть именем процедуры, описанной ранее (или именем текущей процедуры)
  • количество фактических параметров должно совпадать с количеством формальных параметров
  • фактические параметры-переменные должны быть именами переменных, типы которых совпадают с типами соответствующих формальных параметров
  • фактические параметры-значения должны быть выражениями, типы которых совместимы по присваиванию с типами соответствующих формальных параметров

Входно-выходные параметры

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

Пример 1. Увеличение значения переменной на заданное число.

Пример 2. Перемена местами значений двух переменных.

Функции

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

Пример. Функция sgn(x) — знак числа

называется заголовком функции, а integer — это тип возвращаемого значения.

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

Пример неправильной(. ) функции.

Выведется непредсказуемое значение, находящееся в этот момент в памяти, т.к. по ветке

переменная Result не инициализируется.

Пример. Считывание значения с клавиатуры.

Сравнение использования процедуры и функции

Пример. Сумма первых N натуральных чисел.

<xh4> Синтаксис описания функции </xh4>

<xh4> Синтаксис вызова функции </xh4>

<xh4> Семантика </xh4> Замечание. Формальные параметры функции не рекомендуется делать параметрами-переменными.

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

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

Оператор exit

Оператор exit — оператор досрочного завершения подпрограммы.

Пример. Поиск числа k среди n введенных.

Замечание. Оператор exit, в отличие от break, позволяет завершить подпрограмму и выйти сразу из нескольких вложенных циклов. При вызове его в теле основной программы программа завершается.

Локальные и глобальные переменные

Замечание. Локальная переменная, описанная в процедуре или функции, может иметь то же имя, что и глобальная переменная.
Если глобальная описана ранее, то её имя внутри процедуры становится недоступным.

Глобальные переменные по умолчанию инициализируются 0, а локальные по умолчанию не инициализируются.
Локальная переменная Result в функции по умолчанию также не инициализируется.

В данном примере:

writeln(n) выведет непредсказуемый результат; writeln(m) выведет 0;

Пространство имен

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

  • глобальное пространство имен
  • пространство имен каждой подпрограммы

Формальные параметры подпрограммы являются локальными по отношению к этой подпрограмме.

Примеры допустимых и недопустимых описаний:

Область видимости и время жизни объекта

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

  • для глобальных переменных это время работы программы
  • для локальных — с момента описания до конца работы блока, где они описаны

Область видимости переменной — область в программе, в которой можно обратиться к переменной по имени.

Побочный эффект

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

Замечание. Если подпрограмма желает изменить глобальную переменную, то в большинстве случаев эту переменную следует передать как параметр.

Принцип локальности

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

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

Пример. Вычислить произведениe целых чисел от a до b.
Решение 1.

  • опишем i в заголовке цикла
  • инициализируем p непосредственно перед циклом, вычисляющим произведение

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

Подпрограммы (продолжение)

Внутренний механизм передачи параметра-переменной

b, i: фактические параметры при вызове MyInc a, n: формальные параметры (a — параметр-переменная; n — параметр-значение)

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

Ссылкой обычно называют другое имя некоторого объекта.

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

При передаче параметра по ссылке в подпрограмму передается не сама переменная, а её адрес:

Замечание 1. В 32-битных ОС размер адреса — 4 байта, это позволяет адресовать примерно 4 Гб операционной памяти.

Замечание 2. Размер адреса не зависит от размера переменной, поэтому при передаче параметров большого размера их предпочитают передавать по ссылке.

Перегрузка имен подпрограмм

Предположим, у нас описана процедура:

Возможно ли описать процедуру с таким же именем, параметры которой были бы вещественными? Да, возможно:

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

Замечание 1. Тип возвращаемого значения функции не участвует в операции разрешения перегрузки.

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

Замечание 2. Разрешить перегрузку можно не всегда.
Пример.

Замечание 3. В процессе разрешения перегрузки происходит неявное преобразование типов.

Параметры по умолчанию

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

Замечание. Параметры по умолчанию корректно сочетаются с перегрузкой.

Предварительное объявление подпрограмм

Такое описание вызовет ошибку компиляции, т.к. в p используется еще не известная процедура. Чтобы таких ошибок не возникало, нужно использовать предварительное объявление подпрограммы:

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

Процедурные переменные

Процедурный тип и переменные

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

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

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

Замечание. До первого присваивания процедурная переменная имеет тип nil. В этот момент вызывать процедуру через переменную нельзя — будет ошибка выполнения.

Функции обратного вызова (callback)

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

Такой вызов называется обратным вызовом (callback).
Примечание. Прямой вызов — это передача процедуры в качестве параметра.

Пример. Вычисление определённого интеграла методом прямоугольников.

Вызов нескольких процедур через процедурную переменную

Замечание 1. Такое возможно только в .NET;

Замечание 2. Подобный механизм не имеет смысла использовать для функций;

Методы разработки подпрограмм

Пример. Вывести таблицу простых чисел <= 1000.

Метод разработки сверху вниз

После этого реализуем функцию IsPrime;

Этот метод используется, когда:

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

Замечание. В коде главной программы имеются вызовы других подпрограмм, которые реализуются позже (возможно, другими разработчиками);
На период, пока они не написаны, вместо них могут использоваться «заглушки» (подпрограммы с тривиальными телами).

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

Метод разработки снизу вверх

Метод используется, когда:

  • на момент начала решения задача нечетко поставлена
  • когда задача — большая
  • нет ясно выраженного главного алгоритма, а есть множество взаимосвязанных задач (примером может служить программа, реализующая деятельность университета)

Замечание 1. Написание самых «нижних» подпрограмм позволяет лучше войти в предметную область;

Замечание 2. С какого-то момента разработка хотя бы упрощенного главного алгоритма становится необходимой;

Оператор goto

Синтаксис

Метка представляет собой идентификатор или целое положительное число.
Метка должна описываться в разделе описаний меток в виде:

Семантические ограничения

  • метка должна использоваться в той же подпрограмме, в которой описана;
  • нельзя, используя goto, перейти внутрь какой-нибудь конструкции (цикла или условного оператора);

<xh4> Пример плохого кода </xh4>

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

Пример. Найти a, b, c;
a 2 + b 2 = c 2 , 50 <= a,b,c <= 100

Вызов подпрограммы на этапе выполнения

Введение

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

Устройство ЗА подпрограммы

ЗА.png

Штриховкой отмечены поля, заполняемые до запуска п/п.

Алгоритм входа в подпрограмму

  1. Увеличить top стека на размер ЗА п/п, вычесленного на этапе компиляции: top += rЗА
  2. Вычислить адрес возврата (АВ) и адрес конца ЗА вызывающей п/п
  3. Вычислить значения всех фактических параметров и подставить их на место формальных.
  4. Перейти в коде программы на начало выполнения п/п

Алгоритм выхода из подпрограммы

  1. Уменьшитьtop стека, переместив его на адрес конца ЗА вызывающей подпрограммы
  2. В коде программы перейти по АВ

Пример

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

При перемещении top на программном стеке накапливается мусор, потом в этот мусор опять записывается ЗА.
Коды top и current хранятся в специальных регистрах.

Вывод 1. Если подпрограмма — маленькая, то накладные расходы на её вызов могут существенно превысить время работы самой подпрограммы.

Вывод 2. Если локальные переменные или формальные параметры, передаваемые по значению имеют большой размер, то ЗА соответствующей подпрограммы будет большой. В результате при нескольких вложенных вызовах таких подпрограмм может произойти переполнение программного стека (Stack overflow), т.к. программный стек не увеличивается в размерах, а память под него выделяется один раз.

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

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

Дополнительные сведения о подпрограммах

Переменное число параметров подпрограмм

Шаблоны подпрограмм

Модули

Введение

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

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

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

Программа, подключающая модуль MyLib

Модуль в языке Object Pascal состоит из двух разделов:

  • раздел интерфейса
  • раздел реализации

В разделе интерфейса описываются все

  • переменные
  • константы
  • типы
  • заголовки подпрограмм,

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

В разделе реализации содержится

  • реализация подпрограмм, заголовки которых приведены в разделе интерфейса
  • описание вспомогательных констант, переменных, типов и подпрограмм,

которые нужны для реализации подпрограмм из раздела интерфейса и не видны из других модулей.

Данный принцип получил название принципа сокрытия информации.
Его преимущества:

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

Синтаксис модуля

Семантические ограничения

  • Модули, перечисленные в секции uses в разделах интерфейса и реализации не должны пересекаться
  • циклическая зависимость между модулями в разделе интерфейса запрещена:
  • интерфейс
  • реализация

Разделы инициализации и финализации модуля

Операторы в разделе initialization модуля выполняются раньше тела основной программы,
а операторы в разделе finalization выполняются после основной программы.

Т.е. последовательность выполнения будет такой:

Примечание. В разделе инициализации обычно инициализируются глобальные переменные из раздела интерфейса.

Схема компиляции программы с модулями

1. Компилируется файл основной программы.
2. Если в нем встречена секция uses, то компилируются модули из этой секции слева направо.
3. Каждый модуль компилируется так же, как и основная программа по пунктам 1-2:

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

4. По окончании компиляции модуля его откомпилированный вариант (.pcu в PascalABC.NET) записывается на диск.
5. После записи откомпилированного модуля на диск компилятор возвращается к основному модулю (вызывающему) или программе, и докомпилирует его до конца. Основная программа после компиляции хранится в оперативной памяти.
6. Первый этап компиляции закончен. Начинается заключительный этап компиляции — линковка (компоновка). Специальная программа — линковщик — собирает из откомпилированных модулей единый исполняемый файл (.exe в Windows).

Замечание 1. Ошибки могут происходить как на этапе компиляции, так и на этапе, собственно, линковки.
Замечание 2. Наличие откомпилированного файла модуля существенно ускоряет процесс компиляции (сводя его к процессу линковки).
Замечание 3. Если есть откомпилированные файлы модулей, то исходные тексты модулей можно удалить. При этом компилятор проанализирует, что данный модуль откомпилирован, и продолжит компиляцию дальше.
Замечание 4. Если файл модуля .pas создан после откомпилированного файла модуля (.pcu), то произойдет его перекомпиляция.
Замечание 5. При работе в интегрированной среде компилятор в первую очередь берет тексты модулей из открытых файлов и только затем смотрит файлы на диске.

Примечание 1. Файлы модулей могут храниться в другом каталоге относительно файла исходной программы. Тогда надо вместе с именем модуля указывать, в каком каталоге он хранится (тогда имя модуля и имя файла модуля могут не совпадать):

Примечание 2. Откомпилированные файлы модулей по умолчанию создаются:

  • в каталоге основной программы
  • если установлен специальный путь в среде программирования для выходных файлов, то по этому пути

Кроме этого, стандартные откомпилированные модули хранятся в специальной папке, например, в PascalABC.NET — в папке \LIB. Если модуль претендует на звание стандартного, его можно туда поместить.

Упрощенная структура модуля

В PascalABC.NET можно использовать упрощенную структуру модуля:

В <разделе описаний> описываются типы, константы, переменные и подпрограммы.
Раздел begin + <операторы> соответствует разделу инициализации.

Алгоритм поиска имен в модулях

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

Правило 1. Имя вначале ищется в текущем модуле. Если не найдено, то в подключенных модулях секции uses справа налево.
Правило 2. Если нужно явно указать переменную из какого-то модуля, то перед ней ставится <имя модуля>.

Стандартный системный модуль PABCSystem

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

  • стандартные константы
  • типы
  • подпрограммы

В Delphi — это System,
в PascalABC.NET — PABCSystem.

Библиотеки

<xh4> Сходства с модулем </xh4> Библиотеки, как и модули:

  • содержат группу взаимосвязанных подпрограмм
  • находятся в откомпилированном файле
  • предназначены для обращения к ним из различных программ

В Windows получили распространение библиотеки .dll (dynamically linked libraries). Они находятся либо в текущем каталоге приложения (локальные), либо в системном каталоге (глобальные библиотеки).

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

<xh4> Отличия библиотек от модулей </xh4>

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

Линковка модуля и библиотеки

<xh4> Библиотеки в PascalABC.NET </xh4> Синтаксис

Замечание. В библиотеках отсутствуют секции инициализации и финализации.

Для подключения библиотеки используются конструкции:

Примечание. reference — директива компилятора. Указывает компилятору, что программа использует внешние библиотеки, расположенные в файле MyLib.dll.

Документирующие комментарии ///

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

<xh4> Документирующие комментарии в PascalABC.NET </xh4> Отображаются в виде всплывающего окна при наведении указателя на имя подпрограммы.

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

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

Перечислимый тип

Определение и примеры

Переменные перечислимого типа хранятся в памяти, как целые числа. Первому значению соответствует 0, второму — 1, и т.д.

Замечание. Все имена из определения перечислимого типа помещаются в текущее пространство имен.

Переменная перечислимого типа может служить параметром цикла for, а также переключателем в операторе case.

Стандартные подпрограммы для работы с перечислимым типом

Замечание. Тип boolean = (False, True)

Если не инициализировать глобальную переменную перечислимого типа, то по умолчанию она получает значение первой константы типа.

Диапазонный тип

Диапазонный тип строится на базе

  • целого
  • символьного
  • или перечислимого типов

Массивы

Введение

Как и диапазонный тип, индексы могут иметь типы:

  • целый
  • символьный
  • перечислимый

Кроме того, в качестве индекса может выступать порядковый тип, например:

Обращение к элементам массивов

Чтобы обратиться к элементу массива, нужно использовать конструкцию

В некоторых компиляторах можно специальными директивами отключить проверку выхода за границы диапазона, это увеличивает скорость выполнения.
В PascalABC.NET проверка выполняется всегда. А вот в Delphi и Free Pascal существует соответствующая директива

Динамические массивы

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

Динамические массивы индексируются с нуля, тип индекса - только целое.

Выделение памяти

Для выделения памяти динамическому массиву имеется два варианта. Объектный стиль:

Здесь n может быть не только константой, но и переменной.

В обоих случаях элементы массивов заполняются нулями.

До выделения памяти в переменной-динамическом массиве хранится специальное значение nil. Присваивание nil переменной-массиву приводит к освобождению памяти, им занимаемой:

При попытке использования неинициализированного динамического массива выдается исключение времени выполнения "System.NullReferenceException: Ссылка на объект не указывает на экземпляр объекта."

Перевыделение памяти

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

При этом старое содержимое массива будет сохранено.

Длина массива

Чтобы узнать количество элементов в динамическом массиве, следует воспользоваться функцией Length:

или свойством Length:

Таким образом, элементы динамического массива:

Циклы по массиву

или с помощью цикла foreach (для каждого)

В цикле foreach доступ к элементам массива осуществляется только на чтение.

Инициализация массивов

Элементы массива можно инициализировать при описании:

При этом под массив автоматически выделится память: в данном случае под 3 элемента.

Хранение массивов в памяти

Присваивание и сравнение массивов

Именная и структурная эквивалентность типов

Передача массивов в качестве параметров подпрограмм

При передаче статического массива должна соблюдаться именная эквивалентность

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

Динамический массив можно передавать в виде array of integer, т.к. для него определена структурная эквивалентность типов.

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

Массив как возвращаемое значение функции

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

Переменное число параметров подпрограмм

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

Обобщенные подпрограммы

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

Выход - обобщенные подпрограммы.

В момент вызова п/п происходит:

  • выведение типов шаблона по фактическим параметрам
  • инстанцирование - подстановка конкретных типов шаблонов и генерация кода подпрограммы с этими конкретными типами.

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

Массивы (продолжение)

Задачи на одномерные массивы

  • инвертирование массива (шаблон)
  • поиск элемента в массиве - найти и вернуть индекс (шаблон)

можно с for и break,

можно и другим способом - с while

  • поиск с барьером (шаблон). Его преимущества
  • минимальный элемент массива и его индекс
  • слияние двух упорядоченных массивов в один упорядоченный (барьер)
  • сдвиг элементов массива влево (шаблон)

знакомство со значением default(T), Т - тип

Задачи на одномерные массивы

pas-файл с задачами

используется тип IArr = array [1..size] of integer

  • сдвиг элементов массива вправо (ShiftRight)

[ два варианта определения граничных значений цикла (от n-1 до 1; от n до 2) ]

  • циклический сдвиг элементов массива вправо (CycleShiftRight)
  • удаление элемента по заданному индексу (Delete)
  • вставка элемента по заданному индексу (Insert)
Задачи с процедурными переменными в качестве параметров

Определяется тип IUnPred = function (x: integer): boolean

  • поиск элемента по заданному условию (Find)
  • количество элементов, удовлетворяющих условию (Count)
  • условный минимум (MinElem)
  • удаление всех элементов, удовлетворяющих условию (DeleteAll)

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

Сортировки массивов

Сортировка выбором
Пузырьковая сортировка
Сортировка вставками
  • Выбором (нахождение минимального элемента в неупорядоченной части массива и перемещение его на первую после уже отсортированного участка позицию)
  • Пузырьковая

Это самый компактный алгоритм сортировки. Его можно оптимизировать, проверяя случай "холостого" прохода по элементам массива. Т.е. если за проход ни один элемент не изменил позицию, значит массив уже отсортирован и проверять дальше нет смысла.

  • Вставками (вставка элемента из еще не упорядоченного участка массива в "нужную" позицию отсортированного, для чего сдвиг части элементов вправо и вставка нового в освободившуюся позицию)

Замечание. Рассмотренные виды сортировки не являются самыми эффективными.

Асимптотическая оценка количества шагов алгоритма

Определение. Число шагов алгоритма асимптотически равно Θ(f(n)) если, существуют такие N, с1, с2>0 (c1<c2), что для любых n ≥ N выполняется:

Замечание 1. Для рассмотренных алгоритмов сортировки асимптотическая сложность = Θ(n 2 ).

Замечание 2. Существуют алгоритмы сортировки с асимптотической сложностью = Θ(n*logn) (они будут рассмотрены в следующем семестре).

Бинарный поиск в отсортированном массиве

Задачи на двумерные массивы (матрицы)

  • Вывод матрицы
    • внешний цикл по строкам
    • если внешним сделать цикл по столбцам будет выведена транспонированная матрица
    • Сумма элементов в j-том столбце
    • Сумма элементов в каждом столбце
      • использование функции для нахождения суммы в j-ом столбце
      • в отличие от предыдущей задачи, для реализации не создается дополнительная п/п.

      Замечание. Решать такие задачи можно и реализуя алгоритм полностью, и создавая для этого дополнительные п/п. Если задача несложная, то вполне можно пользоваться первым способом, однако если решение не очевидно, лучше выносить часть алгоритма в п/п, иначе код будет очень трудно читать.

      • Квадратные матрицы и элементы выше-ниже главной (побочной) диагонали.
      • Поиск элемента в матрице

      если для поиска используется функция, то при нахождении элемента выходить из циклов с помощью exit,

      иначе удобно использовать goto КОНЕЦ_ВНЕШНЕГО_ЦИКЛА К основной странице курса

      Записи

      Введение

      Инициализация записей при описании (на примере Student)

      Доступ к полям записей. Точечная нотация.

      Замечание. Для записей имеет место именная эквивалентность типов.

      Передача записей в подпрограммы. Записи как возвращаемые значения функции

      Передача записей в п/п (Print(s)). Запись как возвращаемое значение функции (s := ReadStudent;).

      Передавать записи по значению неэффективно, т.к. копируются все поля. Поэтому следуют передавать их по ссылке (с ключевым словом const - если значения полей не изменяются, и var - если внутри п/п их требуется изменить.

      Оператор удобен, когда нужно выполнить достаточное количество операций с одной и той же переменной (имя этой переменной и точка добавляются неявно перед всеми полями)

      Методы в записях

      На примере Student.Print.

      Запись как пространство имен

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

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

      Т.о. возникает понятие инкапсуляции:

      Инкапсуляция — хранение в записи одновременно данных и методов (запись представляет собой «капсулу»).
      Инкапсуляция тесно связана с защитой данных: лишь некоторые члены в этой «капсуле» являются открытыми.

      Создается окружение при описании переменной типа запись.

      • Сравнение s.Print и Print(s)

      s.Print - объектно-ориентированный подход, доминирует объект, который сам выполняет над собой действие.

      Print(s) - процедурно-ориентированный подход, главным является действие, выполняющееся над переменной.

      • Метод Init - инициализатор полей записи.

      Создание простейших графических объектов

      Для каждого типа определяются методы Print, Draw, MoveOn

      Записи как средство упаковки параметров

      Пример. Используем определенные типы записей для создания перегруженных версий процедур Rectangle и Line:

      Переменная типа запись как объект

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

      Поля записи как состояние объекта.

      Методы записи как действия, воздействующие на состояние объекта.

      Методы делятся на две категории

      • меняющие состояние объекта (MoveOn для RPoint)
      • осуществляющие доступ к состоянию объекта на чтение (Draw для RPoint)

      Сортировка массива записей.

      Индексная сортировка

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

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

      Дан массив целых (с реальными индексами):

      А так выглядит отсортированный массив по виртуальным индексам:

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

      Вначале удобно положить элементы index соответствующими тождественной подстановке (т.е. a[i] = i).

      Статические методы записей

      Множества

      Описание множеств. Множества-константы. Пустое множество.

      Операции над множествами:

      Цикл foreach по множеству.

      Пример использования множеств: решето Эратосфена. Алгоритм.

      Алгоритм Эратосфена

      Код алгоритма Эратосфена

      Символы

      Коды символов. Однобайтовые и двухбайтовые кодировки. ASCII - стандарт на символы с кодами 0..127. Unicode. Однобайтовые кодировки: Windows, DOS (CP866), Koi8

      Стандартные подпрограммы работы с символами

      Для символов с кодами 0..127

      char - тип, содержащий ряд статических методов:

      Строки

      Отводится память (до 2 Гб), равная длине строки, плюс некоторая дополнительная информация

      Строки - массивы символов, индексируемые с 1: s[i] - i - тый символ строки. var s := 'IT'; // s[1]='I', s[2]='T'

      Операции со строками:

      Основные подпрограммы работы со строками

      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, в которой удалены все удаляет все начальные и заключительные пробелы

      Преобразование строка ↔ число

      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 к вещественному; может генерировать исключение

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *