МинистерствоОбразования Республики Беларусь
Учреждение Образования «Гомельскийгосударственный университет им. Ф. Скорины»Математический факультетКафедра ВМ и ПрограммированияКонтрольнаяработа
Тема:
«Способы описания алгоритма. Видыоператоров»
1. Алгоритм и егосвойства. Способы описания алгоритма
Для поясненияпонятия «алгоритм» важное значение имеет определение понятия «исполнительалгоритма». Алгоритм формулируется в расчёте на конкретного исполнителя;алгоритм является руководством к действию для исполнителя, поэтому значениеслова «алгоритм» близко по смыслу к значению слов «указание» или «предписание».Можно сказать, что алгоритм – понятное и точное предписание исполнителюсовершить определённую последовательность действий для достижения указаннойцели или решения поставленной задачи или алгоритм – точное предписание, котороезадаёт вычислительный процесс, начинающийся с произвольного исходного данногоиз некоторой совокупности возможных для этого процесса данных и направленный наполучение полностью определяемого этими исходными данными результата.
Основные свойства алгоритма.
1. Алгоритмимеет некоторое число входных величин – аргументов, задаваемых до началаисполнения. Цель выполнения алгоритма – получение результата, имеющего вполнеопределённое отношение к исходным данным. Для алгоритма можно выбиратьразличные наборы входных данных из множества допустимых для этого процессаданных, т. е. можно применять алгоритм для решения целого класса задачодного типа, различающихся исходными данными. Это свойство алгоритма называют массовостью.Однако существуют алгоритмы, применимые только к единственному набору данных.Тогда свойство массовости означает применимость алгоритма ко всем объектамэтого класса.
2. Чтобыалгоритм можно было выполнить, он должен быть понятен исполнителю. Понятностьалгоритма означает знание исполнителя о том, что надо делать дляисполнения этого алгоритма.
3. Алгоритмпредставляется в виде конечной последовательности шагов, (алгоритм имеетдискретную структуру) и его исполнение расчленяется на выполнение отдельныхшагов.
4. Каждыйшаг алгоритма должен быть чётко и недвусмысленно определён и не должендопускать произвольной трактовки исполнителем. Алгоритм рассчитан на чистомеханическое исполнение. Именно определённость алгоритма даётвозможность поручить его исполнение автомату.
5. Выполнениеалгоритма заканчивается после выполнения конечного числа шагов. Привыполнении алгоритма некоторые его шаги могут повторяться многократно.
6. Каждыйшаг алгоритма должен быть выполнен точно и за конечное время. Алгоритм долженбыть эффективным.
2. Линейныеи ветвящиеся вычислительные процессы
1. Линейный – это такойвычислительный процесс, в котором самостоятельные этапы вычисления выполняютсяв линейной последовательности.
2. Ветвящийся – это процесс,реализация которого в зависимости от исходных данных или промежуточныхрезультатов происходит по одному из нескольких, заранее определяемыхнаправлений, выбор той или иной ветви вычислений осуществляется проверкойлогического условия, определяющего свойства исходных данных или промежуточныхрезультатов.
3. Основные понятия языка Паскаль
Программа на языке Паскаль формируется с помощью конечногонабора знаков, образующих алфавит языка, и состоит из букв, цифр,специальных символов.
В качестве букв используются прописные и строчныебуквы латинского алфавита и знак подчёркивания; в качестве цифр: арабскиецифры от 0 до 9.
При написании программ применяются специальные символы:+, -, *, /, =, , [], (), @, {},:,;’, # (номер), $ (знак денежнойединицы), ^ (тильда), пробел, точка и запятая.
Неделимые последовательности знаков алфавита образуют слова, отделённыедруг от друга разделителями и несущими определённый смысл в программе.Разделителем может служить пробел, символ конца строки, комментарий. Словаподразделяются на зарезервированные, стандандартные идентификаторы иидентификаторы пользователя.
Зарезервированные слова являются составнойчастью языка и их нельзя использовать в качестве идентификаторов. В языкеПаскаль зарезервированными являются следующие слова: and, array, begin, case,const, div, do, downto, else, end, file, for, forward, function, goto, if, in,lable, mod, nil, not, of, or, packed, procedure, program, record, repeat, set,shl, shr, string, then, to, type, unit, until, uses, var, while, with, xor.
Стандартные идентификаторы служат для обозначениязаранее определённых разработчиками языка типов данных, констант, процедур ифункций.
Идентификаторы пользователя используются дляобозначения меток, констант, типов, переменных, процедур и функций,определённых самим программистом.
4. Общая структура программы. Описание меток,определение констант, определение типов, описание переменных
Структура программы.
Program ;
{Раздел описаний}
Uses{подключаемые модули}
Label{объявление глобальныхметок}
Const {объявление констант}
Type {объявление типов}
Var{объявление переменных}
Procedure{описание процедур}
Function {описание функций}
{Раздел операторов}
Begin
{операторы}
End.
Все данные, в зависимости от способа их хранения и обработкиможно разделить на две группы константы и переменные.
Константами называются элементы данных, значениякоторых установлены в описательной части программы и в процессе выполненияпрограммы не изменяются.
Стандартные виды констант:
1. Целочисленные – определяютсяпосредством чисел, записанных в десятичном или шестнадцатеричном формате, несодержащих десятичной точки.
2. Вещественные – определяются посредством чисел,записанных в десятичном формате данных.
3. Символьные – это любой символ персональногокомпьютера, заключённый в апострофы.
4. Строковые – определяютсяпоследовательностью произвольных символов, заключённых в апострофы.
5. Типизированные–переменные с начальным значением. Каждой типизированной константе ставится всоответствие имя, тип и начальное значение.
6. Зарезервированныеконстанты.
Формат описания констант:
Const
Идентификатор=значение;
Типы данных.
Тип – это множество значений, которые могутпринимать объекты программы, и совокупность операций, допустимых над этимизначениями.
Переменные в отличие от констант могут менять свои значения впроцессе выполнения программы. Тип констант автоматически распознаётсякомпилятором без предварительного описания. Тип переменной должен быть описанперед тем, как с переменными будут выполняться какие-либо действия.
Формат описания переменных:
Var
Идентификатор: тип;
5. Скалярныетипы данных: стандартные и описанные пользователем
Логический тип. Значениями логического типа может бытьодна из констант False или True.
Целые типы. Диапазон возможных значений целых типов зависитот их внутреннего представления.Тип Название Длина, байт Диапазон значений Byte Длиной в байт 1 0. 255 ShortInt Короткое целое 1 -128..127 Word Длиной в слово 2 0..65535 Integer Целое 2 -32768..32767 LongInt Длинное целое 4 -2147483648..2147483647
Символьный тип. Значениями символьного типа являетсямножество всех символов ПК. Для кодировки используется код ASCII(American Standard Code for Information Interchange).
Перечисляемый тип. Задаётся перечислениемтех значений, которые он может получить. Каждое значение именуется некоторымидентификатором и располагается в списке, обрамлённом круглыми скобками.
Переменные перечисляемого типа можно объявлять безпредварительного описания типа.
Тип-диапазон. Тип-диапазон есть подмножество своегобазового типа, в качестве которого может выступать любой скалярный тип, кромевещественного и типа-диапазона. Тип-диапазон задаётся границами своих значенийвнутри базового типа.
Тип-диапазон можно непосредственно указывать при объявлениипеременной.
Вещественные типы. Значения вещественныхтипов определяют произвольное вещественное число с некоторой конечнойточностью, зависящей от внутреннего формата числа.Тип Название Длина, байт Кол-во цифр мантиссы Диапазон десятичного порядка Real Вещественный 6 11..12 -39..38 Single С одинарной точностью 4 7..8 -45..38 Double С двоичной точностью 8 15..16 -324..308 Extended С повышенной точностью 10 19..20 -4932..4932 Comp Сложный 8 10..20
-2*10 +1
-2*10 -1
6. Простыеоператоры: присваивания, перехода Goto, пустой оператор. Простейшийввод-вывод
Операторывыполняются в том порядке, в котором они записаны в программе. Разделителемоператора служит точка с запятой.
Все операторыразделяются на две группы: простые и структурные.
Операторы, несодержащие внутри себя других операторов, называются простыми. К нимотносятся операторы присваивания, безусловного перехода, пустой оператор иоператор вызова процедур.
Операторприсваивания выполняет выражение, заданное в его правой части, и присваиваетрезультат переменной, идентификатор которой расположен в левой части.
Форматоператора:
Идентификатор:=выражение;
Операторбезусловного перехода Goto служит для передачи управления оператору,помеченному меткой. Метка отделяется от оператора двоеточием. Оператор Goto применяется в случае,когда после выполнения некоторого оператора надо выполнить не следующий попорядку, а какой-либо другой, отмеченный меткой оператор.
Форматоператора:
Goto метка;
Форматописания меток:
Label
Имя метки;
Пустойоператорне содержит ни одного символа и не выполняет никаких действий.
Длявыполнения операций ввода-вывода служат 4 процедуры: Read, Readln, Write, Writeln.
Процедурачтения Read обеспечивает ввод числовых данных, символов, строк и т. д.для последующей их обработки программой.
Формат:
Read (x1, x2,…, xn);
где x1, x2, …, xn – переменные допустимыхтипов.
Процедурачтения Readln аналогична процедуре Read. Единственное отличие заключается в том, чтопосле считывания последнего в списке значения для одной процедуры Readln данные для следующейпроцедуры Readln будут считываться с начала новой строки.
Процедуразаписи Write производит вывод числовых данных, символов, строк и булевскихзначений.
Формат:
Write(y1, y2,…, yn);
где y1, y2, …, yn – выраженияцелочисленного, вещественного, символьного, строкового, булевского и др. типов.
Процедуразаписи Writeln аналогична процедуре Write, но после вывода последнего в списке значениядля текущей процедуры Writeln происходит перевод курсора к началу следующейстроки. Процедура Writeln, записанная без параметров, вызывает перевод строки.
7. Структурныеоператоры: условный оператор If, составной оператор Begin-End, оператор выбора Case
Структурныеоператорыпредставляют собой структуры, построенные из других операторов по строгоопределённым правилам.
Составнойоператорпредставляет собой группу из произвольного числа операторов, отделённых друг отдруга точкой с запятой и ограниченную операторными скобками Begin и End.
Форматоператора:Begin
Оператор 1;
…
оператор N;
End;
Условныеоператорыобеспечивают выполнение или невыполнение некоторого оператора, группыоператоров или блока в зависимости от заданных условий.
Операторусловия If может принимать одну из форм:
1. If условие then оператор1 {полная условная конструкция}
Else оператор2;
2. If условие thenоператор; {неполнаяусловная конструкция}
Операторвыбора Case является обобщением оператора If и позволяет сделатьвыбор из произвольного числа имеющихся вариантов. Он состоит из выражения,называемого селектором, и списка параметров, каждому из которых предшествуетсписок констант выбора. Как и в операторе If, здесь можетприсутствовать слово Else, имеющее тот же смысл.
Форматоператора:
Case выражение-селектор of
Список 1:оператор 1;
…
Список N: оператор N
Else оператор
End