Министерство общего и профессионального образования Российской Федерации Уральский государственный университет им. А.М. Горького Лахтин А.С Искакова Л.Ю. Языки и технология программирования. Начальный курс. Учебное пособие Екатеринбург 1998 С Искакова Л.Ю. Языки и технология программирования.
Начальный курс. Учеб. пособие. Екатеринбург, 1998. Данное учебное пособие представляет собой первую часть одноименного лекционного курса, который читается студеттам математико-механического фаультета в 1 семестре. Начальный курс посвящен изложению основ создания программ. Изложение ведется с использованием языка программирования
Турбо Паскаль. Рассматриваются некоторые классические алгоритмы. Приводятся примеры решения типовых задач. Пособие предназначено для студентов дистантной формы обучения специальности Информационные системы , а также может быть использовано для студентов дневной формы обучения по этой специальности. А.С. Лахтин, Л.Ю. Искакова, 1998. СОДЕРЖАНИЕ ВВЕДЕНИЕ 5 ОСНОВЫ ЯЗЫКА 5 АЛГОРИТМЫ 5 АЛФАВИТ
ЯЗЫКА 5 СТРУКТУРА ПРОГРАММЫ 6 ТИПЫ ДАННЫХ 7 Целые типы 7 Вещественные типы 8 Логический тип 9 Символьный тип 9 ВЫРАЖЕНИЯ 9 СОВМЕСТИМОСТЬ ТИПОВ ДАННЫХ 10 ЛИНЕЙНЫЕ АЛГОРИТМЫ 11 ПУСТОЙ И СОСТАВНОЙ ОПЕРАТОРЫ 11 ОПЕРАТОР ПРИСВАИВАНИЯ 11 ПРОСТЕЙШИЙ ВВОД И ВЫВОД 11 РАЗВЕТВЛЯЮЩИЕСЯ
АЛГОРИТМЫ 12 ОПЕРАТОР ПЕРЕХОДА 12 УСЛОВНЫЙ ОПЕРАТОР 13 ОПЕРАТОР ВЫБОРА 13 ЦИКЛИЧЕСКИЕ АЛГОРИТМЫ 14 ЦИКЛЫ С ПАРАМЕТРОМ. 14 ЦИКЛЫ С УСЛОВИЕМ. 16 ПОЛЬЗОВАТЕЛЬСКИЕ ТИПЫ ДАННЫХ 17 ПЕРЕЧИСЛЯЕМЫЙ ТИП 17 ТИП-ДИАПАЗОН 17 МАССИВЫ 17 ЗАПИСИ 17 РАБОТА СО СТРОКАМИ 17 ПРОЦЕДУРЫ
И ФУНКЦИИ 17 Параметры-значения 17 Параметры-переменные 17 Параметры-константы 17 ОТКРЫТЫЕ ПАРАМЕТРЫ-МАССИВЫ 17 БЕСТИПОВЫЕ ПАРАМЕТРЫ 17 ПРОЦЕДУРНЫЕ ТИПЫ 17 РЕКУРСИЯ 17 ТИПИЗИРОВАННЫЕ КОНСТАНТЫ 17 МОДУЛИ 17 АЛГОРИТМЫ ПОИСКА 17 ЛИНЕЙНЫЙ ПОИСК 17 ПОИСК С БАРЬЕРОМ 17 ДВОИЧНЫЙ БИНАРНЫЙ
ПОИСК 17 АЛГОРИТМЫ СОРТИРОВКИ 17 СОРТИРОВКА ВЫБОРОМ 17 СОРТИРОВКА ОБМЕНОМ методом пузырька 17 ШЕЙКЕРНАЯ СОРТИРОВКА 17 СОРТИРОВКА ВКЛЮЧЕНИЕМ 17 СОРТИРОВКА ХОАРА 17 СОРТИРОВКА С ИСПОЛЬЗОВАНИЕМ ВЕКТОРА ИНДЕКСОВ 17 МОДУЛЬ CRT основные возможности 17 ЛИТЕРАТУРА 17 ВВЕДЕНИЕ Первая версия языка Паскаль была разработана швейцарским ученым
Никлаусом Виртом в 1968 году. Первоначально язык предназначался для целей обучения, поскольку он является достаточно детерминированным, т.е. все подчиняется определенным правилам, исключений из которых не так много. Основные характеристики относительно небольшое количество базовых понятий, простой синтаксис, быстрый компилятор для перевода исходных текстов в машинный код. В 1992 г. фирма Borland International выпустила два пакета, основанных на языке
Паскаль Borland Pascal 7.0 и Turbo Pascal 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 и идентификатора - имени программы, за котором следует точка с запятой.
Порядок объявлений и описаний не регламентируется. ПРИМЕР Простейшая программа. program prim 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. program sravnenie 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 eps. Число eps можно определять следующим образом min abs a ,abs b 10 -m , где m - необходимое число совпадающих десятичных разрядов. Логический тип Переменные логического типа 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 операции отношения
В логическом выражении 2 4 and 5 3 Паскаль выдаст ошибку, поскольку операция and будет выполнена раньше операций сравнения. Верная запись - 2 4 and 5 3 . СОВМЕСТИМОСТЬ ТИПОВ ДАННЫХ Когда в операциях или операторах вашей программы присутствуют данные разных типов, то встает вопрос об их совместимости. В языке Турбо Паскаль этому вопросу уделяется очень большое внимание, разработаны строгие правила, определяющие идентичность, совместимость в общем случае и совместимость по присваиванию
различных типов. Нам в начале курса достаточно помнить следующее. Переменные или выражения одного типа являются полностью совместимыми. Другим понятием является совместимость по присваиванию. Присваивание переменной одного типа выражения другого типа допустимо в том случае, когда множество значений второго типа является подмножеством значений первого.
Например, результат сложения двух целых переменных типа integer и word может присваиваться в целую переменную, тип которой только longint, поскольку только этот целый тип содержит в себе весь возможный диапазон значений как для типа integer, так и для типа word. Также, можно присваивать целое выражение в вещественную переменную или символьное выражение в строку. ЛИНЕЙНЫЕ АЛГОРИТМЫ Алгоритмические действия над исходными данными и рабочими объектами языка, необходимые
для решения поставленной задачи описываются при помощи операторов Турбо Паскаля. Операторы разделяются точкой с запятой, их последовательность и составляет тело программы. Наиболее простой случай представляют собой линейные алгоритмы. При выполнении линейных участков алгоритма операторы выполняются последовательно друг за другом в том порядке, в котором они перечислены в программе. При этом могут использоваться операторы присваивания,
операции ввода и вывода. ПУСТОЙ И СОСТАВНОЙ ОПЕРАТОРЫ В программе может применяться пустой оператор, не выполняющий никакого действия. Он представляет собой точку с запятой. Составным оператором считается последовательность произвольных операторов, заключенная в операторные скобки - зарезервированные слова begin end. Допускается произвольная глубина вложенности составных операторов.
Составной оператор применяется там, где по синтаксическим правилам языка может стоять только один оператор, а нам надо выполнить несколько действий. В этом случае набор необходимых команд должен быть оформлен как составной оператор. По сути, все тело программы представляет собой один составной оператор. ОПЕРАТОР ПРИСВАИВАНИЯ Оператор присваивания используется для задания значения переменных и имеет следующий синтаксис имя переменной выражение Вычисляется выражение, стоящее в правой части оператора, после чего
его значение записывается в переменную, имя которой стоит слева. Тип выражения и тип переменной должны быть совместимы, т.е. множество допустимых значений для типа выражения содержится во множестве допустимых значений для типа переменной. ПРОСТЕЙШИЙ ВВОД И ВЫВОД Рассмотрим простейшие процедуры ввода и вывода. По умолчанию ввод осуществляется с клавиатуры, а вывод на экран.
К операторам ввода относятся Read список переменных через запятую Readln список переменных Readln Второй отличается от первого тем, что после ввода переводит курсор на новую строку, точнее, в конце своей работы считывает с клавиатуры код клавиши Enter . Третий оператор используется для организации паузы - выполнение программы продолжится, как правило, только после нажатия на клавиатуре клавиши Enter .
К операторам вывода относятся Write список вывода Writeln список вывода Writeln В списке вывода кроме имен переменных можно писать строковые константы последовательность символов в апострофах и даже выражения выводятся их значения . Второй оператор отличается от первого тем, что после вывода переводит курсор на новую строку. Третий оператор просто переводит курсор на новую строку.
Существует так называемый форматированный вывод. Можно задать количество позиций, отводимых под число. Для целых - после выражения или переменной через двоеточие указывается меньше какого количества позиций не может быть выделено значению. Для вещественных - дополнительно через двоеточие можно указать количество цифр в дробной части. При этом происходит округление в ближнюю сторону. ПРИМЕР Простые вычисления. program vvod vyvod const n 1.5 var y1,y2 real x byte begin writeln
Введите натуральное число 255 readln x y1 cos n y2 cos x write Зачем-то посчитали writeln n ,n, y1 ,y1 7 4, cos Pi 2 8 4 напечатается Зачем-то посчитали n 1.50E 0000 y1 0.0707 1.0000 writeln x ,x 3, y2 ,y2 7 4 end. РАЗВЕТВЛЯЮЩИЕСЯ АЛГОРИТМЫ В Турбо Паскале имеется возможность нелинейного хода программы, т.е. выполнения операторов не в том порядке, в котором они записаны.
Такую возможность нам предоставляют разветвляющиеся алгоритмы. Они могут быть реализованы одним из трех способов с использованием операторов перехода, условного оператора или оператора выбора. ОПЕРАТОР ПЕРЕХОДА Оператор перехода имеет вид GOTO метка . Он позволяет передать управление непосредственно на нужный оператор программы. Перед этим оператором должна располагаться метка отделенная от него двоеточием.
В Турбо Паскале в качестве меток выступают либо целые числа от 0 до 9999, либо идентификаторы. Все метки должны быть описаны в разделе объявления меток следующим образом label список меток через запятую Каждой меткой в программе может быть помечен только один оператор. Операторов перехода с одной и той же меткой можно писать любое количество. Необходимо, чтобы раздел описания метки, сама метка h оператор перехода с ее использованием располагались
в пределах одного блока программы см. тему процедуры и функции . Кроме того, нельзя передавать управление внутрь структурированных операторов например, if, for, while, repeat и др УСЛОВНЫЙ ОПЕРАТОР Условный оператор IF позволяет изменить порядок выполнения команд в зависимости от некоторого логического условия, т.е. он осуществляет ветвление вычислительного процесса. Условный оператор имеет вид IF условие THEN оператор1
ELSE оператор2 В случае истиности логического выражения, стоящего в условии, выполняется оператор1 , а оператор2 пропускается. При ложном значении логического выражения пропускается оператор1 и выполняется оператор2 . Оператор IF может быть полным присутствуют обе ветви или неполным Else-ветви нет, при ложном условии ничего не делается . По правилам каждая из ветвей может содержать либо один выполняемый оператор, либо несколько, объединенных
в составной. Точка с запятой перед Else считается ошибкой. ПРИМЕР Ввести целое число. Вывести соответствующий ему символ ASCII- таблицы, либо сообщить, что такого символа нет 0-31 - управляющие коды, затем до 256 - печатаемые символы . program ascii symbol var i word begin write Введите целое число readln i if i 31 and i 256 then writeln
Соответствующий символ Chr i else writeln Такого символа нет readln end. ОПЕРАТОР ВЫБОРА Если у вас не два возможных варианта выполнения программы, а больше, то может использоваться оператор выбора CASE. Структура этого оператора в Турбо Паскале CASE ключ выбора OF C1 оператор1 C2 оператор2 CN операторN ELSE оператор0 END Здесь ключ выбора - это выражение порядкового типа, в зависимости от
значения которого принимается решение C1, ,CN - значения, с которыми сравнивается значение ключа оператор1 операторN - оператор возможно составные , из которых выполняется rnr, с константой которого происходит первое совпадение значения ключа , оператор0 выполнится, если значение ключа не совпадает ни с одной из констант C1, ,CN. Ветвь Else не обязательна, и в отличие от оператора if, перед ней можно ставить точку с запятой. Если для нескольких значений ключа действия совпадают, то эти константы можно перечислить
через запятую перед двоеточием или даже задать диапазон значений нижняя граница верхняя граница . ПРИМЕР Вводится целое число, если это цифра, то определить четная она или нет, а если число, то определить попадает ли оно в диапазон от 10 до 100, если нет, то выдать соответствующее сообщение. program chislo var i integer begin write Введите целое число readln i case i of 0,2,4,6,8 writeln Четная цифра 1,3,5,7,9 writeln Нечетная цифра 10 100,200 writeln
Число от 10 до 100 или 200 else writeln Число либо отрицательное, либо 100, но не 200 end readln end. ЦИКЛИЧЕСКИЕ АЛГОРИТМЫ Турбо Паскаль позволяет использовать три различных оператора для организации повторяющихся последовательностей действий, которые называют циклами. ЦИКЛЫ С ПАРАМЕТРОМ. Оператор цикла For организует выполнение одного оператора заранее определенное число раз. Его еще называют цикл со счетчиком. Существует две формы оператора
FOR параметр nz TO kz DO оператор FOR параметр nz DOWNTO kz DO оператор Здесь параметр цикла счетчик представляет собой переменную порядкового ординального типа nz и kz - выражения, определяющие начальное и конечное значение счетчика оператор - один возможно составной оператор, который называют телом цикла, повторяемый определенное число раз. На первом шаге цикла параметр принимает значение nz.
В этот же момент происходит вычисление kz - значения параметра на последнем шаге цикла. После каждого выполнения тела цикла, если параметр цикла не равен kz, происходит изменение параметра на следующее большее или меньшее значение в зависимости от формы оператора for, т.е. неявно происходит выполнение одного из двух операторов параметр Succ параметр параметр Pred параметр В случае nz kz в первой форме оператора или nz kz во второй его форме ошибки не происходит,
но цикл не выполняется ни разу. После завершения работы цикла значение параметра остается равным kz. РЕКОМЕНДАЦИИ Использовать цикл for при заранее известном количестве повторений. Не изменять параметр в теле цикла. При использовании кратных вложенных циклов применять разные переменные в качестве параметров. Определять до цикла значения всех используемых в нем переменных. Не ставить точку с запятой после do. ПРИМЕР Вводятся 10 чисел, посчитать среди них количество положительных.
program cycle for1 var i,kn byte x real begin kn 0 for i 1 to 10 do begin writeln Введите ,i, число readln x if x 0 then kn kn 1 увеличиваем количество на 1 end writeln Вы ввели ,kn, положительных чисел. readln end. ПРИМЕР Напечатать буквы от Z до A . program cycle for2 var c char begin for c Z downto A do write c readln end ПРИМЕР Вычислить N-е число
Фиббоначчи. Числа Фиббоначчи строятся следующим образом F 0 F 1 1 F i 1 F i F i-1 для i 1. Это пример вычислений по рекуррентным формулам. program Fib var a,b,c word i,n byte begin write введите номер числа Фиббоначчи readln N a 1 a F 0 , a соответствует F i-2 b 1 b F 1 , b соответствует F i-1 for i 2 to N do begin c a b c соответствует
F i a b b c в качестве a и b берется следующая пара чисел end writeln N, -е число Фиббоначчи ,b для N 2 b c readln end. ЦИКЛЫ С УСЛОВИЕМ. Если заранее неизвестно число повторений цикла, то используются циклы с условием. В паскале имеется два типа таких циклов. Циклы While называют циклами с пред-условием. Они имеют вид WHILE логич.выражение DO оператор Цикл
While организует выполнение одного возможно составного оператора пока истинно логическое выражение, стоящее в заголовке цикла. Поскольку значение логического выражения проверяется в начале каждой итерации, то тело цикла может не выполниться ни разу. Таким образом, в этом цикле логическое выражение - это условие продолжения работы в цикле. Другой вариант циклов с условием - это циклы Repeat. Их называют циклами с пост-условием. Они имеют вид
REPEAT оператор 1 оператор N UNTIL логич.выражение Оператор Repeat организует повторяющееся выполнение нескольких операторов до тех пор пока не станет истинным условие, стоящее в Until- части. Тело цикла обязательно выполняется хотя бы один раз. Таким образом, в этом цикле логическое выражение - это условие выхода из цикла. При создании циклических алгоритмов Турбо Паскаль позволяет использовать процедуры
Continue и Break. Процедура Continue досрочно завершает очередной шаг цикла, передает управление на заголовок. Процедура Break реализует немедленный выход из цикла. РЕКОМЕНДАЦИИ Для того, чтобы избежать зацикливания программы необходимо обеспечить изменение на каждом шаге цикла значения хотя бы одной переменной, входящей в условие цикла. После выхода из цикла со сложным условием с использованием операций and, or, xor как правило необходима
проверка того, по какому условию цикл завершен. ПРИМЕР Пары неотрицательных вещественных чисел вводятся с клавиатуры. Посчитать произведение для каждой пары и сумму всех чисел. program cycle while var x,y,sum real otv char begin sum 0 otv Д while otv Д or otv д do begin write Введите числа x,y 0 readln x,y writeln Их произведение ,x y 8 3 sum sum x y write
Завершить программу Д Н ? readln otv end writeln Общая сумма ,sum 8 3 readln end. ПРИМЕР В той же задаче можно использовать другой цикл с условием program cycle repeat var x,y,sum real otv char begin sum 0 repeat write Введите числа x,y 0 readln x,y writeln Их произведение ,x y 8 3 sum sum x y write Завершить программу Д Н ? readln otv until otv Д or otv д writeln Общая сумма ,sum 8 3 readln end.
ПРИМЕР Нахождение наибольшего общего делителя двух целых чисел с помощью Алгоритма Эвклида. program Evklid var a,b,c integer begin write введите два целых числа readln a,b while b 0 do begin c a mod b a b b c end writeln наибольший общий делитель ,a readln end. ПОЛЬЗОВАТЕЛЬСКИЕ ТИПЫ ДАННЫХ В Турбо Паскале предусмотрен механизм создания новых типов, которые принято называть пользовательскими или конструируемыми. Их можно создавать на основе стандартных и ранее созданных
типов. Описание новых типов происходит в разделе TYPE. После этого можно в разделе Var создавать переменные этих типов. Также, можно сразу описывать новый тип при создании переменной в разделе Var. В этой главе мы рассмотрим следующие пользовательские типы перечисляемый тип, тип-диапазон, массивы, записи. ПЕРЕЧИСЛЯЕМЫЙ ТИП Перечисляемый тип задается перечислением тех значений, которые он может получать.
Каждое значение должно являться идентификатором смотри главу Алфавит языка и располагаться в круглых скобках через запятую. Количество элементов в перечислении не более 65536. Вводить и выводить переменные перечисляемого типа запрещено. Перечислимый тип является порядковым смотри главу
Типы данных , поэтому к переменным такого типа можно применять функции Ord, Pred, Succ. Функция Ord возвращает порядковый номер значения начиная с нуля. ПРИМЕР Объявление перечисляемых типов. Type Colors Red,Green,Blue Numbers Zero,One,Two,Three,Four,Five var c Colors n Numbers begin c Red write Ord c 0 n Four write
Ord n 4 c Succ c c Green for n One to Five do write Ord n 12345 end. Следует отметить, что стандартные типы byte, word, char и boolean также можно считать вариантами перечислимого типа. ТИП-ДИАПАЗОН Тип-диапазон также называют ограниченным или интервальным типом. Он является подмножеством своего базового типа, в качестве которого может выступать любой порядковый тип кроме типа-диапазона. Типдиапазон наследует все свойства своего базового типа.
Имеются две стандартные функции, работающие с этим типом High x - возвращает максимальное значение типа-диапазона, к которому принадлежит переменная x Low x - возвращает минимальное значение. ПРИМЕР Объявление типа-диапазон. type Numbers Zero,One,Two,Three,Four,Five Num Two Four диапазон на базе типа Numbers Abc A z все английские буквы диапазон на базе типа
Char Digits 0 9 цифры var n Num c,d Abc x integer begin n Four writeln Ord n 4 как в базовом типе n Succ n ОШИБКА следующее значение вне диапазона read c,d if c d then write одинаковые буквы writeln Low c , ,High c A z writeln Low x , ,High x -32768 32767 end. В тексте программы на Турбо Паскале могут встречаться директивы компилятору, которые также называют опциями.
Опции R и R- позволяют включать и отключать проверку соблюдения границ при работе с диапазонами. Когда проверка включена, при нарушении границ диапазонов происходит аварийное завершение работы программы. В другом случае ответственность за возможные ошибки лежит на программисте. МАССИВЫ Массив - это упорядоченная структура однотипных данных, хранящая их последовательно. Доступ к элементу массива осуществляется через его индекс.
Массивы описываются следующим образом Имя типа ARRAY диапазоны индексов OF тип элемента массива В качестве типа для элементов массива можно использовать любые типы Турбо Паскаля кроме файловых. Диапазоны индексов представляют собой один или несколько диапазонов, перечисленные через запятую. В качестве диапазонов индексов нельзя использовать диапазоны с базовым типом Longint. ПРИМЕР Три способа описания одного и того же типа массива type 1
M1 array 0 5 of integer M2 array char of M1 M3 array -2 2 of M2 2 M3 array -2 2 of array char of array 0 5 of integer 3 M3 array -2 2,char,0 5 of integer var A M3 Обращаться к элементам массива можно следующим образом begin read A -1, a ,3 read A 1 x 0 A 1 c ,1 100 end. Глубина вложенности, т.е. количество индексов, при определении массивов не ограничена. Играет роль только суммарный объем данных в программе.
В стандартном режиме работы Турбо Паскаля этот объем ограничен размерами сегмента, т.е. 64 килобайта. Целиком над массивами допускается применение только операции присваивания массивов подмассивов одинаковых типов. Остальные операции должны выполняться поэлементно. ПРИМЕР Вычисление значения многочлена степени N, коэффициенты которого находятся в массиве A в точке X по схеме Горнера. Pn x A 0 X n A 1 X n-1
A n-1 X A n A 0 X A 1 X A 2 X A n-1 X A n . program Scheme Gorner type Mas array 0 100 of integer var A Mas i,j,n integer x,p real begin write степень многочлена read n writeln введите целые коэффициенты for i 0 to n do read A i write значение X read x p 0 for i 0 to n do p p x A i writeln Pn X ,p end. ЗАПИСИ Запись - это стpуктуpа данных, котоpая может содеpжать инфоpмацию pазных
типов, объединенную под одним названием. Компоненты записи называются полями. Их фиксиpованное число. Описание записей имеет следующую стpуктуpу Имя типа RECORD список полей 1 тип 1 список полей N тип N CASE поле выбора тип OF значение 1 полей 1 тип 1 END Типы полей записи могут быть любыми. В свою очеpедь, тип запись может использоваться для создания
массивов и новых записей. Степень вложенности не огpаничена. Список полей может состоять из двух pазделов постоянной и ваpиантной части. В постоянной части идет пеpечисление полей записи идентификатоpов с указанием их типов. Синтаксис такой же, как в pазделе var. ПРИМЕР Пример объявления типа запись. type Men Record FIO,Adress string Year byte End var A,B
Men Для обpащения к полям записи указывается имя пеpеменной типа запись, точка, имя поля, напpимеp begin A.FIO Иванов И.И. A.Adress пp. Ленина, д. 40, кв. 10 A.Year 1981 end. После описания постоянных полей может следовать ваpиантная часть, котоpая может быть только одна и имеет вид CASE поле выбоpа тип OF значение 1 список полей 1 значение N список полей N Поле выбоpа может отсутствовать. Если оно есть, то его воспpинимают как постоянное
поле записи. Если его нет, указывается только тип, котоpый должен быть поpядковым, но он не влияет ни на количество пеpечисленных ниже значений, ни на типы этих значений. Все ваpианты pасполагаются в одном и том же месте памяти, котоpой выделяется столько, сколько тpебуется для максимального по pазмеpу ваpианта. Это пpиводит к тому, что изменение одного ваpиантного поля оказывает влияние на все остальные. Это увеличивает возможности пpеобpазования типов,
ПРИМЕР Запись с вариантами. var R Record rem string Case byte of 3 n integer 5 x,y,z char a i,j byte end begin R.rem запись с ваpиантами R.n 25000 write R.i,R.x,R.j,R.y 168и97a ord и 168, ord a 97, 168 97 256 25000 end. Значения выбоpа могут повтоpяться. Имена полей записи не являются пеpеменными и, следовательно, могут
повтоpяться, но только на pазных уpовнях, напpимеp var Rec Record x real Sr Record a real x,y integer end I byte end Для удобства обpащения к полям записей может использоваться опеpатоp пpисоединения WITH пеpеменная DO опеpатоp Здесь пеpеменная - это запись, за котоpой может следовать список вложенных полей, напpимеp следующие тpи опеpатоpа эквивалентны
With Rec,Sr Do a x y With Rec.Sr Do a x y Rec.Sr.a Rec.Sr.x Rec.Sr.y РАБОТА СО СТРОКАМИ Тип String строка в Турбо Паскале широко используется для обработки текстов. Этот тип является стандартным и во многом похож на одномерный массив символов Array 0 N of Char. Значение N соответствует количеству символов в строке и может меняться от 0 до 255.
Символы, входящие в строку, занимают позиции с 1 до N. Начальный байт строки с индексом 0 содержит информацию о ее длине, т.е. это символ с кодом, равным длине строки. Можно, также описывать переменные типа String K , где K - целое число не больше 255. Так определяются строки с длиной не больше K. Этот тип уже не является стандартным. С символами строки можно работать как с элементами массива
из символов, но в отличие от массивов, строки можно вводить целиком, сравнивать друг с другом и сцеплять операцией . ПРИМЕР Работа со строками. var s,x,y,z string begin x turbo y pascal z x y z turbo pascal s пустая строка for c a to z do s s c s abcd xyz writeln s end. Сравнение строк выполняется посимвольно в соответствии с их кодами до первого несовпадения. Если одна из строк закончилась до первого несовпадения, то она считается меньшей.
Пустая строка меньше любой строки. ПРИМЕР Сравнение строк. abcd abcD d D abcd abc d abc axxc b x abcd abcd Существует ряд стандартных функций и процедур для работы со строками. Функция Length s выдает длину строки s. Функция Concat s1,s2, ,sn возращает строку s1 s2 sn. Функция Copy s,p,k возвращает фрагмент строки s, который начинается в позиции p и имеет длину k. Функция Pos s1,s ищет первое вхождение подстроки s1 в строку s и возвращает номер первого символа s1
в строке s или 0 если не нашли. Процедура Delete s,p,k удаляет из строки s фрагмент, который начинается в позиции p и имеет длину k. Процедура Insert s,s1,p вставляет в строку s подстроку s1, начиная с заданной позиции p. Турбо паскаль позволяет производить преобразования числовых значений в строковые и наоборот. Для этого используются процедуры Str X n d,S и Val S,X,e . Первая получает их числа X строку S с изображением этого числа, в которой не менее n символов
и из них d знаков после запятой. Параметры n и d необязательные. Вторая процедура получает из строки S число X. При успешном результате e 0. ПРОЦЕДУРЫ И ФУНКЦИИ Турбо Паскаль позволяет выделять фрагменты программы во вспомогательные алгоритмы ВА . Это позволяет писать хорошо структурированные программы. Языки программирования, в которых предусмотрены ВА, называются процедурно-ориентированными.
Структурированные программы обычно проще в понимании и отладке. Наличие ВА в языке программирования позволяет применять более совершенные методы при разработке и проектировании сложных программных комплексов. Известны два наиболее широко применяемых подхода. Первый называется методом нисходящего программирования или разработкой программ сверху - вниз . При этом сначала создается главная программа, предполагая наличие некоторых
ВА, решающих определенные задачи. Затем переходят к детальной разработке упомянутых выше необходимых ВА. Другим подходом в разработке программ является метод восходящего программирования или проектированием снизу - вверх . В этом случае все начинается с создания небольших ВА, из которых затем создаются более сложные ВА и, наконец, основная программа. В Турбо Паскале ВА оформляются в виде процедур или функций.
Каждый ВА имеет собственное имя. Вызов процедуры на выполнение осуществляется отдельным оператором с помощью ее имени. Вызов функции может быть составной частью любого выражения при условии согласованности типов. Описание процедур и функций должно предшествовать их вызову и располагается перед началом основной программы. Нельзя вызывать на выполнение те ВА, которые содержатся внутри других процедур и функций. Описание процедуры имеет следующую структуру. Procedure
Имя Список формальных параметров label const Описание локальных меток, type констант, типов и переменных var procedure Описание внутренних процедур function и функций begin Операторы end Описание функции имеет следующую структуру. Function Имя Список формальных параметров Тип результата label const Описание локальных меток, type констант, типов и переменных var procedure
Описание внутренних процедур function и функций begin Операторы, среди которых хотя бы один, который присваивает имени функции значение результата end. Типом результата в функциях может быть любой из стандартных типов Турбо Паскаля кроме файловых типов. Использование конструируемых типов здесь недопустимо. Существуют понятия локальных и глобальных меток, констант, типов и переменных.
Поясним эти понятия на примере переменных. Переменные, описанные в основной программе, являются глобальными по отношению к процедурам и функциям, которые описаны позже этих переменных. Аналогично, переменные, описанные в процедурах и функциях, являются глобальными по отношению к внутренним процедурам и функциям, которые описаны позже. Остальные переменные называются локальными. Их область действия локализована, т.е. ограничена, тем
ВА, где они описаны. Исходные данные для работы ВА можно передавать через глобальные переменные, а также через параметры. Параметры при вызове ВА называются фактическими, а параметры в заголовке ВА называются формальными. Формальные параметры ВА также относятся к его локальным переменным. Локальные данные создаются, т.е. им выделяется память, при вызове ВА, а освобождение этой памяти происходит при завершении работы
ВА. В том случае, когда локальная переменная имеет тот же идентификатор, что и глобальная, алгоритм работает с локальной. При этом, значение глобальной переменной сохраняется в специальной области памяти, которая называется стек. По способу передачи параметры в Турбо Паскале делятся на три типа параметры-значения, параметры-переменные, параметры-константы. Параметры-значения При вызове процедур и функций формальным параметрам-значениям выделяется новое место
в памяти и присваиваются значения фактических параметров. При этом на месте фактических параметров могут стоять выражения. Совместимость типов определяется возможностями присваивания. После выполнения подпрограммы место формальных параметров освобождается. Изменение формальных параметров не сказывается на значении фактических.
Заголовок процедуры с параметрами- значениями имеет вид Procedure MyProc1 par1,par2 type1 par3,par4 type2 Параметры-переменные При вызове процедур и функций формальные параметры-переменные занимают то же самое место в памяти, что и соответствующие им фактические параметры. Таким образом, дополнительное место в памяти не выделяется и изменения формального параметра приводят к изменениям фактического.
Параметры-переменные, как правило, используются для передачи результатов из процедур в вызывающий алгоритм. Такой механизм передачи данных требует, чтобы фактические параметры были переменными, причем в точности того же типа, что и формальные параметры. При описании ВА перед параметрами-переменными должно присутствовать слово var. Заголовок процедуры с параметрамипеременными имеет вид
Procedure MyProc2 var par1,par2 type1 var par3,par4 type2 Параметры-константы Работа с формальными параметрами-константами внутри ВА ведется как с обычными локальными константами. Только эти константы принимают значения выражений, которые находятся в фактических параметрах. Им не выделяется новая память как локальным переменным. Запрещается изменять их значения во время выполнения подпрограммы и контроль за этим осуществляется
на уровне компилятора, как для обычных констант. Использовать параметры-константы рекомендуется при передаче данных большого объема с гарантией сохранения их значений. Заголовок процедуры с параметрами-константами имеет вид Procedure MyProc3 const par1,par2 type1 const par3,par4 type2 ОТКРЫТЫЕ ПАРАМЕТРЫ-МАССИВЫ Открытые параметры-массивы могут быть параметрами-значениями, параметрами-
переменными и параметрами-константами. Они используются для передачи массивов произвольной размерности. Заголовок процедуры с открытыми параметрами-массивами имеет вид Procedure OpenArray Vector array of MyType Формальный параметр при этом является массивом элементов некоторого типа MyType с нулевой базой, т.е. Array 0 N-1 of MyType где N - количество элементов массива, которое можно определить с помощью стандартной функции
High. ПРИМЕР Увеличение вдвое всех элементов массива. program DoubleProgram const n 10 m 20 type T1 array 1 n of integer T2 array -m m of integer var A T1 B T2 k integer Procedure Double var X array of integer var i byte begin for i 0 to High X -1 do X i X i 2 end begin for k 1 to n do read
A k for k -m to m do read B k Double A увеличение в 2 раза элементов массива A Double B увеличение в 2 раза элементов массива B Double k то же самое, что и присваивание k k 2 writeln k ,k напечатается k 40 for k 1 to n do write A k , writeln for k -m to m do write B k , end. БЕСТИПОВЫЕ ПАРАМЕТРЫ В Турбо Паскале существует возможность создания процедур и функций с параметрами, не имеющими
типа. Бестиповые параметры могут быть параметрами-переменными и параметрами-константами, так как передаются только по адресу. Заголовок процедуры с параметрами, не имеющими типа может выглядеть таким образом Procedure MyProc var par1,par2 const par3,par4 Перед использованием формальных параметров необходимо выполнить их приведение к какому-либо типу. Использование бестиповых параметров дает большую гибкость программе, но ответственность за их корректное применение возлагается на программиста.
ПРИМЕР Сложение первых N байт, начиная с того же места, что и X. program without type var N word s string R- отключение контроля за границами диапазонов function Sum var X N byte word type A array 1 1 of byte var i byte s word begin s 0 for i 1 to n do S S A X i Sum s end begin readln s writeln Sum s,1 длина строки s writeln Sum s 1 ,1 код первого символа строки s writeln Sum s 1 ,length s сумма кодов всех символов строки s
read N writeln Sum N,2 сумма двух байт, из которых состоит N типа word end. ПРОЦЕДУРНЫЕ ТИПЫ В Турбо Паскале существует два процедурных типа тип-процедура и тип-функция. Для объявления процедурного типа используется заголовок процедуры или функции без имени. ПРИМЕР type Proc1 Procedure a,b,c integer x real Proc2 Procedure var a,b Proc3 Procedure Func1 Function real
Func2 Function n integer boolean Можно описывать переменные этих типов, например var p1,p2 Proc1 f1,f2 Func2 Переменным процедурных типов можно присваивать в качестве значений имена соответствующих ВА. При этом нельзя использовать стандартные процедуры и функции. После такого присваивания имя переменной становится синонимом имени ВА. Переменные процедурного типа можно, также передавать в подпрограммы в виде параметров.
Благодаря этому, имеется возможность создания более гибких вспомогательных алгоритмов. РЕКУРСИЯ Рекурсия - это способ организации вычислительного процесса, при котором подпрограмма в ходе выполнения обращается сама к себе. С идейной точки зрения рекурсия аналогична методу математической индукции. Базе индукции соответствует база рекурсии. Предположению индукции соответствует предположение о том, что нужный
ВА уже написан. Наконец, шагу индукции соответствует вызов создаваемого рекурсивного ВА. В любой рекурсии необходимо предусмотреть условие завершения процесса, т.е. когда вызова больше не происходит. ПРИМЕР Вычислить N-е число Фиббоначчи. Смотри тему Циклы program Fib var n byte function F k byte word begin if k 2 then F 1 else F F k-1 F k-2 рекурсивный вызов end begin write введите номер
числа Фиббоначчи readln N writeln N, -е число Фиббоначчи ,F N readln end. Рекурсивный вызов может быть косвенным, или неявным. Например это происходит в случае, когда один ВА вызывает другой, а тот в свою очередь - первый. При использовании такой программной конструкции необходимо опережающее описание процедур и функций с директивой Forward. Сначала пишется только заголовок
ВА со словом Forward, а реализация приводится ниже. При этом, в ней можно писать в заголовке либо только имя ВА, либо полностью повторять заголовок. ПРИМЕР Неявная рекурсия. Procedure B x byte forward Procedure A y byte begin B y end Procedure B begin A x end РЕКОМЕНДАЦИИ Необходимо по возможности избегать применения рекурсии,
так как большая глубина рекурсивных вызовов часто приводит к переполнению стека. В некоторых случаях проблему можно устранить, установив новый размер стека от 1024 до 65520 байт с помощью директивы M размер стека, нижняя граница, верхняя граница памяти ТИПИЗИРОВАННЫЕ КОНСТАНТЫ Кроме обычных констант в Турбо Паскале можно использовать типизированные константы, которые фактически являются переменными с начальными
значениями. Они описываются в разделе Const в форме имя типизированной константы тип значение ПРИМЕР const x integer 10 y real 3.14 A array 1 5 of integer 1,2 3,24,0 B array 1 2 1 1 of byte 1,2,3 , 4,5,6 R record m string 10 d,y integer end m January d 20 y 1999 S string 4 abcd Типизированные константы могут быть любого типа кроме файлов. При работе они практически ничем не отличаются от переменных.
Разница состоит только в том, что если типизированная константа описана в процедуре или функции, то при первом вызове этой подпрограммы типизированная константа принимает начальное значение, а при последующих вызовах сохраняет значение от предыдущего вызова. Таким способом можно, например, контролировать количество вызовов процедур или функций. ПРИМЕР Использование типизированных констант program typed const var N integer procedure Test const k integer 1 begin if k
N then begin writeln k, -й вызов процедуры k k 1 Test end else writeln последний вызов процедуры end begin read N if N 0 then Test end. МОДУЛИ Модуль Unit в паскале - это специальным образом оформленная библиотека определений типов, констант, переменных, а также процедур и функций. Модуль компилируется отдельно, в результате чего создается файл с расширением tpu turbo pascal unit . Он не может быть запущен на выполнение самостоятельно, а может использоваться только из других программ.
Для этого в программах указывается список имен используемых модулей в разделе Uses, после чего программа может использовать константы, типы и переменные, описанные в этих модулях. В Турбо Паскале существует несколько стандартных модулей System, Crt, Dos, Printer, Overlay, которые составляют библиотеку Турбо Паскаля файл turbo.tpl turbo pascal library .
К числу стандартных модулей также относится модуль Graph. Существует возможность создавать новые модули. Файл модуля имеет следующую структуру UNIT имя модуля INTERFACE раздел объявлений IMPLEMENTATION раздел реализации Begin раздел инициализации End. Имя модуля должно совпадать с именем файла, в котором он хранится.
Раздел объявлений или интерфейсная часть содержит объявления всех глобальных объектов модуля типов, констант, переменных и подпрограмм , которые будут доступны программам, использующим этот модуль. Подпрограммы в этом разделе объявляются только заголовками. В интерфейсной части модулей нельзя использовать опережающее описание, т.е. директиву forward. Раздел реализации или исполняемая часть модуля содержит описание локальных объектов модуля типов, констант,
переменных и подпрограмм. Здесь же содержится описание подпрограмм, объявленных в интерфейсной части. Для этих подпрограмм заголовок может указываться либо без параметров, либо с параметрами, которые в точности повторяют описание из раздела объявлений. Локальные объекты модуля доступны в пределах модуля, но не доступны программам, использующим модуль. Раздел инициализации может отсутствовать. В этом случае можно даже не писать слово
Begin, а сразу завершать модуль, написав End. В раздел инициализации входят операторы, которые будут выполняться при запуске программы, использующей модуль, перед выполнением основной программы. Разделы инициализаций выполняются в том порядке, в котором подключаются модули. ПРИМЕР Модуль для работы с одномерными массивами до 100 целых чисел. модуль описаний, глобальных для основной программы и всех модулей Unit Globals Interface const
Len 100 type Vector array 1 Len of integer Implementation End. Unit Vectors Interface uses Globals находит максимальный элемент массива function Max V A Vector n byte integer поэлементное сложение двух векторов procedure Add V A,B Vector n byte var C Vector скалярное произведение векторов function Scal V A,B Vector n byte integer Implementation function
Max V заголовок без параметров var i,max integer begin max A 1 for i 2 to n do if A i max then max A i Max V max end procedure Add V var i integer begin for i 1 to n do C i A i B i end function Scal V A,B Vector n byte integer заголовок из interface var s integer i byte begin s 0 for i 1 to n do s s A i B i Scal V s end End. раздел инициализации модуля отсутствует
АЛГОРИТМЫ ПОИСКА Алгоритмы поиска применяются для нахождения, например, в массиве элемента с нужными свойствами. Обычно различают постановки задачи поиска для первого и последнего вхождения элемента. Во всех ниже изложенных алгоритмах будем считать, что производится поиск в массиве A из N целых чисел элемента, равного X. ЛИНЕЙНЫЙ ПОИСК Линейный поиск осуществляется циклом while или repeat - until с двойным условием.
Первое условие контролирует индекс на принадлежность массиву, например, i N . Второе условие - это условие поиска. В нашем случае в цикле while это условие продолжения поиска A i X , а в цикле repeat - until это условие завершения поиска A i X . В теле цикла обычно пишется только один оператор изменение индекса в массиве. После выхода из цикла необходимо проверить, по какому из условий мы вышли.
В операторе if обычно повторяют первое условие цикла. Можно говорить об успешном поиске с циклом while при выполнении этого условия, а с циклом repeat - until при его нарушении. ПРИМЕР Линейный поиск program Poisk1 var A array 1 100 of integer N, X, i integer begin read N N 100 for i 1 to N do read A i read X i 1 i 0 while i
N and A i X do i i 1 repeat i i 1 until i N or A i X if i N then write первое вхождение числа ,X, в массив A на ,i, месте else write не нашли end. При поиске последнего вхождения после ввода должны идти операторы i N i N 1 while i 1 and A i X do i i-1 repeat i i-1 until i 1 or A i X if i 1 then write последнее вхождение числа ,
X, в массив A на ,i, месте else write не нашли ПОИСК С БАРЬЕРОМ Идея поиска с барьером состоит в том, чтобы не проверять каждый раз в цикле условие, связанное с границами массива. Это можно обеспечить, установив в массив так называемый барьер любой элемент, который удовлетворяет условию поиска. Тем самым будет ограничено изменение индекса. Выход из цикла, в котором теперь остается только условие поиска, может произойти либо на найденном
элементе, либо на барьере. Таким образом, после выхода из цикла проверяется, не барьер ли мы нашли? Вычислительная сложность поиска с барьером меньше, чем у линейного поиска, но также является величиной того же порядка, что и N - количество элементов массива. Существует два способа установки барьера дополнительным элементом или вместо крайнего элемента массива. ПРИМЕР Поиск с барьером program Poisk2a var A array 1 101 of integer
N,X,i integer begin read N N 100 for i 1 to N do read A i read X A N 1 X установка барьера дополнительным элементом i 1 i 0 while A i X do i i 1 repeat i i 1 until A i X if i N then write первое вхождение числа ,X, в массив A на ,i, месте else write не нашли end. program Poisk2b var A array 1 100 of integer N,X,i,y integer begin read
N N 100 for i 1 to N do read A i read X y A N сохранение последнего элемента A N X установка барьера на последнее место массива i 1 i 0 while A i X do i i 1 repeat i i 1 until A i X if i N or y X then write первое вхождение числа ,X, в массив A на ,i, месте else write не нашли A N y восстановление последнего элемента массива end.
ДВОИЧНЫЙ БИНАРНЫЙ ПОИСК Алгоритм двоичного поиска можно использовать для поиска элемента с заданным свойством только в массивах, упорядоченных по этому свойству. Так при поиске числа с заданным значением необходимо иметь массив, упорядоченный по возрастанию или по убыванию значений элементов. А, например, при поиске числа с заданной суммой цифр массив должен быть упорядочен по возрастанию или по убыванию сумм цифр элементов.
Идея алгоритма состоит в том, что массив каждый раз делится пополам и выбирается та часть, где может находиться нужный элемент. Деление продолжается пока часть массива для поиска больше одного элемента, после чего остается проверить этот оставшийся элемент на выполнение условия поиска. Существуют две модификации этого алгоритма для поиска первого и onqkedmecn вхождения. Все зависит от того, как выбирается средний элемент округлением в меньшую или большую сторону.
В первом случае средний элемент относится к левой части массива, а во втором - к правой. В процессе работы алгоритма двоичного поиска размер фрагмента, где этот поиск должен продолжаться, каждый раз уменьшается примерно в два раза. Это обеспечивает вычислительную сложность алгоритма порядка логарифма N по основанию 2, где N - количество элементов массива. ПРИМЕР Поиск в упорядоченном по возрастанию массиве первого вхождения числа
X. program Poisk3a var A array 1 100 of integer N,X,left,right integer begin read N N 100 write введите упорядоченный по возрастанию массив for i 1 to N do read A i read X left 1 right N левая и правая граница фрагмента для поиска while left right do begin c left right div 2 середина с округлением в меньшую сторону if X A c then если массив упорядочен по убыванию, то if
X A c left c 1 выбираем правую половину без середины, меняя left else right c выбираем левую половину с серединой, меняя right end if X A left then здесь left right, но не всегда c write первое вхождение числа ,X, в массив A на ,left, месте else write не нашли end. ПРИМЕР Поиск в массиве, упорядоченном по возрастанию сумм цифр элементов массива, последнего числа с суммой цифр равной X. program Poisk3b var A array 1 100 of integer
N,X,left,right integer функция считает сумму цифр числа a, здесь a - локальная переменная function Sum a integer integer var s integer begin s 0 a abs a while a 0 do begin s s a mod 10 a a div 10 end Sum s end begin read N N 100 write введите массив, упорядоченный по возрастанию сумм цифр например, для N 4 122, -432, 88, 593 for i 1 to N do read A i read X left 1 right N левая и правая граница фрагмента для поиска while left right do begin c left right 1
div 2 середина с округлением в большую сторону if X Sum A c then left c выбираем правую половину с серединой, меняя left else right c-1 выбираем левую половину без середины, меняя right end if X Sum A left then здесь left right, но не всегда c write последнее число с суммой цифр ,X, равно ,A left , находится в массиве A на ,left, месте else write не нашли end. АЛГОРИТМЫ
СОРТИРОВКИ Простейшая задача сортировки заключается в упорядочении элементов массива по возрастанию или убыванию. Другой задачей является упорядочение элементов массива в соответствии с некоторым критерием. Обычно в качестве такого критерия выступают значения определенной функции, аргументами которой выступают элементы массива. Эту функцию принято называть упорядочивающей функцией. Существуют различные методы сортировки. Будем рассматривать каждый из методов на примере задачи сортировки
по возрастанию массива из N целых чисел. СОРТИРОВКА ВЫБОРОМ Идея метода заключается в том, что находится максимальный элемент массива и меняется местами с последним элементом с номером N . Затем, максимум ищется среди элементов с первого до предпоследнего и ставится на N-1 место, и так далее. Необходимо найти N-1 максимум. Можно искать не максимум, а минимум и ставить его на первое, второе и так далее место.
Также применяют модификацию этого метода с одновременным поиском максимума и минимума. В этом случае количество шагов внешнего цикла N div 2. Вычислительная сложность сортировки выбором - величина порядка N N, что обычно записывают как O N N . Это объясняется тем, что количество сравнений при поиске первого максимума равно N-1. Затем N- 2, N-3, и так далее до 1, итого
N N-1 2. ПРИМЕР Сортировка выбором по возрастанию массива A из N целых чисел. program Sort Vybor1 var A array 1 100 of integer N,i,m,k,x integer begin write количество элементов массива read N for i 1 to n do read A i for k n downto 2 do k - количество элементов для поиска max begin m 1 m - место max for i 2 to k do if A i A m then m i меняем местами элементы с номером m и номером k x
A m A m A k A k x end for i 1 to n do write A i , упорядоченный массив end. ПРИМЕР Та же задача с одновременным выбором max и min. program Sort Vybor2 var A array 1 100 of integer N,i,m,k,x,p integer begin write количество элементов массива read N for i 1 to n do read A i for k 1 to n div 2 do k - номер пары max и min begin m k m - место max p k p - место min max и min ищутся среди элементов с k до n-k 1 for i k 1 to n-k 1 do if
A i A m then m i else if A i A p then p i меняем местами элементы с номером p и номером k x A p A p A k A k x if m k then m p если max стоял на месте k, то сейчас он на месте p меняем местами элементы с номером m и номером n-k 1 x A m A m A n-k 1 A n-k 1 x end for i 1 to n do write A i , упорядоченный массив end. СОРТИРОВКА ОБМЕНОМ методом пузырька Идея метода заключается в том, что последовательно сравниваются
пары соседних элементов массива. Если они располагаются не в том порядке, то совершаем перестановку, меняя местами пару соседних элементов. После одного такого прохода на последнем месте номер N окажется максимальный элемент всплыл первый пузырек . Следующий проход должен рассматривать элементы до предпоследнего и так далее. Всего требуется N-1 проход. Вычислительная сложность сортировки обменом
O N N . ПРИМЕР Сортировка обменом по возрастанию массива A из N целых чисел. Базовый вариант program Sort Obmen1 var A array 1 100 of integer N,i,k,x integer begin write количество элементов массива read N for i 1 to n do read A i for k n-1 downto 1 do k - количество сравниваемых пар for i 1 to k do if A i A i 1 then меняем местами соседние элементы begin x
A i A i A i 1 A i 1 x end for i 1 to n do write A i , упорядоченный массив end. Можно заметить, что если при выполнении очередного прохода в сортировке обменом не произведено ни одной перестановки, то это означает, что массив уже упорядочен. Таким образом, можно модифицировать алгоритм, чтобы следующий проход делался только при наличии перестановок в предыдущем. ПРИМЕР Сортировка обменом с проверкой факта перестановки. program
Sort Obmen2 var A array 1 100 of integer N,i,k,x integer p boolean begin write количество элементов массива read N for i 1 to n do read A i k n-1 количество пар при первом проходе p true логическая переменная p истинна, если были перестановки, т.е. нужно продолжать сортировку while p do begin p false Начало нового прохода. Пока перестановок не было. for i 1 to k do if A i A i 1 then begin x A i A i A i 1 A i 1 x меняем элементы местами p true и запоминаем факт перестановки
end k k-1 уменьшаем количество пар для следующего прохода end for i 1 to n do write A i , упорядоченный массив end. Следующая модификация алгоритма сортировки обменом получается при запоминании места последней перестановки. Если при очередном проходе последней парой элементов, которые поменялись местами, были A i и A i 1 , то элементы массива с i 1 до последнего уже стоят на своих местах. Использование этой информации позволяет нам сделать количество пар для следующего прохода равным i-1.
ПРИМЕР Сортировка обменом с запоминанием места последней перестановки. program Sort Obmen3 var A array 1 100 of integer N,i,k,x,m integer begin write количество элементов массива read N for i 1 to n do read A i k n-1 количество пар при первом проходе while k 0 do begin m 0 пока перестановок на этом проходе нет, место равно 0 for i 1 to k do if A i A i 1 then begin x A i A i A i 1 A i 1 x меняем элементы местами m i и запоминаем место перестановки
end k m-1 количество пар зависит от места последней перестановки end for i 1 to n do write A i , упорядоченный массив end. ШЕЙКЕРНАЯ СОРТИРОВКА Этот алгоритм, по сути, является модификацией сортировки обменом. Отличие состоит только в том, что если в сортировке обменом проходы осуществлялись только в одном направлении, то здесь направление каждый раз меняется. В шейкерной сортировке также можно проверять факт перестановки
или запоминать место последней перестановки. В базовом алгоритме количество двойных проходов равно N div 2. Вычислительная сложность шейкерной сортировки O N N . ПРИМЕР Шейкерная сортировка по возрастанию массива A из N целых чисел. program Shaker var A array 1 100 of integer N,i,k,x,j,d integer begin write количество элементов массива read
N for i 1 to n do read A i d 1 i 0 for k n-1 downto 1 do k - количество сравниваемых пар begin i i d for j 1 to k do begin if A i -A i d d 0 then меняем местами соседние элементы begin x A i A i A i d A i d x end i i d end d -d меняем направление движения на противоположное end for i 1 to n do write A i , упорядоченный массив end. СОРТИРОВКА ВКЛЮЧЕНИЕМ Идея данного метода состоит в том, что каждый раз, имея уже упорядоченный массив из
K элементов, мы добавляем еще один элемент, включая его в массив таким образом, чтобы упорядоченность не нарушилась. Сортировка может производиться одновременно со вводом массива. В начале сортировки упорядоченная часть массива содержит только один элемент, который вводится отдельно или, если массив уже имеется, считается единственным, стоящим на нужном месте. Различные методы поиска места для включаемого элемента приводят к различным модификациям сортировки
включением. При использовании линейного поиска вычислительная сложность сортировки включением составляет O N N , а при использовании двоичного поиска - O N LogN имеется в виду логарифм по основанию 2 . ПРИМЕР Сортировка по возрастанию массива A из N целых чисел включением с линейным поиском. program Sort Include1 var A array 1 100 of integer N,i,k,x integer begin write количество элементов массива
read N read A 1 for i 1 to n do read A i k - количество элементов в упорядоченной части массива for k 1 to n-1 do begin read x x A k 1 i k while i 0 and A i x do begin A i 1 A i i i-1 end A i 1 x end for i 1 to n do write A i , упорядоченный массив end. ПРИМЕР Сортировка по возрастанию массива A из N целых чисел включением с двоичным поиском. program
Sort Include2 var A array 1 100 of integer N,i,k,x,c,left,right integer begin write количество элементов массива read N read A 1 for i 1 to n do read A i k - количество элементов в упорядоченной части массива for k 1 to n-1 do begin read x x A k 1 left 1 right k левая и правая граница фрагмента для поиска while left right do двоичный поиск последнего вхождения begin c left right 1 div 2 середина с округлением в большую сторону if x A c then left c берем правую половину с серединой else right c-1 берем левую
половину без середины end if x A left then left left 1 сдвигаем на 1 вправо часть массива, освобождая место для включения x for i k downto left do A i 1 A i A left x end for i 1 to n do write A i , упорядоченный массив end. СОРТИРОВКА ХОАРА Эту сортировку также называют быстрой сортировкой. Метод был разработан в 1962 году профессором Оксфордского университета
К. Хоаром. Это прекрасный пример использования рекурсии. Рассмотрим ophmvho работы алгоритма при упорядочении массива A из N элементов по возрастанию. Значение какого-нибудь элемента, обычно центрального, записывается в переменную X. Просматриваются элементы массива. При движении слева-направо ищем элемент больше или равный X. А при движении справа-налево ищем элемент меньше или равный
X. Найденные элементы меняются местами и продолжается встречный поиск. После этого массив окажется разделенным на две части. В первой находятся элементы меньше либо равные X, а справа - больше либо равные X. Можно заменить исходную задачу о сортировке массива A на две подзадачи о сортировке полученных частей массива.
Вычислительная сложность одного вызова данного рекурсивного алгоритма пропорциональна количеству элементов сортируемого фрагмента массива. В лучшем случае деление на части производится пополам, поэтому вычислительная сложность всего алгоритма быстрой сортировки составляет величину порядка N LogN логарифм по основанию 2 . Вычислительная сложность в среднем того же порядка. ПРИМЕР Быстрая сортировка по возрастанию массива A из
N целых чисел. program Quick Sort var A array 1 100 of integer N,i integer В процедуру передаются левая и правая границы сортируемого фрагмента procedure QSort L,R integer var X,y,i,j integer begin X A L R div 2 i L j R while i j do begin while A i X do i i 1 while A j X do j j-1 if i j then begin y A i A i A j A j y i i 1 j j-1 end end if
L j then QSort L,j if i R then QSort i,R end begin write количество элементов массива read N for i 1 to n do read A i QSort 1,n упорядочить элементы с первого до n-го for i 1 to n do write A i , упорядоченный массив end. СОРТИРОВКА С ИСПОЛЬЗОВАНИЕМ ВЕКТОРА ИНДЕКСОВ В отличии от всех ранее изложенных методов сортировки, этот не является самостоятельным алгоритмом, а представляет собой идею, которую можно применять к любому из них.
Идея заключается в том, что вводится дополнительный массив B, который принято называть вектором индексов. Числа в нем говорят о том, в каком порядке нужно смотреть на элементы из A, например Массив A 4 7 3 5 Массив B 3 1 4 2 A 3 A 1 A 4 A 2 В начале программы в вектор индексов B записываются последовательно натуральные числа от 1 до
N. При работе любой сортировки вместо элемента A i обращаются к элементу A B i . Это сделано для того, чтобы менять местами не элементы массива A, а их индексы, т.е. элементы массива B. МОДУЛЬ CRT основные возможности Модуль Crt относится к стандартным модулям Турбо Паскаля и находится в файле turbo.tpl Turbo Pascal Library . Для подключения модуля достаточно написать uses
Crt. Модуль Crt содержит средства управления экраном в текстовом режиме и клавиатурой. На экране используются два активных цвета цвет текста и цвет фона. Их можно установить с помощью процедур TextColor и TextBackground, которые имеют по одному параметру целому числу, задающему номер цвета. Для цвета текста используются числа от 0 до 15, а для цвета фона - от 0 до 7.
Обе эти процедуры оказывают влияние только на последующий вывод. Координаты на экране задаются следующим образом. Левый верхний угол имеет координаты 1,1 , а правый нижний 80,25 . Можно вводить относительные координаты, объявляя окно с помощью процедуры Window x1,y1,x2,y2 , где x1,y1 - абсолютные координаты левого верхнего, а x2,y2 - правого нижнего угла окна. После этого все процедуры и функции кроме Window используют относительные координаты.
Вернуться к работе со всем экраном можно, написав Window 1,1,80,25 . С помощью процедуры GotoXY x,y можно установить курсор в заданную позицию окна, а с помощью пары функций WhereX и WhereY без параметров можно узнать текущие координаты курсора. Процедура ClrScr не имеет параметров и закрашивает текущее окно цветом фона. Модуль Crt позволяет осуществлять контроль клавиатуры.
Известно, что информация о нажатых клавишах поступает сначала в буфер клавиатуры и только затем считывается компьютером. Также известно, что клавиши и комбинации клавиш делятся на обычные, и управляющие. В результате нажатия обычной клавиши в буфер клавиатуры поступает ее код, который может быть от 1 до 255, а при нажатии управляющей клавиши в буфер клавиатуры поступает два кода, первый из которых 0. Функция KeyPressed не имеет параметров и возвращает истиный результат если буфер не пуст.
При этом содержимое буфера не изменяется. Функция ReadKey также не имеет параметров и забирает из буфера клавиатуры очередное число, возвращая в программу символ тип char , код которого соответствует этому числу. В случае, когда буфер пуст, функция ReadKey ожидает нажатия на клавиатуре. ЛИТЕРАТУРА 1. Абрамов А.Г Трифонов Н.П Трифонова Г.
Н. Введение в язык Паскаль. М Наука, 1988. 2. Абрамов С.А Гнездилова Г.Г Капустина Е.Н Селюн М.И. Задачи по программированию. М Наука, 1988. 3. Ахо А Хопкрофт Дж Ульман Дж. Построение и анализ вычислительных алгоритмов. М Мир, 1979. 4. Вирт Н. Алгоритмы и структуры данных. М Мир, 1989. 5. Епанешников А Епанешников В. Программирование в среде
Turbo Pascal 7.0. М Диалог-Мифи, 1993. 6. Зуев Е.А. Система программирования Turbo Pascal. М Радио и связь, 1992. 7. Зуев Е.А. Программирование на языке Турбо-Паскаль 6.0,7.0. М. Радио и связь. Веста. 1993. 8. Йодан Э. Структурное программирование и конструирование программ.
М. Мир, 1979. 9. Кенин А.М Печенкина Н.С. Работа на IBM PC. М АО Книга и бизнес , 1992. 10. Кнут Д. Искусство программирования на ЭВМ. М. МИР, т.1, 1976 т.2, 1977 т.3, 1978. 11. Липский В. Комбинаторика для программистов. М Мир, 1988. 12. Майерс Г. Искусство тестирование программ. М. Финансы и статистика,
1982. Гласс Р Нуазо Р. Сопровождение программного обеспечения, М. Мир, 1983. 13. Пильщиков В.Н. Сборник упражнений по языку Паскаль. М Наука, 1989. 14. Поляков Д.Б Круглов И.Ю. Программирование в среде Турбо Паскаль версия 5.5 . Изд-во МАИ, 1992. 15. Рейнгольд Э Нивергельт Ю Део
Н. Комбинаторные алгоритмы. М Мир, 1980. 16. Фаронов В.В. Турбо Паскаль 7.0. Начальный курс. М Нолидж, 1997. 17. Фаронов В.В. Турбо Паскаль 7.0. Практика программирования. М Нолидж, 1997. 18. Шень А. Программирование Теоремы и задачи. М МЦНМО, 1995. Министерство общего и профессионального образования
Российской Федерации Уральский государственный университет им. А.М. Горького Лахтин А.С Искакова Л.Ю. Языки и технология программирования. Начальный курс. Учебное пособие Екатеринбург 1998 Лахтин А.С Искакова Л.Ю. Языки и технология программирования. Начальный курс. Учеб. пособие. Екатеринбург, 1998.
Данное учебное пособие представляет собой первую часть одноименного лекционного курса, который читается студеттам математико-механического фаультета в 1 семестре. Начальный курс посвящен изложению основ создания программ. Изложение ведется с использованием языка программирования Турбо Паскаль. Рассматриваются некоторые классические алгоритмы.
Приводятся примеры решения типовых задач. Пособие предназначено для студентов дистантной формы обучения специальности Информационные системы , а также может быть использовано для студентов дневной формы обучения по этой специальности. А.С. Лахтин, Л.Ю. Искакова, 1998. СОДЕРЖАНИЕВВЕДЕНИЕ 5 ОСНОВЫ ЯЗЫКА 5 АЛГОРИТМЫ 5 АЛФАВИТ ЯЗЫКА 5 СТРУКТУРА ПРОГРАММЫ 6 ТИПЫ ДАННЫХ 7 Целые типы 7
Вещественные типы 8 Логический тип 9 Символьный тип 9 ВЫРАЖЕНИЯ 9 СОВМЕСТИМОСТЬ ТИПОВ ДАННЫХ 10 ЛИНЕЙНЫЕ АЛГОРИТМЫ 11 ПУСТОЙ И СОСТАВНОЙ ОПЕРАТОРЫ 11 ОПЕРАТОР ПРИСВАИВАНИЯ 11 ПРОСТЕЙШИЙ ВВОД И ВЫВОД 11 РАЗВЕТВЛЯЮЩИЕСЯ АЛГОРИТМЫ 12 ОПЕРАТОР ПЕРЕХОДА 12 УСЛОВНЫЙ ОПЕРАТОР 13
ОПЕРАТОР ВЫБОРА 13 ЦИКЛИЧЕСКИЕ АЛГОРИТМЫ 14 ЦИКЛЫ С ПАРАМЕТРОМ. 14 ЦИКЛЫ С УСЛОВИЕМ. 16 ПОЛЬЗОВАТЕЛЬСКИЕ ТИПЫ ДАННЫХ 17 ПЕРЕЧИСЛЯЕМЫЙ ТИП 17 ТИП-ДИАПАЗОН 17 МАССИВЫ 17 ЗАПИСИ 17 РАБОТА СО СТРОКАМИ 17 ПРОЦЕДУРЫ И ФУНКЦИИ 17 Параметры-значения 17 Параметры-переменные 17
Параметры-константы 17 ОТКРЫТЫЕ ПАРАМЕТРЫ-МАССИВЫ 17 БЕСТИПОВЫЕ ПАРАМЕТРЫ 17 ПРОЦЕДУРНЫЕ ТИПЫ 17 РЕКУРСИЯ 17 ТИПИЗИРОВАННЫЕ КОНСТАНТЫ 17 МОДУЛИ 17 АЛГОРИТМЫ ПОИСКА 17 ЛИНЕЙНЫЙ ПОИСК 17 ПОИСК С БАРЬЕРОМ 17 ДВОИЧНЫЙ БИНАРНЫЙ ПОИСК 17 АЛГОРИТМЫ СОРТИРОВКИ 17 СОРТИРОВКА ВЫБОРОМ 17
СОРТИРОВКА ОБМЕНОМ методом пузырька 17 ШЕЙКЕРНАЯ СОРТИРОВКА 17 СОРТИРОВКА ВКЛЮЧЕНИЕМ 17 СОРТИРОВКА ХОАРА 17 СОРТИРОВКА С ИСПОЛЬЗОВАНИЕМ ВЕКТОРА ИНДЕКСОВ 17 МОДУЛЬ CRT основные возможности 17 ЛИТЕРАТУРА 17 ВВЕДЕНИЕ Первая версия языка Паскаль была разработана швейцарским ученым Никлаусом Виртом в 1968 году. Первоначально язык предназначался для целей обучения, поскольку он является
достаточно детерминированным, т.е. все подчиняется определенным правилам, исключений из которых не так много. Основные характеристики относительно небольшое количество базовых понятий, простой синтаксис, быстрый компилятор для перевода исходных текстов в машинный код. В 1992 г. фирма Borland International выпустила два пакета, основанных на языке Паскаль Borland Pascal 7.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 и идентификатора - имени программы, за котором следует точка с запятой. Порядок объявлений и описаний не регламентируется.
ПРИМЕР Простейшая программа. program prim 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. program sravnenie 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 eps.
Число eps можно определять следующим образом min abs a ,abs b 10 -m , где m - необходимое число совпадающих десятичных разрядов. Логический тип Переменные логического типа 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 9 Символьный тип Символьный тип 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 операции отношения В логическом выражении 2 4 and 5 3 Паскаль выдаст ошибку, поскольку операция and будет выполнена раньше
операций сравнения. Верная запись - 2 4 and 5 3 . СОВМЕСТИМОСТЬ ТИПОВ ДАННЫХ Когда в операциях или операторах вашей программы присутствуют данные разных типов, то встает вопрос об их совместимости. В языке Турбо Паскаль этому вопросу уделяется очень большое внимание, разработаны строгие правила, определяющие идентичность, совместимость в общем случае и совместимость по присваиванию различных типов. Нам в начале курса достаточно помнить следующее.
Переменные или выражения одного типа являются полностью совместимыми. Другим понятием является совместимость по присваиванию. Присваивание переменной одного типа выражения другого типа допустимо в том случае, когда множество значений второго типа является подмножеством значений первого. Например, результат сложения двух целых переменных типа integer и word может присваиваться в целую
переменную, тип которой только longint, поскольку только этот целый тип содержит в себе весь возможный диапазон значений как для типа integer, так и для типа word. Также, можно присваивать целое выражение в вещественную переменную или символьное выражение в строку. ЛИНЕЙНЫЕ АЛГОРИТМЫ Алгоритмические действия над исходными данными и рабочими объектами языка, необходимые для решения поставленной задачи описываются при помощи операторов
Турбо Паскаля. Операторы разделяются точкой с запятой, их последовательность и составляет тело программы. Наиболее простой случай представляют собой линейные алгоритмы. При выполнении линейных участков алгоритма операторы выполняются последовательно друг за другом в том порядке, в котором они перечислены в программе. При этом могут использоваться операторы присваивания, операции ввода и вывода. ПУСТОЙ И СОСТАВНОЙ ОПЕРАТОРЫ
В программе может применяться пустой оператор, не выполняющий никакого действия. Он представляет собой точку с запятой. Составным оператором считается последовательность произвольных операторов, заключенная в операторные скобки - зарезервированные слова begin end. Допускается произвольная глубина вложенности составных операторов. Составной оператор применяется там, где по синтаксическим правилам языка может стоять только один оператор,
а нам надо выполнить несколько действий. В этом случае набор необходимых команд должен быть оформлен как составной оператор. По сути, все тело программы представляет собой один составной оператор. ОПЕРАТОР ПРИСВАИВАНИЯ Оператор присваивания используется для задания значения переменных и имеет следующий синтаксис имя переменной выражение Вычисляется выражение, стоящее в правой части оператора, после чего его значение записывается в переменную, имя которой стоит слева.
Тип выражения и тип переменной должны быть совместимы, т.е. множество допустимых значений для типа выражения содержится во множестве допустимых значений для типа переменной. ПРОСТЕЙШИЙ ВВОД И ВЫВОД Рассмотрим простейшие процедуры ввода и вывода. По умолчанию ввод осуществляется с клавиатуры, а вывод на экран. К операторам ввода относятся Read список переменных через запятую
Readln список переменных Readln Второй отличается от первого тем, что после ввода переводит курсор на новую строку, точнее, в конце своей работы считывает с клавиатуры код клавиши Enter . Третий оператор используется для организации паузы - выполнение программы продолжится, как правило, только после нажатия на клавиатуре клавиши Enter . К операторам вывода относятся Write список вывода
Writeln список вывода Writeln В списке вывода кроме имен переменных можно писать строковые константы последовательность символов в апострофах и даже выражения выводятся их значения . Второй оператор отличается от первого тем, что после вывода переводит курсор на новую строку. Третий оператор просто переводит курсор на новую строку. Существует так называемый форматированный вывод. Можно задать количество позиций, отводимых под число.
Для целых - после выражения или переменной через двоеточие указывается меньше какого количества позиций не может быть выделено значению. Для вещественных - дополнительно через двоеточие можно указать количество цифр в дробной части. При этом происходит округление в ближнюю сторону. ПРИМЕР Простые вычисления. program vvod vyvod const n 1.5 var y1,y2 real x byte begin writeln Введите натуральное число 255 readln x y1 cos n y2 cos x write
Зачем-то посчитали writeln n ,n, y1 ,y1 7 4, cos Pi 2 8 4 напечатается Зачем-то посчитали n 1.50E 0000 y1 0.0707 1.0000 writeln x ,x 3, y2 ,y2 7 4 end. РАЗВЕТВЛЯЮЩИЕСЯ АЛГОРИТМЫ В Турбо Паскале имеется возможность нелинейного хода программы, т.е. выполнения операторов не в том порядке, в котором они записаны. Такую возможность нам предоставляют разветвляющиеся алгоритмы.
Они могут быть реализованы одним из трех способов с использованием операторов перехода, условного оператора или оператора выбора. ОПЕРАТОР ПЕРЕХОДА Оператор перехода имеет вид GOTO метка . Он позволяет передать управление непосредственно на нужный оператор программы. Перед этим оператором должна располагаться метка отделенная от него двоеточием. В Турбо Паскале в качестве меток выступают либо целые числа от 0 до 9999, либо идентификаторы.
Все метки должны быть описаны в разделе объявления меток следующим образом label список меток через запятую Каждой меткой в программе может быть помечен только один оператор. Операторов перехода с одной и той же меткой можно писать любое количество. Необходимо, чтобы раздел описания метки, сама метка и оператор перехода с ее использованием располагались в пределах одного блока программы см. тему процедуры и функции .
Кроме того, нельзя передавать управление внутрь структурированных операторов например, if, for, while, repeat и др УСЛОВНЫЙ ОПЕРАТОР Условный оператор IF позволяет изменить порядок выполнения команд в зависимости от некоторого логического условия, т.е. он осуществляет ветвление вычислительного процесса. Условный оператор имеет вид IF условие THEN оператор1 ELSE оператор2 В случае истиности логического выражения, стоящего в условии, выполняется оператор1 ,
а оператор2 пропускается. При ложном значении логического выражения пропускается оператор1 и выполняется оператор2 . Оператор IF может быть полным присутствуют обе ветви или неполным Else-ветви нет, при ложном условии ничего не делается . По правилам каждая из ветвей может содержать либо один выполняемый оператор, либо несколько, объединенных в составной. Точка с запятой перед Else считается ошибкой.
ПРИМЕР Ввести целое число. Вывести соответствующий ему символ ASCII-таблицы, либо сообщить, что такого символа нет 0-31 - управляющие коды, затем до 256 - печатаемые символы . program ascii symbol var i word begin write Введите целое число readln i if i 31 and i 256 then writeln Соответствующий символ Chr i else writeln Такого символа нет readln end.
ОПЕРАТОР ВЫБОРА Если у вас не два возможных варианта выполнения программы, а больше, то может использоваться оператор выбора CASE. Структура этого оператора в Турбо Паскале CASE ключ выбора OF C1 оператор1 C2 оператор2 CN операторN ELSE оператор0 END Здесь ключ выбора - это выражение порядкового типа, в зависимости от значения которого принимается решение C1, ,CN - значения, с которыми сравнивается значение ключа оператор1
операторN - оператор возможно составные , из которых выполняется тот, с константой которого происходит первое совпадение значения ключа , оператор0 выполнится, если значение ключа не совпадает ни с одной из констант C1, ,CN. Ветвь Else не обязательна, и в отличие от оператора if, перед ней можно ставить точку с запятой. Если для нескольких значений ключа действия совпадают, то эти константы можно перечислить через запятую перед двоеточием или даже задать диапазон значений нижняя граница верхняя граница .
ПРИМЕР Вводится целое число, если это цифра, то определить четная она или нет, а если число, то определить попадает ли оно в диапазон от 10 до 100, если нет, то выдать соответствующее сообщение. program chislo var i integer begin write Введите целое число readln i case i of 0,2,4,6,8 writeln Четная цифра 1,3,5,7,9 writeln Нечетная цифра 10 100,200 writeln Число от 10 до 100 или 200 else writeln Число либо отрицательное, либо 100, но не 200 end readln end.
ЦИКЛИЧЕСКИЕ АЛГОРИТМЫ Турбо Паскаль позволяет использовать три различных оператора для организации повторяющихся последовательностей действий, которые называют циклами. ЦИКЛЫ С ПАРАМЕТРОМ. Оператор цикла For организует выполнение одного оператора заранее определенное число раз. Его еще называют цикл со счетчиком. Существует две формы оператора FOR параметр nz TO kz DO оператор FOR параметр nz DOWNTO kz
DO оператор Здесь параметр цикла счетчик представляет собой переменную порядкового ординального типа nz и kz - выражения, определяющие начальное и конечное значение счетчика оператор - один возможно составной оператор, который называют телом цикла, повторяемый определенное число раз. На первом шаге цикла параметр принимает значение nz. В этот же момент происходит вычисление kz - значения параметра на последнем шаге цикла.
После каждого выполнения тела цикла, если параметр цикла не равен kz, происходит изменение параметра на следующее большее или меньшее значение в зависимости от формы оператора for, т.е. неявно происходит выполнение одного из двух операторов параметр Succ параметр параметр Pred параметр В случае nz kz в первой форме оператора или nz kz во второй его форме ошибки не происходит, но цикл не выполняется ни разу. После завершения работы цикла значение параметра остается равным kz.
РЕКОМЕНДАЦИИ Использовать цикл for при заранее известном количестве повторений. Не изменять параметр в теле цикла. При использовании кратных вложенных циклов применять разные переменные в качестве параметров. Определять до цикла значения всех используемых в нем переменных. Не ставить точку с запятой после do. ПРИМЕР Вводятся 10 чисел, посчитать среди них количество положительных. program cycle for1 var i,kn byte x real begin kn 0 for i 1 to 10 do begin writeln
Введите ,i, число readln x if x 0 then kn kn 1 увеличиваем количество на 1 end writeln Вы ввели ,kn, положительных чисел. readln end. ПРИМЕР Напечатать буквы от Z до A . program cycle for2 var c char begin for c Z downto A do write c readln end ПРИМЕР Вычислить N-е число Фиббоначчи. Числа Фиббоначчи строятся следующим образом
F 0 F 1 1 F i 1 F i F i-1 для i 1. Это пример вычислений по рекуррентным формулам. program Fib var a,b,c word i,n byte begin write введите номер числа Фиббоначчи readln N a 1 a F 0 , a соответствует F i-2 b 1 b F 1 , b соответствует F i-1 for i 2 to N do begin c a b c соответствует F i a b b c в качестве a и b берется следующая пара чисел end writeln
N, -е число Фиббоначчи ,b для N 2 b c readln end. ЦИКЛЫ С УСЛОВИЕМ. Если заранее неизвестно число повторений цикла, то используются циклы с условием. В паскале имеется два типа таких циклов. Циклы While называют циклами с пред-условием. Они имеют вид WHILE логич.выражение DO оператор Цикл While организует выполнение одного возможно составного оператора пока истинно логическое выражение,
стоящее в заголовке цикла. Поскольку значение логического выражения проверяется в начале каждой итерации, то тело цикла может не выполниться ни разу. Таким образом, в этом цикле логическое выражение - это условие продолжения работы в цикле. Другой вариант циклов с условием - это циклы Repeat. Их называют циклами с пост-условием. Они имеют вид REPEAT оператор 1 оператор N UNTIL логич.выражение
Оператор Repeat организует повторяющееся выполнение нескольких операторов до тех пор пока не станет истинным условие, стоящее в Until-части. Тело цикла обязательно выполняется хотя бы один раз. Таким образом, в этом цикле логическое выражение - это условие выхода из цикла. При создании циклических алгоритмов Турбо Паскаль позволяет использовать процедуры Continue и Break. Процедура Continue досрочно завершает очередной шаг цикла, передает управление на
заголовок. Процедура Break реализует немедленный выход из цикла. РЕКОМЕНДАЦИИ Для того, чтобы избежать зацикливания программы необходимо обеспечить изменение на каждом шаге цикла значения хотя бы одной переменной, входящей в условие цикла. После выхода из цикла со сложным условием с использованием операций and, or, xor как правило необходима проверка того, по какому условию цикл завершен. ПРИМЕР
Пары неотрицательных вещественных чисел вводятся с клавиатуры. Посчитать произведение для каждой пары и сумму всех чисел. program cycle while var x,y,sum real otv char begin sum 0 otv Д while otv Д or otv д do begin write Введите числа x,y 0 readln x,y writeln Их произведение ,x y 8 3 sum sum x y write Завершить программу Д Н ? readln otv end writeln Общая сумма ,sum 8 3 readln end.
ПРИМЕР В той же задаче можно использовать другой цикл с условием program cycle repeat var x,y,sum real otv char begin sum 0 repeat write Введите числа x,y 0 readln x,y writeln Их произведение ,x y 8 3 sum sum x y write Завершить программу Д Н ? readln otv until otv Д or otv д writeln Общая сумма ,sum 8 3 readln end. ПРИМЕР Нахождение наибольшего общего делителя двух целых чисел с помощью
Алгоритма Эвклида. program Evklid var a,b,c integer begin write введите два целых числа readln a,b while b 0 do begin c a mod b a b b c end writeln наибольший общий делитель ,a readln end. ПОЛЬЗОВАТЕЛЬСКИЕ ТИПЫ ДАННЫХ В Турбо Паскале предусмотрен механизм создания новых типов, которые принято называть пользовательскими или конструируемыми. Их можно создавать на основе стандартных и ранее созданных типов. Описание новых типов происходит в разделе TYPE.
После этого можно в разделе Var создавать переменные этих типов. Также, можно сразу описывать новый тип при создании переменной в разделе Var. В этой главе мы рассмотрим следующие пользовательские типы перечисляемый тип, тип-диапазон, массивы, записи. ПЕРЕЧИСЛЯЕМЫЙ ТИП Перечисляемый тип задается перечислением тех значений, которые он может получать. Каждое значение должно являться идентификатором смотри главу
Алфавит языка и располагаться в круглых скобках через запятую. Количество элементов в перечислении не более 65536. Вводить и выводить переменные перечисляемого типа запрещено. Перечислимый тип является порядковым смотри главу Типы данных , поэтому к переменным такого типа можно применять функции
Ord, Pred, Succ. Функция Ord возвращает порядковый номер значения начиная с нуля. ПРИМЕР Объявление перечисляемых типов. Type Colors Red,Green,Blue Numbers Zero,One,Two,Three,Four,Five var c Colors n Numbers begin c Red write Ord c 0 n Four write Ord n 4 c Succ c c Green for n One to Five do write
Ord n 12345 end. Следует отметить, что стандартные типы byte, word, char и boolean также можно считать вариантами перечислимого типа. ТИП-ДИАПАЗОН Тип-диапазон также называют ограниченным или интервальным типом. Он является подмножеством своего базового типа, в качестве которого может выступать любой порядковый тип кроме типа-диапазона. Тип-диапазон наследует все свойства своего базового типа. Имеются две стандартные функции, работающие с этим типом
High x - возвращает максимальное значение типа-диапазона, к которому принадлежит переменная x Low x - возвращает минимальное значение. ПРИМЕР Объявление типа-диапазон. type Numbers Zero,One,Two,Three,Four,Five Num Two Four диапазон на базе типа Numbers Abc A z все английские буквы диапазон на базе типа Char Digits 0 9 цифры var n Num c,d Abc x integer begin n
Four writeln Ord n 4 как в базовом типе n Succ n ОШИБКА следующее значение вне диапазона read c,d if c d then write одинаковые буквы writeln Low c , ,High c A z writeln Low x , ,High x -32768 32767 end. В тексте программы на Турбо Паскале могут встречаться директивы компилятору, которые также называют опциями. Опции R и R- позволяют включать и отключать проверку соблюдения границ при работе с диапазонами.
Когда проверка включена, при нарушении границ диапазонов происходит аварийное завершение работы программы. В другом случае ответственность за возможные ошибки лежит на программисте. МАССИВЫ Массив - это упорядоченная структура однотипных данных, хранящая их последовательно. Доступ к элементу массива осуществляется через его индекс. Массивы описываются следующим образом Имя типа ARRAY диапазоны индексов
OF тип элемента массива В качестве типа для элементов массива можно использовать любые типы Турбо Паскаля кроме файловых. Диапазоны индексов представляют собой один или несколько диапазонов, перечисленные через запятую. В качестве диапазонов индексов нельзя использовать диапазоны с базовым типом Longint. ПРИМЕР Три способа описания одного и того же типа массива type 1 M1 array 0 5 of integer M2 array char of M1 M3 array -2 2 of
M2 2 M3 array -2 2 of array char of array 0 5 of integer 3 M3 array -2 2,char,0 5 of integer var A M3 Обращаться к элементам массива можно следующим образом begin read A -1, a ,3 read A 1 x 0 A 1 c ,1 100 end. Глубина вложенности, т.е. количество индексов, при определении массивов не ограничена. Играет роль только суммарный объем данных в программе. В стандартном режиме работы Турбо Паскаля этот объем ограничен размерами сегмента, т.е.
64 килобайта. Целиком над массивами допускается применение только операции присваивания массивов подмассивов одинаковых типов. Остальные операции должны выполняться поэлементно. ПРИМЕР Вычисление значения многочлена степени N, коэффициенты которого находятся в массиве A в точке X по схеме Горнера. Pn x A 0 X n A 1 X n-1 A n-1 X A n A 0 X A 1 X A 2 X A n-1 X A n . program
Scheme Gorner type Mas array 0 100 of integer var A Mas i,j,n integer x,p real begin write степень многочлена read n writeln введите целые коэффициенты for i 0 to n do read A i write значение X read x p 0 for i 0 to n do p p x A i writeln Pn X ,p end. ЗАПИСИ Запись - это стpуктуpа данных, котоpая может содеpжать инфоpмацию pазных типов, объединенную под одним названием. Компоненты записи называются полями.
Их фиксиpованное число. Описание записей имеет следующую стpуктуpу Имя типа RECORD список полей 1 тип 1 список полей N тип N CASE поле выбора тип OF значение 1 полей 1 тип 1 END Типы полей записи могут быть любыми. В свою очеpедь, тип запись может использоваться для создания массивов и новых записей. Степень вложенности не огpаничена.
Список полей может состоять из двух pазделов постоянной и ваpиантной части. В постоянной части идет пеpечисление полей записи идентификатоpов с указанием их типов. Синтаксис такой же, как в pазделе var. ПРИМЕР Пример объявления типа запись. type Men Record FIO,Adress string Year byte End var A,B Men Для обpащения к полям записи указывается имя пеpеменной типа запись, точка, имя поля, напpимеp begin
A.FIO Иванов И.И. A.Adress пp. Ленина, д. 40, кв. 10 A.Year 1981 end. После описания постоянных полей может следовать ваpиантная часть, котоpая может быть только одна и имеет вид CASE поле выбоpа тип OF значение 1 список полей 1 значение N список полей N Поле выбоpа может отсутствовать. Если оно есть, то его воспpинимают как постоянное поле записи. Если его нет, указывается только тип, котоpый должен быть поpядковым, но он не влияет ни
на количество пеpечисленных ниже значений, ни на типы этих значений. Все ваpианты pасполагаются в одном и том же месте памяти, котоpой выделяется столько, сколько тpебуется для максимального по pазмеpу ваpианта. Это пpиводит к тому, что изменение одного ваpиантного поля оказывает влияние на все остальные. Это увеличивает возможности пpеобpазования типов, ПРИМЕР Запись с вариантами. var R Record rem string
Case byte of 3 n integer 5 x,y,z char a i,j byte end begin R.rem запись с ваpиантами R.n 25000 write R.i,R.x,R.j,R.y 168и97a ord и 168, ord a 97, 168 97 256 25000 end. Значения выбоpа могут повтоpяться. Имена полей записи не являются пеpеменными и, следовательно, могут повтоpяться, но только на pазных уpовнях, напpимеp var
Rec Record x real Sr Record a real x,y integer end I byte end Для удобства обpащения к полям записей может использоваться опеpатоp пpисоединения WITH пеpеменная DO опеpатоp Здесь пеpеменная - это запись, за котоpой может следовать список вложенных полей, напpимеp следующие тpи опеpатоpа эквивалентны With Rec,Sr Do a x y With Rec.Sr Do a x y Rec.Sr.a
Rec.Sr.x Rec.Sr.y РАБОТА СО СТРОКАМИ Тип String строка в Турбо Паскале широко используется для обработки текстов. Этот тип является стандартным и во многом похож на одномерный массив символов Array 0 N of Char. Значение N соответствует количеству символов в строке и может меняться от 0 до 255. Символы, входящие в строку, занимают позиции с 1 до
N. Начальный байт строки с индексом 0 содержит информацию о ее длине, т.е. это символ с кодом, равным длине строки. Можно, также описывать переменные типа String K , где K - целое число не больше 255. Так определяются строки с длиной не больше K. Этот тип уже не является стандартным. С символами строки можно работать как с элементами массива из символов, но в отличие от массивов, строки можно вводить целиком, сравнивать друг с другом и сцеплять
операцией . ПРИМЕР Работа со строками. var s,x,y,z string begin x turbo y pascal z x y z turbo pascal s пустая строка for c a to z do s s c s abcd xyz writeln s end. Сравнение строк выполняется посимвольно в соответствии с их кодами до первого несовпадения. Если одна из строк закончилась до первого несовпадения, то она считается меньшей. Пустая строка меньше любой строки. ПРИМЕР Сравнение строк. abcd abcD d
D abcd abc d abc axxc b x abcd abcd Существует ряд стандартных функций и процедур для работы со строками. Функция Length s выдает длину строки s. Функция Concat s1,s2, ,sn возращает строку s1 s2 sn. Функция Copy s,p,k возвращает фрагмент строки s, который начинается в позиции p и имеет длину k. Функция Pos s1,s ищет первое вхождение подстроки s1 в строку s и возвращает номер первого символа s1 в строке s или 0 если не нашли. Процедура Delete s,p,k удаляет из строки s фрагмент, который начинается
в позиции p и имеет длину k. Процедура Insert s,s1,p вставляет в строку s подстроку s1, начиная с заданной позиции p. Турбо паскаль позволяет производить преобразования числовых значений в строковые и наоборот. Для этого используются процедуры Str X n d,S и Val S,X,e . Первая получает их числа X строку S с изображением этого числа, в которой не менее n символов и из них d знаков после запятой. Параметры n и d необязательные.
Вторая процедура получает из строки S число X. При успешном результате e 0. ПРОЦЕДУРЫ И ФУНКЦИИ Турбо Паскаль позволяет выделять фрагменты программы во вспомогательные алгоритмы ВА . Это позволяет писать хорошо структурированные программы. Языки программирования, в которых предусмотрены ВА, называются процедурно-ориентированными. Структурированные программы обычно проще в понимании и отладке.
Наличие ВА в языке программирования позволяет применять более совершенные методы при разработке и проектировании сложных программных комплексов. Известны два наиболее широко применяемых подхода. Первый называется методом нисходящего программирования или разработкой программ сверху - вниз . При этом сначала создается главная программа, предполагая наличие некоторых ВА, решающих определенные задачи. Затем переходят к детальной разработке упомянутых выше необходимых
ВА. Другим подходом в разработке программ является метод восходящего программирования или проектированием снизу - вверх . В этом случае все начинается с создания небольших ВА, из которых затем создаются более сложные ВА и, наконец, основная программа. В Турбо Паскале ВА оформляются в виде процедур или функций. Каждый ВА имеет собственное имя. Вызов процедуры на выполнение осуществляется отдельным оператором
с помощью ее имени. Вызов функции может быть составной частью любого выражения при условии согласованности типов. Описание процедур и функций должно предшествовать их вызову и располагается перед началом основной программы. Нельзя вызывать на выполнение те ВА, которые содержатся внутри других процедур и функций. Описание процедуры имеет следующую структуру. Procedure Имя Список формальных параметров label const Описание локальных меток, type констант, типов и переменных
var procedure Описание внутренних процедур function и функций begin Операторы end Описание функции имеет следующую структуру. Function Имя Список формальных параметров Тип результата label const Описание локальных меток, type констант, типов и переменных var procedure Описание внутренних процедур function и функций begin
Операторы, среди которых хотя бы один, который присваивает имени функции значение результата end. Типом результата в функциях может быть любой из стандартных типов Турбо Паскаля кроме файловых типов. Использование конструируемых типов здесь недопустимо. Существуют понятия локальных и глобальных меток, констант, типов и переменных. Поясним эти понятия на примере переменных. Переменные, описанные в основной программе, являются глобальными
по отношению к процедурам и функциям, которые описаны позже этих переменных. Аналогично, переменные, описанные в процедурах и функциях, являются глобальными по отношению к внутренним процедурам и функциям, которые описаны позже. Остальные переменные называются локальными. Их область действия локализована, т.е. ограничена, тем ВА, где они описаны. Исходные данные для работы ВА можно передавать через глобальные переменные, а также
через параметры. Параметры при вызове ВА называются фактическими, а параметры в заголовке ВА называются формальными. Формальные параметры ВА также относятся к его локальным переменным. Локальные данные создаются, т.е. им выделяется память, при вызове ВА, а освобождение этой памяти происходит при завершении работы ВА. В том случае, когда локальная переменная имеет тот же идентификатор, что и глобальная, алгоритм
работает с локальной. При этом, значение глобальной переменной сохраняется в специальной области памяти, которая называется стек. По способу передачи параметры в Турбо Паскале делятся на три типа параметры-значения, параметры-переменные, параметры-константы. Параметры-значения При вызове процедур и функций формальным параметрам-значениям выделяется новое место в памяти и присваиваются значения фактических параметров.
При этом на месте фактических параметров могут стоять выражения. Совместимость типов определяется возможностями присваивания. После выполнения подпрограммы место формальных параметров освобождается. Изменение формальных параметров не сказывается на значении фактических. Заголовок процедуры с параметрами-значениями имеет вид
Procedure MyProc1 par1,par2 type1 par3,par4 type2 Параметры-переменные При вызове процедур и функций формальные параметры-переменные занимают то же самое место в памяти, что и соответствующие им фактические параметры. Таким образом, дополнительное место в памяти не выделяется и изменения формального параметра приводят к изменениям фактического. Параметры-переменные, как правило, используются для передачи результатов из процедур в вызывающий алгоритм.
Такой механизм передачи данных требует, чтобы фактические параметры были переменными, причем в точности того же типа, что и формальные параметры. При описании ВА перед параметрами-переменными должно присутствовать слово var. Заголовок процедуры с параметрами-переменными имеет вид Procedure MyProc2 var par1,par2 type1 var par3,par4 type2
Параметры-константы Работа с формальными параметрами-константами внутри ВА ведется как с обычными локальными константами. Только эти константы принимают значения выражений, которые находятся в фактических параметрах. Им не выделяется новая память как локальным переменным. Запрещается изменять их значения во время выполнения подпрограммы и контроль за этим осуществляется на уровне компилятора, как для обычных констант. Использовать параметры-константы рекомендуется при
передаче данных большого объема с гарантией сохранения их значений. Заголовок процедуры с параметрами-константами имеет вид Procedure MyProc3 const par1,par2 type1 const par3,par4 type2 ОТКРЫТЫЕ ПАРАМЕТРЫ-МАССИВЫ Открытые параметры-массивы могут быть параметрами-значениями, параметрами-переменными и параметрами-константами. Они используются для передачи массивов произвольной размерности.
Заголовок процедуры с открытыми параметрами-массивами имеет вид Procedure OpenArray Vector array of MyType Формальный параметр при этом является массивом элементов некоторого типа MyType с нулевой базой, т.е. Array 0 N-1 of MyType где N - количество элементов массива, которое можно определить с помощью стандартной функции High. ПРИМЕР Увеличение вдвое всех элементов массива. program
DoubleProgram const n 10 m 20 type T1 array 1 n of integer T2 array -m m of integer var A T1 B T2 k integer Procedure Double var X array of integer var i byte begin for i 0 to High X -1 do X i X i 2 end begin for k 1 to n do read A k for k -m to m do read B k Double A увеличение в 2 раза элементов массива
A Double B увеличение в 2 раза элементов массива B Double k то же самое, что и присваивание k k 2 writeln k ,k напечатается k 40 for k 1 to n do write A k , writeln for k -m to m do write B k , end. БЕСТИПОВЫЕ ПАРАМЕТРЫ В Турбо Паскале существует возможность создания процедур и функций с параметрами, не имеющими типа. Бестиповые параметры могут быть параметрами-переменными и параметрами-константами, так как передаются
только по адресу. Заголовок процедуры с параметрами, не имеющими типа может выглядеть таким образом Procedure MyProc var par1,par2 const par3,par4 Перед использованием формальных параметров необходимо выполнить их приведение к какому-либо типу. Использование бестиповых параметров дает большую гибкость программе, но ответственность за их корректное применение возлагается на программиста. ПРИМЕР Сложение первых N байт, начиная с того же места, что и
X. program without type var N word s string R- отключение контроля за границами диапазонов function Sum var X N byte word type A array 1 1 of byte var i byte s word begin s 0 for i 1 to n do S S A X i Sum s end begin readln s writeln Sum s,1 длина строки s writeln Sum s 1 ,1 код первого символа строки s writeln Sum s 1 ,length s сумма кодов всех символов строки s read N writeln Sum N,2 сумма двух байт, из которых состоит
N типа word end. ПРОЦЕДУРНЫЕ ТИПЫ В Турбо Паскале существует два процедурных типа тип-процедура и тип-функция. Для объявления процедурного типа используется заголовок процедуры или функции без имени. ПРИМЕР type Proc1 Procedure a,b,c integer x real Proc2 Procedure var a,b Proc3 Procedure Func1 Function real Func2 Function n integer boolean Можно описывать переменные этих типов, например var p1,p2
Proc1 f1,f2 Func2 Переменным процедурных типов можно присваивать в качестве значений имена соответствующих ВА. При этом нельзя использовать стандартные процедуры и функции. После такого присваивания имя переменной становится синонимом имени ВА. Переменные процедурного типа можно, также передавать в подпрограммы в виде параметров. Благодаря этому, имеется возможность создания более гибких вспомогательных алгоритмов.
РЕКУРСИЯ Рекурсия - это способ организации вычислительного процесса, при котором подпрограмма в ходе выполнения обращается сама к себе. С идейной точки зрения рекурсия аналогична методу математической индукции. Базе индукции соответствует база рекурсии. Предположению индукции соответствует предположение о том, что нужный ВА уже написан. Наконец, шагу индукции соответствует вызов создаваемого рекурсивного
ВА. В любой рекурсии необходимо предусмотреть условие завершения процесса, т.е. когда вызова больше не происходит. ПРИМЕР Вычислить N-е число Фиббоначчи. Смотри тему Циклы program Fib var n byte function F k byte word begin if k 2 then F 1 else F F k-1 F k-2 рекурсивный вызов end begin write введите номер числа Фиббоначчи readln N writeln N, -е число Фиббоначчи ,
F N readln end. Рекурсивный вызов может быть косвенным, или неявным. Например это происходит в случае, когда один ВА вызывает другой, а тот в свою очередь - первый. При использовании такой программной конструкции необходимо опережающее описание процедур и функций с директивой Forward. Сначала пишется только заголовок ВА со словом Forward, а реализация приводится ниже.
При этом, в ней можно писать в заголовке либо только имя ВА, либо полностью повторять заголовок. ПРИМЕР Неявная рекурсия. Procedure B x byte forward Procedure A y byte begin B y end Procedure B begin A x end РЕКОМЕНДАЦИИ Необходимо по возможности избегать применения рекурсии, так как большая глубина рекурсивных вызовов часто приводит к переполнению стека.
В некоторых случаях проблему можно устранить, установив новый размер стека от 1024 до 65520 байт с помощью директивы M размер стека, нижняя граница, верхняя граница памяти ТИПИЗИРОВАННЫЕ КОНСТАНТЫ Кроме обычных констант в Турбо Паскале можно использовать типизированные константы, которые фактически являются переменными с начальными значениями. Они описываются в разделе Const в форме имя типизированной константы тип значение
ПРИМЕР const x integer 10 y real 3.14 A array 1 5 of integer 1,2 3,24,0 B array 1 2 1 1 of byte 1,2,3 , 4,5,6 R record m string 10 d,y integer end m January d 20 y 1999 S string 4 abcd Типизированные константы могут быть любого типа кроме файлов. При работе они практически ничем не отличаются от переменных. Разница состоит только в том, что если типизированная константа описана в процедуре или функции, то
при первом вызове этой подпрограммы типизированная константа принимает начальное значение, а при последующих вызовах сохраняет значение от предыдущего вызова. Таким способом можно, например, контролировать количество вызовов процедур или функций. ПРИМЕР Использование типизированных констант program typed const var N integer procedure Test const k integer 1 begin if k N then begin writeln k, -й вызов процедуры k k 1 Test end else writeln последний вызов процедуры end
begin read N if N 0 then Test end. МОДУЛИ Модуль Unit в паскале - это специальным образом оформленная библиотека определений типов, констант, переменных, а также процедур и функций. Модуль компилируется отдельно, в результате чего создается файл с расширением tpu turbo pascal unit . Он не может быть запущен на выполнение самостоятельно, а может использоваться только из других программ. Для этого в программах указывается список имен используемых модулей в разделе
Uses, после чего программа может использовать константы, типы и переменные, описанные в этих модулях. В Турбо Паскале существует несколько стандартных модулей System, Crt, Dos, Printer, Overlay, которые составляют библиотеку Турбо Паскаля файл turbo.tpl turbo pascal library . К числу стандартных модулей также относится модуль
Graph. Существует возможность создавать новые модули. Файл модуля имеет следующую структуру UNIT имя модуля INTERFACE раздел объявлений IMPLEMENTATION раздел реализации Begin раздел инициализации End. Имя модуля должно совпадать с именем файла, в котором он хранится. Раздел объявлений или интерфейсная часть содержит объявления всех глобальных объектов модуля типов,
констант, переменных и подпрограмм , которые будут доступны программам, использующим этот модуль. Подпрограммы в этом разделе объявляются только заголовками. В интерфейсной части модулей нельзя использовать опережающее описание, т.е. директиву forward. Раздел реализации или исполняемая часть модуля содержит описание локальных объектов модуля типов, констант, переменных и подпрограмм. Здесь же содержится описание подпрограмм, объявленных в интерфейсной части.
Для этих подпрограмм заголовок может указываться либо без параметров, либо с параметрами, которые в точности повторяют описание из раздела объявлений. Локальные объекты модуля доступны в пределах модуля, но не доступны программам, использующим модуль. Раздел инициализации может отсутствовать. В этом случае можно даже не писать слово Begin, а сразу завершать модуль, написав End. В раздел инициализации входят операторы, которые будут
выполняться при запуске программы, использующей модуль, перед выполнением основной программы. Разделы инициализаций выполняются в том порядке, в котором подключаются модули. ПРИМЕР Модуль для работы с одномерными массивами до 100 целых чисел. модуль описаний, глобальных для основной программы и всех модулей Unit Globals Interface const Len 100 type Vector array 1 Len of integer Implementation
End. Unit Vectors Interface uses Globals находит максимальный элемент массива function Max V A Vector n byte integer поэлементное сложение двух векторов procedure Add V A,B Vector n byte var C Vector скалярное произведение векторов function Scal V A,B Vector n byte integer Implementation function Max V заголовок без параметров var i,max integer begin max
A 1 for i 2 to n do if A i max then max A i Max V max end procedure Add V var i integer begin for i 1 to n do C i A i B i end function Scal V A,B Vector n byte integer заголовок из interface var s integer i byte begin s 0 for i 1 to n do s s A i B i Scal V s end End. раздел инициализации модуля отсутствует АЛГОРИТМЫ ПОИСКА Алгоритмы поиска применяются для нахождения, например, в массиве элемента с нужными
свойствами. Обычно различают постановки задачи поиска для первого и последнего вхождения элемента. Во всех ниже изложенных алгоритмах будем считать, что производится поиск в массиве A из N целых чисел элемента, равного X. ЛИНЕЙНЫЙ ПОИСК Линейный поиск осуществляется циклом while или repeat - until с двойным условием. Первое условие контролирует индекс на принадлежность массиву, например, i
N . Второе условие - это условие поиска. В нашем случае в цикле while это условие продолжения поиска A i X , а в цикле repeat - until это условие завершения поиска A i X . В теле цикла обычно пишется только один оператор изменение индекса в массиве. После выхода из цикла необходимо проверить, по какому из условий мы вышли. В операторе if обычно повторяют первое условие цикла.
Можно говорить об успешном поиске с циклом while при выполнении этого условия, а с циклом repeat - until при его нарушении. ПРИМЕР Линейный поиск program Poisk1 var A array 1 100 of integer N, X, i integer begin read N N 100 for i 1 to N do read A i read X i 1 i 0 while i N and A i X do i i 1 repeat i i 1 until i N or A i
X if i N then write первое вхождение числа ,X, в массив A на ,i, месте else write не нашли end. При поиске последнего вхождения после ввода должны идти операторы i N i N 1 while i 1 and A i X do i i-1 repeat i i-1 until i 1 or A i X if i 1 then write последнее вхождение числа ,X, в массив A на ,i, месте else write не нашли ПОИСК
С БАРЬЕРОМ Идея поиска с барьером состоит в том, чтобы не проверять каждый раз в цикле условие, связанное с границами массива. Это можно обеспечить, установив в массив так называемый барьер любой элемент, который удовлетворяет условию поиска. Тем самым будет ограничено изменение индекса. Выход из цикла, в котором теперь остается только условие поиска, может произойти либо на найденном элементе, либо на барьере. Таким образом, после выхода из цикла проверяется, не барьер ли мы нашли?
Вычислительная сложность поиска с барьером меньше, чем у линейного поиска, но также является величиной того же порядка, что и N - количество элементов массива. Существует два способа установки барьера дополнительным элементом или вместо крайнего элемента массива. ПРИМЕР Поиск с барьером program Poisk2a var A array 1 101 of integer N,X,i integer begin read N N 100 for i 1 to N do read
A i read X A N 1 X установка барьера дополнительным элементом i 1 i 0 while A i X do i i 1 repeat i i 1 until A i X if i N then write первое вхождение числа ,X, в массив A на ,i, месте else write не нашли end. program Poisk2b var A array 1 100 of integer N,X,i,y integer begin read N N 100 for i 1 to N do read A i read X y A N сохранение последнего элемента
A N X установка барьера на последнее место массива i 1 i 0 while A i X do i i 1 repeat i i 1 until A i X if i N or y X then write первое вхождение числа ,X, в массив A на ,i, месте else write не нашли A N y восстановление последнего элемента массива end. ДВОИЧНЫЙ БИНАРНЫЙ ПОИСК Алгоритм двоичного поиска можно использовать для поиска элемента с заданным
свойством только в массивах, упорядоченных по этому свойству. Так при поиске числа с заданным значением необходимо иметь массив, упорядоченный по возрастанию или по убыванию значений элементов. А, например, при поиске числа с заданной суммой цифр массив должен быть упорядочен по возрастанию или по убыванию сумм цифр элементов. Идея алгоритма состоит в том, что массив каждый раз делится пополам и выбирается та часть, где может
находиться нужный элемент. Деление продолжается пока часть массива для поиска больше одного элемента, после чего остается проверить этот оставшийся элемент на выполнение условия поиска. Существуют две модификации этого алгоритма для поиска первого и последнего вхождения. Все зависит от того, как выбирается средний элемент округлением в меньшую или большую сторону. В первом случае средний элемент относится к левой части массива, а во втором - к правой.
В процессе работы алгоритма двоичного поиска размер фрагмента, где этот поиск должен продолжаться, каждый раз уменьшается примерно в два раза. Это обеспечивает вычислительную сложность алгоритма порядка логарифма N по основанию 2, где N - количество элементов массива. ПРИМЕР Поиск в упорядоченном по возрастанию массиве первого вхождения числа X. program Poisk3a var A array 1 100 of integer N,X,left,right integer begin read
N N 100 write введите упорядоченный по возрастанию массив for i 1 to N do read A i read X left 1 right N левая и правая граница фрагмента для поиска while left right do begin c left right div 2 середина с округлением в меньшую сторону if X A c then если массив упорядочен по убыванию, то if X A c left c 1 выбираем правую половину без середины, меняя left else right c выбираем левую половину
с серединой, меняя right end if X A left then здесь left right, но не всегда c write первое вхождение числа ,X, в массив A на ,left, месте else write не нашли end. ПРИМЕР Поиск в массиве, упорядоченном по возрастанию сумм цифр элементов массива, последнего числа с суммой цифр равной X. program Poisk3b var A array 1 100 of integer N,X,left,right integer функция считает сумму цифр числа a, здесь a - локальная переменная function
Sum a integer integer var s integer begin s 0 a abs a while a 0 do begin s s a mod 10 a a div 10 end Sum s end begin read N N 100 write введите массив, упорядоченный по возрастанию сумм цифр например, для N 4 122, -432, 88, 593 for i 1 to N do read A i read X left 1 right N левая и правая граница фрагмента для поиска while left right do begin c left right 1 div 2 середина с округлением в большую сторону if X
Sum A c then left c выбираем правую половину с серединой, меняя left else right c-1 выбираем левую половину без середины, меняя right end if X Sum A left then здесь left right, но не всегда c write последнее число с суммой цифр ,X, равно ,A left , находится в массиве A на ,left, месте else write не нашли end. АЛГОРИТМЫ СОРТИРОВКИ Простейшая задача сортировки заключается в упорядочении элементов массива по возрастанию
или убыванию. Другой задачей является упорядочение элементов массива в соответствии с некоторым критерием. Обычно в качестве такого критерия выступают значения определенной функции, аргументами которой выступают элементы массива. Эту функцию принято называть упорядочивающей функцией. Существуют различные методы сортировки. Будем рассматривать каждый из методов на примере задачи сортировки по возрастанию массива из N целых чисел. СОРТИРОВКА
ВЫБОРОМ Идея метода заключается в том, что находится максимальный элемент массива и меняется местами с последним элементом с номером N . Затем, максимум ищется среди элементов с первого до предпоследнего и ставится на N-1 место, и так далее. Необходимо найти N-1 максимум. Можно искать не максимум, а минимум и ставить его на первое, второе и так далее место. Также применяют модификацию этого метода с одновременным поиском максимума и минимума.
В этом случае количество шагов внешнего цикла N div 2. Вычислительная сложность сортировки выбором - величина порядка N N, что обычно записывают как O N N . Это объясняется тем, что количество сравнений при поиске первого максимума равно N-1. Затем N-2, N-3, и так далее до 1, итого N N-1 2. ПРИМЕР Сортировка выбором по возрастанию массива
A из N целых чисел. program Sort Vybor1 var A array 1 100 of integer N,i,m,k,x integer begin write количество элементов массива read N for i 1 to n do read A i for k n downto 2 do k - количество элементов для поиска max begin m 1 m - место max for i 2 to k do if A i A m then m i меняем местами элементы с номером m и номером k x A m A m A k A k x end for i 1 to n do write A i , упорядоченный массив end.
ПРИМЕР Та же задача с одновременным выбором max и min. program Sort Vybor2 var A array 1 100 of integer N,i,m,k,x,p integer begin write количество элементов массива read N for i 1 to n do read A i for k 1 to n div 2 do k - номер пары max и min begin m k m - место max p k p - место min max и min ищутся среди элементов с k до n-k 1 for i k 1 to n-k 1 do if A i A m then m i else if A i A p then p i меняем местами элементы с номером p и номером k x
A p A p A k A k x if m k then m p если max стоял на месте k, то сейчас он на месте p меняем местами элементы с номером m и номером n-k 1 x A m A m A n-k 1 A n-k 1 x end for i 1 to n do write A i , упорядоченный массив end. СОРТИРОВКА ОБМЕНОМ методом пузырька Идея метода заключается в том, что последовательно сравниваются пары соседних элементов массива. Если они располагаются не в том порядке, то совершаем перестановку,
меняя местами пару соседних элементов. После одного такого прохода на последнем месте номер N окажется максимальный элемент всплыл первый пузырек . Следующий проход должен рассматривать элементы до предпоследнего и так далее. Всего требуется N-1 проход. Вычислительная сложность сортировки обменом O N N . ПРИМЕР Сортировка обменом по возрастанию массива
A из N целых чисел. Базовый вариант program Sort Obmen1 var A array 1 100 of integer N,i,k,x integer begin write количество элементов массива read N for i 1 to n do read A i for k n-1 downto 1 do k - количество сравниваемых пар for i 1 to k do if A i A i 1 then меняем местами соседние элементы begin x A i A i A i 1 A i 1 x end for i 1 to n do write A i , упорядоченный массив end.
Можно заметить, что если при выполнении очередного прохода в сортировке обменом не произведено ни одной перестановки, то это означает, что массив уже упорядочен. Таким образом, можно модифицировать алгоритм, чтобы следующий проход делался только при наличии перестановок в предыдущем. ПРИМЕР Сортировка обменом с проверкой факта перестановки. program Sort Obmen2 var A array 1 100 of integer N,i,k,x integer p boolean begin write количество элементов
массива read N for i 1 to n do read A i k n-1 количество пар при первом проходе p true логическая переменная p истинна, если были перестановки, т.е. нужно продолжать сортировку while p do begin p false Начало нового прохода. Пока перестановок не было. for i 1 to k do if A i A i 1 then begin x A i A i A i 1 A i 1 x меняем элементы местами p true и запоминаем факт перестановки end k k-1 уменьшаем количество пар для следующего прохода end for i 1 to n do write
A i , упорядоченный массив end. Следующая модификация алгоритма сортировки обменом получается при запоминании места последней перестановки. Если при очередном проходе последней парой элементов, которые поменялись местами, были A i и A i 1 , то элементы массива с i 1 до последнего уже стоят на своих местах. Использование этой информации позволяет нам сделать количество пар для следующего прохода равным i-1. ПРИМЕР Сортировка обменом с запоминанием места последней перестановки. program
Sort Obmen3 var A array 1 100 of integer N,i,k,x,m integer begin write количество элементов массива read N for i 1 to n do read A i k n-1 количество пар при первом проходе while k 0 do begin m 0 пока перестановок на этом проходе нет, место равно 0 for i 1 to k do if A i A i 1 then begin x A i A i A i 1 A i 1 x меняем элементы местами m i и запоминаем место перестановки end k m-1 количество пар зависит от места последней перестановки end for i 1 to n do write
A i , упорядоченный массив end. ШЕЙКЕРНАЯ СОРТИРОВКА Этот алгоритм, по сути, является модификацией сортировки обменом. Отличие состоит только в том, что если в сортировке обменом проходы осуществлялись только в одном направлении, то здесь направление каждый раз меняется. В шейкерной сортировке также можно проверять факт перестановки или запоминать место последней перестановки. В базовом алгоритме количество двойных проходов равно
N div 2. Вычислительная сложность шейкерной сортировки O N N . ПРИМЕР Шейкерная сортировка по возрастанию массива A из N целых чисел. program Shaker var A array 1 100 of integer N,i,k,x,j,d integer begin write количество элементов массива read N for i 1 to n do read A i d 1 i 0 for k n-1 downto 1 do k - количество сравниваемых пар begin i i d
for j 1 to k do begin if A i -A i d d 0 then меняем местами соседние элементы begin x A i A i A i d A i d x end i i d end d -d меняем направление движения на противоположное end for i 1 to n do write A i , упорядоченный массив end. СОРТИРОВКА ВКЛЮЧЕНИЕМ Идея данного метода состоит в том, что каждый раз, имея уже упорядоченный массив из K элементов, мы добавляем еще один элемент, включая его в массив таким образом, чтобы упорядоченность
не нарушилась. Сортировка может производиться одновременно со вводом массива. В начале сортировки упорядоченная часть массива содержит только один элемент, который вводится отдельно или, если массив уже имеется, считается единственным, стоящим на нужном месте. Различные методы поиска места для включаемого элемента приводят к различным модификациям сортировки включением. При использовании линейного поиска вычислительная сложность сортировки включением составляет
O N N , а при использовании двоичного поиска - O N LogN имеется в виду логарифм по основанию 2 . ПРИМЕР Сортировка по возрастанию массива A из N целых чисел включением с линейным поиском. program Sort Include1 var A array 1 100 of integer N,i,k,x integer begin write количество элементов массива read N read A 1 for i 1 to n do read A i k - количество элементов в упорядоченной части массива for
k 1 to n-1 do begin read x x A k 1 i k while i 0 and A i x do begin A i 1 A i i i-1 end A i 1 x end for i 1 to n do write A i , упорядоченный массив end. ПРИМЕР Сортировка по возрастанию массива A из N целых чисел включением с двоичным поиском. program Sort Include2 var A array 1 100 of integer N,i,k,x,c,left,right integer begin write количество элементов
массива read N read A 1 for i 1 to n do read A i k - количество элементов в упорядоченной части массива for k 1 to n-1 do begin read x x A k 1 left 1 right k левая и правая граница фрагмента для поиска while left right do двоичный поиск последнего вхождения begin c left right 1 div 2 середина с округлением в большую сторону if x A c then left c берем правую половину с серединой else right c-1 берем левую половину без середины end if x A left then left left 1 сдвигаем на 1 вправо часть массива, освобождая
место для включения x for i k downto left do A i 1 A i A left x end for i 1 to n do write A i , упорядоченный массив end. СОРТИРОВКА ХОАРА Эту сортировку также называют быстрой сортировкой. Метод был разработан в 1962 году профессором Оксфордского университета К. Хоаром. Это прекрасный пример использования рекурсии.
Рассмотрим принцип работы алгоритма при упорядочении массива A из N элементов по возрастанию. Значение какого-нибудь элемента, обычно центрального, записывается в переменную X. Просматриваются элементы массива. При движении слева-направо ищем элемент больше или равный X. А при движении справа-налево ищем элемент меньше или равный X. Найденные элементы меняются местами и продолжается встречный поиск.
После этого массив окажется разделенным на две части. В первой находятся элементы меньше либо равные X, а справа - больше либо равные X. Можно заменить исходную задачу о сортировке массива A на две подзадачи о сортировке полученных частей массива. Вычислительная сложность одного вызова данного рекурсивного алгоритма пропорциональна количеству элементов
сортируемого фрагмента массива. В лучшем случае деление на части производится пополам, поэтому вычислительная сложность всего алгоритма быстрой сортировки составляет величину порядка N LogN логарифм по основанию 2 . Вычислительная сложность в среднем того же порядка. ПРИМЕР Быстрая сортировка по возрастанию массива A из N целых чисел. program Quick Sort var A array 1 100 of integer
N,i integer В процедуру передаются левая и правая границы сортируемого фрагмента procedure QSort L,R integer var X,y,i,j integer begin X A L R div 2 i L j R while i j do begin while A i X do i i 1 while A j X do j j-1 if i j then begin y A i A i A j A j y i i 1 j j-1 end end if L j then QSort L,j if i R then QSort i,R end begin write количество элементов массива read
N for i 1 to n do read A i QSort 1,n упорядочить элементы с первого до n-го for i 1 to n do write A i , упорядоченный массив end. СОРТИРОВКА С ИСПОЛЬЗОВАНИЕМ ВЕКТОРА ИНДЕКСОВ В отличии от всех ранее изложенных методов сортировки, этот не является самостоятельным алгоритмом, а представляет собой идею, которую можно применять к любому из них. Идея заключается в том, что вводится дополнительный массив
B, который принято называть вектором индексов. Числа в нем говорят о том, в каком порядке нужно смотреть на элементы из A, например Массив A 4 7 3 5 Массив B 3 1 4 2 A 3 A 1 A 4 A 2 В начале программы в вектор индексов B записываются последовательно натуральные числа от 1 до N. При работе любой сортировки вместо элемента A i обращаются к элементу
A B i . Это сделано для того, чтобы менять местами не элементы массива A, а их индексы, т.е. элементы массива B. МОДУЛЬ CRT основные возможности Модуль Crt относится к стандартным модулям Турбо Паскаля и находится в файле turbo.tpl Turbo Pascal Library . Для подключения модуля достаточно написать uses Crt. Модуль Crt содержит средства управления экраном в текстовом режиме и клавиатурой.
На экране используются два активных цвета цвет текста и цвет фона. Их можно установить с помощью процедур TextColor и TextBackground, которые имеют по одному параметру целому числу, задающему номер цвета. Для цвета текста используются числа от 0 до 15, а для цвета фона - от 0 до 7. Обе эти процедуры оказывают влияние только на последующий вывод.
Координаты на экране задаются следующим образом. Левый верхний угол имеет координаты 1,1 , а правый нижний 80,25 . Можно вводить относительные координаты, объявляя окно с помощью процедуры Window x1,y1,x2,y2 , где x1,y1 - абсолютные координаты левого верхнего, а x2,y2 - правого нижнего угла окна. После этого все процедуры и функции кроме Window используют относительные координаты. Вернуться к работе со всем экраном можно, написав
Window 1,1,80,25 . С помощью процедуры GotoXY x,y можно установить курсор в заданную позицию окна, а с помощью пары функций WhereX и WhereY без параметров можно узнать текущие координаты курсора. Процедура ClrScr не имеет параметров и закрашивает текущее окно цветом фона. Модуль Crt позволяет осуществлять контроль клавиатуры. Известно, что информация о нажатых клавишах поступает сначала в буфер клавиатуры и только затем считывается
компьютером. Также известно, что клавиши и комбинации клавиш делятся на обычные, и управляющие. В результате нажатия обычной клавиши в буфер клавиатуры поступает ее код, который может быть от 1 до 255, а при нажатии управляющей клавиши в буфер клавиатуры поступает два кода, первый из которых 0. Функция KeyPressed не имеет параметров и возвращает истиный результат если буфер не пуст. При этом содержимое буфера не изменяется. Функция
ReadKey также не имеет параметров и забирает из буфера клавиатуры очередное число, возвращая в программу символ тип char , код которого соответствует этому числу. В случае, когда буфер пуст, функция ReadKey ожидает нажатия на клавиатуре. ЛИТЕРАТУРА 1. Абрамов А.Г Трифонов Н.П Трифонова Г.Н. Введение в язык Паскаль. М Наука, 1988. 2. Абрамов
С.А Гнездилова Г.Г Капустина Е.Н Селюн М.И. Задачи по программированию. М Наука, 1988. 3. Ахо А Хопкрофт Дж Ульман Дж. Построение и анализ вычислительных алгоритмов. М Мир, 1979. 4. Вирт Н. Алгоритмы и структуры данных. М Мир, 1989. 5. Епанешников А Епанешников В. Программирование в среде Turbo Pascal 7.0. М Диалог-Мифи, 1993. 6. Зуев Е.А.
Система программирования Turbo Pascal. М Радио и связь, 1992. 7. Зуев Е.А. Программирование на языке Турбо-Паскаль 6.0,7.0. М. Радио и связь. Веста. 1993. 8. Йодан Э. Структурное программирование и конструирование программ. М. Мир, 1979. 9. Кенин А.М Печенкина Н.С. Работа на
IBM PC. М АО Книга и бизнес , 1992. 10. Кнут Д. Искусство программирования на ЭВМ. М. МИР, т.1, 1976 т.2, 1977 т.3, 1978. 11. Липский В. Комбинаторика для программистов. М Мир, 1988. 12. Майерс Г. Искусство тестирование программ. М. Финансы и статистика, 1982. Гласс Р Нуазо Р. Сопровождение программного обеспечения,
М. Мир, 1983. 13. Пильщиков В.Н. Сборник упражнений по языку Паскаль. М Наука, 1989. 14. Поляков Д.Б Круглов И.Ю. Программирование в среде Турбо Паскаль версия 5.5 . Изд-во МАИ, 1992. 15. Рейнгольд Э Нивергельт Ю Део Н. Комбинаторные алгоритмы. М Мир, 1980. 16. Фаронов
В.В. Турбо Паскаль 7.0. Начальный курс. М Нолидж, 1997. 17. Фаронов В.В. Турбо Паскаль 7.0. Практика программирования. М Нолидж, 1997. 18. Шень А. Программирование Теоремы и задачи. М МЦНМО, 1995. Министерство общего и профессионального образования Российской Федерации Уральский государственный университет им.
А.М. Горького Лахтин А.С Искакова Л.Ю. Языки и технология программирования. Начальный курс. Учебное пособие Екатеринбург 1998 Лахтин А.С Искакова Л.Ю. Языки и технология программирования. Начальный курс. Учеб. пособие. Екатеринбург, 1998. Данное учебное пособие представляет собой первую часть одноименного лекционного курса, который читается
студеттам математико-механического фаультета в 1 семестре. Начальный курс посвящен изложению основ создания программ. Изложение ведется с использованием языка программирования Турбо Паскаль. Рассматриваются некоторые классические алгоритмы. Приводятся примеры решения типовых задач. Пособие предназначено для студентов дистантной формы обучения
специальности Информационные системы , а также может быть использовано для студентов дневной формы обучения по этой специальности. А.С. Лахтин, Л.Ю. Искакова, 1998. СОДЕРЖАНИЕВВЕДЕНИЕ 5 ОСНОВЫ ЯЗЫКА 5 АЛГОРИТМЫ 5 АЛФАВИТ ЯЗЫКА 5 СТРУКТУРА ПРОГРАММЫ 6 ТИПЫ ДАННЫХ 7 Целые типы 7 Вещественные типы 8 Логический тип 9 Символьный тип 9
ВЫРАЖЕНИЯ 9 СОВМЕСТИМОСТЬ ТИПОВ ДАННЫХ 10 ЛИНЕЙНЫЕ АЛГОРИТМЫ 11 ПУСТОЙ И СОСТАВНОЙ ОПЕРАТОРЫ 11 ОПЕРАТОР ПРИСВАИВАНИЯ 11 ПРОСТЕЙШИЙ ВВОД И ВЫВОД 11 РАЗВЕТВЛЯЮЩИЕСЯ АЛГОРИТМЫ 12 ОПЕРАТОР ПЕРЕХОДА 12 УСЛОВНЫЙ ОПЕРАТОР 13 ОПЕРАТОР ВЫБОРА 13 ЦИКЛИЧЕСКИЕ АЛГОРИТМЫ 14 ЦИКЛЫ С
ПАРАМЕТРОМ. 14 ЦИКЛЫ С УСЛОВИЕМ. 16 ПОЛЬЗОВАТЕЛЬСКИЕ ТИПЫ ДАННЫХ 17 ПЕРЕЧИСЛЯЕМЫЙ ТИП 17 ТИП-ДИАПАЗОН 17 МАССИВЫ 17 ЗАПИСИ 17 РАБОТА СО СТРОКАМИ 17 ПРОЦЕДУРЫ И ФУНКЦИИ 17 Параметры-значения 17 Параметры-переменные 17 Параметры-константы 17 ОТКРЫТЫЕ ПАРАМЕТРЫ-МАССИВЫ 17
БЕСТИПОВЫЕ ПАРАМЕТРЫ 17 ПРОЦЕДУРНЫЕ ТИПЫ 17 РЕКУРСИЯ 17 ТИПИЗИРОВАННЫЕ КОНСТАНТЫ 17 МОДУЛИ 17 АЛГОРИТМЫ ПОИСКА 17 ЛИНЕЙНЫЙ ПОИСК 17 ПОИСК С БАРЬЕРОМ 17 ДВОИЧНЫЙ БИНАРНЫЙ ПОИСК 17 АЛГОРИТМЫ СОРТИРОВКИ 17 СОРТИРОВКА ВЫБОРОМ 17 СОРТИРОВКА ОБМЕНОМ методом пузырька 17 ШЕЙКЕРНАЯ СОРТИРОВКА 17
СОРТИРОВКА ВКЛЮЧЕНИЕМ 17 СОРТИРОВКА ХОАРА 17 СОРТИРОВКА С ИСПОЛЬЗОВАНИЕМ ВЕКТОРА ИНДЕКСОВ 17 МОДУЛЬ CRT основные возможности 17 ЛИТЕРАТУРА 17 ВВЕДЕНИЕ Первая версия языка Паскаль была разработана швейцарским ученым Никлаусом Виртом в 1968 году. Первоначально язык предназначался для целей обучения, поскольку он является достаточно детерминированным, т.е. все подчиняется определенным правилам, исключений из которых не так
много. Основные характеристики относительно небольшое количество базовых понятий, простой синтаксис, быстрый компилятор для перевода исходных текстов в машинный код. В 1992 г. фирма Borland International выпустила два пакета, основанных на языке Паскаль Borland Pascal 7.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 и идентификатора - имени программы, за котором следует точка с запятой. Порядок объявлений и описаний не регламентируется. ПРИМЕР Простейшая программа. program prim 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. program sravnenie 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 eps. Число eps можно определять следующим образом min abs a ,abs b 10 -m , где m - необходимое число совпадающих
десятичных разрядов. Логический тип Переменные логического типа 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 операции отношения В логическом выражении 2 4 and 5 3 Паскаль выдаст ошибку, поскольку операция and будет выполнена раньше операций сравнения. Верная запись - 2 4 and 5 3 . СОВМЕСТИМОСТЬ
ТИПОВ ДАННЫХ Когда в операциях или операторах вашей программы присутствуют данные разных типов, то встает вопрос об их совместимости. В языке Турбо Паскаль этому вопросу уделяется очень большое внимание, разработаны строгие правила, определяющие идентичность, совместимость в общем случае и совместимость по присваиванию различных типов. Нам в начале курса достаточно помнить следующее. Переменные или выражения одного типа являются полностью совместимыми.
Другим понятием является совместимость по присваиванию. Присваивание переменной одного типа выражения другого типа допустимо в том случае, когда множество значений второго типа является подмножеством значений первого. Например, результат сложения двух целых переменных типа integer и word может присваиваться в целую переменную, тип которой только longint, поскольку только этот целый тип содержит в себе весь возможный
диапазон значений как для типа integer, так и для типа word. Также, можно присваивать целое выражение в вещественную переменную или символьное выражение в строку. ЛИНЕЙНЫЕ АЛГОРИТМЫ Алгоритмические действия над исходными данными и рабочими объектами языка, необходимые для решения поставленной задачи описываются при помощи операторов Турбо Паскаля. Операторы разделяются точкой с запятой, их последовательность и составляет тело программы.
Наиболее простой случай представляют собой линейные алгоритмы. При выполнении линейных участков алгоритма операторы выполняются последовательно друг за другом в том порядке, в котором они перечислены в программе. При этом могут использоваться операторы присваивания, операции ввода и вывода. ПУСТОЙ И СОСТАВНОЙ ОПЕРАТОРЫ В программе может применяться пустой оператор, не выполняющий никакого действия.
Он представляет собой точку с запятой. Составным оператором считается последовательность произвольных операторов, заключенная в операторные скобки - зарезервированные слова begin end. Допускается произвольная глубина вложенности составных операторов. Составной оператор применяется там, где по синтаксическим правилам языка может стоять только один оператор, а нам надо выполнить несколько действий. В этом случае набор необходимых команд должен быть оформлен
как составной оператор. По сути, все тело программы представляет собой один составной оператор. ОПЕРАТОР ПРИСВАИВАНИЯ Оператор присваивания используется для задания значения переменных и имеет следующий синтаксис имя переменной выражение Вычисляется выражение, стоящее в правой части оператора, после чего его значение записывается в переменную, имя которой стоит слева. Тип выражения и тип переменной должны быть совместимы, т.е. множество допустимых значений для типа
выражения содержится во множестве допустимых значений для типа переменной. ПРОСТЕЙШИЙ ВВОД И ВЫВОД Рассмотрим простейшие процедуры ввода и вывода. По умолчанию ввод осуществляется с клавиатуры, а вывод на экран. К операторам ввода относятся Read список переменных через запятую Readln список переменных Readln Второй отличается от первого тем, что после ввода переводит курсор на
новую строку, точнее, в конце своей работы считывает с клавиатуры код клавиши Enter . Третий оператор используется для организации паузы - выполнение программы продолжится, как правило, только после нажатия на клавиатуре клавиши Enter . К операторам вывода относятся Write список вывода Writeln список вывода Writeln В списке вывода кроме имен переменных можно писать строковые константы
последовательность символов в апострофах и даже выражения выводятся их значения . Второй оператор отличается от первого тем, что после вывода переводит курсор на новую строку. Третий оператор просто переводит курсор на новую строку. Существует так называемый форматированный вывод. Можно задать количество позиций, отводимых под число. Для целых - после выражения или переменной через двоеточие указывается меньше какого количества позиций
не может быть выделено значению. Для вещественных - дополнительно через двоеточие можно указать количество цифр в дробной части. При этом происходит округление в ближнюю сторону. ПРИМЕР Простые вычисления. program vvod vyvod const n 1.5 var y1,y2 real x byte begin writeln Введите натуральное число 255 readln x y1 cos n y2 cos x write Зачем-то посчитали writeln n ,n, y1 ,y1 7 4, cos Pi 2 8 4 напечатается
Зачем-то посчитали n 1.50E 0000 y1 0.0707 1.0000 writeln x ,x 3, y2 ,y2 7 4 end. РАЗВЕТВЛЯЮЩИЕСЯ АЛГОРИТМЫ В Турбо Паскале имеется возможность нелинейного хода программы, т.е. выполнения операторов не в том порядке, в котором они записаны. Такую возможность нам предоставляют разветвляющиеся алгоритмы. Они могут быть реализованы одним из трех способов с использованием операторов перехода, условного оператора
или оператора выбора. ОПЕРАТОР ПЕРЕХОДА Оператор перехода имеет вид GOTO метка . Он позволяет передать управление непосредственно на нужный оператор программы. Перед этим оператором должна располагаться метка отделенная от него двоеточием. В Турбо Паскале в качестве меток выступают либо целые числа от 0 до 9999, либо идентификаторы. Все метки должны быть описаны в разделе объявления меток следующим образом label список меток через
запятую Каждой меткой в программе может быть помечен только один оператор. Операторов перехода с одной и той же меткой можно писать любое количество. Необходимо, чтобы раздел описания метки, сама метка и оператор перехода с ее использованием располагались в пределах одного блока программы см. тему процедуры и функции . Кроме того, нельзя передавать управление внутрь структурированных операторов например, if, for, while,
repeat и др УСЛОВНЫЙ ОПЕРАТОР Условный оператор IF позволяет изменить порядок выполнения команд в зависимости от некоторого логического условия, т.е. он осуществляет ветвление вычислительного процесса. Условный оператор имеет вид IF условие THEN оператор1 ELSE оператор2 В случае истиности логического выражения, стоящего в условии, выполняется оператор1 , а оператор2 пропускается. При ложном значении логического выражения пропускается оператор1 и выполняется
оператор2 . Оператор IF может быть полным присутствуют обе ветви или неполным Else-ветви нет, при ложном условии ничего не делается . По правилам каждая из ветвей может содержать либо один выполняемый оператор, либо несколько, объединенных в составной. Точка с запятой перед Else считается ошибкой. ПРИМЕР Ввести целое число. Вывести соответствующий ему символ
ASCII-таблицы, либо сообщить, что такого символа нет 0-31 - управляющие коды, затем до 256 - печатаемые символы . program ascii symbol var i word begin write Введите целое число readln i if i 31 and i 256 then writeln Соответствующий символ Chr i else writeln Такого символа нет readln end. ОПЕРАТОР ВЫБОРА Если у вас не два возможных варианта выполнения программы, а больше, то может использоваться
оператор выбора CASE. Структура этого оператора в Турбо Паскале CASE ключ выбора OF C1 оператор1 C2 оператор2 CN операторN ELSE оператор0 END Здесь ключ выбора - это выражение порядкового типа, в зависимости от значения которого принимается решение C1, ,CN - значения, с которыми сравнивается значение ключа оператор1 операторN - оператор возможно составные , из которых выполняется тот, с константой которого происходит
первое совпадение значения ключа , оператор0 выполнится, если значение ключа не совпадает ни с одной из констант C1, ,CN. Ветвь Else не обязательна, и в отличие от оператора if, перед ней можно ставить точку с запятой. Если для нескольких значений ключа действия совпадают, то эти константы можно перечислить через запятую перед двоеточием или даже задать диапазон значений нижняя граница верхняя граница . ПРИМЕР Вводится целое число, если это цифра, то определить четная она или нет, а если число, то определить
попадает ли оно в диапазон от 10 до 100, если нет, то выдать соответствующее сообщение. program chislo var i integer begin write Введите целое число readln i case i of 0,2,4,6,8 writeln Четная цифра 1,3,5,7,9 writeln Нечетная цифра 10 100,200 writeln Число от 10 до 100 или 200 else writeln Число либо отрицательное, либо 100, но не 200 end readln end. ЦИКЛИЧЕСКИЕ АЛГОРИТМЫ Турбо Паскаль позволяет использовать три различных оператора для организации
повторяющихся последовательностей действий, которые называют циклами. ЦИКЛЫ С ПАРАМЕТРОМ. Оператор цикла For организует выполнение одного оператора заранее определенное число раз. Его еще называют цикл со счетчиком. Существует две формы оператора FOR параметр nz TO kz DO оператор FOR параметр nz DOWNTO kz DO оператор Здесь параметр цикла счетчик представляет собой переменную порядкового ординального типа
nz и kz - выражения, определяющие начальное и конечное значение счетчика оператор - один возможно составной оператор, который называют телом цикла, повторяемый определенное число раз. На первом шаге цикла параметр принимает значение nz. В этот же момент происходит вычисление kz - значения параметра на последнем шаге цикла. После каждого выполнения тела цикла, если параметр цикла не равен kz, происходит изменение параметра
на следующее большее или меньшее значение в зависимости от формы оператора for, т.е. неявно происходит выполнение одного из двух операторов параметр Succ параметр параметр Pred параметр В случае nz kz в первой форме оператора или nz kz во второй его форме ошибки не происходит, но цикл не выполняется ни разу. После завершения работы цикла значение параметра остается равным kz. РЕКОМЕНДАЦИИ Использовать цикл for при заранее известном количестве повторений.
Не изменять параметр в теле цикла. При использовании кратных вложенных циклов применять разные переменные в качестве параметров. Определять до цикла значения всех используемых в нем переменных. Не ставить точку с запятой после do. ПРИМЕР Вводятся 10 чисел, посчитать среди них количество положительных. program cycle for1 var i,kn byte x real begin kn 0 for i 1 to 10 do begin writeln Введите ,i, число readln x if x 0 then kn kn 1 увеличиваем количество на 1 end writeln
Вы ввели ,kn, положительных чисел. readln end. ПРИМЕР Напечатать буквы от Z до A . program cycle for2 var c char begin for c Z downto A do write c readln end ПРИМЕР Вычислить N-е число Фиббоначчи. Числа Фиббоначчи строятся следующим образом F 0 F 1 1 F i 1 F i F i-1 для i 1. Это пример вычислений по рекуррентным формулам. program
Fib var a,b,c word i,n byte begin write введите номер числа Фиббоначчи readln N a 1 a F 0 , a соответствует F i-2 b 1 b F 1 , b соответствует F i-1 for i 2 to N do begin c a b c соответствует F i a b b c в качестве a и b берется следующая пара чисел end writeln N, -е число Фиббоначчи ,b для N 2 b c readln end. ЦИКЛЫ
С УСЛОВИЕМ. Если заранее неизвестно число повторений цикла, то используются циклы с условием. В паскале имеется два типа таких циклов. Циклы While называют циклами с пред-условием. Они имеют вид WHILE логич.выражение DO оператор Цикл While организует выполнение одного возможно составного оператора пока истинно логическое выражение, стоящее в заголовке цикла. Поскольку значение логического выражения проверяется в начале каждой итерации,
то тело цикла может не выполниться ни разу. Таким образом, в этом цикле логическое выражение - это условие продолжения работы в цикле. Другой вариант циклов с условием - это циклы Repeat. Их называют циклами с пост-условием. Они имеют вид REPEAT оператор 1 оператор N UNTIL логич.выражение Оператор Repeat организует повторяющееся выполнение нескольких операторов до тех пор пока не станет
истинным условие, стоящее в Until-части. Тело цикла обязательно выполняется хотя бы один раз. Таким образом, в этом цикле логическое выражение - это условие выхода из цикла. При создании циклических алгоритмов Турбо Паскаль позволяет использовать процедуры Continue и Break. Процедура Continue досрочно завершает очередной шаг цикла, передает управление на заголовок. Процедура Break реализует немедленный выход из цикла.
РЕКОМЕНДАЦИИ Для того, чтобы избежать зацикливания программы необходимо обеспечить изменение на каждом шаге цикла значения хотя бы одной переменной, входящей в условие цикла. После выхода из цикла со сложным условием с использованием операций and, or, xor как правило необходима проверка того, по какому условию цикл завершен. ПРИМЕР Пары неотрицательных вещественных чисел вводятся с клавиатуры.
Посчитать произведение для каждой пары и сумму всех чисел. program cycle while var x,y,sum real otv char begin sum 0 otv Д while otv Д or otv д do begin write Введите числа x,y 0 readln x,y writeln Их произведение ,x y 8 3 sum sum x y write Завершить программу Д Н ? readln otv end writeln Общая сумма ,sum 8 3 readln end. ПРИМЕР В той же задаче можно использовать другой цикл с условием program cycle repeat var x,y,sum real
otv char begin sum 0 repeat write Введите числа x,y 0 readln x,y writeln Их произведение ,x y 8 3 sum sum x y write Завершить программу Д Н ? readln otv until otv Д or otv д writeln Общая сумма ,sum 8 3 readln end. ПРИМЕР Нахождение наибольшего общего делителя двух целых чисел с помощью Алгоритма Эвклида. program Evklid var a,b,c integer begin write введите два целых числа readln a,b while
b 0 do begin c a mod b a b b c end writeln наибольший общий делитель ,a readln end. ПОЛЬЗОВАТЕЛЬСКИЕ ТИПЫ ДАННЫХ В Турбо Паскале предусмотрен механизм создания новых типов, которые принято называть пользовательскими или конструируемыми. Их можно создавать на основе стандартных и ранее созданных типов. Описание новых типов происходит в разделе TYPE. После этого можно в разделе Var создавать переменные этих типов.
Также, можно сразу описывать новый тип при создании переменной в разделе Var. В этой главе мы рассмотрим следующие пользовательские типы перечисляемый тип, тип-диапазон, массивы, записи. ПЕРЕЧИСЛЯЕМЫЙ ТИП Перечисляемый тип задается перечислением тех значений, которые он может получать. Каждое значение должно являться идентификатором смотри главу Алфавит языка и располагаться в круглых скобках через запятую.
Количество элементов в перечислении не более 65536. Вводить и выводить переменные перечисляемого типа запрещено. Перечислимый тип является порядковым смотри главу Типы данных , поэтому к переменным такого типа можно применять функции Ord, Pred, Succ. Функция Ord возвращает порядковый номер значения начиная с нуля.
ПРИМЕР Объявление перечисляемых типов. Type Colors Red,Green,Blue Numbers Zero,One,Two,Three,Four,Five var c Colors n Numbers begin c Red write Ord c 0 n Four write Ord n 4 c Succ c c Green for n One to Five do write Ord n 12345 end. Следует отметить, что стандартные типы byte, word, char и boolean также можно считать
вариантами перечислимого типа. ТИП-ДИАПАЗОН Тип-диапазон также называют ограниченным или интервальным типом. Он является подмножеством своего базового типа, в качестве которого может выступать любой порядковый тип кроме типа-диапазона. Тип-диапазон наследует все свойства своего базового типа. Имеются две стандартные функции, работающие с этим типом High x - возвращает максимальное значение типа-диапазона, к которому принадлежит переменная x
Low x - возвращает минимальное значение. ПРИМЕР Объявление типа-диапазон. type Numbers Zero,One,Two,Three,Four,Five Num Two Four диапазон на базе типа Numbers Abc A z все английские буквы диапазон на базе типа Char Digits 0 9 цифры var n Num c,d Abc x integer begin n Four writeln Ord n 4 как в базовом типе n Succ n ОШИБКА следующее значение вне диапазона read c,d if
c d then write одинаковые буквы writeln Low c , ,High c A z writeln Low x , ,High x -32768 32767 end. В тексте программы на Турбо Паскале могут встречаться директивы компилятору, которые также называют опциями. Опции R и R- позволяют включать и отключать проверку соблюдения границ при работе с диапазонами. Когда проверка включена, при нарушении границ диапазонов происходит аварийное завершение работы программы.
В другом случае ответственность за возможные ошибки лежит на программисте. МАССИВЫ Массив - это упорядоченная структура однотипных данных, хранящая их последовательно. Доступ к элементу массива осуществляется через его индекс. Массивы описываются следующим образом Имя типа ARRAY диапазоны индексов OF тип элемента массива В качестве типа для элементов массива можно использовать любые типы
Турбо Паскаля кроме файловых. Диапазоны индексов представляют собой один или несколько диапазонов, перечисленные через запятую. В качестве диапазонов индексов нельзя использовать диапазоны с базовым типом Longint. ПРИМЕР Три способа описания одного и того же типа массива type 1 M1 array 0 5 of integer M2 array char of M1 M3 array -2 2 of M2 2 M3 array -2 2 of array char of array 0 5 of integer 3
M3 array -2 2,char,0 5 of integer var A M3 Обращаться к элементам массива можно следующим образом begin read A -1, a ,3 read A 1 x 0 A 1 c ,1 100 end. Глубина вложенности, т.е. количество индексов, при определении массивов не ограничена. Играет роль только суммарный объем данных в программе. В стандартном режиме работы Турбо Паскаля этот объем ограничен размерами сегмента, т.е. 64 килобайта. Целиком над массивами допускается применение только операции присваивания массивов подмассивов
одинаковых типов. Остальные операции должны выполняться поэлементно. ПРИМЕР Вычисление значения многочлена степени N, коэффициенты которого находятся в массиве A в точке X по схеме Горнера. Pn x A 0 X n A 1 X n-1 A n-1 X A n A 0 X A 1 X A 2 X A n-1 X A n . program Scheme Gorner type Mas array 0 100 of integer var A
Mas i,j,n integer x,p real begin write степень многочлена read n writeln введите целые коэффициенты for i 0 to n do read A i write значение X read x p 0 for i 0 to n do p p x A i writeln Pn X ,p end. ЗАПИСИ Запись - это стpуктуpа данных, котоpая может содеpжать инфоpмацию pазных типов, объединенную под одним названием. Компоненты записи называются полями. Их фиксиpованное число. Описание записей имеет следующую стpуктуpу
Имя типа RECORD список полей 1 тип 1 список полей N тип N CASE поле выбора тип OF значение 1 полей 1 тип 1 END Типы полей записи могут быть любыми. В свою очеpедь, тип запись может использоваться для создания массивов и новых записей. Степень вложенности не огpаничена. Список полей может состоять из двух pазделов постоянной и ваpиантной части.
В постоянной части идет пеpечисление полей записи идентификатоpов с указанием их типов. Синтаксис такой же, как в pазделе var. ПРИМЕР Пример объявления типа запись. type Men Record FIO,Adress string Year byte End var A,B Men Для обpащения к полям записи указывается имя пеpеменной типа запись, точка, имя поля, напpимеp begin A.FIO Иванов И.И. A.Adress пp. Ленина, д. 40, кв. 10
A.Year 1981 end. После описания постоянных полей может следовать ваpиантная часть, котоpая может быть только одна и имеет вид CASE поле выбоpа тип OF значение 1 список полей 1 значение N список полей N Поле выбоpа может отсутствовать. Если оно есть, то его воспpинимают как постоянное поле записи. Если его нет, указывается только тип, котоpый должен быть поpядковым, но он не влияет ни на количество пеpечисленных ниже значений, ни на типы этих значений.
Все ваpианты pасполагаются в одном и том же месте памяти, котоpой выделяется столько, сколько тpебуется для максимального по pазмеpу ваpианта. Это пpиводит к тому, что изменение одного ваpиантного поля оказывает влияние на все остальные. Это увеличивает возможности пpеобpазования типов, ПРИМЕР Запись с вариантами. var R Record rem string Case byte of 3 n integer 5 x,y,z char a i,j byte end begin
R.rem запись с ваpиантами R.n 25000 write R.i,R.x,R.j,R.y 168и97a ord и 168, ord a 97, 168 97 256 25000 end. Значения выбоpа могут повтоpяться. Имена полей записи не являются пеpеменными и, следовательно, могут повтоpяться, но только на pазных уpовнях, напpимеp var Rec Record x real Sr Record a real x,y integer end
I byte end Для удобства обpащения к полям записей может использоваться опеpатоp пpисоединения WITH пеpеменная DO опеpатоp Здесь пеpеменная - это запись, за котоpой может следовать список вложенных полей, напpимеp следующие тpи опеpатоpа эквивалентны With Rec,Sr Do a x y With Rec.Sr Do a x y Rec.Sr.a Rec.Sr.x Rec.Sr.y РАБОТА СО СТРОКАМИ Тип String строка в
Турбо Паскале широко используется для обработки текстов. Этот тип является стандартным и во многом похож на одномерный массив символов Array 0 N of Char. Значение N соответствует количеству символов в строке и может меняться от 0 до 255. Символы, входящие в строку, занимают позиции с 1 до N. Начальный байт строки с индексом 0 содержит информацию о ее длине, т.е. это символ с кодом, равным
длине строки. Можно, также описывать переменные типа String K , где K - целое число не больше 255. Так определяются строки с длиной не больше K. Этот тип уже не является стандартным. С символами строки можно работать как с элементами массива из символов, но в отличие от массивов, строки можно вводить целиком, сравнивать друг с другом и сцеплять операцией . ПРИМЕР Работа со строками. var s,x,y,z string begin x turbo y pascal z x y z turbo pascal
s пустая строка for c a to z do s s c s abcd xyz writeln s end. Сравнение строк выполняется посимвольно в соответствии с их кодами до первого несовпадения. Если одна из строк закончилась до первого несовпадения, то она считается меньшей. Пустая строка меньше любой строки. ПРИМЕР Сравнение строк. abcd abcD d D abcd abc d abc axxc b x abcd abcd Существует ряд стандартных функций и процедур для работы со строками.
Функция Length s выдает длину строки s. Функция Concat s1,s2, ,sn возращает строку s1 s2 sn. Функция Copy s,p,k возвращает фрагмент строки s, который начинается в позиции p и имеет длину k. Функция Pos s1,s ищет первое вхождение подстроки s1 в строку s и возвращает номер первого символа s1 в строке s или 0 если не нашли. Процедура Delete s,p,k удаляет из строки s фрагмент, который начинается в позиции p и имеет длину k. Процедура Insert s,s1,p вставляет в строку s подстроку s1, начиная с заданной
позиции p. Турбо паскаль позволяет производить преобразования числовых значений в строковые и наоборот. Для этого используются процедуры Str X n d,S и Val S,X,e . Первая получает их числа X строку S с изображением этого числа, в которой не менее n символов и из них d знаков после запятой. Параметры n и d необязательные. Вторая процедура получает из строки S число X. При успешном результате e 0.
ПРОЦЕДУРЫ И ФУНКЦИИ Турбо Паскаль позволяет выделять фрагменты программы во вспомогательные алгоритмы ВА . Это позволяет писать хорошо структурированные программы. Языки программирования, в которых предусмотрены ВА, называются процедурно-ориентированными. Структурированные программы обычно проще в понимании и отладке. Наличие ВА в языке программирования позволяет применять более совершенные методы при разработке и проектировании
сложных программных комплексов. Известны два наиболее широко применяемых подхода. Первый называется методом нисходящего программирования или разработкой программ сверху - вниз . При этом сначала создается главная программа, предполагая наличие некоторых ВА, решающих определенные задачи. Затем переходят к детальной разработке упомянутых выше необходимых ВА. Другим подходом в разработке программ является метод восходящего программирования или проектированием
снизу - вверх . В этом случае все начинается с создания небольших ВА, из которых затем создаются более сложные ВА и, наконец, основная программа. В Турбо Паскале ВА оформляются в виде процедур или функций. Каждый ВА имеет собственное имя. Вызов процедуры на выполнение осуществляется отдельным оператором с помощью ее имени. Вызов функции может быть составной частью любого выражения при условии согласованности
типов. Описание процедур и функций должно предшествовать их вызову и располагается перед началом основной программы. Нельзя вызывать на выполнение те ВА, которые содержатся внутри других процедур и функций. Описание процедуры имеет следующую структуру. Procedure Имя Список формальных параметров label const Описание локальных меток, type констант, типов и переменных var procedure Описание внутренних процедур function и функций begin
Операторы end Описание функции имеет следующую структуру. Function Имя Список формальных параметров Тип результата label const Описание локальных меток, type констант, типов и переменных var procedure Описание внутренних процедур function и функций begin Операторы, среди которых хотя бы один, который присваивает имени функции значение результата end.
Типом результата в функциях может быть любой из стандартных типов Турбо Паскаля кроме файловых типов. Использование конструируемых типов здесь недопустимо. Существуют понятия локальных и глобальных меток, констант, типов и переменных. Поясним эти понятия на примере переменных. Переменные, описанные в основной программе, являются глобальными по отношению к процедурам и функциям, которые описаны позже этих переменных.
Аналогично, переменные, описанные в процедурах и функциях, являются глобальными по отношению к внутренним процедурам и функциям, которые описаны позже. Остальные переменные называются локальными. Их область действия локализована, т.е. ограничена, тем ВА, где они описаны. Исходные данные для работы ВА можно передавать через глобальные переменные, а также через параметры. Параметры при вызове ВА называются фактическими, а параметры в заголовке
ВА называются формальными. Формальные параметры ВА также относятся к его локальным переменным. Локальные данные создаются, т.е. им выделяется память, при вызове ВА, а освобождение этой памяти происходит при завершении работы ВА. В том случае, когда локальная переменная имеет тот же идентификатор, что и глобальная, алгоритм работает с локальной. При этом, значение глобальной переменной сохраняется в специальной области памяти,
которая называется стек. По способу передачи параметры в Турбо Паскале делятся на три типа параметры-значения, параметры-переменные, параметры-константы. Параметры-значения При вызове процедур и функций формальным параметрам-значениям выделяется новое место в памяти и присваиваются значения фактических параметров. При этом на месте фактических параметров могут стоять выражения.
Совместимость типов определяется возможностями присваивания. После выполнения подпрограммы место формальных параметров освобождается. Изменение формальных параметров не сказывается на значении фактических. Заголовок процедуры с параметрами-значениями имеет вид Procedure MyProc1 par1,par2 type1 par3,par4 type2 Параметры-переменные
При вызове процедур и функций формальные параметры-переменные занимают то же самое место в памяти, что и соответствующие им фактические параметры. Таким образом, дополнительное место в памяти не выделяется и изменения формального параметра приводят к изменениям фактического. Параметры-переменные, как правило, используются для передачи результатов из процедур в вызывающий алгоритм. Такой механизм передачи данных требует, чтобы фактические параметры были переменными, причем в точности
того же типа, что и формальные параметры. При описании ВА перед параметрами-переменными должно присутствовать слово var. Заголовок процедуры с параметрами-переменными имеет вид Procedure MyProc2 var par1,par2 type1 var par3,par4 type2 Параметры-константы Работа с формальными параметрами-константами внутри
ВА ведется как с обычными локальными константами. Только эти константы принимают значения выражений, которые находятся в фактических параметрах. Им не выделяется новая память как локальным переменным. Запрещается изменять их значения во время выполнения подпрограммы и контроль за этим осуществляется на уровне компилятора, как для обычных констант. Использовать параметры-константы рекомендуется при передаче данных большого объема с гарантией сохранения их значений.
Заголовок процедуры с параметрами-константами имеет вид Procedure MyProc3 const par1,par2 type1 const par3,par4 type2 ОТКРЫТЫЕ ПАРАМЕТРЫ-МАССИВЫ Открытые параметры-массивы могут быть параметрами-значениями, параметрами-переменными и параметрами-константами. Они используются для передачи массивов произвольной размерности. Заголовок процедуры с открытыми параметрами-массивами имеет вид
Procedure OpenArray Vector array of MyType Формальный параметр при этом является массивом элементов некоторого типа MyType с нулевой базой, т.е. Array 0 N-1 of MyType где N - количество элементов массива, которое можно определить с помощью стандартной функции High. ПРИМЕР Увеличение вдвое всех элементов массива. program DoubleProgram const n 10 m 20 type T1 array 1 n of integer
T2 array -m m of integer var A T1 B T2 k integer Procedure Double var X array of integer var i byte begin for i 0 to High X -1 do X i X i 2 end begin for k 1 to n do read A k for k -m to m do read B k Double A увеличение в 2 раза элементов массива A Double B увеличение в 2 раза элементов массива B
Double k то же самое, что и присваивание k k 2 writeln k ,k напечатается k 40 for k 1 to n do write A k , writeln for k -m to m do write B k , end. БЕСТИПОВЫЕ ПАРАМЕТРЫ В Турбо Паскале существует возможность создания процедур и функций с параметрами, не имеющими типа. Бестиповые параметры могут быть параметрами-переменными и параметрами-константами, так как передаются только по адресу. Заголовок процедуры с параметрами, не имеющими типа может выглядеть таким образом
Procedure MyProc var par1,par2 const par3,par4 Перед использованием формальных параметров необходимо выполнить их приведение к какому-либо типу. Использование бестиповых параметров дает большую гибкость программе, но ответственность за их корректное применение возлагается на программиста. ПРИМЕР Сложение первых N байт, начиная с того же места, что и X. program without type var N word s string R- отключение контроля за границами диапазонов function
Sum var X N byte word type A array 1 1 of byte var i byte s word begin s 0 for i 1 to n do S S A X i Sum s end begin readln s writeln Sum s,1 длина строки s writeln Sum s 1 ,1 код первого символа строки s writeln Sum s 1 ,length s сумма кодов всех символов строки s read N writeln Sum N,2 сумма двух байт, из которых состоит N типа word end. ПРОЦЕДУРНЫЕ ТИПЫ В Турбо Паскале существует два процедурных типа тип-процедура и тип-
функция. Для объявления процедурного типа используется заголовок процедуры или функции без имени. ПРИМЕР type Proc1 Procedure a,b,c integer x real Proc2 Procedure var a,b Proc3 Procedure Func1 Function real Func2 Function n integer boolean Можно описывать переменные этих типов, например var p1,p2 Proc1 f1,f2 Func2 Переменным процедурных типов можно присваивать в качестве значений имена соответствующих
ВА. При этом нельзя использовать стандартные процедуры и функции. После такого присваивания имя переменной становится синонимом имени ВА. Переменные процедурного типа можно, также передавать в подпрограммы в виде параметров. Благодаря этому, имеется возможность создания более гибких вспомогательных алгоритмов. РЕКУРСИЯ Рекурсия - это способ организации вычислительного процесса, при котором подпрограмма в ходе
выполнения обращается сама к себе. С идейной точки зрения рекурсия аналогична методу математической индукции. Базе индукции соответствует база рекурсии. Предположению индукции соответствует предположение о том, что нужный ВА уже написан. Наконец, шагу индукции соответствует вызов создаваемого рекурсивного ВА. В любой рекурсии необходимо предусмотреть условие завершения процесса, т.е. когда вызова больше
не происходит. ПРИМЕР Вычислить N-е число Фиббоначчи. Смотри тему Циклы program Fib var n byte function F k byte word begin if k 2 then F 1 else F F k-1 F k-2 рекурсивный вызов end begin write введите номер числа Фиббоначчи readln N writeln N, -е число Фиббоначчи ,F N readln end. Рекурсивный вызов может быть косвенным, или неявным.
Например это происходит в случае, когда один ВА вызывает другой, а тот в свою очередь - первый. При использовании такой программной конструкции необходимо опережающее описание процедур и функций с директивой Forward. Сначала пишется только заголовок ВА со словом Forward, а реализация приводится ниже. При этом, в ней можно писать в заголовке либо только имя
ВА, либо полностью повторять заголовок. ПРИМЕР Неявная рекурсия. Procedure B x byte forward Procedure A y byte begin B y end Procedure B begin A x end РЕКОМЕНДАЦИИ Необходимо по возможности избегать применения рекурсии, так как большая глубина рекурсивных вызовов часто приводит к переполнению стека. В некоторых случаях проблему можно устранить, установив новый размер стека от 1024 до 65520 байт с
помощью директивы M размер стека, нижняя граница, верхняя граница памяти ТИПИЗИРОВАННЫЕ КОНСТАНТЫ Кроме обычных констант в Турбо Паскале можно использовать типизированные константы, которые фактически являются переменными с начальными значениями. Они описываются в разделе Const в форме имя типизированной константы тип значение ПРИМЕР const x integer 10 y real 3.14 A array 1 5 of integer 1,2 3,24,0
B array 1 2 1 1 of byte 1,2,3 , 4,5,6 R record m string 10 d,y integer end m January d 20 y 1999 S string 4 abcd Типизированные константы могут быть любого типа кроме файлов. При работе они практически ничем не отличаются от переменных. Разница состоит только в том, что если типизированная константа описана в процедуре или функции, то при первом вызове этой подпрограммы типизированная константа принимает начальное значение, а при последующих
вызовах сохраняет значение от предыдущего вызова. Таким способом можно, например, контролировать количество вызовов процедур или функций. ПРИМЕР Использование типизированных констант program typed const var N integer procedure Test const k integer 1 begin if k N then begin writeln k, -й вызов процедуры k k 1 Test end else writeln последний вызов процедуры end begin read N if N 0 then Test end. МОДУЛИ Модуль Unit в паскале - это специальным образом оформленная
библиотека определений типов, констант, переменных, а также процедур и функций. Модуль компилируется отдельно, в результате чего создается файл с расширением tpu turbo pascal unit . Он не может быть запущен на выполнение самостоятельно, а может использоваться только из других программ. Для этого в программах указывается список имен используемых модулей в разделе Uses, после чего программа может использовать константы, типы и переменные, описанные в этих модулях.
В Турбо Паскале существует несколько стандартных модулей System, Crt, Dos, Printer, Overlay, которые составляют библиотеку Турбо Паскаля файл turbo.tpl turbo pascal library . К числу стандартных модулей также относится модуль Graph. Существует возможность создавать новые модули.
Файл модуля имеет следующую структуру UNIT имя модуля INTERFACE раздел объявлений IMPLEMENTATION раздел реализации Begin раздел инициализации End. Имя модуля должно совпадать с именем файла, в котором он хранится. Раздел объявлений или интерфейсная часть содержит объявления всех глобальных объектов модуля типов, констант, переменных и подпрограмм , которые будут доступны программам, использующим этот модуль.
Подпрограммы в этом разделе объявляются только заголовками. В интерфейсной части модулей нельзя использовать опережающее описание, т.е. директиву forward. Раздел реализации или исполняемая часть модуля содержит описание локальных объектов модуля типов, констант, переменных и подпрограмм. Здесь же содержится описание подпрограмм, объявленных в интерфейсной части. Для этих подпрограмм заголовок может указываться либо без параметров, либо с параметрами, которые в
точности повторяют описание из раздела объявлений. Локальные объекты модуля доступны в пределах модуля, но не доступны программам, использующим модуль. Раздел инициализации может отсутствовать. В этом случае можно даже не писать слово Begin, а сразу завершать модуль, написав End. В раздел инициализации входят операторы, которые будут выполняться при запуске программы, использующей модуль, перед выполнением основной программы.
Разделы инициализаций выполняются в том порядке, в котором подключаются модули. ПРИМЕР Модуль для работы с одномерными массивами до 100 целых чисел. модуль описаний, глобальных для основной программы и всех модулей Unit Globals Interface const Len 100 type Vector array 1 Len of integer Implementation End. Unit Vectors Interface uses Globals находит максимальный элемент массива function
Max V A Vector n byte integer поэлементное сложение двух векторов procedure Add V A,B Vector n byte var C Vector скалярное произведение векторов function Scal V A,B Vector n byte integer Implementation function Max V заголовок без параметров var i,max integer begin max A 1 for i 2 to n do if A i max then max A i Max V max end procedure
Add V var i integer begin for i 1 to n do C i A i B i end function Scal V A,B Vector n byte integer заголовок из interface var s integer i byte begin s 0 for i 1 to n do s s A i B i Scal V s end End. раздел инициализации модуля отсутствует АЛГОРИТМЫ ПОИСКА Алгоритмы поиска применяются для нахождения, например, в массиве элемента с нужными свойствами. Обычно различают постановки задачи поиска для первого и последнего вхождения элемента.
Во всех ниже изложенных алгоритмах будем считать, что производится поиск в массиве A из N целых чисел элемента, равного X. ЛИНЕЙНЫЙ ПОИСК Линейный поиск осуществляется циклом while или repeat - until с двойным условием. Первое условие контролирует индекс на принадлежность массиву, например, i N . Второе условие - это условие поиска. В нашем случае в цикле while это условие продолжения поиска
A i X , а в цикле repeat - until это условие завершения поиска A i X . В теле цикла обычно пишется только один оператор изменение индекса в массиве. После выхода из цикла необходимо проверить, по какому из условий мы вышли. В операторе if обычно повторяют первое условие цикла. Можно говорить об успешном поиске с циклом while при выполнении этого условия, а с циклом repeat -
until при его нарушении. ПРИМЕР Линейный поиск program Poisk1 var A array 1 100 of integer N, X, i integer begin read N N 100 for i 1 to N do read A i read X i 1 i 0 while i N and A i X do i i 1 repeat i i 1 until i N or A i X if i N then write первое вхождение числа ,X, в массив
A на ,i, месте else write не нашли end. При поиске последнего вхождения после ввода должны идти операторы i N i N 1 while i 1 and A i X do i i-1 repeat i i-1 until i 1 or A i X if i 1 then write последнее вхождение числа ,X, в массив A на ,i, месте else write не нашли ПОИСК С БАРЬЕРОМ Идея поиска с барьером состоит в том, чтобы не проверять каждый раз в цикле условие, связанное
с границами массива. Это можно обеспечить, установив в массив так называемый барьер любой элемент, который удовлетворяет условию поиска. Тем самым будет ограничено изменение индекса. Выход из цикла, в котором теперь остается только условие поиска, может произойти либо на найденном элементе, либо на барьере. Таким образом, после выхода из цикла проверяется, не барьер ли мы нашли? Вычислительная сложность поиска с барьером меньше, чем у линейного поиска, но также является величиной
того же порядка, что и N - количество элементов массива. Существует два способа установки барьера дополнительным элементом или вместо крайнего элемента массива. ПРИМЕР Поиск с барьером program Poisk2a var A array 1 101 of integer N,X,i integer begin read N N 100 for i 1 to N do read A i read X A N 1 X установка барьера дополнительным элементом i 1 i 0 while
A i X do i i 1 repeat i i 1 until A i X if i N then write первое вхождение числа ,X, в массив A на ,i, месте else write не нашли end. program Poisk2b var A array 1 100 of integer N,X,i,y integer begin read N N 100 for i 1 to N do read A i read X y A N сохранение последнего элемента A N X установка барьера на последнее место массива i 1 i 0 while
A i X do i i 1 repeat i i 1 until A i X if i N or y X then write первое вхождение числа ,X, в массив A на ,i, месте else write не нашли A N y восстановление последнего элемента массива end. ДВОИЧНЫЙ БИНАРНЫЙ ПОИСК Алгоритм двоичного поиска можно использовать для поиска элемента с заданным свойством только в массивах, упорядоченных по этому свойству.
Так при поиске числа с заданным значением необходимо иметь массив, упорядоченный по возрастанию или по убыванию значений элементов. А, например, при поиске числа с заданной суммой цифр массив должен быть упорядочен по возрастанию или по убыванию сумм цифр элементов. Идея алгоритма состоит в том, что массив каждый раз делится пополам и выбирается та часть, где может находиться нужный элемент. Деление продолжается пока часть массива для поиска больше одного элемента,
после чего остается проверить этот оставшийся элемент на выполнение условия поиска. Существуют две модификации этого алгоритма для поиска первого и последнего вхождения. Все зависит от того, как выбирается средний элемент округлением в меньшую или большую сторону. В первом случае средний элемент относится к левой части массива, а во втором - к правой. В процессе работы алгоритма двоичного поиска размер фрагмента, где этот поиск должен продолжаться,
каждый раз уменьшается примерно в два раза. Это обеспечивает вычислительную сложность алгоритма порядка логарифма N по основанию 2, где N - количество элементов массива. ПРИМЕР Поиск в упорядоченном по возрастанию массиве первого вхождения числа X. program Poisk3a var A array 1 100 of integer N,X,left,right integer begin read N N 100 write введите упорядоченный по возрастанию массив for i 1 to
N do read A i read X left 1 right N левая и правая граница фрагмента для поиска while left right do begin c left right div 2 середина с округлением в меньшую сторону if X A c then если массив упорядочен по убыванию, то if X A c left c 1 выбираем правую половину без середины, меняя left else right c выбираем левую половину с серединой, меняя right end if X A left then здесь left right, но не всегда c write первое вхождение
числа ,X, в массив A на ,left, месте else write не нашли end. ПРИМЕР Поиск в массиве, упорядоченном по возрастанию сумм цифр элементов массива, последнего числа с суммой цифр равной X. program Poisk3b var A array 1 100 of integer N,X,left,right integer функция считает сумму цифр числа a, здесь a - локальная переменная function Sum a integer integer var s integer begin s 0 a abs a while a 0 do begin s s a mod 10 a a div 10 end
Sum s end begin read N N 100 write введите массив, упорядоченный по возрастанию сумм цифр например, для N 4 122, -432, 88, 593 for i 1 to N do read A i read X left 1 right N левая и правая граница фрагмента для поиска while left right do begin c left right 1 div 2 середина с округлением в большую сторону if X Sum A c then left c выбираем правую половину с серединой, меняя left else right c-1 выбираем левую половину
без середины, меняя right end if X Sum A left then здесь left right, но не всегда c write последнее число с суммой цифр ,X, равно ,A left , находится в массиве A на ,left, месте else write не нашли end. АЛГОРИТМЫ СОРТИРОВКИ Простейшая задача сортировки заключается в упорядочении элементов массива по возрастанию или убыванию. Другой задачей является упорядочение элементов массива в соответствии с некоторым критерием.
Обычно в качестве такого критерия выступают значения определенной функции, аргументами которой выступают элементы массива. Эту функцию принято называть упорядочивающей функцией. Существуют различные методы сортировки. Будем рассматривать каждый из методов на примере задачи сортировки по возрастанию массива из N целых чисел. СОРТИРОВКА ВЫБОРОМ Идея метода заключается в том, что находится максимальный элемент массива и меняется местами
с последним элементом с номером N . Затем, максимум ищется среди элементов с первого до предпоследнего и ставится на N-1 место, и так далее. Необходимо найти N-1 максимум. Можно искать не максимум, а минимум и ставить его на первое, второе и так далее место. Также применяют модификацию этого метода с одновременным поиском максимума и минимума. В этом случае количество шагов внешнего цикла N div 2.
Вычислительная сложность сортировки выбором - величина порядка N N, что обычно записывают как O N N . Это объясняется тем, что количество сравнений при поиске первого максимума равно N-1. Затем N-2, N-3, и так далее до 1, итого N N-1 2. ПРИМЕР Сортировка выбором по возрастанию массива A из N целых чисел. program Sort Vybor1 var A array 1 100 of integer
N,i,m,k,x integer begin write количество элементов массива read N for i 1 to n do read A i for k n downto 2 do k - количество элементов для поиска max begin m 1 m - место max for i 2 to k do if A i A m then m i меняем местами элементы с номером m и номером k x A m A m A k A k x end for i 1 to n do write A i , упорядоченный массив end. ПРИМЕР Та же задача с одновременным выбором max и min. program
Sort Vybor2 var A array 1 100 of integer N,i,m,k,x,p integer begin write количество элементов массива read N for i 1 to n do read A i for k 1 to n div 2 do k - номер пары max и min begin m k m - место max p k p - место min max и min ищутся среди элементов с k до n-k 1 for i k 1 to n-k 1 do if A i A m then m i else if A i A p then p i меняем местами элементы с номером p и номером k x A p A p A k A k x if m k then m p если max стоял на месте k, то сейчас он на месте p меняем местами
элементы с номером m и номером n-k 1 x A m A m A n-k 1 A n-k 1 x end for i 1 to n do write A i , упорядоченный массив end. СОРТИРОВКА ОБМЕНОМ методом пузырька Идея метода заключается в том, что последовательно сравниваются пары соседних элементов массива. Если они располагаются не в том порядке, то совершаем перестановку, меняя местами пару соседних элементов. После одного такого прохода на последнем месте номер
N окажется максимальный элемент всплыл первый пузырек . Следующий проход должен рассматривать элементы до предпоследнего и так далее. Всего требуется N-1 проход. Вычислительная сложность сортировки обменом O N N . ПРИМЕР Сортировка обменом по возрастанию массива A из N целых чисел. Базовый вариант program Sort Obmen1 var
A array 1 100 of integer N,i,k,x integer begin write количество элементов массива read N for i 1 to n do read A i for k n-1 downto 1 do k - количество сравниваемых пар for i 1 to k do if A i A i 1 then меняем местами соседние элементы begin x A i A i A i 1 A i 1 x end for i 1 to n do write A i , упорядоченный массив end. Можно заметить, что если при выполнении очередного прохода в сортировке обменом не произведено ни одной
перестановки, то это означает, что массив уже упорядочен. Таким образом, можно модифицировать алгоритм, чтобы следующий проход делался только при наличии перестановок в предыдущем. ПРИМЕР Сортировка обменом с проверкой факта перестановки. program Sort Obmen2 var A array 1 100 of integer N,i,k,x integer p boolean begin write количество элементов массива read N for i 1 to n do read A i k n-1 количество пар при первом проходе p true логическая переменная
p истинна, если были перестановки, т.е. нужно продолжать сортировку while p do begin p false Начало нового прохода. Пока перестановок не было. for i 1 to k do if A i A i 1 then begin x A i A i A i 1 A i 1 x меняем элементы местами p true и запоминаем факт перестановки end k k-1 уменьшаем количество пар для следующего прохода end for i 1 to n do write A i , упорядоченный массив end. Следующая модификация алгоритма сортировки обменом получается при запоминании
места последней перестановки. Если при очередном проходе последней парой элементов, которые поменялись местами, были A i и A i 1 , то элементы массива с i 1 до последнего уже стоят на своих местах. Использование этой информации позволяет нам сделать количество пар для следующего прохода равным i-1. ПРИМЕР Сортировка обменом с запоминанием места последней перестановки. program Sort Obmen3 var A array 1 100 of integer N,i,k,x,m integer begin write количество элементов массива
read N for i 1 to n do read A i k n-1 количество пар при первом проходе while k 0 do begin m 0 пока перестановок на этом проходе нет, место равно 0 for i 1 to k do if A i A i 1 then begin x A i A i A i 1 A i 1 x меняем элементы местами m i и запоминаем место перестановки end k m-1 количество пар зависит от места последней перестановки end for i 1 to n do write A i , упорядоченный массив end. ШЕЙКЕРНАЯ СОРТИРОВКА
Этот алгоритм, по сути, является модификацией сортировки обменом. Отличие состоит только в том, что если в сортировке обменом проходы осуществлялись только в одном направлении, то здесь направление каждый раз меняется. В шейкерной сортировке также можно проверять факт перестановки или запоминать место последней перестановки. В базовом алгоритме количество двойных проходов равно N div 2. Вычислительная сложность шейкерной сортировки
O N N . ПРИМЕР Шейкерная сортировка по возрастанию массива A из N целых чисел. program Shaker var A array 1 100 of integer N,i,k,x,j,d integer begin write количество элементов массива read N for i 1 to n do read A i d 1 i 0 for k n-1 downto 1 do k - количество сравниваемых пар begin i i d for j 1 to k do begin if A i -A i d d 0 then меняем местами соседние элементы begin x
A i A i A i d A i d x end i i d end d -d меняем направление движения на противоположное end for i 1 to n do write A i , упорядоченный массив end. СОРТИРОВКА ВКЛЮЧЕНИЕМ Идея данного метода состоит в том, что каждый раз, имея уже упорядоченный массив из K элементов, мы добавляем еще один элемент, включая его в массив таким образом, чтобы упорядоченность не нарушилась. Сортировка может производиться одновременно со вводом массива.
В начале сортировки упорядоченная часть массива содержит только один элемент, который вводится отдельно или, если массив уже имеется, считается единственным, стоящим на нужном месте. Различные методы поиска места для включаемого элемента приводят к различным модификациям сортировки включением. При использовании линейного поиска вычислительная сложность сортировки включением составляет O N N , а при использовании двоичного поиска - O N
LogN имеется в виду логарифм по основанию 2 . ПРИМЕР Сортировка по возрастанию массива A из N целых чисел включением с линейным поиском. program Sort Include1 var A array 1 100 of integer N,i,k,x integer begin write количество элементов массива read N read A 1 for i 1 to n do read A i k - количество элементов в упорядоченной части массива for k 1 to n-1 do begin read x x A k 1 i k while i 0 and
A i x do begin A i 1 A i i i-1 end A i 1 x end for i 1 to n do write A i , упорядоченный массив end. ПРИМЕР Сортировка по возрастанию массива A из N целых чисел включением с двоичным поиском. program Sort Include2 var A array 1 100 of integer N,i,k,x,c,left,right integer begin write количество элементов массива read N read A 1 for i 1 to n do read A i k - количество элементов в упорядоченной части массива
for k 1 to n-1 do begin read x x A k 1 left 1 right k левая и правая граница фрагмента для поиска while left right do двоичный поиск последнего вхождения begin c left right 1 div 2 середина с округлением в большую сторону if x A c then left c берем правую половину с серединой else right c-1 берем левую половину без середины end if x A left then left left 1 сдвигаем на 1 вправо часть массива, освобождая место для включения x for i k downto left do A i 1
A i A left x end for i 1 to n do write A i , упорядоченный массив end. СОРТИРОВКА ХОАРА Эту сортировку также называют быстрой сортировкой. Метод был разработан в 1962 году профессором Оксфордского университета К. Хоаром. Это прекрасный пример использования рекурсии. Рассмотрим принцип работы алгоритма при упорядочении массива
A из N элементов по возрастанию. Значение какого-нибудь элемента, обычно центрального, записывается в переменную X. Просматриваются элементы массива. При движении слева-направо ищем элемент больше или равный X. А при движении справа-налево ищем элемент меньше или равный X. Найденные элементы меняются местами и продолжается встречный поиск. После этого массив окажется разделенным на две части.
В первой находятся элементы меньше либо равные X, а справа - больше либо равные X. Можно заменить исходную задачу о сортировке массива A на две подзадачи о сортировке полученных частей массива. Вычислительная сложность одного вызова данного рекурсивного алгоритма пропорциональна количеству элементов сортируемого фрагмента массива. В лучшем случае деление на части производится пополам, поэтому вычислительная
сложность всего алгоритма быстрой сортировки составляет величину порядка N LogN логарифм по основанию 2 . Вычислительная сложность в среднем того же порядка. ПРИМЕР Быстрая сортировка по возрастанию массива A из N целых чисел. program Quick Sort var A array 1 100 of integer N,i integer В процедуру передаются левая и правая границы сортируемого фрагмента procedure
QSort L,R integer var X,y,i,j integer begin X A L R div 2 i L j R while i j do begin while A i X do i i 1 while A j X do j j-1 if i j then begin y A i A i A j A j y i i 1 j j-1 end end if L j then QSort L,j if i R then QSort i,R end begin write количество элементов массива read N for i 1 to n do read A i QSort 1,n упорядочить элементы с первого до n-го for i 1 to n do write
A i , упорядоченный массив end. СОРТИРОВКА С ИСПОЛЬЗОВАНИЕМ ВЕКТОРА ИНДЕКСОВ В отличии от всех ранее изложенных методов сортировки, этот не является самостоятельным алгоритмом, а представляет собой идею, которую можно применять к любому из них. Идея заключается в том, что вводится дополнительный массив B, который принято называть вектором индексов. Числа в нем говорят о том, в каком порядке нужно смотреть
на элементы из A, например Массив A 4 7 3 5 Массив B 3 1 4 2 A 3 A 1 A 4 A 2 В начале программы в вектор индексов B записываются последовательно натуральные числа от 1 до N. При работе любой сортировки вместо элемента A i обращаются к элементу A B i . Это сделано для того, чтобы менять местами не элементы массива
A, а их индексы, т.е. элементы массива B. МОДУЛЬ CRT основные возможности Модуль Crt относится к стандартным модулям Турбо Паскаля и находится в файле turbo.tpl Turbo Pascal Library . Для подключения модуля достаточно написать uses Crt. Модуль Crt содержит средства управления экраном в текстовом режиме и клавиатурой. На экране используются два активных цвета цвет текста и цвет фона.
Их можно установить с помощью процедур TextColor и TextBackground, которые имеют по одному параметру целому числу, задающему номер цвета. Для цвета текста используются числа от 0 до 15, а для цвета фона - от 0 до 7. Обе эти процедуры оказывают влияние только на последующий вывод. Координаты на экране задаются следующим образом. Левый верхний угол имеет координаты 1,1 , а правый
нижний 80,25 . Можно вводить относительные координаты, объявляя окно с помощью процедуры Window x1,y1,x2,y2 , где x1,y1 - абсолютные координаты левого верхнего, а x2,y2 - правого нижнего угла окна. После этого все процедуры и функции кроме Window используют относительные координаты. Вернуться к работе со всем экраном можно, написав Window 1,1,80,25 . С помощью процедуры GotoXY x,y можно установить курсор в заданную позицию окна, а
с помощью пары функций WhereX и WhereY без параметров можно узнать текущие координаты курсора. Процедура ClrScr не имеет параметров и закрашивает текущее окно цветом фона. Модуль Crt позволяет осуществлять контроль клавиатуры. Известно, что информация о нажатых клавишах поступает сначала в буфер клавиатуры и только затем считывается компьютером. Также известно, что клавиши и комбинации клавиш делятся на обычные, и управляющие.
В результате нажатия обычной клавиши в буфер клавиатуры поступает ее код, который может быть от 1 до 255, а при нажатии управляющей клавиши в буфер клавиатуры поступает два кода, первый из которых 0. Функция KeyPressed не имеет параметров и возвращает истиный результат если буфер не пуст. При этом содержимое буфера не изменяется. Функция ReadKey также не имеет параметров и забирает из буфера клавиатуры очередное число, возвращая в программу
символ тип char , код которого соответствует этому числу. В случае, когда буфер пуст, функция ReadKey ожидает нажатия на клавиатуре. ЛИТЕРАТУРА 19. Абрамов А.Г Трифонов Н.П Трифонова Г.Н. Введение в язык Паскаль. М Наука, 1988. 20. Абрамов С.А Гнездилова Г.Г Капустина Е.Н Селюн М.И. Задачи по программированию.
М Наука, 1988. 21. Ахо А Хопкрофт Дж Ульман Дж. Построение и анализ вычислительных алгоритмов. М Мир, 1979. 22. Вирт Н. Алгоритмы и структуры данных. М Мир, 1989. 23. Епанешников А Епанешников В. Программирование в среде Turbo Pascal 7.0. М Диалог-Мифи, 1993. 24. Зуев Е.А. Система программирования Turbo Pascal. М Радио и связь,
1992. 25. Зуев Е.А. Программирование на языке Турбо-Паскаль 6.0,7.0. М. Радио и связь. Веста. 1993. 26. Йодан Э. Структурное программирование и конструирование программ. М. Мир, 1979. 27. Кенин А.М Печенкина Н.С. Работа на IBM PC. М АО Книга и бизнес , 1992. 28. Кнут Д. Искусство программирования на
ЭВМ. М. МИР, т.1, 1976 т.2, 1977 т.3, 1978. 29. Липский В. Комбинаторика для программистов. М Мир, 1988. 30. Майерс Г. Искусство тестирование программ. М. Финансы и статистика, 1982. Гласс Р Нуазо Р. Сопровождение программного обеспечения, М. Мир, 1983. 31. Пильщиков В.Н. Сборник упражнений по языку
Паскаль. М Наука, 1989. 32. Поляков Д.Б Круглов И.Ю. Программирование в среде Турбо Паскаль версия 5.5 . Изд-во МАИ, 1992. 33. Рейнгольд Э Нивергельт Ю Део Н. Комбинаторные алгоритмы. М Мир, 1980. 34. Фаронов В.В. Турбо Паскаль 7.0. Начальный курс. М Нолидж, 1997. 35.
Фаронов В.В. Турбо Паскаль 7.0. Практика программирования. М Нолидж, 1997. 36. Шень А. Программирование Теоремы и задачи. М МЦНМО, 1995.
| ! |
Как писать рефераты Практические рекомендации по написанию студенческих рефератов. |
| ! | План реферата Краткий список разделов, отражающий структура и порядок работы над будующим рефератом. |
| ! | Введение реферата Вводная часть работы, в которой отражается цель и обозначается список задач. |
| ! | Заключение реферата В заключении подводятся итоги, описывается была ли достигнута поставленная цель, каковы результаты. |
| ! | Оформление рефератов Методические рекомендации по грамотному оформлению работы по ГОСТ. |
| → | Виды рефератов Какими бывают рефераты по своему назначению и структуре. |