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

Алгоритмы можно записывать не только при помощи слов. В настоящее время различают несколько способов описания алгоритмов:


1. Словесный, т.е. записи на естественном языке, описание словами последовательности выполнения алгоритма.

Например: Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел. Алгоритм может быть следующим: задать два числа; если числа равны, то взять любое из них в качестве ответа и остановиться, в противном случае продолжить выполнение алгоритма; определить большее из чисел; заменить большее из чисел разностью большего и меньшего из чисел; повторить алгоритм с шага


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

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


3. Графический, т.е. с помощью блок-схем.

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


4.Программный, т.е. тексты на языках программирования.

cls
input a, b
c = a + b
print c

 

Б2) Паскаль (англ. Pascal) — язык программирования общего назначения. Один из наиболее известных языков программирования, широко применялся в промышленном программировании[4], до сих пор используется для обучения программированию в высшей школе, является базой для ряда других языков.

Алфавит языка состоит из следующих символов:

  • Заглавные и строчные латинские буквы и символ подчеркивания:

А,В,С.. .,X,Y,Z,a,b,c, .. .,x,y,z.

Обратите внимание, что в языке Turbo Pascal символ подчеркивания считается буквой.Буквы используются для формирования идентификаторов и служебных слов.

  • Десять арабских цифр от 0 до 9:

0,1,2,3,4,5,6,7,8,9

Цифры используются для записи чисел и идентификаторов.

  • Двадцать два специальных символа:

+ -*/-><. , ; : ( )[ ]{ }#$

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

Лексическая структура языка.

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

Лексема - минимальная единица языка, имеющая самостоятельный смысл.

В Turbo Pascal имеются следующие классы лексем:

1. Служебные (зарезервированные) слова.
Это ограниченная группа слов, построенных из букв. Каждое служебное слово представляет собой неделимое образование, смысл которого фиксирован в языке. Служебные слова НЕЛЬЗЯ использовать в качестве имен, вводимых программистом (т.е. в качестве идентификаторов переменных, констант и т.д.).

Все 55 служебных слов языка представлены ниже.

absolute array and asm assembler
begin case const constructor destructor
div downto else end external
file for forward function goto
if implementation in inline interface
interrupt label mod nil not
object of or packed private
procedure program record repeat set
shl shr string then to
type unit until uses var
virtual while with xor  

Заметим, что синтаксис языка Turbo Pascal на самом деле допускает использование некоторых служебных слов в качестве идентификаторов (к числу таких слов относятся assembler, external, forward, interrupt, private, virtual). Строго говоря, эти слова называются в языке директивами. Однако в целях большей ясности программ использование директив в качестве идентификаторов не рекомендуется.

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

Длина идентификатора может быть произвольной, однако компилятор воспринимает только ПЕРВЫЕ 63 его символа.

Важно помнить, что в языке Turbo Pascal соответствующие заглавные и строчные буквы в идентификаторах и служебных словах НЕ РАЗЛИЧАЮТСЯ. Таким образом, следующие три идентификатора обозначают одну и ту же переменную:

index
INDEX
Index

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

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

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

; : = ( .

 

В текстах Pascal-программ допускаются фрагменты пояс­нительного характера - комментарии. Наличие комментари­ев не изменяет смысл программы и не влияет на ее выполне­ние.

 

В Turbo Pascal комментарии представляют собой произ­вольную последовательность символов (не обязательно из алфавита языка; то есть допускаются и русские буквы), за­ключенную в фигурные скобки '{' и ')' или в разделители вида ' (*' и '*)’ например:

{Это комментарий}

(*А это длинный комментарий,

расположенный на

нескольких строках*)

 

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

 

В качестве констант в языке программирования Pascal могут использоваться:

Целые числа. Они записываются со знаком или без знака и могут иметь значение от – 2 147 483 648 до + 2 147 483 647. Если константа имеет значение, выходящее за эти пределы, то в качестве значения константы необходимо использовать вещественные числа.

Вещественные числа записываются со знаком или без знака с использованием десятичной точки или экспоненциальной части, которая начинается с символа «e», за которым следует десятичный порядок. Например, запись 3.14e5 означает 3,14*105. А запись – 3.14e-4 означает – 3,14*10-4.

Шестнадцатеричные числа, которые состоят из шестнадцатеричных цифр со знаком доллара «$» впереди. Диапазон шестнадцатеричных чисел — от $00000000 до $FFFFFFFF.

 

Раздел описания меток в Паскале:

 

Метка – любой идентификатор, в целях совместимости со стандартом допускается использование в качестве метки целого без знака в диапазоне (от 0 до 9999).

 

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

 

LABEL LB1, LB2, R8; LABEL 10, 120, 55;

 

Б3) Program ... ; { Заголовок программы }

 

Uses ... ; { Подключение модулей }

 

Label ... ; { Раздел объявления меток }

 

Const ... ; { Раздел объявления констант }

 

Type ... ; { Раздел объявления новых типов }

 

Var ... ; { Раздел объявления переменных }

 

Procedure ... ; { Описание своих процедур }

 

Function ... ; { Описание своих функций }

 

Begin { начало основной программы }

 

...;

 

{ Операторы }

 

...;

 

End.

 

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

 

Б4) Программа на языке Паскаль состоит из заголовка, разделов описаний и раздела операторов. Заголовок программы содержит имя программы, например:

 

Program PRIM;

Описания могут включать в себя:

 

раздел подключаемых библиотек (модулей);

раздел описания меток;

раздел описания констант;

раздел описания типов;

раздел описания переменных;

раздел описания процедур и функций.

Раздел описания модулей определяется служебным словом USES и содержит имена подключаемых модулей (библиотек) как входящих в состав системы Turbo Pascal, так и написанных пользователем. Раздел описания модулей должен быть первым среди разделов описаний. Имена модулей отделяются друг от друга запятыми:

 

uses CRT, Graph;

Б5) Пользовательские типы

 

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

 

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

К стандартным относятся целые, действительные, логические,

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

 

ЦЕЛЫЕ типы определяют константы, переменные и функции, значения

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

 

тип диапозон значений требуемая память

Shortint -128 .. 127 1 байт

Integer -32768 .. 32767 2 байт

Longint -2147483648 .. 2147483647 4 байт

Byte 0 .. 255 1 байт

Word 0 .. 65535 2 байт

Над целыми операндами можно выполнять следующие арифметические

операции: сложение, вычитание, умножение, деление, получение остатка

от деления. Знаки этих операций:

 

+ - * div mod

 

Результат арифметической операции над целыми операндами есть вели-

чина целого типа. Результат выполнения операции деления целых величин

есть целая часть частного. Результат выполнения операции получения

остатка от деления - остаток от деления целых. Например:

 

17 div 2 = 8, 3 div 5 = 0.

17 mod 2 = 1, 3 mod 5 = 3.

 

Операции отношения, примененные к целым операндам, дают результат

логического типа TRUE или FALSE ( истина или ложь ).

В языке ПАСКАЛЬ имеются следующие операции отношения: равенство =,

неравенство <>, больше или равно >=, меньше или равно <=, больше >,

меньше < .

К аргументам целого типа применимы следующие стандартные (встроен-

ные) функции, результат выполнения которых имеет целый тип:

 

Abs(X), Sqr(X), Succ(X), Pred(X),

 

и которые определяют соответственно абсолютное значение Х, Х в квад-

рате, Х+1, Х-1.

Следующая группа стандартных функций для аргумента целого типа да-

ет действительный результат:

 

Sin(X), Cos(X), ArcTan(X), Ln(X), Exp(X), Sqrt(X).

 

Эти функции вычисляют синус, косинус и арктангенс угла, заданного

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

ответственно.

Результат выполнения функции проверки целой величины на нечетность

Odd(X) имеет значение истина, если аргумент нечетный, и значение

ложь, если аргумент четный:

 

X=5 Odd(X)=TRUE , X=4 Odd(X)=FALSE.

 

Для быстрой работы с целыми числами определены процедуры:

 

Inc(X) X:=X+1

Inc(X,N) X:=X+N

Dec(X) X:=X-1

Dec(X,N) X:=X-N

 

ДЕЙСТВИТЕЛЬНЫЕ типы определяет те данные, которые реализуются

подмножеством действительных чисел, допустимых в данной ЭВМ.

 

1.Тип Диапазон 2. Количество цифр 3. Требуемая

значений 4.мантиссы память (байт)

 

1 2 3 4

---------------------------------------------------------------

Real 2.9e-39 .. 1.7e+38 11 6

Single 1.5e-45 .. 3.4e+38 7 4

Double 5.0e-324 .. 1.7e+308 15 8

Extended 3.4e-4932 .. 1.1e+4932 19 10

Comp -9.2e+18 .. 9.2e+18 19 8

---------------------------------------------------------------

 

Тип Real определен в стандартном ПАСКАЛЕ и математическим сопро-

цессором не поддерживается.

Остальные действительные типы определены стандартом IEEE 457 и ре-

ализованы на всех современных компьютерах.

Для их использования при наличии сопроцессора или при работе на

ЭВМ типа 80486 необходимо компилировать программу с ключом {$ N+}, а

при отсутствии сопроцессора - с ключами {$N-,E+}.

Тип Comp хотя и относится к действительным типам, хранит только

длинные целые значения.

Над действительными операндами можно выполнять следующие арифмети-

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

 

сложение + , вычитание - , умножение * , деление / .

 

К величинам действительного типа применимы все операции отношения,

дающие булевский результат.

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

К действительным аргументам применимы функции, дающие действитель-

ный результат:

 

Abs(X), Sqr(X), Sin(X), Cos(X), ArcTan(X), Ln(X), Exp(X),

Sqrt(X), Frac(X), Int(X), Pi.

 

Функция Frac(X) возвращает дробную часть X, функция Int(X) - целую

часть X.

Безаргументная функция Pi возвращает значение числа Пи действи-

тельного типа.

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

 

Trunc(X) и Round(X),

 

дающие целый результат. Первая из них выделяет целую часть действи-

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

аргумент до ближайшего целого.

 

ЛОГИЧЕСКИЙ тип (Boolean) определяет те данные, которые могут при-

нимать логические значения TRUE и FALSE.

К булевским операндам применимы следующие логические операции:

 

not and or xor.

 

Логический тип определен таким образом, что FALSE < TRUE. Это поз-

воляет применять к булевским операндам все операции отношения.

В ТУРБО ПАСКАЛЬ введены еще разновидности логического типа:

ByteBool, WordBool и LongBool, которые занимают в памяти ЭВМ один, два

и четыре байта соответственно.

 

СИМВОЛЬНЫЙ тип (Char) определяет упорядоченную совокупность симво-

лов, допустимых в данной ЭВМ. Значение символьной переменной или

константы - это один символ из допустимого набора.

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

способами:

-как один символ, заключенный в апострофы, например:

 

'A' 'a' 'Ю' 'ю';

 

-с помощью конструкции вида #K, где K - код соответствущего симво-

ла, при этом значение K должно находиться в пределах 0..255;

-с помощью конструкции вида ^C, где C - код соответствущего управ-

ляющего символа, при этом значение C должно быть на 64 больше

кода управляющего символа.

К величинам символьного типа применимы все операции отношения.

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

 

Ord(C) Chr(K).

 

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

волов, вторая определяет по порядковому номеру К символ, стоящий на

К-ом месте в наборе символов. Порядковый номер имеет целый тип.

К аргументам символьного типа применяются функции, которые опреде-

ляют предыдущий и последующий символы:

 

Pred(C) Succ(C). Pred('F') = 'E' ; Succ('Y') = 'Z' .

 

При отсутствии предыдущего или последующего символов значение со-

ответствующих функций не определено.

Для литер из интервала 'a'..'z' применима функция UpCase(C), кото-

рая переводит эти литеры в верхний регистр 'A'..'Z'.

 

АДРЕСНЫЙ тип (Pointer) определяет переменные, которые могут содер-

жать значения адресов данных или фрагментов программы. Для хранения

адреса требуются два слова (4 байта), одно из них определяет сегмент,

второе - смещение.

Работа с адресными переменными (указателями) будет рассмотрена

позже, сейчас отметим, что для получения значения адреса какой-либо

переменной введена унарная операция @.