рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

От автора

От автора - раздел Транспорт, От Автора ...

От автора

1. Общая схема решения задачи на персональном компьютере В общем виде процесс решения любой программистской задачи на ПК можно… 1) разработка алгоритма решения задачи;

E3

B1+4.25+r2

Теперь мы можем присвоить переменным их значения :

 

i:=-11;

j:=22+i;

k:=i+j+177;

 

Наряду с переменными в Паскале есть и другие именованные объекты - это именованныеконстанты (отличайте их от числовых констант, которые не имеют имени, а лишь значение). Именованные константы бывают двух видов - нетипизированные и типизированные. Нетипизированные константы описываются в разделе описаний в виде :

Constимя=значение; имя=значение;...

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

 

Const C=-155;

D=C+100;

E=1E2+C+D;

Const F=D+1;

Const G=C+F;

 

Нетипизированные константы, описанные в разделе описаний, вы можете затем использовать в разделе операторов в выражениях, но изменить их значения невозможно. Не совсем удачное название “нетипизированные” означает не отсутствие у констант типа - любая константа имеет совершенно определенный тип, который определяется ее значением, - а лишь то обстоятельство, что при описании таких констант тип не указывается явно. В нашем примере константы C,D,Fи Gимеют тип Integer, а константа E - тип Real. Второй класс именованных констант - типизированные константы, описание которых имеет вид:

Const имя:тип=значение; имя:тип=значение;...

Эти константы вы можете использовать так же, как и нетипизированные, но можете и изменять их значения (например, с помощью оператора присваивания), подобно переменным. Типизированные константы можно, с небольшими оговорками, рассматривать как переменные, которым присвоено начальное значение. Приведем пример :

 

Const t : Word = $FFFF;

b : Byte = 11;

r : Real = 1.23E-16;

z : Integer= 0;

Begin

t:=t-1;

End.

 

Зачем давать константам имена? Почему нельзя в том месте программы, где используется какая-нибудь не изменяемая в программе величина, просто не записать соответствующее число? Можно поступать и так, но тогда программа с большой вероятностью получится плохой. Один из законов программирования гласит “никогда не используй в программе магические константы”. Магической константой называется любая неименованная константа в программе (не в разделе констант), которая не обусловлена алгоритмом. То есть магическую константу можно заменить на другое значение и после этого программа по-прежнему останется правильной (хотя, быть может, и будет решать несколько другую задачу). В хорошей программе все такие константы должны быть вынесены в раздел констант, где им должно быть дано достаточно осмысленное имя, после этого они превратятся в константы настройки. Константы настройки позволяют очень легко, быстро и надежно модифицировать программу, не внося никаких изменений в алгоритм.

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

Простейший оператор ввода в Паскале - оператор Read, он записывается в виде :

Read(имя,имя,...);

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

ReadLn(имя,имя,...);

Различие между операторами Read и ReadLn заключается в следующем: оператор Read вводит данные, указанные в его списке ввода, рассматривая символ Enter (конец строки) как обычный разделитель, последний из нажатых символов Enter не считывается и остается в буфере клавиатуры. Оператор ReadLn при вводе числовых данных также рассматривает Enter как разделитель, но после того, как все данные введены, считывается и символ конца строки, при этом все данные, располагающиеся во входном потоке до ближайшего конца строки, пропускаются. Пусть, например, программа вводит с клавиатуры числа a,b,c,d,e,f.

 

Begin

Read(a,b,c);

ReadLn(d);

ReadLn(e);

ReadLn(f);

End.

Мы хотим ввести значения 1,2,3,4,5 и 6 и набираем на клавиатуре следующую последовательность символов: 1 2 3 4 5 6 Enter , но программа по-прежнему ждет ввода данных - почему? Оператор Read(a,b,c) успешно ввел значения 1,2,3, оператор ReadLn(d) ввел значение 4 и прочитал символ Enter, а значения 5 и 6 были пропущены, теперь оператор ReadLn(e) ждет вводимого значения, а входной поток пуст. Правильный входной поток для этой программы может быть, например, таким: 1 2 3 4 Enter 5 Enter 6 Enter , или таким: 1 Enter 2 Enter 3 Enter 4 Enter 5 Enter 6 Enter . Если программа вводит только числовые значения, то лучше всегда использовать операторы Read, а не ReadLn, так как в этом случае данные во входном потоке могут располагаться как угодно - все данные в одной строке, или каждое значение в новой строке, или любым другим способом.

Оператор ReadLn; без списка в скобках можно использовать для организации задержки в работе программы - он будет ожидать нажатия клавиши Enter.

При неправильном вводе числовых данных (нечисловая константа или константа, не соответствующая типу вводимой переменной) происходит аварийное завершение программы: выводится сообщение “Error 106 : Invalid numeric format”, и выполнение программы прекращается. Несколько позже мы обсудим способы предотвращения таких ситуаций. При отладке программы всегда бывает полезно задавать опцию компилятора {$D+}- “включить режим отладки”. При аварийном завершении программы, откомпилированной в таком режиме, не только выводится сообщение об ошибке, но и указывается курсором строка, где эта ошибка произошла.

Простейший оператор вывода записывается в виде :

Write(выражение,выражение,...);

или

WriteLn(выражение,выражение,...);

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

 

Var i : Integer;

w : Word;

r : Real;

Begin

WriteLn;

{------------- ввод -------------}

Write('Введите целое число ');

Read(i);

WriteLn;

Write('Введите натуральное число ');

Read(w);

WriteLn;

Write('Введите вещественное число ');

Read(r);

WriteLn;

{------------- вывод -------------}

WriteLn('Вы ввели : ',i,' ',w,' ',r,' их сумма=',i+w+r);

WriteLn('Нажмите Enter для выхода');

ReadLn;

End.

 

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

1. Организация диалога с пользователем. Прежде чем записать операторRead, вы обязаны записать хотя бы один Write, который выведет на экран приглашение "Введите ...", причем из этого приглашения пользователь должен понять, какие именно данные ему следует ввести. Так, в нашем примере операторы Write('Введите i '); Read(i);были бы неуместны, так как пользователю неизвестно, что такоеi, и он мог бы ввести, например, вещественное число, что привело бы к аварийному завершению программы.

2. Оформление текста программы. Хорошо оформленная программа (чаще говорят - хорошо структурированная программа) легко читается и быстрее отлаживается, всегда следует стремиться к “прозрачности” текста, но не к некоторой вполне субъективной “красоте”; так, скажем, операторы, выполняющиеся последовательно, следует и записывать строго друг под другом, но не “елочкой” или какой-либо другой фигурой. Средства, используемые для структурирования текста, крайне просты и доступны всякому - это пробелы, пустые строки и комментарии.

При выводе чисел можно их форматировать, т.е. управлять формой их представления. Для этого в списке вывода после выводимого выражения можно указывать модификаторы: “: L : d” для вещественных значений и “:L” для вещественных и целых. L и d - произвольные целочисленные выражения, первое из них определяет, сколько всего позиций отводится для выводимого числа на экране, а второе - сколько выводится цифр после десятичной точки. Если при выводе вещественного числа задан модификатор “: L : d”, то оно выводится с фиксированной точкой, если же задан модификатор “: L” или он отсутствует - то с плавающей точкой. Пусть значение переменной X равно 123.45678, тогда оператор

Write(X);выведет " 1.2345678000E+02"

Write(X:8:2);выведет " 123.46"

Write(X:10:5);выведет " 1.235E+02"

Write(X:10);выведет " 1.235E+02"

Write(X:8);выведет " 1.2E+02"

Write(X:1);выведет " 1.2E+02"

По умолчанию значения выводимые оператором Write не разделяются пробелами, поэтому если вы выводите подряд несколько чисел, вам нужно позаботиться об их правильном расположении на экране. Так, оператор WRITE(1,2,3); выведет на экран “123”, чтобы вывести три отдельных числа, необходимо выполнить оператор WRITE(1, ’ ‘ , 2 , ’ ‘ , 3); или оператор WRITE(1, 2:2, 3:2);

Арифметические операции. Стандартные математические функции

Для арифметических данных, т.е. для числовых констант, переменных и числовых функций, определены 12 арифметических операций:

+сложение

- вычитание

*умножение

/вещественное деление

Divцелая часть от деления

Modостаток от деления

Notбитовое отрицание

Andбитовое “и”

Orбитовое “или”

Xorбитовое “исключающее или”

ShLбитовый сдвиг влево

ShRбитовый сдвиг вправо

Первые четыре операции определены для любых операндов - как целых, так и вещественных, причем результат операции “/” - всегда вещественное число, даже если оба операнда целые. Остальные восемь операций определены только для целых операндов. Кроме того, выделяют унарную операцию "-", которая применяется не к двум, а к одному операнду, например: -x.

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

0 And 0=0, 0 And 1=0, 1 And 0=0, 1 And 1=1.

Битовые операции Or и Xor выполняются аналогичным образом, при этом операция Or использует правило

0 Or 0=0, 0 Or 1=1, 1 Or 0=1, 1 Or 1=1,

а операция Xor - правило

0 Xor 0=0, 0 Xor 1=1, 1 Xor 0=1, 1 Xor 1=0.

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

 

Var x,y : Byte;

Begin

x:=200; { двоичное представление x : 1100 1000 }

WriteLn(‘Not ‘,x,’ = ‘,Not x);

{ программа выведет Not 200 = 55 - 0011 0111 в двоичном представлении}

y:=100; { двоичное представление y : 0110 0100 }

WriteLn(x,’ And ‘,y,’ = ‘,x And y); { программа выведет 200 And 100 = 64 - 0100 0000 в двоичном представлении }

WriteLn(x,’ Or ‘,y,’ = ‘,x Or y); { программа выведет 200 Or 100 = 236 - 1110 1100 в двоичном представлении }

WriteLn(x,’ Xor ‘,y,’ = ‘,x Xor y); { программа выведет 200 Xor 100 = 172 - 1010 1100 в двоичном представлении }

WriteLn(x,’ ShR 3 = ‘,x ShR 3); { программа выведет 200 ShR 3 = 25 - 0001 1001 в двоичном представлении }

WriteLn(y,’ ShL 2 = ‘,y ShL 2); { программа выведет 100 ShL 2 = 400 - 0000 0001 1001 0000 в двоичном представлении }

End.

 

Выведем двоичное представление числа типа Byte, используя битовые операции.

 

Var b : Byte;

Begin

b:=177;

WriteLn(b And $80 ShR 7, b And $40 ShR 6,

b And $20 ShR 5, b And $10 ShR 4,

b And $08 ShR 3, b And $04 ShR 2,

b And $02 ShR 1, b And $01 ShR 0);

{или} WriteLn( b ShR 7 And 1,b ShR 6 And 1,b ShR 5 And 1,b ShR 4 And 1,

b ShR 3 And 1,b ShR 2 And 1,b ShR 1 And 1,b ShR 0 And 1);

{или} WriteLn( b ShL 8 ShR 15, b ShL 9 ShR 15,

b ShL 10 ShR 15, b ShL 11 ShR 15,

b ShL 12 ShR 15, b ShL 13 ShR 15,

b ShL 14 ShR 15,b ShL 15 ShR 15);

End.

 

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

 

Операнды Byte ShortInt Word Integer LongInt
Byte Integer Integer Word Integer LongInt
ShortInt Integer Integer LongInt Integer LongInt
Word Word LongInt Word LongInt LongInt
Integer Integer Integer LongInt Integer LongInt
LongInt LongInt LongInt LongInt LongInt LongInt

 

Посмотрите еще раз на третий оператор вывода в последнем примере. Почему чтобы получить, например, младший бит однобайтового числа, мы сдвинули биты влево не на 7 (что представляется естественным), а на 15? Здесь срабатывает правило Byte+Byte=Integer (левый верхний угол таблицы), если сдвинуть биты влево на 7 позиций, то все старшие биты сохранятся в старшем байте выражения b ShL 7, имеющего тип Integer, а затем после правого сдвига благополучно вернутся на свои места.

Если один операнд выражения имеет целочисленный тип, а второй - вещественный, то первый автоматически приводится к вещественному типу и значение выражения будет вещественным. Целые значения можно присваивать вещественной переменной, но вещественные значения присвоить целой переменной нельзя. Присваивая значение целочисленной переменной и константе, вы должны следить, чтобы это значение не выходило за пределы диапазона допустимых значений переменной. Если присваиваемое значение не является допустимым для переменной, то происходит аварийное завершение программы и выводится сообщение “Error 201 : Range check error”. В языке Паскаль есть возможность явно преобразовать целочисленное значение к любому из целочисленных типов, для этого используются стандартные функции с именами Byte, ShortInt, Word, Integer и LongInt. Например, преобразуем переменную типа Word к типу Integer :

 

Var x : Word;

Begin

x:=300;

WriteLn(x,' =',Integer(x));

x:=65535;

WriteLn(x,' =',Integer(x));

End.

 

Программа выведет 300=300 и 65535= -1. В первом случае преобразование происходит корректно, а во втором - с изменением значения, так как число 65535 не является допустимым значением типа Integer.

Арифметическое выражение может содержать любое количество операндов и, соответственно, любое количество операций, которые выполняются в последовательности, определенной их приоритетом. Наивысший приоритет имеют унарные операции Not и унарный минус, менее высокий приоритет у операций *, /, Div, Mod , And , ShL , ShR ,и самый низкий приоритет имеют операции + , - , Or , Xor. Операции одного приоритета выполняются в последовательности слева направо. Чтобы изменить порядок выполнения операций, вы можете использовать в выражении круглые скобки. Вычислим, например, частное от деления X на сумму A,B и C : X/(A+B+C) .

При вычислении арифметических выражений могут происходить аварийные прерывания программы, причинами которых обычно являются ошибка 200: Division by zero (происходит при выполнении операций /, Div и Mod , когда делитель равен нулю), ошибка 215: Ariphmetic overflow (происходит при вычислении целочисленного выражения, когда значение выражения неприемлемо для его типа) и ошибка 205: Floating point overflow (происходит при вычислении вещественного выражения, когда значение выражения не умещается в соответствующий вещественный тип, или во время присваивания вещественной переменной недопустимого значения). Остановимся подробнее на двух последних ошибках. Пусть программа вычисляет сумму двух натуральных чисел

 

Var

x,y :Word;

z :LongInt;

Begin

x:=$FFFF;

y:=1;

z:=x+y;

End.

 

В этой программе произойдет “арифметическое переполнение”, но почему? Ведь сумма двух чисел равна всего лишь 65536, а мы присваиваем это число переменной типа LongInt - это вполне допустимая операция. Но ошибка в этой программе происходит не во время присваивания z:=x+y , а раньше - при вычислении выражения x+y (ту же самую ошибку мы получим, если не будем присваивать сумму x+y, а просто попытаемся вывести ее на экран). Вспомним таблицу преобразования целочисленных типов, если операнды выражения имеют тип Word, то и значение выражения имеет тип Word, а для типа Word значение 65536 неприемлемо. Исправить нашу программу черезвычайно легко, и для этого необязательно менять описания переменных, достаточно лишь слегка изменить оператор присваивания : z:=LongInt(x)+y;, теперь тип выражения будет LongInt и никакой ошибки не случится.

Ошибка Floating point overflow (вещественное переполнение) очень похожа на “арифметическое переполнение”, но имеет особенность, связанную с использованием опций компилятора E и N. Пусть программа вычисляет произведение двух вещественных чисел

 

{$E-,N-}

Var

x,y,z : Real;

Begin

x:=1E30;

y:=1E20;

WriteLn(‘x*y=‘,x*y);

z:=x*y;

End.

 

При выполнении оператора WriteLn произойдет вещественное переполнение, все правильно: значение произведения 1050 неприемлемо для типа Real. Но изменим опции компилятора на {$E+,N+}, и оператор WriteLn сработает, и переполнение случится лишь во время присваивания z:=x*y. Дело в том, что в программе, откомпилированной при включенном режиме сопроцессора, все вещественные выражения, независимо от типа операндов, вычисляются в типе Extended, поэтому вычислить произведение можно, а вот присвоить его можно лишь переменным типа Double или Extended.


Набор встроенных математических функций в языке Паскаль невелик, он включает :

1. Abs(x) - абсолютная величина числа

2. Int(x) - целая часть вещественного числа (в вещественном типе)

3. Frac(x) - дробная часть вещественного числа

Trunc(x) - целая часть вещественного числа, преобразованная к типу LongInt

Round(x) - округленное до целого вещественное число, преобразованное к типуLongInt

7. Sqrt(x) - квадратный корень 8. Exp(x) - экспонента 9. Ln(x) - натуральный логарифм

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

'0'...'9'- 48...57 'A'...'Z- 65...90 'a'...'z'- 97...122

Логический тип данных. Операции сравнения. Логические операции

Логические, или булевские, данные предназначены для хранения логических значений “истина” или “ложь”. Логические переменные и константы имеют тип Boolean и занимают в памяти 1 байт. Существует всего две логические константы - True и False. Тип Boolean - это порядковый тип, поэтому для него определены функции Ord, Pred, Succ и процедуры Incи Dec (впрочем, довольно редко применяемые), причем Ord(False) =0, Ord(True) =1. Прежде чем перейти к логическим операциям, рассмотрим операции сравнения, которых в Паскале существует шесть :

=равно

<> не равно

<меньше

<=меньше или равно

>больше

>=больше или равно

Операции сравнения определены для любых однотипных операндов (числовых, символьных, логических), для числовых данных, так же как и в случае арифметических операций, сделано исключение - вы можете сравнивать два числовых выражения любых типов, но сравнивать число и символ, число и логическую величину, символ и логическую величину нельзя. Результат операции сравнения есть True или False, в зависимости от того, выполнено или не выполнено условие. Числа сравниваются между собой естественным образом, символы - в соответствии с их номерами, а для логических величин справедливо неравенство False<True. Логических, или булевских, операций в Паскале четыре:

Not - логическое отрицание;

And - логическое "и";

Or - логическое "или";

Xor - логическое исключающее "или".

Правила выполнения этих операций таковы:

Not - унарная (т.е. применимая к одному операнду) операция :

Not False = True , Not True = False

Правила выполнения бинарных операций And, Or и Xor приведены в таблице:

 

a b a And b a Or b a Xor b
False False False False False
False True False True True
True False False True True
True True True True False

 

Логические операции совпадают по написанию с соответствующими битовыми операциями - это не случайно, фактически это одни и те же операции, и правила их выполнения станут совершенно одинаковыми, если нулевой бит считать логическим значением False, а единичный бит - значением True (именно таким образом и кодируются логические данные в памяти компьютера). Приоритеты логических операций точно такие же, как у соответствующих битовых операций, а приоритеты операций сравнения ниже, чем у всех арифметических и логических операций. Если мы хотим записать логическое выражение, которое будет истинным тогда и только тогда, когда x меньше y и z больше 100, то запись x<y And z>100 будет неверной, так как сначала будет выполняться операция And (в данном случае как битовая, а не логическая). Чтобы повысить приоритет операций сравнения, нужно использовать скобки: (x<y)And(z>100). Существует функция, определенная для целочисленных аргументов и имеющая логическое значение, это функция

30. Odd(x),

она возвращаетTrue, если значение x нечетное, и False, если оно четное. Логические значения можно выводить процедурой Write, но вводить логические переменные процедурой Read нельзя. Теперь попробуем записать программу, использующую логические данные.

 

Var a,b,c,d : Integer;

Begin

WriteLn('Введите 4 целых числа, a,b,c и d, среди ',

'которых должно быть 2 и только 2 одинаковых!');

Read(a,b,c,d);

WriteLn('Вашу понятливость можно оценить как ',

(a=b)And(a<>c)And(a<>d)And(c<>d)Or

(a=c)And(a<>b)And(a<>d)And(b<>d)Or

(a=d)And(a<>b)And(a<>c)And(b<>c)Or

(b=c)And(b<>a)And(b<>d)And(a<>d)Or

(b=d)And(b<>a)And(b<>c)And(a<>c)Or

(c=d)And(c<>a)And(c<>b)And(a<>b));

ReadLn;

End.

 

Программа выведет True, если введенные данные удовлетворили условию, и False в противном случае.

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

31. EoLn - конец строки при символьном вводе.

32. EoF - конец файла при символьном вводе.

33. SeekEoLn- конец строки при числовом вводе.

34. SeekEoF - конец файла при числовом вводе.

Функция EoLn возвращает значение True, если очередным символом во входном потоке является символ конца строки (Enter), и False в противном случае. Функция EoF возвращает True, если очередным символом во входном потоке является символ конца файла (Ctrl-Z). Функции SeekEoLn и SeekEoF отличаются тем, что они пропускают все пробельные символы во входном потоке, для функции SeekEoF пробельным является и символ Enter. Примеры использования этих черезвычайно полезных функций будут приведены несколько позже.

Условный оператор. Блок. Оператор выбора

Условный оператор в Паскале записывается в виде

Ifлогическое выражение Then оператор/блок

[Else оператор/блок]

Логическое выражение - это любое выражение, значение которого имеет тип Boolean, блок - это последовательность операторов, заключенная в логические скобки: Begin операторы End;. Перед Elseникогда не ставится “;”.Если значение логического выражения True, то выполняется оператор или блок, стоящий после Then, в противном случае - оператор или блок, стоящий после Else. Конструкция Else необязательна, условный оператор можно использовать и в усеченном виде, тогда при значении логического выражения False не выполняется никаких действий. Операторы, входящие в условный оператор, сами могут быть условными, т.е. допускается любая вложенность условных операторов. Запишем теперь предыдущую задачу о четырех числах, используя оператор If :

 

Var a,b,c,d : Integer;

Begin

WriteLn('Введите 4 целых числа, a,b,c и d, среди ',

'которых должно быть 2 и только 2 одинаковых!');

Read(a,b,c,d);

If (a=b) And (a<>c) And (a<>d) And (c<>d) Or (a=c) And (a<>b) And (a<>d) And (b<>d) Or (a=d) And (a<>b) And (a<>c) And (b<>c) Or (b=c) And (b<>a) And (b<>d) And (a<>d) Or (b=d) And (b<>a) And (b<>c) And (a<>c) Or (c=d) And (c<>a) And (c<>b) And (a<>b)

Then WriteLn('Вы довольно понятливы')

Else WriteLn('Вы ошиблись !!!');

ReadLn;

End.

 

Можно решить эту задачу и другим способом :

 

Var a,b,c,d : Integer;

Const num : Byte = 0;

Begin

WriteLn('Введите 4 целых числа, a,b,c и d, среди ',

'которых должно быть 2 и только 2 одинаковых!');

Read(a,b,c,d);

If a=b Then Inc(num);

If a=c Then Inc(num);

If a=d Then Inc(num);

If b=c Then Inc(num);

If b=d Then Inc(num);

If c=d Then Inc(num);

If num=1 Then WriteLn('Вы довольно понятливы')

Else WriteLn('Вы ошиблись !!!');

ReadLn;

End.

 

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

 

Var d,m : Byte;

y : Word;

Valid : Boolean;

Begin

Write('Введите дату ');

Read(d,m,y);

If (m=1)Or(m=3)Or(m=5)Or(m=7)Or(m=8)Or(m=10)Or(m=12) Then

If (d>=1)And(d<=31) Then Valid:=True

Else Valid:=False

Else

If (m=4)Or(m=6)Or(m=9)Or(m=11) Then

If (d>=1)And(d<=30) Then Valid:=True

Else Valid:=False

Else

If m=2 Then

If (d>=1)And(d<=28) Then Valid:=True

Else

If d=29 Then

If (y Mod 4=0)And(y Mod 100>0)

Or(y Mod 400=0) Then Valid:=True

Else Valid:=False

Else Valid:=False

Else Valid:=False;

If Valid Then WriteLn('Дата верна')

Else WriteLn('Дата не верна');

End.

 

Оператор выбора во многих случаях удобнее, чем условный оператор, он записывается в виде :

 

Caseвыражение Of

.................................. список значений: оператор/блок [Elseоператор/блок]

Операторы цикла

Для реализации циклических алгоритмов, т.е. алгоритмов, содержащих многократно повторяющиеся одинаковые операции, применяются специальные операторы цикла. В Паскале есть три вида циклов: For, While и Repeat. Оператор цикла For записывается в виде:

For переменная:=начальное значение To конечное значение Do оператор/блок

или

For переменная:=начальное значение DownTo конечное значение Doоператор/блок

 

Здесь переменная - любая переменная порядкового типа, называемая в таком контексте переменной цикла, начальное значение и конечное значение - выражения того же типа (исключение, как всегда, делается для разнотипных целочисленных переменных). Цикл For выполняется следующим образом: переменной цикла присваивается начальное значение, после чего выполняется тело цикла (оператор или блок, стоящий после Do). Два этих действия вместе составляют один шаг цикла. Затем переменной цикла присваивается следующее (в цикле For...To) или предыдущее (в цикле For...DownTo) значение (вспомним функции Succ и Pred) и выполняется следующий шаг цикла. Так происходит до тех пор, пока значение переменной цикла не станет больше (For...To) или меньше (For...DownTo) конечного значения. Цикл For может не выполниться ни разу, если начальное значение больше конечного в цикле For...To или меньше конечного в цикле For...DownTo. Запишем два примера использования цикла For - сначала вычислим сумму квадратов натуральных чисел от 1 до N.

 

Var i : Word;

Const

s : Real = 0;

N = 22;

Begin

For i:=1 To N Do s:=s+Sqr(i);

WriteLn('сумма=',s);

End.

 

и выведем на экран символы с номерами от 32 до 255:

 

Var c : Char;

Begin

For c:=' ' To #255 Do Write(c);

WriteLn;

End.

 

Второй тип цикла - цикл While - записывается в виде:

While логическое выражение Do оператор/блок

 

Здесь логическое выражение - любое выражение типа Boolean. Цикл выполняется следующим образом: вычисляется логическое выражение и, если оно истинно, выполняется тело цикла, в противном случае цикл заканчивается. Очевидно, что цикл While может как не выполниться ни разу, так и выполняться бесконечное количество раз (в последнем случае говорят, что программа зациклилась). Запишем две предыдущие задачи, используя цикл While:

 

Const

i : Word = 1;

s : Real = 0;

N = 22;

Begin

While i<=N Do Begin

s:=s+SQR(i);

Inc(i);

End;

WriteLn('сумма=',s);

End.

 

Var c : Char;

Begin

c:=Pred(' ');

While c<#255 Do Begin

c:=Succ(c);

Write(c);

End;

WriteLn;

End.

 

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

 

Var c : Char; Begin c:=' '; While c<=#255 Do Begin Write(c); c:=Succ(c); End; WriteLn; End.

 

зациклится?

Третий тип цикла - Repeat -записывается в виде :

 

Repeat операторы Untilлогическое выражение;

 

Если тело цикла Repeat содержит больше одного оператора, нет необходимости использовать блок, поскольку сами ключевые слова Repeat и Until являются в данном случае логическими скобками. Перед Until можно не ставить ";". Цикл Repeat выполняется так: сначала выполняется тело цикла, затем вычисляется логическое выражение и, если оно истинно, цикл заканчивается. Таким образом, цикл Repeat всегда выполняется хотя бы один раз и, так же, как и While, подвержен зацикливанию. Запишем наши примеры с помощью цикла Repeat :

 

Const

i : Word = 1;

Real = 0;

N = 22;

Begin

Repeat

s:=s+Sqr(i);

Inc(i)

Until i>N;

WriteLn('сумма=',s);

End.

 

Var c : Char;

Begin

c:=Pred(' ');

Repeat

c:=Succ(c);

Write(c)

Until c=#255;

WriteLn;

End.

 

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

В последней версии языка Паскаль появились процедуры Breakи Continue, аналогичные операторам breakи continueязыка С. Процедура Breakприводит к немедленному окончанию цикла, в котором она вызвана. Вызов процедуры Continue приводит к немедленному переходу к следующему шагу цикла. Запишем наши примеры, используя Break:

 

Const

i : Word = 1;

s : Real = 0;

N = 22;

Begin

While True Do Begin

s:=s+Sqr(i);

Inc(i);

If i>N Then Break;

End;

WriteLn('сумма=',s);

End.

 

Var c : Char;

Begin

c:=Pred(' ');

Repeat

c:=Succ(c);

Write(c);

If c=#255 Then Break

Until False;

WriteLn;

End.

 

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

 

Var c : Char;

Begin

For c:='#32 To #255 Do Begin

If(c>='А')And(c<='Я')Or(c>='а')And(c<='п')Or

(c>='р')And(c<='я') Then Continue;

Write(c);

End;

WriteLn;

End.

 

Впрочем, последнюю задачу, очевидно, можно решить проще:

 

Var c : Char;

Begin

For c:=#32 To #255 Do

If Not((c>='А')And(c<='Я')Or(c>='а')And(c<='п')Or

(c>='р')And(c<='я')) Then Write(c);

WriteLn;

End.

 

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

 

Var

Min,x : LongInt;

Count : Byte;

Begin

WriteLn(‘Введите последовательность целых чисел. Конец ввода -Enter’);

Min:=High(LongInt);

Count:=0;

While Not SeekEoLn Do Begin

{$I-}

Read(x);

If IOResult=0 Then Begin

If Min>x Then Min:=x;

Inc(Count);

End;

{$I+}

End;

If Count=0 Then WriteLn(‘Не введено ни одного числа’)

Else WriteLn(‘Введено ‘,Count,’ чисел, наименьшее из них ‘,Min);

End.

 

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

35. IOResult- возвращает 0, если последняя операция ввода-вывода завершилась успешно, и ненулевое значение в случае ошибки.

Если не задать опцию компилятора {$I-}(которая отменяет контроль за ошибками ввода-вывода), то при попытке ввода неверного значения (например, отрицательного числа) произойдет аварийное завершение программы. Отключив опцию I, мы предотвратим аварийное завершение, но ошибка все равно произойдет, и наша обязанность - обработать эту ошибку. В данном тривиальном примере для этого достаточно не учитывать значение, которое не удалось ввести. Обратите внимание, что, выключив контроль ввода-вывода в некотором фрагменте программы, мы вновь включили его, когда необходимость в этом отпала, просто отключить контроль за ошибками во всей программе и успокоиться - неправильно, тогда программа будет работать всегда, но, возможно, работать неверно.

 

Метки. Оператор Goto. Процедура Halt

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

Goto метка;

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

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

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

 

Var x : Real;

Begin

Write('Введите число ');

Read(x);

x:=Sqrt(x);

{вычисление функции от x}

End.

 

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

 

Var x : Real;

Label Finish;

Begin

Write('Введите число '); Read(x); If x<0 Then Goto Finish;

x:=Sqrt(x); {вычисление функции от x}

Finish: End.

 

Однако можно не использовать Goto :

 

Var x : Real;

Begin

Write('Введите число ');

Read(x);

If x<0 Then WriteLn('ошибка !')

Else Begin

x:=Sqrt(x);

{вычисление функции от x}

End;

End.

 

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

36. Halt(код завершения),

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

 

Var x : Real;

Begin

Write('Введите число ');

Read(x);

If x<0 Then Begin

WriteLn('ошибка !');

Halt(0);

End;

x:=Sqrt(x); {вычисление функции от x}

End.

 

Наша программа стала почти идеальной. Доведем ее до совершенства :

 

Var x : Real;

Begin

Repeat

Write('Введите неотрицательное число ');

{$I-}

Read(x);

If IOResult<>0 Then x:=-1;

{$I+}

WriteLn;

Until x>=0;

x:=Sqrt(x);

{вычисление функции от x}

End.

Интервальные типы данных. Оператор Type. Массивы

Интервальный тип - это некоторый подтип порядкового типа данных (вспомним, что порядковые типы - это ShortInt, Byte, Integer, Word, LongInt, Char и Boolean). Пусть, например, некоторая переменная в программе может принимать значения от -1 до 99. Мы могли бы описать ее как LongInt или Integer (совершенно излишне), а также как ShortInt, что достаточно разумно. Но можно создать для нее и специальный тип данных, объединяющий только числа от -1 до 99: Var x : -1..99;

Вместо имени одного из стандартных типов мы использовали в описании переменной построенный нами собственный интервальный тип. Описанная таким образом переменная x может принимать только значения -1,0,1,...,99, в остальном она ничем не отличается от других целых переменных. Ее можно вводить, выводить, использовать в качестве переменной цикла, подставлять в выражения и т.п. Любой интервальный тип есть подтип некоторого стандартного базового типа, в нашем случае - типа ShortInt. Но если бы мы стали использовать интервальный тип -1..200, то он уже был бы подтипом типа Integer, а0..200 - подтипом типа Byte. Компилятор Паскаля самостоятельно анализирует интервальные типы и подбирает для них минимальный подходящий базовый тип, это нужно знать, чтобы определять размер и способ кодировки ваших переменных. Вы можете выполнить оператор Write('переменная x:-1..99 занимает', SizeOf(x),' байт');и убедиться, что ее размер действительно равен 1.

В качестве базового типа можно использовать не только арифметические типы, но и типы Char и Boolean (правда, в последнем случае это довольно бессмысленно). Опишем, например, переменную, значением которой могут быть только маленькие латинские буквы: Var Letter : 'a'..'z';

или переменную, в которой могут храниться русские буквы: Var RusLetter : 'А'..'я';В общем случае интервальный тип описывается как

константное выражение 1.. константное выражение 2

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

Type имя типа=описание типа;

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

 

Const Tmin=-5;

Tmax=15;

Type T_Range_Type=Tmin..Tmax;

Var t:T_Range_Type;

Type T_Range_SubType=Tmin+3..Tmax-5;

Var t1:T_Range_SubType;

 

Заметим, что хороший программист всегда дает имена собственным типам, причем старается, чтобы эти имена были осмысленными.

Теперь, зная об интервальных типах, мы можем говорить о массивах. Массив во всех языках программирования - это множество индексированных (пронумерованных) однотипных элементов. В Паскале описание одномерного массива имеет вид :

Array [тип индекса] Of тип элемента

Здесь тип индекса - ShortInt, Byte, Char, Boolean или интервальный тип, тип элемента - любой тип, в т.ч. и массив. Вы заметили, что не все порядковые типы можно использовать как тип индекса, это не значит, что, например, тип Word чем-то хуже типа Byte. Такое ограничение обусловлено тем, что в Паскале никакой объект не может иметь размер больше (64 К - 2) байта или 65534 байта. Это ограничение действует и для интервальных типов; так, вы можете описать массив

Var a : Array[1..65534] Of Byte; но не массив

Var a : Array[1..65535] Of Byte;и не массив

Var a : Array[1..33000] Of Word;

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

Тип элементов массива может быть любым - целочисленным, вещественным, символьным, логическим, интервальным. Элементы массива могут быть массивами, тогда вы получите массив размерностью больше, чем 1. Опишем несколько массивов :

Var a : Array[Char] Of 1..5;- массив из 256 элементов, каждый из которых есть целое число от 1 до 5, индексы элементов изменяются от #0 до #255;

Const Max = 99;

Min = 10;

Type Nums = Min..Max;

Type ArrayType = Array[-10..0] Of Nums;

Var a : ArrayType;- массив из 11 элементов с индексами от -10 до 0, каждый элемент - целое положительное число из двух цифр;

Type IndexType = 'a'..'z';

Var a : Array[IndexType] Of Boolean;- массив из 26 элементов с индексами от 'a' до 'z', каждый элемент - логическая переменная.

В программе вы можете использовать массивы как целиком, так и отдельные их элементы. Элемент одномерного массива записывается в виде:

имя массива[ индексное выражение ]

Индексное выражение - это любое выражение соответствующего типа. Если элемент массива - не массив, то с ним можно выполнять любые операции, разрешенные для простых переменных соответствующего типа. Если значение индексного выражения неприемлемо для типа индекса, то происходит уже известная нам ошибкаRange check error: пусть, например, массив описан как Var m:Array[-3..7] Of Real; тогда обращение к элементу m[-4] или m[8] вызовет эту ошибку.

Целому массиву (всей совокупности элементов) можно лишь присваивать массив того же типа. Заметим, что, если массивы описаны в программе таким образом

Var a : Array[1..3] Of Real;

b,c,d : Array[1..3] Of Real;

Type Massiv=Array[1..3] Of Real;

Var e,f : Massiv;

g : Massiv;

h,i : Massiv;

то массивыb,c,d - однотипные и массивы e,f,g,h,i тоже однотипные, но массивы a иb (a иc, a и d) имеют разный тип, и массивы b (c,d,a) и e (f,g,h,i) имеют разный тип! Компилятор считает, что две переменные имеют один и тот же тип, только если они описаны в одном операторе через запятую либо имена их типов одинаковы. Запомните это очень важное правило.

Запишем пример программы, использующей (пока одномерные) массивы :

 

{ программа вводит массив из N целых чисел, где N не превосходит 20, и выводит его в порядке неубывания }

Const Nmax=20;

Type IndexType=1..Nmax;

Massiv=Array[IndexType] Of Integer;

Var a : Massiv;

i,j,N : IndexType;

t : Integer;

Begin

WriteLn;

Repeat

Write('Введите длину массива от 1 до ',Nmax,' ');

Read(N);

WriteLn;

Until (N>=1)And(N<=Nmax);

{ Вводим массив поэлементно }

WriteLn('Введите элементы массива');

For i:=1 To N Do Read(a[i]);

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

For i:=1 To N-1 Do

For j:=i+1 To N Do

If a[i]>a[j] Then Begin

t:=a[i];

a[i]:=a[j];

a[j]:=t;

End;

{ Выводим отсортированный массив поэлементно }

WriteLn('Результат сортировки :');

For i:=1 To N Do Write(a[i]:8);

End.

 

Обратите внимание на алгоритм перестановки двух элементов массива. Запись a[i]:=a[j]; a[j]:=a[i]; , очевидно, привела бы к неверному результату. Использованный нами алгоритм сортировки (он называется “сортировка обменами”) прост и вполне надежен, но не очень эффективен, так как выполняет много лишних операций. Не составляет труда усовершенствовать его - для каждого i от 1 до N-1 найдем наименьший из элементов ai, ai+1, ... , aN и поместим его на i-е место; такой алгоритм выполняет столько же сравнений, сколько и первоначальный, но требует существенно меньшего количества перестановок, он называется “сортировка выбором”:

 

For i:=1 To N-1 Do Begin

a_max:=a[i]; n_max:=i;

For j:=i+1 To N Do

IF a[j]<a_max Then Begin a_max:=a[j]; n_max:=j; End;

If n_max<>i Then Begin a[n_max]:=a[i];a[i]:=a_max; End;

End;

 

Как видите, запись алгоритма несколько длиннее, и потребовались две новые переменные a_max - типа Integer иn_max - типа IndexType. Это действие одного из законов программирования - из двух верных алгоритмов более эффективный, как правило, сложнее. Решим еще одну, более сложную, но и более интересную задачу: даны два упорядоченных массива X1 длиной n1 и X2 длиной n2, требуется объединить эти массивы в массив Y длиной n1+n2, не нарушая упорядоченности. Есть тривиальное, но очень плохое решение этой задачи - дописать массив X2 справа к массиву X1, а затем упорядочить полученный массив. Этот алгоритм неэффективен, так как он не использует упорядоченность массивов X1 и X2. Если мы будем пользоваться сортировкой обменами или сортировкой выбором, то потребуется порядка (n1+n2)2 действий (сравнений и обменов). Гораздо лучше использовать так называемый “алгоритм слияния“, идея которого очень проста: вначале массив Y пуст; если первый элемент X1 меньше, чем первый элемент X2, то “заберем” элемент из X1, в противном случае - из X2. Действительно, если X1[1] меньше, чем X2[1], то он является наименьшим элементом в обоих массивах. Будем поступать таким образом, пока не “заберем” все элементы обоих массивов. Если один из массивов “опустел”, то можно сразу “забрать” весь остаток второго массива. Этот алгоритм требует всего лишь порядка n1+n2 действий, очевидно, что более эффективных алгоритмов не существует (нельзя решить эту задачу, не обратившись хотя бы один раз к каждому из элементов X1 и к каждому из элементов X2, а это как раз n1+n2 действий). Запишем один из вариантов алгоритма слияния.

 

Const

n1= 100;

n2= 200;

Var

X1 : Array[1..n1] Of Word;

X2 : Array[1..n2] Of Word;

Y : Array[1..n1+n2] Of Word;

j1,j2,n : Word;

Begin

{вычисление элементов массивов X1 и X2}

For j1:=1 To n1 Do X1[j1]:=3*j1;

For j2:=1 To n2 Do X2[j2]:=2*j2;

n:=0; {массив Y пуст}

j1:=1; {текущий элемент массива X1}

j2:=1; {текущий элемент массива X2}

While n<n1+n2 Do Begin

{есть хотя бы один элемент в X1 или X2, так как Y не полон}

Inc(n); {увеличиваем индекс текущего элемента массива Y}

If(j1<=n1)And((j2>n2)Or(j2<=n2)And(X1[j1]<X2[j2]))Then Begin

{массив X1 не пуст и либо массив X2 пуст, либо текущий элемент в X1

меньше, чем текущий элемент в X2, следовательно, берем элемент из X1}

Y[n]:=X1[j1];

Inc(j1);

End

Else Begin

{в остальных случаях берем элемент из X2}

Y[n]:=X2[j2];

Inc(j2);

End;

End;

{выведем массив Y}

For n:=1 To n1+n2 Do Write(Y[n]:4);

End.

 

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

Var a : Array[1..10] Of Array[1..20] Of Real;

Переменнуюa можно рассматривать как одномерный массив одномерных массивов и использовать в программе запись видаa[i] ; но можно рассматривать и как двумерный массив вещественных чисел. Элемент этого массива записывается в программе в видеa[индексное выражение ,индексное выражение]и является переменной типаReal, например a[i+1,3]. Впрочем, можно записать и так: a[i+1][3], обе эти записи эквивалентны. Описание многомерных массивов можно записывать более компактно: вместо

Array[ t1 ] Of Array[ t2 ] Of Array ... Of t ;

можно записать

Array[ t1, t2 , ...] Of t ;

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

 

Const Nmax=20; {максимальный размер матрицы}

Type IndexType = 1..Nmax;

Matrix = Array[IndexType,IndexType] Of Real;

Var a,b,c : Matrix;

n,i,j,k : IndexType;

Begin

Write('введите размер матриц ');

Read(n);

If (n<1)Or(n>Nmax) Then Begin

WriteLn('неверный размер!');

Halt(1);

End;

WriteLn('введите матрицу A построчно ');

For i:=1 To n Do

For j:=1 To n Do Read(a[i,j]);

WriteLn('введите матрицу B построчно ');

For i:=1 To n Do

For j:=1 To n Do Read(b[i,j]);

For i:=1 To n Do

For j:=1 To n Do Begin

c[i,j]:=0;

For k:=1 To n Do c[i,j]:=c[i,j]+a[i,k]*b[k,j];

End;

WriteLn('матрица A*B :');

For i:=1 To n Do Begin

For j:=1 To n Do Write(c[i,j]);

WriteLn;

End;

End.

 

В Паскале допускаются типизированные константы - массивы, список значений элементов массива задается в круглых скобках и разделяется запятыми :

Const a : Array[‘a’..’e’] Of Byte=(1,2,3,4,5);

c : Array[0..3] Of Char=('a','b','c','d');

b : Array[-1..1] Of Boolean=(False,True,False);

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

Const c : Array[0..3] Of Char='abcd';

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

Const A : Array[1..3,1..2] Of Real = ((0,1),(2,4),(3,5));

Каким именно образом сгруппировать значения элементов, легко понять, вспомнив, что массив Array[1..3,1..2] Of Real есть на самом деле компактная запись описанияArray[1..3] Of Array[1..2] Of Real.

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

 

Процедуры и функции. Сфера действия описаний

Структура процедуры или функции очень похожа на структуру главной процедуры, она также содержит раздел описаний и раздел операторов; раздел… Procedure имя ( список параметров ) ; Здесь имя - имя процедуры (любой идентификатор), список параметров может отсутствовать, но, если он есть, записывается…

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

имя : Array Of тип; где тип - тип элемента массива (может быть любым, в том числе и массивом, но…  

Множества

Set Of тип где тип - базовый для этого множества тип, т.е. тип элементов множества.… [ подмножество , подмножество, ...]

Тип String

Тип String - это строковый тип в Паскале. Строкой называется последовательность символов. Строковыми константами мы уже неоднократно пользовались, это последовательность любых символов, заключенная в апострофы; допускаются и пустые строки, они записываются так ''. Строковые переменные и типизированные константы описываются в виде:

String

или

String [ максимальная длина]

Если максимальная длина не задана, то по умолчанию она берется равной 255. Максимальная длина при описании строковых данных задается целочисленным константным выражением и не может превышать 255. Это ограничение обусловлено самой структурой типа String : фактически строка - это массив Array [ Byte ] Of Char, причем в нулевом символе закодирована текущая длина строки. Строковые переменные могут иметь любую длину от 0 до максимальной. В программе строку можно использовать и как единый структурированный объект (чуть позже мы познакомимся с различными возможностями обработки строк), и как массив символов, т.е. обращаться к элементам строк так же, как к элементам массивов. Для строк определены следующие операции :

- строке можно присвоить строку;

- строки можно вводить процедурой ReadLn;

- строки можно выводить процедурой Write[Ln];

- для строк определена операция сцепления +, при этом вторая строка дописывается справа к первой и длина результата становится равной сумме длин операндов (если она не превосходит 255).

Запишем программу, выполняющую простейшие операции со строками :

 

Type ShortString = String[80];

Var

s1,s2 : ShortString;

s3 : String;

Begin

Write('Введите 1-ю строку ');

ReadLn(s1);

Write('Введите 2-ю строку ');

ReadLn(s2);

WriteLn('Вы ввели ',s1,' и ',s2);

WriteLn('s1+s2=',s1+s2);

s3:=s1+s1+s1;

WriteLn('s1,повторенная 3 раза ',s3);

End.

 

Обратите внимание, что при вводе строк всегда используется ReadLn, но не Read. Процедура Read в отличие от ReadLn считывает лишь символы до символа конца строки (клавишаEnter), который остается в буфере клавиатуры; таким образом, пользуясь процедурой Read, можно ввести только одну строку, все строки, вводимые вслед за первой, станут пустыми. Например, программа

 

Var s1,s2 : String;

Begin

Write('Введите 1-ю строку '); Read(s1);

Write('Введите 2-ю строку '); Read(s2);

WriteLn('Вы ввели "',s1,'" и "',s2,'"');

End.

при входном потоке abcdef Enter 123456 Enterвыведет : Вы ввели "abcdef" и "". Запишем теперь программу, которая вводит некоторую строку, заменяет в ней все цифры на пробелы и дописывает в конец строки символы три вопросительных знака:

 

Var

s : String;

L,i : Byte;

Begin

Write('Введите строку ');

ReadLn(s);

L:=Ord(s[0]);

For i:=1 To L Do

If s[i] In ['0'..'9'] Then s[i]:=' ';

For i:=L+1 To L+3 Do s[i]:='?';

WriteLn('Вот что получилось : ',s);

End.

 

Наша программа заменила цифры, но никаких “?” не добавила. Дело в том, что, обращаясь к элементам строки, невозможно изменить текущую длину строки. Второй цикл нашей программы сработал правильно, записав символы “?” в соответствующие элементы строки, но длина строки осталась прежней и процедура WriteLn вывела только символы с 1-го по L-й. Чтобы решить задачу корректно, мы могли бы добавить в программу еще один оператор Inc(s[0],3); но, конечно, лучше всего просто записать s:=s+'???';

Для обработки строк в Паскале существует несколько стандартных функций и процедур.

1. Function Length(S: String): Integer; - возвращает текущую длину строки.

2. Function Concat(S1[,S2,...,Sn]: String): String; - возвращает строку, полученную сцеплением аргументов, может использоваться вместо операции "+".

3. Function Pos(Substr: String; S: String): Byte; - возвращает номер первого слева символа строки S, начиная с которого строка Substr входит в S, если Substr не входит в S, то значение функции равно 0.

4. Function Copy(S: String; Index: Integer; Count: Integer): String; - возвращает подстроку строки S, которая начинается с символа с номером Index и имеет длину Count.

5. Procedure Delete(Var S: String; Index: Integer; Count:Integer); - удаляет из строки S подстроку, начинающуюся с символа с номером Index и имеющую длину Count.

6.Procedure Insert(Substr: String; Var S: String; Index: Integer); - вставляет в строку S подстроку Substr начиная с символа с номером Index.

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

7. Procedure Val(S: String; Var V; Var Code: Integer); - преобразует строку S в число V (если это возможно), V - любая переменная арифметического типа, переменная Code возвращает 0, если преобразование прошло успешно, или номер первого неправильного символа строки.

8. Procedure Str(X[:Width[:Decimals]];Var S:String); - преобразует произвольное арифметическое выражение X в строку S, параметры Width и Decimals позволяют форматировать строку и имеют такой же смысл, как и в процедуре Write[Ln].

Решим часто встречающуюся задачу о распаковке текста: дана строка, содержащая текст на русском языке (или на любом другом языке, в т.ч. и искусственном, вы увидите, что это не принципиально), выделить слова, содержащиеся в этом тексте. Сначала уясним, что такое текст. Текстом будем называть последовательность слов, разделенных любым количеством “пробелов“. Слова - это последовательности букв языка (в нашем случае - русских букв), “пробелы” - любые символы, не являющиеся буквами.

 

Var

s : String; {строка}

w : String; {слово}

j : Byte;

Const

Letters : Set Of Char = ['а'..'п','р'..'я','А'..'Я']; {буквы языка }

Begin

Write('Введите текст '); ReadLn(s);

j:=1;

While j<=Length(s) Do {последовательно проверяем все симвлы}

If s[j] In Letters Then Begin {встретили букву} w:=‘’; {начинаем формировать слово}

While (s[j] In Letters)And(j<=Length(s)) Do Begin

w:=w+s[j]; Inc(j); End;

{слово сформировано, теперь либо s[j] - не буква, либо строка закончилась}

WriteLn(w);

End

Else Inc(j); {пропускаем “пробел”}

End.

Обратите внимание, что во внутреннем цикле условия s[j] In Letters недостаточно, если последний символ строки - буква, поэтому необходимо продублировать условие выполнения внешнего цикла j<=Length(s) и во внутреннем цикле.

Графические средства языка Паскаль

Uses модуль , ... ; Этот оператор должен быть первым оператором в программе, в нем перечисляются… 1. Procedure InitGraph(Var GraphDriver,GraphMode: Integer; PathToDriver: String); - эта процедура инициализирует…

Особенности вещественных вычислений

тип Single: s (1 бит), p+127 (8 битов),m-1 (23 бита), тип Double: s (1 бит), p+1023 (11 битов), m-1 (52 бита), тип Extended: s (1 бит), p+16383 (15 битов), m(63 бита).

Записи

Записи - это объекты, объединяющие данные разных типов. Записи состоят из полей. Описание записи имеет вид :

Record описания полей End;

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

 

Var c : Record

Name : String[40];

Phone : String[20];

End;

Type CoordType = Record x,y : Integer; End;

Var a : Array[1..3] Of CoordType;

Type PointType =

Record

c : CoordType;

Color : Word;

End;

Var T : PointType;

Чтобы обратиться в программе к полю записи, нужно использовать составное имя: имя записи .имя поля, например: c.Name[25] , a[2].x , T.c.y. Поэтому имена полей и не обязаны быть уникальными. Поля записей можно использовать точно так же, как и простые переменные того же типа. Однотипные записи можно присваивать друг другу. Иногда полные имена полей бывают довольно громоздкими и усложняют текст программы, этого можно избежать, используя оператор присоединения With, который записывается в виде:

With имя записи Do оператор/блок

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

Const имя:тип=(имя поля:значение; имя поля:значение;...);

Опишем, например, константу типа PoinType :

Const p : PointType = (c:(x:100; y:20); Color:15);

Выведем эту константу :

WriteLn(p.c.x,p.c.y,p.Color);

или

With p Do WriteLn(c.x,c.y,Color);

или

With p.c Do WriteLn(x,y,p.Color);

Теперь решим более содержательную задачу: дано n точек на плоскости, каждая из которых покрашена в свой цвет, упорядочить точки по цвету, а точки одного цвета - по неубыванию радиус-вектора. Будем считать, что n не превосходит 100.

 

Type

CoordType = Record x,y : Real; End;

PointType = Record XY:CoordType; Color:Word; R:Real; End;

Var

p : Array[1..100] Of PointType;

Min : PointType;

n,i,j,Num : Byte;

Begin

Write('Введите количество точек ');

Read(n);

For i:=1 To n Do Begin

Write('Введите ',i:2,'-ю точку ');

With p[i] Do Read(XY.x,XY.y,Color);

End;

For i:=1 To n Do With p[i] Do

R:=Sqrt(Sqr(XY.x)+Sqr(XY.y));

For i:=1 To n-1 Do Begin

Min:=p[i];

Num:=i;

For j:=i+1 To n Do With p[j] Do

If (Color<Min.Color) Or (Color=Min.Color) And

(R<Min.R) Then Begin

Min:=p[j];

Num:=j;

End;

If Num<>i Then Begin

p[Num]:=p[i];

p[i]:=Min;

End;

End;

WriteLn('Упорядоченное множество точек :');

For i:=1 To n Do With p[i] Do WriteLn(XY.x:10:1,XY.y:10:1,Color:5);

End.

 

В Паскале записи могут содержать так называемые вариантные поля, в которых могут храниться одновременно (в одном и том же месте памяти) данные разных типов. Описание вариантного поля имеет вид:

 

Case тип Of

константа 2 : (описание поля); ..................................  

Модуль Crt

Var TextAttr : Byte

1. Function KeyPressed : Boolean - возвращает True, если буфер клавиатуры не пуст (все нажатия клавиш во время работы программы накапливаются в… 2. Function ReadKey : Char - считывает символ из буфера клавиатуры, если буфер… 3. Procedure Delay(MS: Word) - приостанавливает выполнение программы на MS миллисекунд.

Модули. Создание и использование модулей

Наряду со стандартными модулями Паскаля вы можете создавать и использовать в программах свои собственные модули. Модуль имеет следующую структуру:

 

Unitимя модуля;

Interface

интефейсная часть

Implementation

внутренняя часть

Begin

исполняемая часть

End.

 

Имя модуля - идентификатор длиной не более 8 символов, причем файл, содержащий модуль, должен иметь такое же имя. После ключевого слова Interface располагаются описания типов, констант, переменных, функций и процедур, которые будут доступны пользователю этого модуля. Ключевое слово Implementationоткрывает внутреннюю часть модуля. В ней должны быть записаны все процедуры и функции, заголовки которых есть в интерфейсной части. Кроме того, во внутренней части можно описывать и другие переменные, константы, типы, функции и процедуры, но они уже будут недоступны другим программам. Исполняемая часть модуля может содержать обычные операторы, которые выполняются до начала выполнения программы, использующей этот модуль. Но, как правило, исполняемая часть пустая (а можно вообще не записывать слово Begin). Любой модуль может использовать другие модули как в интерфейсной, так и во внутренней части, но следует избегать перекрестных ссылок, когда модуль А использует модуль Б, а Б использует А. Напишем небольшой модуль.

 

Unit Service; {исходный текст модуля должен находиться в файле Service.pas}

Interface {интерфейсная часть модуля, константы OK и Error, переменная Result и процедуры DrawWindow и PrintString доступны любой программе, в которой есть оператор Uses Service}

Const

OK=0;

Error=-1;

Var

Result:ShortInt; {переменная возвращает значение OK или Error}

Procedure DrawWindow(x1,y1,x2,y2,BkColor:Byte); {процедура рисует на экране окно}

Procedure PrintString(x,y,BkColor,Color:Byte; s:String); {процедура выводит строку на экран}

Implementation {внутренняя часть модуля}

Uses Crt;

Var xSize,ySize : Byte;

{переменные, в которых хранятся размеры текущего окна}

Procedure Clear;

{внутренняя процедура, недоступная пользователям модуля}

Begin

TextAttr:=$07;

Window(1,1,80,25);

ClrScr;

End;

Procedure DrawWindow;

{во внутренней части список параметров указывать не обязательно}

Begin

If (x1<1)Or(x1>79)Or(x2<x1)Or(x2>80)Or

(y1<1)Or(y1>24)Or(y2<y1)Or(y2>25) Then Begin

{координаты окна неверны}

Result:=Error;

Exit;

End;

Window(x1,y1,x2,y2);

xSize:=x2-x1+1;

ySize:=y2-y1+1;

TextBackground(BkColor);

ClrScr;

Result:=OK; {вывод окна завершен удачно}

End;

Procedure PrintString;

Begin

If (x<1)Or(x>xSize)Or(y<1)Or(y>ySize) Then Begin

{координаты выводимой строки неверны}

Result:=Error;

Exit;

End;

GotoXY(x,y);

TextBackground(BkColor);

TextColor(Color);

Write(s);

Result:=OK; {вывод строки завершен удачно}

End;

Begin

{исполняемая часть модуля - экран будет очищен, прежде чем начнется выполнение программы}

Clear;

End.

 

Если откомпилировать этот модуль, то будет создан файл с именем SERVICE.TPU, который впоследствии и будут использовать наши программы (расширение TPU означает Turbo Pascal Unit). Например:

 

Uses Service;

Begin

Randomize;

Repeat

DrawWindow (1+Random(80), 1+Random(25),

1+Random(80), 1+Random(25), Random(8));

Until Result=OK;

Repeat

PrintString(1+Random(80),1+Random(25),

Random(8),Random(16),'OK');

Until Result=OK;

End.

Файлы

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

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

1. Assign(Var f:Text; Name:String),

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

2. Reset(Varf : Text) - открывает файл для чтения;

3. Rewrite(Varf : Text) - открывает файл для записи;

4. Append(Var f : Text) - открывает файл для записи в конец файла. Процедуры Reset и Append выполняются только для существующих файлов, процедура Rewrite - для любых файлов, но если файл существует, он будет уничтожен и создан заново. Чтение из файла и запись в файл выполняются процедурамиRead[Ln] и Write[Ln], но перед списком ввода или вывода указывается файловая переменная:

5. Read[Ln](Var f : Text; список ввода).

6. Write[Ln](Var f : Text;список вывода).

Списки ввода и вывода строятся точно так же, как и в случае ввода с клавиатуры и вывода на экран. Особенностью текстовых файлов является то, что они состоят из строк, каждая из которых заканчивается символом конца строки. Процедура WriteLnзаписывает в файл этот символ, а процедура Write- нет. Вы можете сами управлять длинами записываемых строк, в нужный момент вызывая процедуруWriteLn. При вводе следует помнить, что если символ конца строки не считан процедурой ReadLn, то следующая строка недоступна. Как правило, текстовый файл используется для хранения строк или символов, но можно держать там и числа, ввод чисел из текстового файла осуществляется так же, как и с клавиатуры, то есть файл должен содержать правильные числовые константы, разделенные пробелами или символами конца строки. При выводе чисел в текстовый файл их можно форматировать так же, как при выводе на экран. Для текстовых файлов определены четыре логические функции:

7. Function EoLn(Var f : Text):Boolean - возвращает True, если при чтении достигнут конец строки.

8. Function EoF(Var f : Text):Boolean - возвращает True, если при чтении достигнут конец файла.

9. Function SeekEoLn(Var f : Text):Boolean - возвращает True, если в текущей строке остались только пробельные символы.

10. Function SeekEoF(Var f : Text):Boolean - возвращает True, если в файле нет больше ничего, кроме пробельных символов. ФункцияEoLn пригодится вам, если вы читаете из текстового файла символы, функция EoF - если вы читаете символы или строки, а функции SeekEoLn и SeekEoF необходимы при вводе чисел из текстового файла. Текстовый файл, открытый для чтения, можно усекать процедурой

11. Procedure Truncate(Var f:Text) -

эта процедура уничтожает весь непрочтенный остаток файла. Файл закрывается процедурой

12. Procedure Close(Var f:Text),

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

13.Procedure Erase(Varf).

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

 

 

Var

f : Text;

s : String;

Const Name='test.pas';

Begin

Assign(f,Name);

Reset(f);

While Not EoF(f) Do Begin

ReadLn(f,s);

WriteLn(s);

End;

End.

 

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

 

Var

f : Text;

c : Char;

Const Name='test.pas';

Begin

Assign(f,Name);

Reset(f);

While Not EoF(f) Do Begin

Read(f,c);

Write(c);

End;

End.

 

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

 

Var

f 1,f2 : Text;

x : Real;

Const

Name1='num.txt';

Name2=‘res.txt’;

Begin

Assign(f1,Name1);

Reset(f1);

Assign(f2,Name2);

Rewrite(f2);

While Not SeekEoF(f1) Do Begin

Read(f1,x);

WriteLn(f2,x:10);

End;

Close(f1); {файлы, открытые процедурой Reset, закрывать не обязательно, но аккуратный программист делает это}

Close(f2); {файлы, открытые процедурой Rewrite или Append, обязательно должны быть закрыты, в противном случае записанная туда информация может не сохраниться на диске}

End.

 

Второй тип файлов - типизированные файлы. Файловая переменная описывается в этом случае как File Of тип; где тип - любой тип, кроме файлового. Считается, что типизированный файл содержит некоторое количество записей одного и того же типа. Читать и записывать в такой файл можно только данные этого типа. В отличие от текстовых файлов типизированные допускают прямой доступ, т.е. вы можете записывать в любое место файла и читать из любого места файла. Процедура Assign применяется для типизированных файлов точно так же, как и для текстовых. Типизированный файл можно открыть процедурами Reset и Rewrite (процедура Appendнеприменима!), в обоих случаях файл доступен и для чтения, и для записи. Процедуру Reset следует применять для существующих файлов, а Rewrite - для новых файлов. ПроцедурыTruncateи Close работают точно так же, как и для текстовых файлов. Чтение и запись в типизированный файл осуществляется процедурами Read и Write (ReadLn и WriteLn не имеют смысла). Но в списках ввода и вывода можно записывать только переменные соответствующего типа. Функция EoF применима для типизированных файлов, а EoLn - нет. Прямой доступ к файлу осуществляется с помощью процедур FileSize, FilePos и Seek.

14. Procedure FileSize(Var f): LongInt - возвращает текущий размер файла в записях, размер файла в байтах можно получить, умножив эту величину на размер одной записи.

15. Procedure FilePos(Var f): LongInt- возвращает текущее значение файлового указателя. Файловый указатель хранит текущий адрес в файле, начиная с которого будет выполняться очередная операция ввода или вывода. При каждой операции ввода-вывода файловый указатель автоматически смещается на количество введенных или выведенных записей.

16. Procedure Seek(Var f; n : LongInt); - устанавливает новое значение файлового указателя. Значение файлового указателя равно номеру последней обработанной записи, поэтому номер текущей записи будет равен n+1. Таким образом, чтобы установить указатель на первую запись, необходимо выполнить Seek(f,0), а на последнюю - Seek(f,FileSize(f)-1). Запишем программу, которая работает с типизированным файлом:

 

Var

f : File Of Real;

i,n : Byte;

r : Real;

Begin

Assign(f,'TMP');

Rewrite(f);

Randomize;

n:=Random(100)+1; { количество записей в файле }

For i:=1 To n Do Begin

r:=Sqrt(i);

Write(f,r);

End;

WriteLn('Размер файла=',FileSize(f));

i:=Random(n);

Seek(f,i);

Read(f,r);

WriteLn('Запись номер ',FilePos(f),' содержит ',r);

Close(f);

End.

 

Третий тип файлов в Паскале - бинарные файлы. Бинарные файлы рассматриваются как последовательности байтов и могут содержать любые данные. Файловая переменная в этом случае должна иметь типFile. Бинарный файл открывается процедурами

17. Procedure Reset(Var f : File; RecSize: Word);

18. Procedure Rewrite(Var f :File; RecSize: Word);

Второй параметр RecSize - это длина записи в байтах. Ввод-вывод в бинарный файл можно осуществлять порциями, кратными длине записи. Если при открытии файла задать длину записи в 1 байт, то такой файл сможет содержать любые данные. Для бинарных файлов также определены процедуры Close, FileSize, FilePos и Seek. Но чтение и запись осуществляются специальными процедурами:

19. Procedure BlockRead(Var f:File; Var Buf; Count:Word [;VarRes:Word]);

20. Procedure BlockWrite(Var f:File; Var Buf; Count:Word [;Var Res:Word]);

Здесь Buf - любая переменная, Count - количество вводимых или выводимых записей, Res - выходной параметр, возвращающий количество введенных или выведенных записей. Последний параметр необязателен, но в некоторых случаях его использование очень полезно. Запишем предыдущую программу, используя бинарный файл:

 

Var

f : File;

i,n : Byte;

r : Real;

Begin

Assign(f,'TMP');

Rewrite(f,SizeOf(Real));

Randomize;

n:=Random(100)+1; { количество записей в файле }

For i:=1 To n Do Begin

r:=Sqrt(i);

BlockWrite(f,r,1);

End;

WriteLn('Размер файла=',FileSize(f));

i:=Random(n);

Seek(f,i);

BlockRead(f,r,1);

WriteLn('Запись номер ',FilePos(f),' содержит ',r);

Close(f);

End.

 

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

 

Var

Source,Target : File;

Buf : Array[1..64000] Of Byte; {большой массив - буфер}

Result : Word;

Const

SourceName='TEST.PAS';

TargetName='COPY.BIN';

Begin

Assign(Source,SourceName);

Reset(Source,1);

Assign(Target,TargetName);

Rewrite(Target,1);

Repeat

{читаем из исходного файла как можно больше информации}

BlockRead(Source,Buf,SizeOf(Buf),Result);

{записываем в новый файл столько, сколько удалось прочесть}

BlockWrite(Target,Buf,Result);

{прекращаем чтение-запись, когда прочитано меньше, чем умещается в буфере, это значит, что в исходном файле больше ничего нет}

Until Result<SizeOf(Buf);

WriteLn('OK...,см. файл "',TargetName,'"');

Close(Source);

Close(Target);

End.

Другие средства обработки файлов и модуль DOS

  Var Name : String[12];

Type SearchRec=Record

Attr : Byte; Time : LongInt; Size : LongInt;

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

Type имя типа=Procedure(список параметров); Описание процедурного типа отличается от заголовка процедуры только… {$F+} Procedure A(x:Real; c:Char); Begin...End; {$F-},

Указатели и динамическая память

  Var b : Byte;

Динамические структуры: списки, деревья

Каждый элемент такого списка можно рассматривать как совокупность двух полей -…

Type

Adres = ^Element;

Element = Record Body :тип; Next : Adres; End;

В этом случае язык Паскаль допускает использование при описании типа Adres еще не описанного идентификатора Element. Но оба типа должны быть описаны в одном операторе Type . Следующая запись синтаксически ошибочна:

Type Adres = ^Element;

Type Element = Record Body :тип; Next : Adres; End;

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

Type Element = Record Body : тип; Next : Pointer; End;

Теперь мы легко сможем описать элементы двусвязного списка и бинарного дерева :

Type Adres2 = ^Element2;

Element2 = Record

Body :тип; Previous,Next : Adres2;

End;

Type Adres_Tree = ^Element_Tree;

Element_Tree = Record

Body:тип;[Up,]Left,Right: Adres_Tree; End;

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

 

Type

P_Stack = ^T_Satck;

T_Stack = Record

Num : Real;

Next : Adres;

End;

Var

Top,p : P_Stack;

Num : Real;

Begin

Top:=Nil;

While Not SeekEoLn Do Begin

Read(Num);

New(p);

p^.Num:=Num;

p^.Next:=Top;

Top:=p;

End;

{ теперь выведем полученный список }

p:=Top;

While p<>Nil Do Begin

WriteLn(p^.Num);

p:=p^.Next;

End;

End.

 

В этой программе список формируется по принципу стека - чем раньше введен элемент, тем глубже он находится в списке. Такие структуры данных часто называют LIFO-структурами (от английской фразы Last In First Out: последним вошел - первым вышел). Если в решаемой задаче порядок элементов в списке важен, то такой способ формирования списка не годится. Запишем другой алгоритм.

 

Type

P_Queue = ^T_Queue;

T_Queue = Record Num : Real; Next : T_Queue; End;

Var

Top,p,p0 : Adres;

Num : Real;

Begin

Top:=Nil;

While Not SeekEoLn Do Begin

Read(Num);

New(p);

p^.Num:=Num;

If Top=Nil Then Top:=p Else p0^.Next:=p;

p0:=p;

End;

p^.Next:=Nil;

p:=Top;

While p<>Nil Do Begin

WriteLn(p^.Num);

p:=p^.Next;

End;

End.

 

В нем список формируется по принципу очереди и является FIFO-структурой (First In First Out). Выполним несколько простейших операций с нашим списком. Найдем сумму чисел, содержащихся в списке:

 

S:=0;

p:=Top;

While p<>Nil Do Begin

S:=S+p^.Num;

p:=p^.Next;

End;

 

Упорядочим список по неубыванию чисел:

 

p1:=Top;

While p1^.Next<>Nil Do Begin

p2:=p1^.Next;

While p2<>Nil Do Begin

If p1^.Num>p2^.Num Then Begin

Num:=p1^.Num;

p1^.Num:=p2^.Num;

p2^.Num:=Num;

End;

p2:=p2^.Next;

End;

p1:=p1^.Next;

End;

 

Найдем наименьший элемент списка и удалим его:

 

p:=Top;

Min:=1.7E38;

While p<>Nil Do Begin

If p^.Num<Min Then Begin

Min:=p^.Num;

MinAdr:=p;

End;

p:=p^.Next;

End;

{мы нашли адрес наименьшего элемента, но, поскольку наш список односвязный, необходимо еще найти адрес предыдущего элемента}

If MinAdr<>Top Then Begin

p:=Top;

While p^.Next<>MinAdr Do p:=p^.Next;

End;

{теперь можем удалять}

If MinAdr=Top Then Top:=Top^.Next

Else p^.Next:=MinAdr^.Next;

Dispose(MinAdr);

 

Найдем наименьший элемент списка и вставим после него число 0:

 

p:=Top;

Min:=1.7E38;

While p<>Nil Do Begin

If p^.Num<Min Then Begin

Min:=p^.Num;

MinAdr:=p;

End;

p:=p^.Next;

End;

New(p);

p^.Num:=0;

p^.Next:=MinAdr^.Next;

MinAdr^.Next:=p;

 

Уничтожим весь список:

 

While Top<>Nil Do Begin

p:=Top^.Next;

Dispose(Top);

Top:=p;

End;

 

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

Открытые строки

Открытыми строками, или длинными строками, или C-строками, называются символьные последовательности длиной до 65535 символов, ограниченные справа… 1. Function StrNew(Str: PChar): PChar; - размещает в хипе копию строки Str и… 2. Function StrDispose(Str: PChar); - освобождает место в хипе, отведенное под строку Str .

Использование командной строки и вызов внешних программ

Function ParamCount: Word - возвращает номер последнего заданного при запуске программы параметра. Параметры разделяются в командной строке… Function ParamStr(n:Word): String - возвращает n-й параметр или пустую строку,…  

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

Переменная ExitProc типа Pointer может содержать адрес процедуры, которая будет обрабатывать программные прерывания. Эта процедура должна иметь…   Procedure MyExitProc; Far;

Объекты

Данные в объекте называются полями, а процедуры и функции - методами. Объектный тип описывается в виде:

Type имя типа=Object

Поля объектов описываются так же, как поля записей, а описание метода - это заголовок процедуры или функции. Сами методы располагаются в программе… имя экземпляра объекта .имя поля/метода либо оператор присоединенияWith имя экземпляра объекта, внутри которого можно записывать простые имена полей и…

Рекурсия и динамическое программирование

  Function Fibonacci_Recursive(n:Word):LongInt; Begin

Рекурсия и стек отложенных заданий

  Procedure Moving(i{количество перемещаемых дисков}, m{откуда перемещаются},… Var s : Word;

Стеки и очереди

  Type T_Num_Stack = Array[1..100] Of LongInt; {В этой программе будем хранить стек в массиве}

Комбинаторные алгоритмы

  Procedure SubSets_Recursive(n,Last:Byte; S:T_Set); {n - количество элементов, Last - наибольший элемент в текущем подмножестве, S - само это подмножество}

Бинарные деревья

Тогда его префиксная запись - abdecfg, постфиксная запись - debfgca и…

Упорядоченные бинарные деревья и приоритетные очереди

 

Алгоритмы сортировки

Сортировка “пузырьком” - также довольно простой и широко известный алгоритм. Он заключается в следующем: сравниваем X[1] и X[2], если X[1] <…   Procedure Bubble_Sorting(n1,n2 : Word; Var x : T_Array);

Графы

В этом разделе мы рассмотрим некоторые алгоритмы обработки графов: поиск в глубину, поиск в ширину, метод ветвей и границ, топологическую сортировку, “волновой алгоритм” и алгоритм Дейкстры. Во всех примерах предполагается, что граф задан матрицей смежности, в которой элемент с индексами i,j равен 1, если вершины i и j смежны, и равен 0 в противном случае. Если граф ориентированный, то матрица не симметрична, для взвешенного графа элементы матрицы могут быть произвольными положительными числами или нулями. Вершины графа пронумерованы натуральными числами от 1 до n.

Поиск в глубину, или обход графа в глубину - это префиксный обход универсального покрытия графа. Универсальным покрытием называют дерево, которое получается следующим образом: в качестве корня выбирают произвольную вершину графа, вершинами первого уровня становятся все вершины графа, смежные с корневой вершиной, вершинами второго уровня - все вершины, смежные с вершинами первого уровня, за исключением самих этих вершин, и так далее. Если граф не связен, то универсальное покрытие можно построить для каждой из компонент связности. Каждая вершина графа входит в универсальное покрытие только один раз. Конечно, универсальное покрытие можно построить не единственным образом, даже если зафиксировать корневую вершину. Алгоритм поиска в глубину довольно просто получается из рекурсивного алгоритма префиксного обхода дерева, нужно только учесть, что универсальное покрытие не является бинарным деревом, и запоминать в специальном множестве все обойденные вершины, чтобы предотвратить зацикливание. В приведенной ниже процедуре n - количество вершин в графе, G- матрица смежности, Start - корневая вершина, Used - множество пройденных вершин.

 

Procedure Pass_To_Depth_Recursive {Рекурсивный обход в глубину}

(n:Byte; Var G:T_Graf_Matrix; Start:Byte; Var Used:T_Set);

Var i : Byte;

Begin

Write(Start,'-');

Used:=Used+[Start];

For i:=1 To n Do

If Not(i In Used)And(G[Start,i]>0) Then Pass_To_Depth_Recursive(n,G,i,Used);

End;

 

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

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

 

Procedure Pass_To_Width(n:Byte; G:T_Graf_Matrix; Start:Byte); {Нерекурсивный обход в ширину}

Var

i,t : Byte;

Used : T_Set;

Q : Array[0..N_max-1] Of Byte;

Top,Len: Byte;

Begin

Used:=[];

Len:=1;

Top:=1;

Q[1]:=Start;

While Len>0 Do Begin

t:=Q[Top];

Top:=(Top+1)Mod N_Max; Dec(Len);

If t In Used Then Continue;

Write(t,'-');

Used:=Used+[t];

For i:=1 To n Do

If Not(i In Used)And(G[t,i]>0) Then Begin

Inc(Len);

Q[(Top+Len-1)Mod N_Max]:=i;

End;

End;

End;

 

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

 

Procedure Topological_Sorting(n:Byte; G:T_Graf_Matrix);{Топологическая сортировка орграфа, проверяет отсутствие циклов.}

Var

i,j : Byte;

Used : T_Set;

Source,Flag : Boolean;

Begin

Used:=[]; {множество уже отсортированных вершин}

While Used<>[1..n] Do Begin

Flag:=False;{флажок означает : множество отсортированных вершин увеличилось на данном шаге цикла}

For i:=1 To n Do

If Not(i In Used) Then Begin

{вершина i еще не отсортирована}

Source:=True;

{проверяем, является ли эта вершина "источником", то есть проверяем отсутствие еще не отсортированных вершин, из которых в вершину i входят дуги}

For j:=1 To n Do

If (G[j,i]>0)And Not(j In Used) Then Begin

Source:=False;

Break;

End;

If Source Then Begin

{вершина i - "источник", добавляем ее в множество отсортированных вершин}

Flag:=True;

Used:=Used+[i];

Write(i,'>>>');

End;

End;

If Not Flag Then Begin

{множество отсортированных вершин не увеличилось, но есть еще не отсортированные вершины, следовательно, в графе есть циклы}

WriteLn('Есть цикл');

Exit;

End;

End;

End;

 

Теперь рассмотрим одну из наиболее важных практических задач - поиск кратчайшего пути между двумя заданными вершинами графа. Сначала решим ее уже знакомым нам методом ветвей и границ. Алгоритм метода ветвей и границ легко получается из алгоритма поиска в глубину. В приведенной ниже процедуре Start - это текущая вершина графа (при первом обращении к процедуре она равна начальной вершине пути),Finish - конечная вершина пути, ее значение не изменяется, Len - текущая длина пути, Path - текущий путь (одномерный массив, в котором записываются номера вершин, составляющих путь), Used - множество вершин, входящих в текущий путь, MinLen - длина минимального пути, найденного к данному моменту, и MinPath - текущий минимальный путь.

 

Procedure Min_Path_in_Graf_Recursive

(n:Byte; Var G:T_Graf_Matrix; Start,Finish:Byte; Len:Byte; Path:T_Path; Used:T_Set; Var MinLen:Byte; Var MinPath:T_Path);

{Поиск кратчайшего пути между двумя заданными вершинами графа. Рекурсивный алгоритм - метод ветвей и границ}

Var i : Byte;

Begin

Inc(Len); {длина текущего пути увеличивается на 1}

If Len>=MinLen Then Exit; {если текущий путь не короче, чем минимальный из уже найденных, то продолжать рекурсию нет необходимости, какой бы путь мы ни нашли, он будет длиннее}

Path[Len]:=Start; {запоминаем очередную вершину пути}

Include(Used,Start);

If Start=Finish Then Begin

{путь достиг конечной вершины, этот путь обязательно минимальный среди всех найденных, иначе мы бы здесь не оказались, запоминаем новый минимальный путь}

MinLen:=Len;

MinPath:=Path;

Exit;

End;

For i:=1 To n Do {продолжаем поиск в глубину}

If Not(i In Used) Then

If G[Start,i]>0 Then

Min_Path_in_Graf_Recursive

(n,G,i,Finish,Len,Path,Used,MinLen,MinPath);

End;

 

В нерекурсивной записи этого алгоритма используется стек отложенных заданий. Операторы If Len>=MinLen Then Exit; и If Not(i In Used) Then... составляют суть метода ветвей и границ - с их помощью мы отсекаем ненужные ветви универсального покрытия. Слово “ветвей” в названии метода означает обход ветвей дерева решений (здесь - универсального покрытия графа), а слово “границ” означает, что ветви, заведомо не содержащие нужных решений, отсекаются и не обходятся. Метод ветвей и границ - довольно дорогой алгоритм, в худшем случае он имеет сложность n! . Известны алгоритмы меньшей сложности, мы рассмотрим здесь более быстрый волновой алгоритм со сложностью n3. Идея алгоритма заключается в следующем. Пометим конечную вершину пути числом 1. Затем пометим все вершины, смежные с конечной, числом 2. Затем пометим все еще не помеченные вершины, смежные хотя бы с одной вершиной, помеченной двойкой, числом 3. Будем поступать так до тех пор, пока или не окажется помеченной начальная вершина пути, или не выяснится, что не удалось пометить ни одной новой вершины. Во втором случае искомого пути не существует - начальная и конечная вершины не принадлежат одной компоненте связности. Если начальная вершина помечена, то ее метка - длина минимального пути; если в задаче не требуется найти сам путь, а лишь его длину, то алгоритм на этом завершается. Если сам путь (последовательность вершин) нужен, то найдем его так: начальная вершина известна, пусть она помечена числом k, следующая вершина - это любая вершина, помеченная числом k-1 и смежная с начальной, следующая вершина - любая вершина, помеченная числом k-2 и смежная со второй вершиной пути, и так далее. Волновой алгоритм требует выполнения не более n шагов, и на каждом шаге выполняется Сn2 операций, следовательно, его сложность n3 даже в худшем случае. Нетрудно заметить, что волновой алгоритм похож на алгоритм поиска в ширину.

 

Procedure Min_Path_in_Graf_Wave

(n:Byte; G:T_Graf_Matrix; Start,Finish:Byte; Var Len:Byte; Var Path:T_Path);

{Поиск кратчайшего пути между двумя заданными вершинами графа. Волновой алгоритм. }

Var

i,j,Count : Byte;

T : T_Path;

Flag,OK : Boolean;

Begin

FillChar(T,SizeOf(T),0);

Len:=1; {текущее значение метки}

T[Finish]:=Len;

{в массив T записываются метки вершин, 0 означает непомеченную вершину}

If Start=Finish Then Exit;

OK:=False; {OK=True, если путь найден}

Repeat

Flag:=False;

{Flag=True, если на данном шаге удалось пометить хотя бы одну вершину}

For i:=1 To n Do Begin

If T[i]=Len Then Begin

{вершина i помечена на предыдущем шаге, ищем непомеченные вершины, смежные с ней}

For j:=1 To n Do

If (T[j]=0)And(G[j,i]>0) Then Begin

T[j]:=Len+1;

{помечаем новую вершину}

Flag:=True;

If j=Start Then Begin

OK:=True;

{путь найден}

Break;

End;

End;

End;

If OK Then Break;

End;

If OK Then Break;

Inc(Len);

Until Not Flag;

If Not OK Then Begin {путь не найден}

Len:=n+1;

Exit;

End;

Len:=T[Start];

{формируем последовательность вершин, составляющих минимальный путь}

i:=1;

Path[i]:=Start;

Count:=Len;

While Count>1 Do Begin

j:=1;

While (T[j]<>Count-1)Or(G[Path[i],j]=0) Do Inc(j);

Inc(i);

Path[i]:=j;

Dec(Count);

End;

End;

 

Приведенные алгоритмы ищут кратчайший и в неориентированном, и в ориентированном графе. Если в графе каждому ребру (дуге) приписан некоторый вес - неотрицательное число, то такой граф называют взвешенным графом, или сетью, или системой дорог. Мы будем использовать последний термин. Вершины в системе дорог называют городами, а ребра - дорогами. Для нахождения кратчайшего пути между двумя городами можно использовать метод ветвей и границ почти в том же самом виде, что и в процедуре Min_Path_in_Graf_ Recursive, только длина пути будет определяться не количеством вершин, а суммой длин входящих в него дорог. Такой алгоритм будет по-прежнему иметь сложность n! и, следовательно, будет неэффективным при больших n. Другой способ решения этой задачи предоставляет алгоритм Дейкстры, имеющий сложность n2. Этот алгоритм использует дополнительную память, размер которой пропорционален n2. В списке городов для каждого города, кроме начального, будем хранить минимальный путь к нему из начального города и длину этого минимального пути. Сначала для всех городов, смежных с начальным, записывается путь, состоящий из одного начального города, и длина, равная длине дороги из начального города. Для городов, не смежных с начальным, записывается пустой путь и бесконечно большая длина пути. На первом шаге находят город, у которого длина пути минимальна, он является ближайшим городом к начальному, пусть это город M. Затем для всех городов K, смежных с M, проверяют, нельзя ли “проехать в город быстрее” через город M. Для этого сравнивают длину пути, записанную для города K, и сумму длины пути, записанной для города M, и длины дороги из M в K. Если путь к K через M короче, то заменяют путь, записанный для K, на путь, записанный для M, плюс сам город M и меняют текущую длину пути. Проделав это для всех городов K, удаляют город M из списка городов, он больше не потребуется. Алгоритм заканчивается, когда ближайшим городом оказывается конечный город или минимальная длина пути оказывается равной бесконечности. В последнем случае пути из начального города в конечный не существует.

 

Procedure Min_Path_in_Net_Dijkstra

(n:Byte; G:T_Net_Matrix; Start,Finish:Byte; Var Len:Byte; Var Dist:LongInt;

Var Path:T_Path);

{Поиск кратчайшего пути между двумя заданными городами системы дорог. Алгоритм Дейкстры}

Var

NotUsed : T_Set;

TmpLen : T_Path;

TmpDist : Array[1..N_max] Of LongInt;

{массив минимальных расстояний}

TmpPath: Array[1..N_max] Of T_Path; {массив минимальных путей}

j,Jmin : Byte;

Min : LongInt;

 

Begin

If Start=Finish Then Begin

Len:=1;

Dist:=0;

Path[1]:=Start;

Exit;

End;

NotUsed:=[1..n]-[Start]; {множество городов, остающихся в списке}

For j:=1 To n Do If j<>Start Then {инициализируем список городов}

If G[Start,j]>0 Then Begin

TmpLen[j]:=1;

TmpDist[j]:=G[Start,j];

TmpPath[j][1]:=Start;

End

Else

TmpDist[j]:=High(LongInt);

Repeat

Min:=High(LongInt);{ищем минимальную длину пути}

Jmin:=0;

For j:=1 To n Do

If j In NotUsed Then

If TmpDist[j]<Min Then Begin

Min:=TmpDist[j];

Jmin:=j;

End;

If Jmin=0 Then Begin {пути не существует}

Dist:=High(LongInt);

Exit;

End;

If Jmin=Finish Then Begin {конечный город - ближайший}

Len:=TmpLen[Jmin]+1;

Dist:=TmpDist[Jmin];

Path:=TmpPath[Jmin];

Path[Len]:=Jmin;

Exit;

End;

NotUsed:=NotUsed-[Jmin];

{удаляем ближайший город из списка}

For j:=1 To n Do {изменяем содержимое списка городов}

If (j In NotUsed) And (G[Jmin,j]>0) And

(TmpDist[j]>Min+G[Jmin,j])Then Begin

TmpDist[j]:=Min+G[Jmin,j];

TmpLen[j]:=TmpLen[Jmin]+1;

TmpPath[j]:=TmpPath[Jmin];

TmpPath[j,TmpLen[j]]:=Jmin;

End;

Until False;

End;

 

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

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

РЕКОМЕДУЕМАЯ ЛИТЕРАТУРА

1. Ахо А., Хопкрофт Дж.., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

2. Вирт Н. Систематическое программирование. Введение. М.: Мир, 1977.

3. Вирт Н. Алгоритмы + структуры данных = программы. М.: Мир. 1985.

4. Гринбаум О.Н., Фитиалов С.Я. Информатика. Элементы теории программирования. СПБ.: Изд-во С.-Петербургского ун-та. 1997.

5. Грис Д. Наука программирования. М.: Мир. 1984.

6. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир. 1982.

7. Дал У., Дейкстра Э., Хоар К. Структурное программирование. М.: Мир. 1975.

8. Дейкстра Э. Дисциплина программирования. М.: Мир. 1978.

9. Кнут Д. Искусство программирования для ЭВМ. Т.1-3. М.: Мир. 1978.

10. Кушниренко А.Г., Лебедев Г.В. Программирование для математиков. М.: Наука. 1988.

11. Липский В. Комбинаторика для программистов. М.: Мир. 1988.

12. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир. 1980.

13. Фаронов В.В. Основы Турбо-Паскаля. М.:МВТУ-Фесто дидактик. 1992

14. Фаронов В.В. Паскаль и Windows. М.:МВТУ-Фесто дидактик. 1995

15. Холл П. Вычислительные структуры. М.:Мир. 1978.

16. Шень А. Программирование: теоремы и задачи.

МЦНМО. 1995.


 

Содержание

От автора 3

1. Общая схема решения задачи на персональном компью-

тере 4

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

3. Арифметические типы данных. Числовые константы и

переменные. Оператор присваивания. Выражение 8

4. Операторы ввода-вывода 14

5. Арифметические операции. Стандартные математи-

ческие функции 18

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

7. Логический тип данных. Операции сравнения. Логичес-

кие операции 28

8. Условный оператор. Блок. Оператор выбора 31

9. Операторы цикла 35

10 .Метки. Оператор Goto. Процедура Halt 42

11. Интервальные типы данных. Оператор Type. Массивы 44

12. Процедуры и функции. Сфера действия описаний 53

13. Открытые массивы и нетипизированные параметры 60

14. Множества 66

15. Тип String 69

16. Графические средства языка Паскаль 74

17. Особенности вещественных вычислений 84

18. Записи 92

19. Тип "перечисление" 96

20. Модуль Crt 96

21. Модули. Создание и использование модулей 101

22. Файлы 104

23. Другие средства обработки файлов и модуль DOS 111

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

25. Указатели и динамическая память 119

26. Динамические структуры : списки, деревья 125

27. Открытые строки 131

28. Использование командной строки и вызов внешних

программ 136

29. Обработка программных прерываний 139

30. Объекты 142

31. Рекурсия и динамическое программирование 150

32. Рекурсия и стек отложенных заданий 154

33. Стеки и очереди 158

34. Комбинаторные алгоритмы 163

35. Бинарные деревья 170

36. Упорядоченные бинарные деревья и приоритетные

очереди 177

37. Алгоритмы сортировки 185

38. Графы 198

Рекомендуемая литература 208

– Конец работы –

Используемые теги: автора0.02

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: От автора

Что будем делать с полученным материалом:

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

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

Автор и герой в эстетической деятельности ПРОБЛЕМА ОТНОШЕНИЯ
На сайте allrefs.net читайте: "Автор и герой в эстетической деятельности ПРОБЛЕМА ОТНОШЕНИЯ"...

Автор книги: Дормидонтов Роман Александрович! Маленький, глупенький и абсолютно Несерьезный человек!
На сайте allrefs.net читайте: "Автор книги: Дормидонтов Роман Александрович! Маленький, глупенький и абсолютно Несерьезный человек!"

Характеристики транса по данным различных авторов
На сайте allrefs.net читайте: Продемонстрировать необычное, странное поведение...

Роль казачьего движения в ходе Гражданской войны в оценке автора "Тихого Дона"
Связь казачества с белым движением Белое движение глазами Шолохова Белое движение в изображении Шолохова было тесно связано с казачеством. Казаки… Почему же всё-таки им не удалось повлиять на отрицательный исход революции? … Листницкий, убеждённый монархист, обличает подданных царя, брошенного, преданного всеми своими соотечественниками. …

Лермонтов и Печорин - автор и герой
Иногда эти взгляды могут сочетаться.В предисловии к "Герою нашего времени" Михаил Юрьевич Лермонтов говорит, что нарисовал современного человека,… Дуэль Печорина с Грушницким типична для манеры поведения многих людей того… По современ- ным изысканиям лермонтоведов такая ситуация была и у самого Лермонтова и некой Смирновой, чей муж служил…

Мировоззрение скифов в понимании Д.С. Раевского и других авторов
Однако, как правило, включенное в него содержание ограничивается значением термина культура в контексте понятия археологическая культура . Иными… Между тем, если подходить к культуре скифов с учетом присущей ей одной… При таком подходе каждый скифский памятник - от единичной вещи утилитарного назначениядо грандиозного могильного…

ЛЕРМОНТОВ И ПЕЧОРИН - АВТОР И ГЕРОЙ.
Иногда эти взгляды могут сочетаться.В предисловии к "Герою нашего времени" Михаил Юрьевич Лермонтов говорит, что нарисовал современного человека,… Дуэль Печорина с Грушницким типична для манеры поведения многих людей того… По современным изысканиям лермонтоведов такая ситуация была и у самого Лермонтова и некой Смирно-вой, чей муж служил в…

От авторов
Россия В XVI Веке Конец XV начало XVI в властные структуры С образованием единого... Глава вторая... РОССИЯ В КОНЦЕ XVI НАЧАЛЕ XVII вв СМУТНОЕ ВРЕМЯ В конце XVI...

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

Техники холодных звонков, Которые действительно работают! Автор: Стивен Шиффман
Которые действительно работают... Автор Стивен Шиффман... ГЛАВА Холодные звонки это очень важно Да да именно недостаток реальных продаж того чем мы с вами...

0.02
Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • По категориям
  • По работам