Министерство общего и профессионального образования
Российской Федерации
Уральский государственный университет
им.А.М. Горького
ЛахтинА.С., Искакова Л.Ю.
Языки и технология программирования.
Начальный курс.
Учебное пособие
Екатеринбург
1998
Лахтин А.С., Искакова Л.Ю. Языки итехнология программирования. Начальный курс. Учеб. пособие. Екатеринбург, 1998.
Данное учебное пособие представляетсобой первую часть одноименного лекционного курса, который читается студеттамматематико-механического фаультета в 1 семестре.
Начальный курс посвящен изложению основсоздания программ. Изложение ведется с использованием языка программированияТурбо Паскаль. Рассматриваются некоторые классические алгоритмы. Приводятся примеры решения типовых задач.
Пособие предназначено для студентовдистантной формы обучения специальности «Информационные системы», атакже может быть использовано для студентов дневной формы обучения по этойспециальности.
ãА.С.Лахтин, Л.Ю. Искакова, 1998.
СОДЕРЖАНИЕTOC o «1-3»
ВВЕДЕНИЕ… PAGEREF _Toc437758116h 5
ОСНОВЫ ЯЗЫКА… PAGEREF _Toc437758117h 5
АЛГОРИТМЫ____________________________________________ PAGEREF _Toc437758118h 5
АЛФАВИТ ЯЗЫКА________________________________________ PAGEREF _Toc437758119h 5
СТРУКТУРА ПРОГРАММЫ_________________________________ PAGEREF _Toc437758120h 6
ТИПЫ ДАННЫХ__________________________________________ PAGEREF _Toc437758121h 7
Целые типы____________________________________________ PAGEREF _Toc437758122h 7
Вещественные типы_____________________________________ PAGEREF _Toc437758123h 8
Логический тип_________________________________________ PAGEREF _Toc437758124h 9
Символьный тип________________________________________ PAGEREF _Toc437758125h 9
ВЫРАЖЕНИЯ____________________________________________ PAGEREF _Toc437758126h 9
СОВМЕСТИМОСТЬ ТИПОВ ДАННЫХ_______________________ PAGEREF _Toc437758127h 10
ЛИНЕЙНЫЕ АЛГОРИТМЫ… PAGEREF _Toc437758128h 11
ПУСТОЙ И СОСТАВНОЙ ОПЕРАТОРЫ_____________________ PAGEREF _Toc437758129h 11
ОПЕРАТОР ПРИСВАИВАНИЯ____________________________ PAGEREF _Toc437758130h 11
ПРОСТЕЙШИЙ ВВОД И ВЫВОД__________________________ PAGEREF _Toc437758131h 11
РАЗВЕТВЛЯЮЩИЕСЯ АЛГОРИТМЫ… PAGEREF _Toc437758132h 12
ОПЕРАТОР ПЕРЕХОДА___________________________________ PAGEREF _Toc437758133h 12
УСЛОВНЫЙ ОПЕРАТОР__________________________________ PAGEREF _Toc437758134h 13
ОПЕРАТОР ВЫБОРА______________________________________ PAGEREF _Toc437758135h 13
ЦИКЛИЧЕСКИЕ АЛГОРИТМЫ… PAGEREF _Toc437758136h 14
ЦИКЛЫ С ПАРАМЕТРОМ._________________________________ PAGEREF _Toc437758137h 14
ЦИКЛЫ С УСЛОВИЕМ.___________________________________ PAGEREF _Toc437758138h 16
ПОЛЬЗОВАТЕЛЬСКИЕ ТИПЫ ДАННЫХ… PAGEREF _Toc437758139h 17
ПЕРЕЧИСЛЯЕМЫЙ ТИП__________________________________ PAGEREF _Toc437758140h 17
ТИП-ДИАПАЗОН_________________________________________ PAGEREF _Toc437758141h 17
МАССИВЫ_____________________________________________ PAGEREF _Toc437758142h 17
ЗАПИСИ________________________________________________ PAGEREF _Toc437758143h 17
РАБОТА СО СТРОКАМИ… PAGEREF _Toc437758144h 17
ПРОЦЕДУРЫ И ФУНКЦИИ… PAGEREF _Toc437758145h 17
Параметры-значения____________________________________ PAGEREF _Toc437758146h 17
Параметры-переменные_________________________________ PAGEREF _Toc437758147h 17
Параметры-константы_________________________________ PAGEREF _Toc437758148h 17
ОТКРЫТЫЕ ПАРАМЕТРЫ-МАССИВЫ_______________________ PAGEREF _Toc437758149h 17
БЕСТИПОВЫЕ ПАРАМЕТРЫ_______________________________ PAGEREF _Toc437758150h 17
ПРОЦЕДУРНЫЕ ТИПЫ____________________________________ PAGEREF _Toc437758151h 17
РЕКУРСИЯ_____________________________________________ PAGEREF _Toc437758152h 17
ТИПИЗИРОВАННЫЕ КОНСТАНТЫ… PAGEREF _Toc437758153h 17
МОДУЛИ… PAGEREF _Toc437758154h 17
АЛГОРИТМЫ ПОИСКА… PAGEREF _Toc437758155h 17
ЛИНЕЙНЫЙ ПОИСК_____________________________________ PAGEREF _Toc437758156h 17
ПОИСК С БАРЬЕРОМ_____________________________________ PAGEREF _Toc437758157h 17
ДВОИЧНЫЙ (БИНАРНЫЙ) ПОИСК__________________________ PAGEREF _Toc437758158h 17
АЛГОРИТМЫ СОРТИРОВКИ… PAGEREF _Toc437758159h 17
СОРТИРОВКА ВЫБОРОМ_________________________________ PAGEREF _Toc437758160h 17
СОРТИРОВКА ОБМЕНОМ (методом«пузырька»)_____________ PAGEREF _Toc437758161h 17
ШЕЙКЕРНАЯ СОРТИРОВКА_______________________________ PAGEREF _Toc437758162h 17
СОРТИРОВКА ВКЛЮЧЕНИЕМ_____________________________ PAGEREF _Toc437758163h 17
СОРТИРОВКА ХОАРА____________________________________ PAGEREF _Toc437758164h 17
СОРТИРОВКА С ИСПОЛЬЗОВАНИЕМ ВЕКТОРА ИНДЕКСОВ___ PAGEREF _Toc437758165h 17
МОДУЛЬ CRT (основные возможности)… PAGEREF _Toc437758166h 17
ЛИТЕРАТУРА… PAGEREF _Toc437758167h 17
ВВЕДЕНИЕ
Первая версия языка Паскаль быларазработана швейцарским ученым Никлаусом Виртом в 1968 году. Первоначальноязык предназначался для целей обучения,поскольку он является достаточно детерминированным, т.е. все подчиняетсяопределенным правилам, исключений из которых не так много. Основныехарактеристики: относительно небольшое количество базовых понятий, простойсинтаксис, быстрый компилятор для перевода исходных текстов в машинный код.
В 1992 г. фирма BorlandInternational выпустила два пакета, основанных на языке Паскаль: Borland Pascal7.0 и Turbo Pascal 7.0. Первый может работать в трех режимах — обычном изащищенном режимах MS DOS и в системе Windows. Для него необходимо порядка 30Мбайт на жестком диске и около 2 Мбайт оперативной памяти. Турбо Паскаль 7.0работает только в обычном режиме MS DOS и менее требователен к характеристикамкомпьютера. Поскольку основные компоненты, которые мы будем рассматривать внашем курсе, совпадают в обоих продуктах, в дальнейшем будет использоватьсяназвание Турбо Паскаль.
Пакет включает в себяалгоритмический язык программирования высокого уровня, встроенный редактор исреду, предназначенную для отладки и запуска программ. Кроме того, пакетсодержит большой объем справочной информации (англоязычной). Как известно,языки программирования делятся на два типа: интерпретаторы и компиляторы. ТурбоПаскаль относится к компиляторным языкам.
ОСНОВЫ ЯЗЫКА
АЛГОРИТМЫ
Алгоритмом называют описаниепоследовательности действий, необходимых для решения определенной задачи.Основными характеристиками алгоритма являются вычислительная сложность иемкостная сложность. Вычислительная или, иначе, временная сложность алгоритма — это количество элементарных операций в процессе его выполнения. Различаютвычислительную сложность в среднем и в худшем случае. Емкостная сложностьалгоритма — это объем используемых данных, а также объем кода самой программы.При создании алгоритма цельюявляетсясокращение как его вычислительной, так и емкостной сложности.
Алгоритмы могут записыватьсяразличными способами, например, в виде блок-схем или в виде программ. Программаэто набор указаний исполнителю, т.е. в нашем случае – компьютеру.
АЛФАВИТ ЯЗЫКА
Под алфавитом языка понимаютсовокупность допустимых символов. В языке Турбо Паскаль используются символыASCII (американский стандартный код обмена информацией). Можно выделить четыреосновные группы символов: символы, используемые в идентификаторах, разделители,специальные символы инеиспользуемыесимволы.
Идентификатор — это имя любогообъекта языка. Он может состоять из латинских букв (a...z), цифр (0...9) изнака подчеркивания и не должен начинаться с цифры. Прописные и строчные буквыв идентификаторах и зарезервированных словах считаются идентичными, ониразличаются лишь в строковых константах. Длина идентификатора неограничена, но значимыми являются лишь первые 63 символа.
Разделители используются дляотделения друг от друга идентификаторов, чисел и зарезервированных слов. Кразделителям относятся, например, пробел и комментарий. В любом местепрограммы, где разрешается один пробел, их можно вставить любое количество.
Комментарии заключаются либо вфигурные скобки{комментарий 1 },либо в символы (* комментарий 2 *) и могут занимать любое количествострок. Последовательность из трех символов (*)начинает комментарий до конца строки. Текст комментария игнорируется прикомпиляции, если это не директивы компилятора, которые имеют вид {$ }.
ПРИМЕР :
(*Допустимый {{{в (* программе}комментарий*).
(*Недопустимый {{{в (* программе*)комментарий*).
К специальным знакам относятсязнаки пунктуации (. () []…: ;),знаки операций и зарезервированные слова. Знаки операций могут быть каксимвольные (+,-,*,/ и т.д.), так и буквенными (mod,div,not).Зарезервированные слова являются служебными и не могут быть переопределеныпользователем, т.е. их нельзя использовать как имена пользовательских объектов.Неиспользуемые символы — это коды ASCII, которые используются только вкомментариях и символьных строках, но не в языке. К ним относятся все русскиебуквы, а также символы %, &, !и т.п.
СТРУКТУРА ПРОГРАММЫ
В программе, написанной на Турбо Паскале, могут быть следующие разделы:
Program…; { Заголовок программы }
Uses…; { Подключение модулей }
Label…; { Раздел объявления меток }
Const…; { Раздел объявления констант }
Type…; { Раздел объявления новых типов }
Var…; { Раздел объявления переменных }
Procedure…; { Описание своих процедур }
Function…; { Описание своих функций }
Begin{ начало основной программы }
...;
{ Операторы }
...;
End.
Обязательной частью является лишьтело программы, которое начинается словом begin,а заканчивается словом end с точкой.Операторы в Паскале разделяются точкой запятой. Заголовок программы являетсяхотя и необязательным, но желательным элементом и состоит из зарезервированногослова program и идентификатора — имени программы, за котором следует точка с запятой. Порядок объявлений иописаний не регламентируется.
ПРИМЕР : Простейшая программа.
programprim_1; { демонстрация структурыпрограммы}
{эта программа не требует никаких объявлений и описаний}
begin
write('Привет!Вот мы и начали.') (* эта строка текста появится на экране *)
end.
ТИПЫ ДАННЫХ
Понятие типа данных являетсяключевым в языке Паскаль. Тип данных характеризует внутреннее представление,множество допустимых значений для этих данных, а также совокупность операцийнад ними. Среди типов данных различают стандартные (предопределенныеразработчиками языка) и пользовательские (определяемые программистом в своейпрограмме). Мы будем рассматривать следующие стандартные типы: целые числа,вещественные числа, логический тип, символьный и строковый типы. Программистможет описать свой тип на основе этих базовых в разделе описания типов, которыйначинается словом Type. Затем длякаждого типа следует конструкция вида:
идентификатор типа = определение типа;
Рассмотрим сначала простые типы данных,каждый из которых определяет упорядоченное множество значений: целые типы,логический тип, символьный тип, вещественные типы. Все эти типы, кромевещественых являются порядковыми. Каждому значению порядкового типа функция Ord ставит в соответствие натуральноечисло — порядковый номер данного значения в множестве допустимых значений. Клюбым порядковым типам также можно применять функции Pred — возвращает предыдущее значение и Succ — следующее значение. Тип относится к упорядоченным если дляпеременных и выражений этого типа определены операции отношения или сравнения: =, , , =.Любой порядковый тип является упорядоченным, но не наоборот. Так вещественныетипы и тип string упорядоченные, ноне порядковые.
Целые типы
В языке Турбо Паскаль определено 5целых типов:
· Shortint(-128… 127, 1 байт),
· Integer(-32767… 32768, 2 байта),
· Longint(-2147483648… 2147483647, 4байта),
· Byte(0… 255, 1 байт),
· Word(0… 65535, 2 байта).
Для целыхчисел определены такие операции. Унарные: +,-. Бинарные: сложение, вычитание,умножение, получение частного (div)и остатка (mod) при целочисленномделении и некоторые другие. Также с целыми числами можно производить операции,результаты которых не целые числа. Это обычное деление и операции отношения.Кроме того, имеется большое количество встроенных функций для работы с целымичислами: abs, sqr, sqrt, sin, cos, exp,ln и др.
Вещественные типы
В Турбо Паскале имеется 5 вещественных типов.
· Real(занимает 6 байт, диапазон от 2.9E-39 до 1.7E+38 по модулю, точность 11-12 значащихцифр)
· Single (занимает 4 байта, диапазон от 1.5E-45 до 3.4E+38 по модулю, точность 7-8 значащих цифр)
· Double (занимает 8 байт, диапазон от5.0Е-324 до 1.7Е+308 по модулю, точность 15-16 значащих цифр)
· Extended(занимает 10 байт, диапазон от 3.4E-4932 до 1.1E+4932 помодулю, точность19-20 значащих цифр).
· Comp (занимает 8 байт, диапазон от -9.2E-18 до 9.2E+18, хранятся точно, поскольку это целыечисла)
Вещественные типы являютсяупорядоченными, но не порядковыми. Операции над вещественными числами: сложение, вычитание, умножение, деление и операции отношения. Кроме того, имеетсябольшое количество встроенных функций для работы с числами: abs, sqr, sqrt, sin, cos и т.п.
Вещественные числа хранятсянеточно. Каждый из имеющихся вещественных типов гарантирует правильное хранениетолько определенного количества значащих цифр, их называют верными цифрами. Сматематической точки зрения, из за особенностей внутреннего представления речьидет об относительной погрешности.
Неточностив хранении вещественных чисел могут привести к тому, что при вычитании близкихчисел может произойти потеря значимости. Это же объясняет, почему следуетизбегать сравнения вещественных величин на точное равенство.
ПРИМЕР: тип Single — хранится 7-8 знаков после десятичной точки, тип Double — 15-16, тип Extended — 19-20.
programsravnenie;
var x: single; y: double; z: extended;
begin
x := 1/3; y := 1/3;
z := abs(x-y);
writeln('z=',z);
end.
Эта программа выдаст в результатечисло z=9.93410748106882E-0009. Обычно принято считать, что a=b, есливыполняется условие abs(a-b)
Логический тип
Переменные логического типа Booleanзанимают в памяти один байт и могут принимать одно из двух значений False — ложное или True — истинное. Этот тип является порядковым (Ord(False) = 0, Ord(True) = 1) и, следовательно, упорядоченным.Результат любых операций сравнения имеет логический тип и может бытьприсвоен логической переменной. Для операндов типа booleanопределены следующие логические операции: NOT — отрицание(превращает false в true,а true в false),AND — логическое умножение "и", OR – логическоесложение «или», XOR — исключающее или (true если операнды разные). Принцип действия этих операцийможно проиллюстрировать такими схемами:
AND
false
true
false
false
false
true
false
true
OR
false
true
false
false
true
true
true
true
XOR
false
true
false
false
true
true
true
false
Символьныйтип
Символьный тип Char также называют литерным. Онпозволяет работать с символами, которые записываются двумя способами: водинарных кавычках или по их коду, например 'a', 'B', '*' или, что то же самое,#97, #130, #42. В отличие от текста программы на паскале, символы,соответствующие строчным и заглавным буквам различаются. Множество значенийтипа Char представляет собой полный набор ASCII — символов (американскаястандартная кодировка). В компьютере хранятся шестнадцатеричные коды символов(1 байт), которые и используются в операциях отношения (сравнения). Функция Ord выдает код соответствующегосимвола, который может быть от 0 до 255. Обратной функцией, которая по кодувыдает соответствующий символ, является функция Chr.
ВЫРАЖЕНИЯ
Выражение — это единица языка,которая определяет способ вычисления некоторого значения. Выражения формируютсяиз констант, переменных, функций, знаков операций и круглых скобок поопределенным синтаксическим правилам.
Константами называются параметры программы, значения которых не меняются впроцессе ее выполнения. Они встречаются либо непосредственно в виде значения,либо в виде идентификатора константы, описанного в разделе, начинающемся сослова Const. Для каждой константы вразделе указывается конструкция вида:
идентификатор константы = значение;
Целые константы содержат лишь цифрыи знак: -214, 23, вещественные могут содержать также десятичную точку,показатель степени и символ e, который заменяет основание 10 в записи числа:-0.5, -1e-5, 7.2e+15. Логические константы — это значения False или True.Символьная константа представляет собой символ ASCII, заключенный в апострофы.Если символ не имеет физического изображения, то пишется знак # и рядомASCII-код символа без апострофов.
Переменныминазываются параметры программы, которые могут менять свое значение в процессеее выполнения. Все без исключения переменные должны быть описаны в разделепрограммы, начинающемся со слова VAR.Затем следуют конструкции вида:
список идентификаторов переменных: тип1;
список идентификаторов переменных: тип2;
В спискеимена переменных перечисляются через запятую. Кроме базовых типов Турбо Паскаляздесь можно использовать свои типы (описанные ранее в разделе Type). В Турбо Паскале имеется большоеколичество встроенных функций для работы с данными каждого типа. Имена(указатели) этих функций с аргументом в круглых скобках могут также встречатьсяв выражениях. Знаки операций зависят от типа используемых в выражении операндови рассмотрены выше.
Круглыескобки используются для изменения порядка вычисления частей выражения.Выражения без скобок вычисляются в порядке, соответствующем приоритетуопераций. Приоритеты расставлены таким образом:
· вычисления в круглых скобках;
· вычисление значений функций;
· унарные операции ( not,+,- );
· операции типа умножения ( *,/,div,mod,and );
· операции типа сложения ( +,-, or, xor );
· операции отношения ( =, , , = ).
Влогическом выражении 23 Паскаль выдаст ошибку, поскольку операция and будет выполнена раньше операций сравнения. Верная запись — (23).
СОВМЕСТИМОСТЬ ТИПОВ ДАННЫХ
Когда воперациях или операторах вашей программы присутствуют данные разных типов, товстает вопрос об их совместимости. В языке Турбо Паскаль этому вопросууделяется очень большое внимание, разработаны строгие правила, определяющиеидентичность, совместимость в общем случае и совместимость по присваиваниюразличных типов.
Нам вначале курса достаточно помнить следующее. Переменные или выражения одного типаявляются полностью совместимыми. Другим понятием является совместимость поприсваиванию.Присваиваниепеременной одного типа выражения другого типа допустимо в том случае, когдамножество значений второго типа является подмножеством значений первого.Например, результат сложения двух целых переменных типа integer и word может присваиваться в целую переменную,тип которой только longint, поскольку только этот целый тип содержит в себевесь возможный диапазон значений как для типа integer, так и для типа word. Также,можно присваивать целое выражение в вещественную переменную или символьноевыражение в строку.
ЛИНЕЙНЫЕ АЛГОРИТМЫ
Алгоритмическиедействия над исходными данными и рабочими объектами языка, необходимые длярешения поставленной задачи описываются при помощи операторов Турбо Паскаля.Операторы разделяются точкой с запятой, их последовательность и составляет телопрограммы. Наиболее простой случай представляют собой линейные алгоритмы.При выполнении линейных участков алгоритма операторывыполняются последовательно друг за другом в том порядке, в котором ониперечислены в программе. При этом могут использоваться операторы присваивания,операции ввода и вывода.
ПУСТОЙ И СОСТАВНОЙОПЕРАТОРЫ
В программеможет применяться пустой оператор, не выполняющий никакого действия. Он представляетсобой точку с запятой.
Составнымоператором считается последовательность произвольных операторов, заключенная воператорные скобки — зарезервированные слова begin… end.Допускается произвольная глубина вложенности составных операторов. Составнойоператор применяется там, где по синтаксическим правилам языка может стоятьтолько один оператор, а нам надо выполнить несколько действий. В этом случаенабор необходимых команд должен быть оформлен как составной оператор. По сути,все тело программы представляет собой один составной оператор.
ОПЕРАТОР ПРИСВАИВАНИЯ
Операторприсваивания используется для задания значения переменных и имеет следующийсинтаксис:
имя_переменной :=выражение;
Вычисляетсявыражение, стоящее в правой части оператора, после чего его значениезаписывается в переменную, имя которой стоит слева. Тип выражения и типпеременной должны быть совместимы, т.е. множество допустимых значений для типавыражения содержится во множестве допустимых значений для типа переменной.
ПРОСТЕЙШИЙ ВВОД И ВЫВОД
Рассмотримпростейшие процедуры ввода и вывода. По умолчанию ввод осуществляется склавиатуры, а вывод на экран. К операторам ввода относятся:
Read();
Readln();
Readln;
Второйотличается от первого тем, что после ввода переводит курсор на новую строку,точнее, в конце своей работы считывает с клавиатуры код клавиши . Третий оператор используетсядля организации паузы — выполнение программы продолжится, как правило, толькопосле нажатия на клавиатуре клавиши .К операторам вывода относятся:
Write();
Writeln();
Writeln;
В спискевывода кроме имен переменных можно писать строковые константы(последовательность символов в апострофах) и даже выражения (выводятся ихзначения). Второй оператор отличается от первого тем, что после выводапереводит курсор на новую строку. Третий оператор просто переводит курсор нановую строку.
Существуеттак называемый форматированный вывод. Можно задать количество позиций,отводимых под число. Для целых — после выражения или переменной через двоеточиеуказывается меньше какого количества позиций не может быть выделено значению.Для вещественных — дополнительно через двоеточие можно указать количество цифрв дробной части. При этом происходит округление в ближнюю сторону.
ПРИМЕР: Простые вычисления.
programvvod_vyvod;
const n=1.5;
var y1,y2:real; x:byte;
begin
writeln('Введите натуральное число
readln(x);
y1:=cos(n); y2:=cos(x);
write('Зачем-топосчитали: ');
writeln('n=',n,'y1=',y1:7:4, cos(Pi/2):8:4);
{напечатается
Зачем-то посчитали: n= 1.50000000000000E+0000
y1= 0.0707 1.0000}
writeln('x=',x:3,'y2=',y2:7:4);
end.
РАЗВЕТВЛЯЮЩИЕСЯ АЛГОРИТМЫ
В ТурбоПаскале имеется возможность нелинейного хода программы, т.е. выполненияоператоров не в том порядке, в котором они записаны. Такую возможность нам предоставляютразветвляющиеся алгоритмы. Они могут быть реализованы одним из трех способов: сиспользованием операторов перехода, условного оператора или оператора выбора.
ОПЕРАТОР ПЕРЕХОДА
Операторперехода имеет вид
GOTO.
Онпозволяет передать управление непосредственно на нужный оператор программы.Перед этим оператором должна располагаться метка отделенная от него двоеточием.В Турбо Паскале в качестве меток выступают либо целые числа от 0 до 9999, либоидентификаторы. Все метки должны быть описаны в разделе объявления метокследующим образом:
label;
Каждойметкой в программе может быть помечен только один оператор. Операторов переходас одной и той же меткой можно писать любое количество. Необходимо, чтобы разделописания метки, сама метка и оператор перехода с ее использованиемрасполагались в пределах одного блока программы (см. тему процедуры и функции).Кроме того, нельзя передавать управление внутрь структурированных операторов(например, if, for, while, repeat и др.).
УСЛОВНЫЙ ОПЕРАТОР
Условныйоператор IF позволяет изменитьпорядок выполнения команд в зависимости от некоторого логического условия, т.е.он осуществляет ветвление вычислительного процесса. Ус