«Т. В. Диканев, С. Б. Вениг, И. В. Сысоев ПРИНЦИПЫ И АЛГОРИТМЫ ПРИКЛАДНОГО ПРОГРАММИРОВАНИЯ Учебное пособие для студентов, обучающихся на факультете нано- и биомедицинских технологий Саратов Издательство Саратовского ...»

procedure Hello10;

var {открытие раздела описаний локальных переменных} i: integer; {описание локальной переменной i} begin for i:=1 to 10 do write('Hello_');

end;

begin for i:=1 to 5 do Hello10; {пять раз вызываем процедуру} end.

Программа выведет 5 строк по 10 слов Hello.

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

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

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

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

Пример 3. Глобальная и локальная переменные.

var x: real; {описание глобальной переменной x} procedure P2;

var x: real; {описание локальной переменной x} begin x:=10; {присваивание значения локальной переменной} writeln(x); {вывод значения локальной переменной} end;

begin {присваивание значения глобальной переменx:=5;

P2; {вызов процедуры} writeln(x); {вывод значения глобальной переменной} end.

Несмотря на то что при вызове процедуры P2 выполнится инструкция x:=10, глобальная переменная x останется равной 5.

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

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

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

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

var x, y: integer;

procedure Mult(a, b: integer); {заголовок процедуры с var c: integer;

begin c:=a*b; {значения параметров используются для вычисления c} writeln(c);

end;

begin readln(x, y);

Mult(x, y); {вызов процедуры с указанием значений end.

Программа запросит у пользователя значения переменных x и y, затем вызовет процедуру Mult, указав при этом, что значения параметров a и b при данном вызове процедуры должны быть равны значениям переменных x и y. Процедура выведет произведение x*y.

Переменные a и b в заголовке процедуры называются формальными параметрами. То, что подставляется при вызове процедуры (в примере это переменные x и y), называется фактическими параметрами.

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

В качестве фактических параметров в данном примере могут выступать произвольные выражения. Например, возможен такой вызов процедуры: Mult(x/y+1, 2). Значения этих выражений присвоятся формальным параметрам, и процедура напечатает значение выражения (x/y+1)*2.

11.4. Параметры-значения и параметры-переменные Существует два способа описывать параметры: как параметрызначения и как параметры-переменные. В предыдущем параграфе использовались параметры-значения. Параметр-значение является просто локальной переменной, начальное значение которой задается при вызове процедуры.

Пример 5. Исползование глобальных переменных в процедуре.

var a, b: integer; {глобальные переменные} procedure P3(a, b: integer); {внутри процедуры символами a и b обозначаются формальные параметры. Действия с ними никак не повлияют begin a:=a+1;

b:=b+1;

writeln(a+b);

end;

begin a:=1;

b:=1;

P3(a, b); {вызов процедуры, где в качестве фактических параметров использованы значения writeln(a, b);

end.

Если в заголовке процедуры перед какими-либо из параметров поставить слово var, то это будут параметры-переменные. Например:

procedure P3(var a, b: integer; c: real);

Здесь a и b – параметры-переменные, c – параметр-значение. При вызове процедуры фактический параметр, задающий значения этих формальных параметров, не может быть выражением или константой, а должен быть обязательно переменной. Иными словами, недопустимы следующие вызовы:

P3(x+y, y+1, z+2);

P3(x, 2, z);

где x, y, z – глобальные переменные. Такие инструкции вызовут синтаксическую ошибку. В то же время синтаксически правильными будут вызовы P3(x, y, z+1);

P3(x, y, 2);

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

При использовании параметров-переменных память под них не выделяется. Вместо этого на время работы процедуры они становятся синонимами тех переменных, которые указываются в качестве фактических параметров. Так, при вызове P3(x, y, 2) формальные параметры a и b будут работать с теми же ячейками памяти, что и переменные x, y. Соответственно если формальному параметру в процедуре присваивается новое значение, то и значение фактического параметра изменится. Воспроизведем пример, заменив тип параметров (добавим var перед их описанием):

procedure P3(var a, b: integer); {внутри символами a и b обозначаются формальные параметры. Теперь это параметры-переменные, и действия с begin writeln(a+b);

end;

begin P3(a, b);

writeln(a, b);

end.

Если без слова var программа выводила числа 4, 1, 1, то после его добавления получится 4, 2, 2.

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

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

Большие программы строятся методом последовательных уточнений.

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

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

Пример 6. Каркас программы сортировки массивов.

program ArraySort;

const type TArray = array [0..n-1] of real;

var a: TArray;

procedure InputArray(var x: TArray); {процедура procedure PrintArray(x: TArray); {процедура для вывода массива} begin InputArray(a);

SortArray(a);

PrintArray(a);

end.

Какие именно инструкции будут выполняться процедурами InputArray, PrintArray и SortArray, пока не определено. Это следующий этап написания программы. Задачу сортировки, в свою очередь, можно разбить на более простые подзадачи: многократное повторение поиска минимального элемента и постановку его на нужное место (см. параграф 10.5). Эти задачи также можно оформить в виде процедур, создав каркас процедуры SortArray.

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

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

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

11.6. Передача массивов в качестве параметров Как вы знаете, с отдельными элементами массивов можно работать так же, как с обычными (скалярными) переменными. Соответственно появляется возможность использовать их в качестве фактических параметров. Однако может потребоваться передать процедуре не отдельные элементы, а весь массив целиком. При этом недопустим такой, например, способ описания параметра:

procedure P(a: array [1..10] of integer);{так нельзя} Тип параметра должен быть или скалярным, или заранее определенным в разделе type. Иными словами, правильным будет такое описание:

type TArray = array [1..10] of integer;

var x: TArray;

procedure P(a: TArray);

Такую процедуру P можно вызывать, указав в качестве фактического параметра, например, глобальную переменную x.

Пример 7. Программа, вычисляющая сумму элементов массива.

const type TArray = array [0..n-1] of integer;

var x: TArray;

i, sum: integer;

procedure Summa(a: TArray; var s:integer);

var i: integer;

begin s:=0; {операции с параметром-переменной s отразятся на фактическом параметре – глобальной for i:=0 to n-1 do s:=s+a[i];

end;

begin for i:=0 to n-1 do readln(x[i]);

Summa(x, sum); {к моменту вызова процедуры переменной sum ничего еще не присвоили. Это не страшно, так как начальное значение параметра s для работы процедуры несущественно} writeln(sum);

end.

При вызове процедуры содержимое массива x будет скопировано в массив a. Глобальная переменная sum на время работы процедуры приобретет синоним s. Другими словами, присваивая что-то переменной s, мы тем самым изменяем и переменную sum. В итоге программа выведет сумму элементов введенного пользователем массива.

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

Другими словами, при большом размере массива правильнее будет заголовок procedure Summa(var a: TMassive; var s: integer);

11.7. Функции Желаемым результатом работы подпрограммы может быть всего одно значение. Так, например, было в примере с расчетом суммы элементов массива. В этом случае вместо процедур разумно использовать другой вид подпрограмм, а именно функции.

Пример 8. Функция, вычисляющая сумму своих аргументов.

function Sum(a, b: real): real;

begin end;

Мы видим, что структура функции почти повторяет структуру процедуры. Отличия:

1) вместо слова procedure пишется слово function;

2) после списка параметров через двоеточие указывается тип значения, которое получится в результате работы функции;

3) в теле функции должно присутствовать присваивание значения идентификатору функции (Sum:=a+b). Это и будет значением функции.

Вызов функции из программы происходит также, как и в случае со стандартными функциями, таким как sqr, sqrt, random, sin, round и т.д. Иными словами, их значения можно присваивать переменным или использовать их в выражениях. Например, в программе могли бы стоять вызовы:

x := sum(2, 2);

z := sum(x, y);

x := 2*sum(x, y)+1;

z := sqrt(sum(sqr(x), sqr(y)));

z := sum(sum(x, y), z);

и т.п.

С точки зрения синтаксиса допустим вызов функции без присваивания ее значения какой-нибудь переменной. Например, в программе могла бы быть строчка sum(2, 2);

и все. Созданное функцией значение в этом случае никуда не запишется.

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

Правила передачи параметров те же самые, что и для процедур. Так же можно описывать локальные переменные.

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

Пример 9. Функция, вычисляющая сумму элементов массива.

const type TArray = array [0..n-1] of real;

function ArraySum(var a: TArray): real;

var s: real;

i: integer;

begin s:=0;

for i:=0 to n-1 do s:=s+a[i];

ArraySum:=s;

end;

11.8. Опережающее описание В теле каждой процедуры или функции может содержаться вызов других процедур или функций при условии, что они описаны раньше, чем процедура или функция, их вызывающая. Однако есть возможность вызывать и те процедуры, которые описаны после вызывающей. Для этого надо скопировать заголовок вызываемой подпрограммы и разместить его выше всех описаний. Например:

{Опережающее описание функции F1 - заголовок без тела функции} function F(x: real): real;

procedure P;

var x: real;

begin... {Какие-то действия} {Вызов функции F возможен благодаря опережающему описанию} x:=F(x);

... {Какие-то действия} end;

{Описание функции F, теперь тело функции присутствует} function F(x: real): real;

begin... {Какие-то действия} F1 := … {Что-то} end;

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

procedure A(n: integer); {опережающее описание первой procedure B(n: integer); {опережающее описание второй procedure A(n: integer);{полное описание процедуры A} begin writeln(n);

B(n-1);

end;

procedure B(n: integer);{полное описание процедуры B} begin writeln(n);

if n x[m] then end;

begin for i:=0 to n-1 do x[i]:=(i+1) mod 3;

for i:=0 to n-1 do begin for i:=1 to n do writeln(x[i]);

end.

5. Что выведет программа?

const type TIntArray = array [0..n-1] of integer;

var x, y: TIntArray;

i: integer;

procedure Fill(var x: TIntArray);

var i: integer;

begin for i:=0 to n-1 do end;

procedure P(var x, y: TIntArray);

var i: integer;

begin for i:=0 to n-1 do begin x[i] := x[i] + y[n-i+1];

end;

begin Fill(x);

Fill(y);

P(x, y);

P(y, x);

for i:=0 to n-1 do writeln(x[i]);

end.

6. Что выведет программа?

var x, y, z: integer;

procedure Step(var x, y: integer);

begin if x>y then end;

function Nod(x, y: integer): integer;

begin Nod:=x;

end;

begin x:=9;

y:=27;

z:=3;

writeln(Nod(Nod(x, y), z));

end.

Задание 11. Процедуры и функции Простейшие процедуры 1. Создайте процедуру, печатающую на экране слово Hello, и программу, которая с ее помощью напечатает слово Hello 10 раз.

Локальные переменные 2. Создайте процедуру, которая выводит в одну строку слово Hello 5 раз. Осуществите это с помощью цикла. Переменную-счетчик цикла сделайте локальной. С помощью данной процедуры выведите 5 таких строк.

Параметры процедур 3. Создайте процедуру, печатающую слово Hello заданное число раз. Количество раз передавайте в процедуру как параметр-значение.

4. Создайте процедуру, увеличивающую значение переменной на единицу.

5. Создайте процедуру, меняющую значения двух переменных местами.

6. Создайте процедуру, располагающую два числа по возрастанию.

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

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

8. Создайте процедуру, которая пару последовательных чисел Фибоначчи преобразует в следующую пару. Иными словами, если на входе даны элементы с номерами (n–1) и n, то процедура должна в те же переменные записать элементы с номерами n и (n+1). С помощью данной процедуры найдите 10-е число в последовательности Фибоначчи.

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

real);

10. Поворот на угол против часовой стрелки относительно начала координат приводит к следующему преобразованию координат:

Создайте процедуру, осуществляющую такое преобразование.

11. Создайте процедуру, заполняющую массив случайными числами.

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

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

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

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

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

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

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

12. Двумерные массивы 12.1. Двумерные массивы: теория Если элементы одномерного массива можно мыслить себе как координаты некоторого вектора, то двумерный массив будет соответствовать матрице. Опишем для примера двумерный массив размером 10х20:

const type TMatrix = array [0..n-1, 0..m-1] of real;

var A: TMatrix;

При обращении к элементам такого массива необходимо указывать сразу два индекса. Например, A[0,0] – левый верхний элемент матрицы и т.п. В остальном двумерные массивы ничем не отличаются от одномерных.

При желании можно вводить трех-, четырехмерные и т. д. массивы.

Для этого при описании соответствующего типа следует указать не два, а еще больше диапазонов индексов.

Еще один способ описать двумерный массив, это описать массив массивов:

type TVector = array [0..n-1] of real;

TMatrix2 = array [0..m-1] of TVector;

Каждый элемент массива TMatrix2 можно мыслить как векторстроку матрицы. Обращение к левому верхнему элементу в этом случае будет выглядеть так: A[0][0]. Здесь A[0] – первая строка, которая сама является массивом, но одномерным.

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

Задание 12. Двумерные массивы 1. Опишите тип – двумерный массив, количество элементов по горизонтали и вертикали пусть задается константами. Создайте процедуры: заполняющую такой массив случайными числами и печатающую массив на экране.

2. Создайте процедуры:

а) обнуляющую двумерный массив;

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

3. Создайте процедуру, присваивающую элементам двумерного массива их порядковые номера. Элементы нумеруются следующим образом:

а) построчно, т. е.

б) по спирали. Например, для матрицы 55 должно получиться в) по диагонали. Например:

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

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

5. Создайте процедуру, осуществляющую транспонирование матрицы.

13. Графика в Паскале 13.1. Введение Набор графических средств в Паскале чрезвычайно ограничен и не годится для освоения современной компьютерной графики. Однако те элементарные операции, которые все же присутствуют, являются основой, на которой построены многие более сложные алгоритмы, хотя бы поэтому эти операции заслуживают изучения.

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

Поэтому они хорошо подходят для развития азов алгоритмического мышления.

13.2. Инициализация графического режима Для того чтобы использовать в программе графические процедуры, необходимо подключить стандартный модуль с графическими процедурами и функциями. В среде PascalABC он называется GraphABC:

uses GraphABC;

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

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

Кроме того, для работы с графикой придется произвести ряд шаманских действий, а именно описать две целочисленные переменные (традиционно для них используют идентификаторы gd и gm):

gd, gm: integer;

В самой программе, перед тем как использовать графические процедуры, необходимо разместить такие строки:

gd:=DETECT;

InitGraph(gd, gm, '');

Файл egavga.bgi обычно лежит в каталоге BGI, который, в свою очередь, находится в каталоге Паскаля. Например, путь может выглядеть так:

C:\BP\BGI. Нет смысла подробно разбирать, что происходит при выполнении перечисленных операторов и что это за загадочный файл egavga.bgi.

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

Необходимо иметь в виду, что после перехода в графический режим (после выполнения процедуры InitGraph) перестают работать процедуры текстового ввода/вывода (Read, Write и т.д.). Следовательно, если требуется что-то ввести с клавиатуры, делайте это до вызова InitGraph. Выйти из графического режима можно с помощью процедуры CloseGraph.

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

program GraphicsPrg;

uses var gd, gm: integer;

begin gd:=DETECT;

InitGraph(gd, gm, 'c:\BP\bgi');

CloseGraph;

end.

13.3. Экранные координаты. Точка заданного цвета При запуске программы с подключенным модулем GraphABC создается так называемое графическое окно, обычное для ОС Windows, в пределах которого можно рисовать. Площадь окна можно рассматривать как двумерный массив светящихся точек (пикселей). Координаты точек принимают целочисленные значения и отсчитываются от левого верхнего угла окна (рис. 13.1). Такой способ называется экранной системой координат.

Ось ординат направлена вниз. Соответственно сам левый верхний угол имеет координаты (0,0). Координаты соседних с ним точек, очевидно, будут (0, 1), (1, 0) и (1, 1).

(0,WindowWidth) (WindowWidth, WindowHeight) Размеры окна по умолчанию составляют 640 на 480 точек. Однако пользователь может менять их произвольным образом обычным для ОС Windows способом (хватать мышью за угол, распахивать на весь экран и т.д.) Узнать текущий размер окна можно с помощью функций WindowWidth и WindowHeight. Например, инструкция W := WindowWidth;

запишет текущую ширину в переменную W.

Изначально все пиксели окна имеют белый цвет. Однако каждому можно назначить произвольный цвет, заданный в так называемой системе RGB (расшифровывается как Red Green Blue). В этой системе цвет задается тремя целыми числами в диапазоне от 0 до 255, определющими интенсивность красной, зеленой и синей составляющей (как известно, любой цвет можно получить их смешением). Цветовые значения имеют специальный тип Color, их можно получить с помощью функции RGB, имеющей заголовок function RGB(r, g, b: byte): Color;

Также цвет можно задать с помощью одной из определенных в модуле GraphABC констант. Например, clRed – красный цвет, clYellow – желтый и т.д. Полный список смотрите в справочной системе среды PascalABC (http:// pascalabc.net/ downloads/ pabcnethelp/ PABCUnits/ GraphABC/ gr_Colors.htm).

Указать любой точке, какого она должна быть цвета, можно с помощью процедуры PutPixel. Ее заголовок procedure PutPixel(x, y: integer; c: Color);

Здесь x, y – координаты точки, c – цвет точки.

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

Особенности среды Borland Pascal Ширина и высота экрана в пикселях здесь фиксирована (640 x 480).

По умолчанию все пиксели имеют черный цвет (не светятся), но каждому можно назначить один из 16 цветов. Каждому цвету соответствует целочисленная константа, описанная в модуле Graph. Список констант и их значения приведены в табл. 2.

Цвет Константа, описанная в модуле Graph Значение константы Произвольные цвета, не входящие в эту палитру, задать невозможно.

Назначение цвета производится с помощью той же процедуры PutPixel. Ее заголовок procedure PutPixel(X, Y: integer; Color: Word);

Здесь X, Y – координаты точки, Color – цвет точки.

13.4. Простейшие графические объекты Перечислим несколько процедур для рисования простейших графических объектов – так называемых графических примитивов:

– рисование линии:

procedure Line(X1, Y1, X2, Y2: integer);

Здесь (X1, Y1) – координаты начала, (X2, Y2) – координаты конца.

Линия вычерчивается так называемым текущим цветом;

– установка текущего цвета:

procedure SetPenColor(C: Color);

Здесь C – константа (или число), задающая цвет. О задании цвета читайте в предыдущем параграфе;

– рисование окружности:

procedure Circle(X, Y: integer; R: Word);

Здесь (X, Y) – координаты центра, R – радиус окружности. Окружность, как и линия, рисуется текущим цветом;

– рисование дуги:

procedure Arc(X, Y, R, BegA, EndA: integer);

Здесь (X, Y) – координаты центра дуги, BegA и EndA – начальный и конечный углы дуги, R – радиус дуги. Углы отсчитываются против часовой стрелки от положительного направления оси абсцисс и указываются в градусах;

procedure OutText(X, Y: integer; Txt: string);

Данная процедура размещает текст Txt в прямоугольнике, левый верхний угол которого задается координатами (X, Y);

– очистка экрана:

procedure ClearWindow;

За информацией о прочих графических примитивах отсылаем вас к справочной системе среды программирования (F1).

Особенности языка Borland Pascal Некоторые процедуры в Borland Pascal имеют чуть другое название или другой порядок следования параметров:

– установка текущего цвета:

procedure SetColor(C: Word);

– рисование дуги (другой порядок следования параметров):

procedure Arc(X, Y: integer; BegA, EndA, R: Word);

– вывод текста:

procedure OutTextXY(X, Y: integer; Txt: string);

– очистка экрана:

procedure ClearDevice;

13.5. Экранный указатель Экранный указатель – это аналог курсора в текстовом режиме, он указывает положение точки, которая считается «текущей». В отличие от мигающего курсора экранный указатель невидим. После инициализации графического режима экранный указатель располагается в точке с координатами (0, 0). Переместить его в произвольную точку на экране можно с помощью процедуры MoveTo. Ее заголовок procedure MoveTo(X, Y: integer);

Координаты экранного указателя используются многими графическими процедурами. Например, процедура LineTo, имеющая заголовок procedure LineTo(X, Y:integer);

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

13.6. Мировые координаты В задаче, решаемой программистом, может присутствовать своя собственная система координат. Например, если нужно построить график функции y = sin(x) на отрезке [0, 2], то координаты на плоскости, где мыслится этот график, очевидно, не совпадут с экранными. Требуется преобразовать координаты точек на графике в координаты изображаемых точек на экране. Такая система координат, присущая решаемой задаче, называется мировой.

Преобразование из мировых координат ( xm, ym ) в экранные ( xs, ys ) заключается в перемасштабировании (например, отрезок длиной 2 должен быть преобразован в отрезок длиной 600 пикселей) и сдвиге (например, точек с отрицательными координатами на экране нет и требуется сдвинуть перемасштабированный отрезок в положительную область). Это достигается путем линейного преобразования:

Здесь коэффициенты a и c отвечают за перемасштабирование (растягивание по горизонтали и вертикали), а b и d – за сдвиг вдоль этих направлений. Чтобы определить конкретные значения этих коэффициентов, надо решить, какую область (какой прямоугольник) в мировых координатах в какой области экрана мы собираемся отобразить.

Пусть мировые координаты меняются в диапазоне Область на экране, где требуется поместить изображение, зададим, указав координаты верхней левой точки (Left, Top), а также ширину и высоту этой области (Width и Height). Нетрудно убедиться, что в таком случае преобразование мировых координат в экранные будет выглядеть как Данные преобразования дают в общем случае вещественный результат. Поскольку графические процедуры требуют целых значений аргумента, полученные по этим формулам координаты следует округлить.

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

13.7. Сдвиг и поворот Сдвиг на вектор с координатами (dx, dy ) заключается в добавлении этих координат к координатам каждой точки сдвигаемого объекта:

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

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

Координаты точек при повороте на угол относительно начала координат преобразуются по закону (рис. 13.2):

Или в матричном виде Чтобы осуществить поворот относительно произвольной точки ( x0, y0 ), необходимо сделать сдвиг, который перенесет эту точку в начало координат ( dx = x0, dy = y0 ). После этого надо сделать поворот на требуемый угол и снова сделать сдвиг, который вернет бывшую точку ( x0, y0 ) на место (рис. 13.3).

Нетрудно записать такое преобразование следующим образом:

Задание 13. Графика в Паскале Примечание: При выполнении заданий в среде Borland Pascal следует слово «графическое окно» заменить на «экран». Иными словами, вместо «нарисуйте в центре графического окна» следует читать «нарисуйте в центре экрана» и т.п.

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

2. Нарисуйте окружности радиусом 20 пикселей в центре графического окна и по углам окна.

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

4. Создайте процедуру, рисующую квадрат заданной величины по центру окна.

5. Отобразите на экране 1000 точек со случайными координатами и со случайными координатами, лежащими внутри квадрата из предыдущей задачи.

Усложненный вариант: со случайными координатами, лежащими внутри заданной окружности.

6. Воспроизведите орнаменты, оформив рисование их отдельных элементов в виде процедур (рис. 13.4).

7. Нарисуйте домик, над которым светит солнышко.

Усложненный вариант: (а) солнышко имеет лучики, (б) солнышко движется по небу; картинка рисуется процедурой, параметрами которой является координаты солнышка.

8. Воспроизведите рисунки, полученные с помощью поворотов треугольника и окружности (рис. 13.5).

9. Нарисуйте график функции y = a sin t. Параметрами процедуры должны быть интервал значений t, амплитуда a, частота и количество точек, выводимых на график.

14. Символы, строки, текстовые файлы 14.1. Символьный тип данных Переменные типа Char (от английского character) могут хранить одиночный символ. В памяти такая переменная занимает 1 байт, соответственно она может принимать 256 различных значений (на самом деле в памяти хранятся коды символов – числа от 0 до 255). Какие именно символы соответствуют кодам, зависит от кодовой таблицы, установленной в операционной системе. Однако традиционно первые 128 из них – это так называемые ASCII-символы (см. http://ru.wikipedia.org/wiki/ASCII). Первые 32 символа называются управляющими, остальные изображаемыми.

Управляющие символы воспринимаются устройствами вывода как команды. Например (табл. 3):

Опишем переменную символьного типа:

var c: char;

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

c := 'a';

c := '*';

и т.д.

Второй – это записать символ «решетка», за которым следует код задаваемого символа. Например:

c := #7;

Заметим, что в данном случае речь идет только о символьных константах, и если код записан в целочисленную переменную, то написать # нельзя.

Символы можно сравнивать. Больше тот символ, код которого больше. Соответственно 'a' < 'z', 'A' < 'Z' и '0' < '9'.

С символьным типом связаны следующие функции:

1) chr(i) – дает символ с кодом i. Вместо i может стоять любое выражение с целочисленным значением из диапазона от 0 до 255;

2) ord(c) – по символу определяет его код (функция обратная к chr);

3) succ(c) – символ, следующий в кодовой таблице за символом c;

4) pred(c) – символ, предшествующий в кодовой таблице символу c;

5) upcase(c) – преобразует строчные латинские буквы в прописные.

Остальные символы оставляет неизменными, т. е. upcase('f') = 'F', а upcase('*') = '*'.

14.2. Строковый тип Значениями строкового типа (string) в Паскале являются последовательности символов длиной от 0 (пустая строка) до 255 символов. Можно описать строку, предельная длина которой меньше 255, задав ее длину в квадратных скобках. Примеры описания строк:

var s1, s2: string; {обычные строки длиной до 255 символов} name: string[20]; {строка длиной не более 20 символов} group: string[3]; {строка длиной не более 3 символов} txt: array [0..99] of string[80]; {массив из Строку можно рассматривать как массив символов, т. е. обращаться из программы к отдельным символам строки:

s1[2] – второй символ строки s1;

s2[i] – i-й символ строки s2;

txt[3][10] – десятый символ третьей строки из описанного выше массива txt.

Нумерация символов в строке начинается с 1. В памяти строка занимает на 1 байт больше, чем это необходимо для хранения символов. Самый первый (нулевой) байт хранит длину строки. Поэтому присваивание вида s1[10]:= 'x' приведет к желаемому результату, только если в строке десять или больше символов. Та же операция по отношению к более короткой строке не приведет к ее изменению.

Строки можно считывать и печатать обычными процедурами ввода/вывода: read, readln, write, writeln.

Для строк определена операция сложения. При этом складываемые строки объединяются в одну. Например:

s1 := 'abra';

s1[1] := Upcase(s1[1]);

s2 := 'kadabra';

s1 := s1+' '+s2+'!';

writeln(s1);

Здесь первый символ строки s1 (строчная «a») был заменен на прописную «A». Затем к этой строке были добавлены пробел и строка s2. В итоге программа напечатает строку 'Abra kadabra!'.

Переменную или выражение типа Char также можно прибавить к строке.

Отдельные символы строки (s1[1], s1[2] и т.д.) можно рассматривать как переменные типа Char. В примере мы воспользовались этим, заменив строчную букву заглавной.

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

S := '';

Обратите внимание, что «ничего» в данном случае значит совсем ничего. Часто, пытаясь задать пустую строку, ставят между кавычками пробел, что неправильно.

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

1) Length(s) – получение длины строки;

2) Pos(Substr, S) – функция, в качестве результата выдающая номер символа, начиная с которого в строке s начинается подстрока Substr. Если S не содержит подстроки Substr, то результат будет равен 0.

Например: Pos(' ', s) – найдет номер позиции, на которой в строке s находится пробел. Pos('Ivan', s) найдет имя 'Ivan';

3) Copy(s, i, n) – функция, выделяющая из строки s подстроку, начиная с символа за номером i, и включающую n символов. Например:

s1 := 'abracadabra';

s1 := Copy(s1, 5, 6);

В результате строка s1 будет равна 'cadabr';

4) Delete(s, i,n) – процедура, удаляющая из строки s n символов, начиная с символа с номером i;

5) Val(s, n, code) – процедура, переводящая строку s в число n. Если преобразование произошло успешно, то code будет равна 0, если нет, то в эту переменную будет записан код ошибки;

6) Str(n, s) – процедура, переводящая число n в строку s;

7) для преобразования чисел в строки и обратно также удобно пользоваться функциями:

– StrToInt(s) – функция, возвращающая целочисленное значение, записанное в строке s, – StrToFloat(s) – функция, возвращающая целочисленное значение, записанное в строке s, – IntToStr(x) – функция, возвращающая строковое значение, содержащее целое число x, – FloatToStr(x) – функция, возвращающая строковое значение, содержащее вещественное число x.

Заметим, что данные функции не будут работать, если вы программируете в среде Borland Pascal.

14.3. Примеры работы со строками Пример 1. Подсчитать, сколько раз в строке встречается пробел.

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

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

Оформим решение в виде функции function SpaceNumber(s: string): integer;

var i, n: integer;

begin for i := 1 to length(s) do SpaceNumber := n;

end;

Пример 2. Стандартная функция Pos обнаруживает первое появление некоторой подстроки. Создадим функцию, которая возвращает n-е появление подстроки.

Детали работы функции описаны в программных комментариях:

function PosN(Substr, S, n): integer;

var i, pn, SubLen: integer;

begin SubLen := length(Substr);

pn := 0; {в этой переменной считаем, сколько раз i:=1;

while (pn < n)and(i 1 then begin New(Head);

{При работе с однонаправленными списками принципиально важно не потерять ссылку на первый элемент. Поэтому дальнейшие операции будем проводить не с Head, а со вспомогательной переменной H} end else end;

procedure FreeList(var Head: PList);

{Процедура, освобождающая память, выделенную под список с первым элементом Head} var H: PList;

begin {Поскольку список все равно уничтожается, можем спокойно изменять Head} while Head nil do begin Head := Head^.Next;

Dispose(H);

Head := nil;

end;

procedure FillList(Head: PList);

{Процедура заполняет информационную часть элементов списка числами 1, 2, 3, …} var n: integer;

begin n:=1;

while Head nil do begin Head:=Head^.Next;

end;

procedure PrintList(Head: PList);

{Процедура печатает информационную часть элементов begin while Head nil do begin writeln(Head^.x);

Head := Head^.Next;

end;

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

var List: PList;

begin CreateList(List, 5); {создаем список из 5 элементов} FillList(List); {в информационные части пишем числа 1, 2, 3, 4, 5} PrintList(List); {печатаем информационные части ClearList(List); {освобождаем память} readln;

end.

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

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

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

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

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

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

Задание 16. Указатели 1. Присвойте какой-нибудь переменной значение не напрямую, а узнав ее адрес и изменив содержимое памяти по этому адресу.

2. Узнайте, что станет с переменной типа char, если в соответствующую ей память записать целое число.

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

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

б) напечатать значения элементов списка;

в) исключить из списка элемент с заданным номером;

г) поменять местами два элемента списка;

д) уничтожить список.

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

5. Создайте однонаправленный список из целых чисел. Перестройте элементы списка в обратном порядке.

6. По строке, содержащей арифметическое выражение, куда входят числа и символы операций (+, -, /, *), постройте бинарное дерево и создайте функцию, которая по такому дереву вычисляет значение выражения.

Список рекомендуемой литературы Общие вопросы программирования Axo, А. В. Структуры данных и алгоритмы / А. В. Axo, Дж. Хопкрофт, Дж. Д. Ульман : пер. с англ. – М. : Изд. дом «Вильямс», 2003. – 384 с.

Вирт, Н. Алгоритмы и структуры данных. Новая версия для Оберона / пер. с англ. Ф. В. Ткачёва. – М. : ДМК Пресс, 2010. – 272 с.

Кнут, Д. Искусство программирования. Т. 1. Основные алгоритмы / Д. Кнут. – 3-е изд. – М. : Изд. дом «Вильямс», 2006. – 720 с.

Круз, Р. Л. Структуры данных и проектирование программ : учеб. пособие / Р. Л. Круз; пер. 3-го англ. изд. К. Г. Финогенова. – М. : Бином. Лаб. знаний, 2008. – 765 с.

Окулов, С. М. Программирование в алгоритмах : учеб. пособие / С. М. Окулов. – М. : Бином. Лаб. знаний, 2004. – 341 с.

Себеста, Р. У. Основные концепции языков программирования / Р. У. Себеста.

– 5-е изд. : пер. с англ. – М. : Изд. дом «Вильямс», 2001. – 672 с.

Синицын, С. В. Программирование на языке высокого уровня: учебник / С. В. Синицын, А. С. Михайлов, О. И. Хлытчиев. – М. : Изд. центр «Академия», 2010. – 302 с.

Изучение языка Паскаль Алексеев, Е. Р. Free Pascal и Lazarus : учебник по программированию / Е. Р.

Алексеев, О. В. Чеснокова, Т. В. Кучер. – М. : AltLinux, 2010. – 438 с.

Андреева, Т. А. Программирование на языке Pascal : учеб. пособие / Т. А. Андреева. – М. : Интернет-Ун-т Инф. Технологий : Бином. Лаб. знаний, 2010. – 234 с.

Григорьев, С. А. Программирование на языке Паскаль для математиков : учеб.

пособие / С. А. Григорьев. – Калининград : Изд-во Калининград. ун-та, 1997. – 92 с.

Епанешников, А. М. Программирование в среде Turbo Pascal 7.0 : учеб. пособие / А. М. Епанешников, В. А. Епанешников. – 3-е изд. – М. : Диалог-Мифи, 1995. – 368 с.

Зуев, Е. А. Программирование на языке Turbo Pascal 6.0, 7.0 / Е. А. Зуев. – М. :

Радио и связь : Веста, 1993. – 380 с.

Марченко, А. И. Программирование в среде Turbo Pascal 7.0 / А. И. Марченко, Л. А. Марченко. – 5-е изд., доп. и перераб. – Киев : ВЕК+, 1999. – 458 с.

Огнёва, М. В. Turbo Pascal : первые шаги. Примеры и упражнения : учеб. пособие / М. В. Огнёва, Е. В. Кудрина. – 3-е изд., доп. и перераб. – Саратов : Науч. кн., 2008.

– 99 с.

Семашко, Г. Л. Программирование на языке Паскаль / Г. Л. Семашко, А. И. Салтыков. – 2-е изд., перераб. и доп. – М. : Наука, 1993. – 207 с.

Оглавление В в е д е н и е

Выбор среды программирования

1. Линейные программы: арифметические операторы, стандартные функции и ввод/вывод в текстовом режиме

1.1. Алгоритмы

1.2. Переменные и их типы

1.3. Операторы

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

1.5. Структура программы

1.6. Ввод/вывод в текстовом режиме

2. Логические выражения и условный оператор

2.1. Переменная логического типа

2.2. Операторы сравнения

2.3. Логические операторы

2.4. Задачи на составление логических выражений

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

2.6. Оформление текста программ

3. Цикл for

3.1. Цикл с параметром (for)

3.2. Прием накопления суммы

3.3. Прием накопления произведения

3.4. Комбинация обоих приемов

3.5. Цикл с downto

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

4.1. Рекуррентные соотношения: основные понятия

4.3. Многомерные рекуррентные соотношения

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

5.1. Вложенные циклы: теория

6. Задачи на перебор вариантов

6.1. Перебор вариантов: теория

7. Переменные-флаги

7.1. Переменные-флаги: теория

8. Переменная-счетчик событий

8.1. Переменные-счетчики

9. Циклы while и repeat

9.1. Синтаксис циклов while и repeat

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

9.3. Цикл, управляемый меткой

9.4. Вычисление номера шага

9.5. Вычисления с заданной точностью

10. Массивы

10.1. Структурные типы данных

10.2. Основные определения

10.3. Вычислимость индексов

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

11. Процедуры и функции

11.1. Простейшая процедура

11.2. Локальные переменные

11.3. Параметры процедур

11.4. Параметры-значения и параметры-переменные

11.5. Программирование сверху вниз

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

11.7. Функции

11.8. Опережающее описание

11.9. Процедурные типы

11.11. Модули

12. Двумерные массивы

12.1. Двумерные массивы: теория

13. Графика в Паскале

13.1. Введение

13.2. Инициализация графического режима

13.3. Экранные координаты. Точка заданного цвета

13.4. Простейшие графические объекты

13.5. Экранный указатель

13.6. Мировые координаты

13.7. Сдвиг и поворот

14. Символы, строки, текстовые файлы

14.1. Символьный тип данных

14.2. Строковый тип

14.3. Примеры работы со строками

14.4. Текстовые файлы

15. Записи

15.1. Необходимость агрегации данных

15.2. Тип-запись

15.3. Оператор присоединения with

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

16. Указатели

16.1. Ссылочные типы и указатели

16.2. Нетипизированные указатели

16.3. Динамическое выделение памяти

16.4. Рекурсивные структуры данных

Список рекомендуемой литературы

ПРИНЦИПЫ И АЛГОРИТМЫ

ПРИКЛАДНОГО ПРОГРАММИРОВАНИЯ

Учебное пособие для студентов, обучающихся на факультете нано- и биомедицинских технологий Технический редактор В. В. Володина Оригинал-макет подготовлен О. Л. Багаевой Подписано в печать 15.10.2012. Формат 60х84 1/16.

Усл. печ. л. 8,14(8,75). Тираж 100. Заказ 66.

Издательство Саратовского университета.

410012, Саратов, Астраханская, 83.

Типография Издательства Саратовского университета.

410012, Саратов, Астраханская, 83.