Основы программирования на языке Pascal ( ИЗУЧЕНИЕ ОСНОВНЫХ СЕМАНТИК ЯЗЫКА )
Содержание:
ВВЕДЕНИЕ
В настоящее время, несмотря на засилье си-подобных языков программирования в сфере прикладного программирования, однако, всё ещё сохраняет свою актуальность в рамках учебной и образовательной деятельности такой язык программирования как pascal. Эксперты в области образования подчёркивают его важность для обучения программирования, в виду семантики схожей с человеческой речью, а профессиональные программисты отмечают скорость разработки ПО с помощью данного языка программирования. Когда-то являющийся чуть ли не лидирующим языком программирования, он до сих пор продолжает развиваться в ногу со временем и привлекать к себе не только начинающих, но и уже состоявшихся программистов, но тем не менее, всё ещё находятся скептики, которые утверждают, что даже само существование этого языка в современных реалиях –ошибка. Подтвердить или опровергнуть слова этих скептиков и будет являться целью данной работы. Выдвинем гипотезу о том, что изучение этого языка программирования является академически верным решением для изучения основ программирования для людей, которые не планируют продолжить изучение программирования на более глубоком уровне или для тех, кто ещё мало знаком с программированием вообще. [3] Значение данного вопроса на сегодняшний день является достаточно важным, поскольку многие образовательные стандарты предполагают изучение этого языка, и, если окажется, что противники этого языка правы, то и все образовательные стандарты, в которых он содержится, окажутся несостоятельными. [2] Изучением данного вопроса занимались многие, однако, большинство этих исследований относились к знакомству с языками программирования для людей школьного возраста, мы же в ходе этой работы попробуем обобщить сведения о самом языке, ставя открытый вопрос перед самим читателем. [1] Исходя из этой логики могут быть сформированы задачи, которые должны быть решены в ходе данной работы:
- Представить и изучить основные самодостаточные методичные данные для изучения программирования на языке pascal
- Разобрать основные синтаксические конструкции языка с теоретической и практической стороны
- Изучить основополагающие алгоритмы, необходимые для решения базовых задач по программированию
- Попытаться решить ряд прикладных задач, для доказательства состоятельности языка
Методами исследования в данном случае будут выступать различные справочные материалы (актуальные на сегодняшний день, с учётом последних динамик развития языка) и разработанные в ходе данной работы программы. [4]
ГЛАВА 1. ИЗУЧЕНИЕ ОСНОВНЫХ СЕМАНТИК ЯЗЫКА
Изучение языка можно начать с разбора базовой структуры программы. Минимальная структура базовой программы имеет следующий вид:
Program prog_name;
{раздел описаний}
Begin
{раздел операторов}
End.
Слова Program, begin и end выделяют две части программы - раздел описаний и раздел операторов. Такая структура обязательна для любой программы, что является следствием жесткого требования языка: любой нестандартный идентификатор, используемый в исполняемых операторах, должен быть предварительно описан в разделе описаний. [5] (Стандартные идентификаторы связаны с предварительно объявленными объектами и входят в стандартную библиотеку групп идентификаторов языка pascal. Стандартные идентификаторы, если они используются в программе, описывать не нужно). На первый взгляд требования предварительного описания идентификаторов кажется чрезмерно строгим и делающим язык менее свободным. [6] Однако, в нем проявляется тенденция развития языков программирования в сторону повышения надежности создаваемых программ. Обязательное предварительное описание идентификаторов в Паскале защищает программы от многих ошибок и повышает их надежность.
1.1 ОПЕРАЦИИ
Паскаль является языком высокого уровня, причём Тьюринг-полным, это означает в частности, что любую математически возможную операцию можно выполнить средствами языка Паскаль. [7] Однако, на этом преимущества этого языка программирования не заканчиваются – одними из главных парадигм этого языка служат максимальная приближённость к человеческому языку и удобство разработки прикладных программ. Обозначенное удобство определяется прежде всего большим количеством семантически-понятных операторов (как бинарных, так и унарных) имеющих интуитивно понятные перегрузки над соответствующим полем типов данных. [8] Язык pascal имеет ограничения в методах построения программ,которые связаны как со стремлением сделать программы на данном языке программирования более читаемыми и строгой типизацией языка, что повышает безопасность программ, так и с приближением паскаля к правилам классической математики. В частности, не существуют неявных преобразований типов, конструкции всех операторов имеют единообразный синтаксис, а все операторы имеют своё собственное значение приоритета выполнения. [9] Приоритеты операций, а также сами операции, удобнее всего представить в виде таблицы:
|
Уровень приоритета |
Операции |
|
0 |
[],.,^ |
|
1 |
Not,@ |
|
2 |
*, /,div,mod,and,shl,shr |
|
3 |
+,-,or,xor |
|
4 |
=,<>,>,>=,<,<=,in |
Таблица 1. Приоритет операций pascal
Условно операции можно разделить на унарные, мультипликативные и аддитивные, а также по степени приоритета. Рассмотрим каждую из групп операций в таблице.
1.1.1 АРИФМЕТИЧЕСКИЕ ОПЕРАЦИИ
Арифметические операции подчиняются всем базовым законам математики (аксиоматического подхода над полем целых и вещественных чисел и теоретико-множественного подхода в комплексных структурах), поэтому нет особого смысла останавливаться на них отдельно – более подробно их поведение будет рассмотрено в разделе об изучении типов данной работы. [10]
1.1.2 ЛОГИЧЕСКИЕ ОПЕРАЦИИ
Данные операции отдельно определены над полем перечисляемых типов и полем логических типов. С логическими типа данные операции работают согласно их имени – к примеру оператор не (not) возвращает значение обратное исходному, оператор больше (>) возвращает истину, когда левый операнд больше правого, оператор и (and) возвращает истину только когда левый и правый операнд истина –и так далее. [1] Данное предназначение операторов также не вызывает вопросов даже у людей малознакомых с программированием. Единственное замечание, которое необходимо сделать – это политика вычисления логических операторов. В частности, если имеется бинарный логический оператор и его конечное значение может быть найдено без вычисления второго операнда, то он не будет вычислен компилятором. [5] Например, запись (a>b)and (b>c) не будет вычислять значение аргумента b>c, если на этапе вычисления аргумента a>b выяснилось, что он принимает значение false. Более интересны поведения этих же операторов над полем перечисляемого типа (важное замечание: логический тип также является перечисляемым, и всё что будет описано далее применимо и для него, но это вырожденный случай, который ведёт себя точно так же как и случай, описанный выше, а потому, на этом факте не стоит заострять внимание). В частности, при применении логических операторов к числу –берётся во внимание его побитовое представление, а далее уже путём поразрядного применения логического оператора получается новое число. Например, при применении логического оператора и (and) к числу 8, чья побитовая картинка выглядит как 1000 с числом 6, чья побитовая картинка выглядит как 110 –будет применена поразрядная конъюнкция и в результате получится число 0. Важно понимать, что если мы возьмём менее удобный оператор для приведения примера (например не (not)), то нам было бы необходимо построить побитовую картинку числа исходя из его типа, т.е взять все биты, содержащие информацию о числе и, в случае с оператором не (not) –инвертировать. [2] В этой логике также существуют операторы логического сдвига, которые уже не определены для логического типа, а существуют только для целых чисел. Shl и shr –это соответственно логический сдвиг влево и логический сдвиг вправо. Если мы построим побитовую картинку для какого-то целого числа, например для числа 2 –это 10 и применим к нему оператор shl 1, то исходное число преобразуется к 100, т.е числу 4, в случае с оператором shr 1 – соответственно к числу 1. По сути, данные операторы являются более быстрым аналогом умножения и деления числа на 2, но во многих случаях работающих быстрее. [9]
1.1.3 ОСТАЛЬНЫЕ ОПЕРАЦИИ
Оператор включения in, взятия индекса, обращения к полю записи и переход по ссылке также будет рассмотрен более подробно в соответствующих типах, где их поведение было бы наиболее интересно. Оператор получения адреса @ редко употребим и используется одинаковым образом - в качестве унарного оператора который получает адрес в памяти компьютера, соответствующего его аргументу. [3] В частности, язык паскаль является тьюринг-полным и без работы непосредственной работы с памятью компьютера (хотя, язык достаточно мощный, чтобы не только располагать богатым инструментарием для работы с памятью, но и обладает возможностью модульных вставок на языке ассемблера), и чаще всего такой подход используется для обхода строгих правил, предъявляемых языком или для увеличения быстродействия работы программы (иногда даже для экономии места), но поскольку мы рассматриваем лишь основы работы на языке pascal, то данная тема затронута не будет.
1.2 ОПЕРАТОРЫ
Понятие операций имеет семантическую связь с понятием операторов. Под операторами языка Паскаль подразумевают неделимые элементы программы, которые позволяют выполнять алгоритмы. Наличие операторов в программе всегда подразумевают наличие какого-то действия. [8] Операторы представляют собой некоторые зарезервированные слова с особой конструкцией, отделяемых друг от друга с помощью символа ‘;’. Операторы условно можно подразделить на простые и структурированные. К простым операторам относят
- Оператор присвоения (:=);
- Оператор процедуры;
- Оператор безусловного перехода (goto).
Структурированные же операторы содержат в себе другие операторы. К ним относят:
- Составной оператор (begin-end);
- Оператор условий (if then, case of);
- Оператор цикла (for,while,repeat)
- Оператор присоединения (with)
1.2.1 ОПЕРАТОР ПРИСВАИВАНИЯ
Оператор присваивания (:=) служит для копирования значения одного элемента в другой элемент. Несмотря на кажущуюся простоту записи в теле этого оператора заключена большая часть работы по проверке соответствия типов, тем самым делая программы намного более безопасными, чем других языках, где такой проверки не производится. [7] Поведение оператора присваивания целиком и полностью зависит от преобразования одного типа к другому, а значит, нет нужды дополнительно рассказывать об этом, поскольку данная работа и так постоянно будет обращаться к заданной теме.
1.2.2 ОПЕРАТОР ПРОЦЕДУРЫ
Процедуры и неразрывно связанное с ними понятие функции – крайне важный инструмент Pascal, которые позволяют придавать чёткие формы программе и привносить в работу структуру. [4] Чем более структурированная программа, тем, чаще всего, легче понять её любому читателю и тем меньше вероятность возникновения ошибок. Каждая такая структурная единица (процедура или функция) представляет собой, фактически, отдельный самостоятельный блок программы, который может быть связан с основной лишь через небольшой список параметров. Самостоятельность процедур (функций) делает возможным вынести реализацию очередного блока в локальную среду, из-за чего изменение основной программы не будет затрагивать эти участки кода, что делает программы более гибкими в построении. [6] Процедурой (функцией) в pascal называют обрамлённый специальной конструкцией блок программы, имеющий собственное имя. При обращении к этому имени в любом месте программы называется вызовом. После вызова начинает выполняться тот участок кода, который описан в теле функции (процедуры), а после в вызывающей программе будет переданы указанные параметры (если таковые имеются), после чего выполнение программы продолжится с той же строчки. [10] Для обмена информацией между вызывающей программой и вызываемым куском кода существует целое множество различных механизмов, некоторые из которых будут рассмотрены далее в этой работе. Одним из таких механизмов считают список входных параметров, перечисляемых в круглых скобках при объявлении функции (процедуры). Отличие же функций от процедур в языке pascal заключается лишь в том, что результат работы функции возвращается в вызывающую её программу, синтаксически означая, что можно пользоваться именем функции внутри тела этой же функции словно очередным контейнером, процедуры же больше напоминают просто вынесенный участок кода. [1] Процедуры и функции можно подразделить на пользовательские и библиотечные (стандартные). Библиотечные функции содержатся в модулях, подключаемых в разделе описаний с помощью ключевого слова uses, и в исходном модуле программы (в основном это процедуры для ввода-вывода например Read,Write и функции преобразования типов, например ord,chr). Часто функции содержащиеся в исходном модуле называются стандартными, поскольку созданы одновременно с системой pascal и являются неотъемлемой ее частью (даже если не используются в тексте конкретно взятой программы). Синтаксис описания же пользовательских функций имеет следующий вид:
Function [имя функции] (список параметров): возвращаемое значение;
В случае объявления процедур требуется лишь заменить ключевое слово Function на procedure и опустить блок возвращаемых значений. [5]
1.2.3 ОПЕРАТОР БЕЗУСЛОВНОГО ПЕРЕХОДА
Можно привести чёткое математическое доказательство, что любая конструкция, содержащая оператор безусловного перехода (goto) может быть переписана без этого оператора, более того, считается, что наличие этого оператора делает код более сложным для восприятия, однако, иногда всё-таки это не так и использование этого оператора имеет свои преимущества. Такой оператор имеет следующий синтаксис:
Goto [метка]
Где под меткой подразумевается особый тип, данных, представляющий собой указатель на конкретный фрагмент программы. Метка должна быть объявлена в разделе описаний с помощью ключевого слова label. После того, как в программе будет встречен оператор безусловного перехода –выполнение программы продолжится с той строчки, куда указывает оператор безусловного перехода. Существуют также ограничения: при описании меток в теле отдельно взятой процедуры(функции) –они считаются локальными переменными, поэтому переход к этим меткам вне их области видимости невозможен. [2]
1.2.4 СОСТАВНЫЕ ОПЕРАТОРЫ
Составными операторами называют некоторую череду произвольных операторов, обрамлённых в операторные скобки – ключевые слова begin …end. [8] Такие операторы являются очень важным инструментом работы pascal, которые позволяют полностью отказаться от оператора безусловного перехода. Язык не накладывает никаких ограничений как на характер операторов, так и на уровни вложенности операторов. [1]
Составной или пустой оператор – это и есть блок begin..end, на практике его редко используют без каких-либо дополнительных уровней вложенности, но иногда это позволяет логически выделить какой-то блок кода, что делает программу более читаемой. [1]
1.2.5 УСЛОВНЫЙ ОПЕРАТОР
Условный оператор позволяет проверить какое-то условие и делает ветвление процесса выполнения в зависимости от проверки. Синтаксис описания условного оператора выглядит следующим образом:
If [условие] then [оператор1] else [оператор2]
Где оператор1 и оператор2 любые возможные операторы языка с любой степенью вложенности. Принцип работы условного оператора следующий: если при вычислении значения блока условия получается логическая переменная «истина» true, то выполняется оператор1, если же результат «ложь» false, то выполняется оператор2, причём часть после оператора1 является необязательной и может быть опущена, в этом случае, при результате false в блоке условия программа просто продолжит своё выполнение. По причине того, что в теле оператора1 и оператора2 может быть любой оператор, в том числе и условный, но не каждый условный оператор может содержать конструкцию else, следовательно может возникнуть ситуация неопределённости. Язык pascal решает эту ситуацию таким образом, что каждая встретившаяся часть else относится языком к самому ближайшему к ней фрагменту if. [1]
1.2.6 ОПЕРАТОРЫ ПОВТОРЕНИЙ
В стандартном языке pascal существуют три оператора повторений. Операторы повторений –это инструменты, с помощью которых можно выполнить один и тот же участок кода заданное количество раз. Примером такого оператора служит оператор с заданным количеством итераций for, который имеет следующий вид синтаксиса:
For [параметр цикла]:=[начальное значение] to [конечное значение цикла] do [оператор]
Принцип работы этого оператора заключается в следующем: в начале оператор вычисляет аргумент начального значения, после чего осуществляет присваивание этого значения к параметру циклу, затем циклически повторяет следующие операции: осуществляется проверка текущего значения параметра цикла с вычисленным значением конечного значения, в случае, если параметр цикла<=конечного значения, то выполняется оператор и увеличивается значение параметра цикла на единицу, в ином случае оператор завершает свою работу. [2] Следует отметить, что шаг наращивания аргумента составляет ровно 1, это делает этот оператор менее мощным, чем в языках, где приращение аргумента может быть задано произвольно, однако, существует и другая запись этого оператора, которая выглядит следующим образом:
For [параметр цикла]:=[начальное значение] downto [конечное значение] do [оператор].
Данный оператор по логике выполнения практически идентичен предыдущему, однако шаг приращения аргумента в нём составляет -1, и, соответственно, условие выхода также отличается. Два прочих оператора связаны с проверкой условия выхода и не содержат в себе дополнительный счётчик. [2] Считается, что оператор for при схожих условиях выхода работает быстрее двух других, засчёт того, что условие выхода вычисляется лишь 1 раз, а каждая итерация лишь сравнивает очередное значение аргумента с этим условием.
Оператор цикла While с предпроверкой условия
Оператор цикла While имеет следующую конструкцию записи:
While [условие] do [оператор]
Принцип действия этого оператора следующий: если вычисленное значение выражения условие имеет значение true, то выполняется оператор, по завершению которого будет повторно проверено условие. Фактически, данный оператор является циклической формой записи оператора if. [3]
Оператор цикла Repeat..Until с постпроверкой условия.
Оператор Repeat..Until имеет следующий синтаксис:
Repeat [тело цикла] until [условие]
Принцип работы этого оператора заключается в следующем: выполняется тело цикла, после чего проверяется условие и, если его значение есть false, то тело цикла выполняется ещё раз, после чего будет повторно проверено условие. [3] На практике, данный оператор используют в случае, когда какой-то фрагмент кода нужно выполнить несколько раз, но всегда не менее 1. Для более гибкого управления циклами в языке pascal предусмотрены два оператора: break, который осуществляет безусловный выход из тела цикла и continue, которое насильно завершает текущую итерацию цикла и заставляет оператор перейти к следующей итерации.
1.2.7 ОПЕРАТОР ВЫБОРА
Иногда в программе требуется организовать ветвление из большого количества вариантов, специально для таких целей и существует оператор выбора. [3] В качестве параметра он принимает ключ выбора –элемент по которому и будет происходить ветвление исходной программы. Структура записи такого оператора выглядит следующим образом:
Case [ключ выбора] of [список выбора] else [операторы] end
Где под списком выбора понимают конструкцию вида
[констанста выбора]: [оператор];
…
Причём константой выбора должна быть переменная того же типа, что и ключ выбора.
Принцип работы у этого оператора следующий: вычисляется значение ключа выбора, а затем в порядке объявления аргументов списка выбора осуществляется поиск такого, который совпал бы с ключом выбора и выполняется его оператор, в случае, если такой константы выбора не нашлось управление передаётся оператору, следующему за else (эта часть является необязательной, её можно опустить) и затем осуществляется выход из оператора. [4]
1.3 ИДЕНТИФИКАТОРЫ
Теперь рассмотрим более подробно описания идентификаторов. Описать идентификатор - это значит указать тип связанного с ним объекта программы (константы или переменной). [4] Отсюда вытекает одно из фундаментальных понятий почти любого языка программирования - понятие типа. Чтобы не сильно забегать вперёд, укажем на данном этапе то, что тип определяет, во-первых, способ внутреннего для компьютера представления объекта и, во-вторых, действия, которые разрешается над ним выполнять. По способу представления и обработки типы данных можно подразделить на:
- Простые
- Структурированные
- Указатели
- Объекты
- Процедуры
Сейчас же, необходимо ознакомиться с простыми типами языка pascal, поскольку их понимание лежит в основе понимания и всех прочих типов. [4] Для этого удобнее всего воспользоваться таблицей
|
Название типа |
Назначение типа |
Диапазон |
Размер в байтах |
Операции |
Точность |
|
|
Shortint |
Целочисленный тип |
1 |
Любые арифметические, в т.ч div и mod, кроме / |
Целая часть |
||
|
integer |
Целочисленный тип |
2 |
Любые арифметические, в т.ч div и mod, кроме / |
Целая часть |
||
|
longint |
Целочисленный тип |
4 |
Любые арифметические, в т.ч div и mod, кроме / |
Целая часть |
||
|
Byte |
Целочисленный тип |
1 |
Любые арифметические, в т.ч div и mod, кроме / |
Целая часть |
||
|
word |
Целочисленный тип |
2 |
Любые арифметические, в т.ч div и mod, кроме / |
Целая часть |
||
|
Real |
Вещественный тип |
6 |
Почти все, кроме div и mod |
11-12 цифр |
||
|
single |
Вещественный тип |
4 |
Почти все, кроме div и mod |
7-8 |
||
|
Double |
Вещественный тип |
8 |
Почти все, кроме div и mod |
15-16 |
||
|
Extended |
Вещественный тип |
10 |
Почти все, кроме div и mod |
19-20 |
||
|
Comp |
Вещественный тип |
8 |
Почти все, кроме div и mod |
19-20 |
||
|
Char |
Символьный тип |
В зависимости от компилятора и используемой кодировки или 0..255 или 0..127 |
1 |
Могут выступать входными аргументами для некоторых функций и операторов. |
Целая часть |
|
|
Boolean |
Логический тип |
True или false |
1 |
Логические операции, такие как not,and,or,xor |
Состояние |
|
Таблица 2. Типы данных в языке pascal
Как видно из таблицы простые типы можно условно поделить на порядковые и вещественные типы. Рассмотрим каждый из типов отдельно.
1.3.1 ПОРЯДКОВЫЕ ТИПЫ
Порядковые типы отличаются прежде всего конечным количеством возможных значений, которые можно определённым образом упорядочить, а следовательно, составить некоторое целое число, обозначающее порядковый номер элемента. [5] Если говорить строго, то вещественные типы также имеют конечное число элементов (оно определяется внутренним представлением числа, которое состоит из фиксированного количества бит, а также диапазоном значений), однако, возможное количество значений настолько велико, что сопоставление каждого значения числа вещественного типа с определённым порядковым номером не представляется возможным. Следствием этого факта является то, что над полем порядкового типа определены операции по работе с порядковым номером, примером таких операций могут служить такие стандартные функции языка паскаль, как Ord(X)-возвращающая порядковый номер элемента X, если он принадлежит простому перечисляемому типу данных, Pred(X)-возвращающее предыдущее значение порядкового типа, Succ(X)-возвращающее следующее значение порядкового типа. [5] Причём, функция Pred(X) и Succ(x) не определены для левого и правого конца отрезка порядкового типа соответственно.
1.3.1.1 ЦЕЛОЧИСЛЕННЫЙ ТИП
Использование процедур и функций с целочисленными параметрами обычно руководствуется логикой «вложенности», в частности, это означает, что везде, где допускается использование Byte (но не наоборот), в тип longint «входит» Integer, а тот, соответственно, включает в себя Shortint. Также к возможным операциям с любыми целочисленными типами относятся арифметические операции *,+,-,div (т.е взятие целочисленной части деления одного числа на другое), mod (т.е взятие остатка от деления одного числа на другое). [5] Существует также перечень стандартных процедур и функций, применимых только к целочисленным типам, они также приводятся в таблице ниже:
|
Вызов |
Выходной параметр |
Результат |
|
Abs(x) |
X |
Модуль числа x |
|
Char(byte) |
Char |
Возвращает символ по коду |
|
Dec(vx[,i]) |
- |
Уменьшает значение vx на I, при отсутствии i на 1 |
|
Inc(vx[,i]) |
- |
Увеличивает значение vx на I, при отсутствии i на 1 |
|
Hi(integer) или Hi(word) |
Byte |
Возвратить старший байт аргумента |
|
Lo(integer) или Lo(word) |
Byte |
Возвращает младший байт аргумента |
|
Odd(longint) |
Boolean |
Истина, если аргумент нечётный |
|
Random(x) |
X |
Вернёт псевдослучайное число,равномерно распределённое в диапазоне 0..(w-1) |
|
Sqr(x) |
X |
Вернёт квадрат аргумента |
|
Swap(integer) или swap(word) |
Word |
Поменяет местами байты в слове |
Таблица 3. Целочисленные функции
При любом действии с типом целых чисел результат соответствует типу операндов, а если операнды относятся к различным целым типам, - типу операнда наибольшей мощности. [6] Переполнение программно не контролируется и должно учитываться при составлении программы. Логический тип может принимать только 2 значения из объявленных констант FALSE(ложь) и TRUE(истина). В логическом типе справедливы следующие равенства:
Ord(false)=0,ord(true)=1,false<true,succ(false)=true,pred(true)=false. Логический тип также можно использовать в операторах счетного типа
1.3.1.2 СИМВОЛЬНЫЙ ТИП
Значением символьного типа служит множество всех символов. Символы же в памяти компьютера служат целые числа в диапазоне от 0 до 255. Кодировкой по умолчанию считается кодировка ASCII, в некоторых компиляторах по умолчанию используют кодировку ANSII. [6] Общая черта этих кодировок заключается в том, что коды от 0 до 31 относят к служебным командам, интерпретация этих команд в тексте программы зависит от компилятора, однако при использовании в операциях ввода-вывода или при обращении напрямую к этим командам через специальный оператор # они могут иметь следующие значения (далее описываются только наиболее часто употребимые команды в виде таблицы)
|
Символ |
Код |
Значение |
|
BEL |
7 |
Звуковой сигнал |
|
HT |
9 |
Горизонтальная табуляция |
|
LF |
10 |
Перевод строки |
|
VT |
11 |
Вертикальная табуляция |
|
FF |
12 |
Прогон страницы. Формирование страницы при выводе на принтер. |
|
CR |
13 |
Возврат каретки |
|
SUB |
26 |
Конец файла |
|
ESC |
27 |
Конец работы |
Таблица 4. Примеры служебных кодов
К символьному типу применимы операции отношения и некоторые встроенные функции:
CHR(BYTE)-преобразует байт в символ
Upcase(char)-возвращает заглавную букву, соответствующую прописной латинской букве из входного аргумента. [7]
1.3.1.3 ПОЛЬЗОВАТЕЛЬСКИЙ ПЕРЕЧИСЛЯЕМЫЙ ТИП
Данный тип задаётся указанием пользователем всех тех значений, которое он может получать, причём каждое такое значение называется идентификатором перечисляемого типа и должно быть описано в списке, обрамлённым круглыми скобками. (например, colors=(red,green,blue);). Соответствие каждого элемента списка с его порядковым номером однозначно определяется через порядок объявления этого типа. Нумерация начинается с нулевого элемента. Максимальное количество элементов такого множества -65536. [7]
1.3.1.4 ТИП-ДИАПАЗОН
Такой тип можно задать с помощью следующей записи: [минимальное значение]..[максимальное значение], причём должно удовлетворяться равенство [максимальное значение]>=[минимальное значение]. [7] Такой тип наследует все свойства обычного перечисляемого типа, но с возможными ограничениями. Существуют также 2 отдельные функции для работы с перечисляемыми типами: High(X) –который возвращает максимальный элемент диапазона и Low(X)-который возвращает минимальный элемент диапазона.
1.3.2 ВЕЩЕСТВЕННЫЕ ТИПЫ
Все вещественные числа имеют следующую структуру представления данных:
|
S |
E |
M |
Таблица 5. Представление вещественного числа
Где S-знаковый разряд числа, 1 бит со значениями 0 при положительных значениях и 1 при отрицательных. [8] E-экспоненциальная составляющая, которая содержит двоичный порядок представления числа и m-мантиса числа, которая имеет длину от 23 (Single) до 63 (Extended) двоичных разрядов, что и обуславливает определённую точность числа. Так же следует отметить, что все вычисления для чисел с плавающей запятой в арифметическом сопроцессоре сопроцессоре обрабатываются в формате EXTENDED, а все прочие вещественные типы получаются простым усечением этого типа и применяются в основном для экономии памяти. Исключением является тип Real, который оптимизирован для работы без сопроцессора, поэтому использование типа Real на компьютере оснащённым сопроцессором приводит к дополнительным преобразованием Real к Extended (что вызывает дополнительные вычисления, а значит требует дополнительного времени и сводит на нет все выигрыши в памяти). [8] Также сильно выделяется на общем фоне тип Comp –вещественное число без экспоненциальной и дробной части. Грубо говоря, Comp- это просто большое целое число со знаком, которое хранит в себе до 20 значащих цифр. [8] Тем не менее, этот тип обладает всеми свойствами других вещественных типов и может являться аргументом для любых функций, требующих вещественное число в качестве входного аргумента. Для ознакомления с основными функциями, принимающие вещественные типы составим таблицу:
|
Вызов |
Входной параметр |
Результат |
Действие |
|
Abs(x) |
Целый или вещественный |
Тип аргумента |
Модуль аргумента |
|
Arctan(x) |
Вещественный |
x |
Арктангенс (в радианах) |
|
Cos(x) |
Вещественный |
x |
Косинус (в радианах) |
|
Exp(x) |
Вещественный |
X |
Экспонента |
|
Frac(x) |
Вещественный |
X |
Дробная часть числа |
|
Int(x) |
Вещественный |
X |
Целая часть числа |
|
Ln(x) |
Вещественный |
X |
Натуральный логарифм |
|
Random() |
- |
Вещественный |
Псевдослучайное число в диапазоне 0..1 |
|
Sin(x) |
Вещественный |
X |
Синус в радианах |
|
Sqr(x) |
Целочисленный или вещественный |
X |
Квадрат аргумента |
|
Sqrt(x) |
Целочисленный или вещественный |
Вещественный |
Корень квадратный. |
Таблица 6. Вещественные функции
На основании вышеприведённой таблицы можно сделать вывод, что наиболее активное применение вещественных чисел в программе сопряжено с математическими вычислениями с заданной точностью. [9]
1.3.3 СТРУКТУРИРОВАННЫЕ ТИПЫ
Каждый структурированный тип (а их можно подразделить на 4 категории: записи, множества, файлы и массивы) выделяется тем, что образован из нескольких элементов, каждый из которых также считается структурированным типом, в следствии чего можно говорить о вложенности типов. Глубина вложения определяется параметрами компиляции, однако, по умолчанию, она не должна превышать 65520 байт. [9] Для экономии памяти (и совместимости с более строгим стандартом) можно указать компилятору по возможности экономить место, отводимое под структурированные типы (зарезервированное слово Packed), если компилятор не делает это по умолчанию.
1.3.3.1 МАССИВЫ
Массивы – это упорядоченная цепочка данных одного типа. Стандартные средства языка позволяют управлять элементами массива с помощью оператора индексации («[]»), входным аргументом которого является порядковый номер элемента. Описание массивного типа в общем виде выглядит так: [имя типа]=Array [{список одного или нескольских индексных типов}] of {любой тип Паскаль}. [9] В качестве индексных типов могут быть использованы любые порядковые типы, кроме Longint (в некоторых компиляторах) и типов-диапазонов содержащие тип longint (в некоторых компиляторах). Показательно, что типом после ключевого слова of может служить также массив – на этом факте основано описание многомерных массивов. В памяти компьютера все элементы массива расположены последовательно таким образом, что при переходе от младших адресов памяти к более старшим быстрее меняется самый правый индекс массива. Этот факт считается очень важным при использовании стандартных приёмов копирования массива. Над полем массивных типов определены операция присваивания (но не сравнения). Для задания динамических массивов пользуются функцией SetLength([переменная массива],[размерность массива]), что совершенно не меняет логику работы с массивами, но позволяет более эффективно расходовать память. [10]
1.3.3.2 ЗАПИСИ
Под записью понимают структуру даннах, отличительной особенностью которой является фиксированность числа компонентов (которые называются полями записи). Поля записи могут располагаться не последовательно, и быть разными типами данных. Всю работу по расположению записей в памяти компьютера берёт на себя компилятор. [10] Для обращения к полям записи они должны иметь определённое имя, которое выступает своеобразным указателем на область памяти, содержащее значение поля записи. Сама по себе структура объявления этого типа выглядит следующим образом:
[имя типа]=Record {список полей} End.
Над полем этого типа также определён оператор присваивания, а для обращения к конкретному полю записи используется оператор с одноимённым названием – «.». Для более удобного обращения к полям записи существует оператор With (хотя на сегодняшний день он объявлен устаревшим и небезопасным и в прикладном программировании используется другая конструкция). Все современные компиляторы Паскаля поддерживают так называемые вариантные поля, с помощью оператора Case of, отличительной особенностью таких полей служит то, что каждому варианту такой записи отводится одна и та же область памяти, что открывает дополнительные возможности для преобразования типов. [10]
1.3.3.3 МНОЖЕСТВА
Тип данных множество очень напоминает его соответствующий аналог в математике. Это также некоторый набор логически связанных объектов. Элементам множества предъявляются требования уникальности, а порядок следования не играет никакой роли. [2] В зависимости от компилятора мощность множества ограничено определённым числом (чаще всего – это диапазон от 0 до 256). Запись объявления множества имеет следующий вид:
[имя типа]=set of {базовый тип элементов множества}.
В качестве базового типа могут выступать любые перечисляемые типы, кроме word,integer и longint (в некоторых компиляторах). Над этим типом данных определены операция пересечения (перегрузка оператора *), операция объединения (перегрузка оператора +), операции исключения (перегрузка оператора -), проверка включения одного множества в другое с помощью операторов сравнения, а также проверка принадлежности элемента множеству с помощью оператора in. [6] Для работы с множеством также существуют функции Include([имя множества],[имя типа совпадающего с базовым типом множества]) и Exclude([имя множества],[имя типа совпадающего с базовым типом множества]), которые соответственно включают или исключают элемент или множество из исходного. Отличие от соответствующих операторов заключаются только в лучшей оптимизации этих функций над полем одиночных элементов.
1.3.3.4 СТРОКИ
Наиболее широкоупотребимый контейнер для работы с текстом – тип String. Он по структуре напоминает обычный массив из элементов символьного типа, однако имеет ряд отличий. [3] В частности, тип String имеет динамическую структуру хранения информации (т.е способность увеличиваться в процессе компиляции программы), но не может содержать более 255 элементов (хотя, в некоторых современных компиляторах есть возможность увеличить этот диапазон), также в отличие от массива у строк нет возможности задания произвольной индексации, а в элементе с индексом 0 –всегда содержится текущее количество элементов в строке. Определена операция конкатенации (причём, при условии превышения диапазона значений, лишние символы будут отсечены), а также ряд специализированных функций, которые принимают входным параметром только строки (количество таких функций даже в стандартной библиотеки Паскаль достаточно велико, поэтому, они не будут подробно рассмотрены в ходе этой работы.). Также определены операторы сравнения, причём в реализации происходит посимвольное сравнение строк. [3]
Формально файлы являются объектным типом данных в языке pascal, однако, данная тема является столь обширной, что одной её было бы достаточно, чтобы сделать полноценную курсовую работу, поэтому в рамках текущей работы файлы будут рассмотрены лишь ключевые моменты по работе с файлами, упуская значительную часть теоретических сведений. Под файлом понимают какую-то именованную область внешней памяти компьютера, средствами языка можно получить доступ к этим отделам памяти и прочитать или записать информацию. [7] Не вдаваясь в подробности об устройстве файлах в различных файловых системах можно сказать, что у любого файла есть 3 характерные особенности (очень упрощёно). В первую очередь имя, что позволяет однозначно ссылаться на него и работать с несколькими файлами, также вся информация записанная в файле интерпретируется языком pascal однотипно, и наконец, размер файла ограничен лишь ёмкостью внешней памяти. [1] Для обращения к файловой переменной существуют три конструкции:
1)[имя]=file of [тип];
2)[имя]=Text;
3)[имя]=file;
Отличие в этих объявлениях в том, что первый вариант используют для задания типизированных файлов, чья отличительная черта заключается в том, что компилятор ожидает, что каждая лексема встреченная в файле имеет объявленный тип, в следствии чего, повышается скорость работы с файлом, упрощается разделение файла на лексемы и уменьшается количество кода, необходимого для обработки информации. [4] Второй вариант предполагает наличие текстового файла –т.е работа считается, что неделимым элементом такого файла является символ char. Третий вариант –объявление нетипизированного файла, тип каждого элемента такого файла заранее неопределён. Для того, чтобы связать переменную с именем файла используется стандартная процедура assign([файловая переменная],[имя файла]), в случае если задаётся пустое имя файла, то переменная связывается со стандартными файлами для ввода или вывода информации input или output. [6] Для начала работы с файловыми переменными необходимо инициировать файл т.е указать направление передачи данных. Для этих целей служит функция Reset([файловая переменная]); которая подготавливает файл для чтения и процедуры rewrite([файловая переменная]) и Append([файловая переменная])–которые подготавливают файл для записи. После этого обычно следует проверка файла на открытие, во-избежании ошибок на этапе выполнения программы. После завершения работы с любым файлом его необходимо закрыть, для обеспечения безопасности содержащихся на нём данных, делается это с помощью процедуры Close([файловая переменная]). [5] Для удаления файла используют процедуру erase([файловая переменная]), для переименования используют функцию rename([файловая переменная],[новое имя]). Для чтения и записи данных используют перегрузку стандартных функций read,readln,write,writeln, которые первым аргументом принимают файловую переменную, а весь остальной синтаксис остаётся без изменений. Чтобы получить информацию достигнут ли конец файла используют функцию EOF([файловая переменная]):Boolean. Чаще всего этих наборов инструментов достаточно, чтобы обработать алгоритм, не акцентирующий своё внимание на файловой структуре (т.е просто прочитать информацию с файла или записать информацию на файл). [9]
На этом подошла к концу первая глава, рассматривающая основные семантики языка. Большая часть алгоритмических программ может быть составлена опираясь лишь на эти базовые правила языка. В следующих главах будут рассмотрены программы с опорой лишь на эти базовые инструменты.[3]
ГЛАВА 2. ОСНОВНЫЕ АЛГОРИТМЫ ЯЗЫКА
2.1 МЕТОД ГРАНИЦ
Очень часто в процессе работы программы необходимо разбить какую-то строку на лексемы. Т.е выделить необходимую в строке информацию. Для этих целей служит стандартный алгоритм, который называется «Метод границ». [2] Одна из возможных реализаций этого алгоритма (вариация, когда в строке ищется вхождение числа и записывается в элемент массива, без дополнительных проверок) представлена ниже:
Program m_granic;
Type TintMassiv=array of integer
Var intmassiv:tintmassiv
s:string;
c_:char;
Count,I,a:integer;
Begin
Readln(s);
C_:=’ ‘;
count:=0;
a:=0;
setlength(intmassiv,count+1);
For i:=1 to length(s) do
Begin
If ((ord (s[i])>=48)and(ord(s[i])<=57)) then
A:=a*10+ord(s[i])-48;
Else if ((ord(c_)>=48)and (ord(c_)<=57)) then
Begin
Intmassiv[count]:=a;
Inc(count);
Setlength(intmassiv,count+1);
A:=0;
End;
C_:=s[i];
End;
End.
Сложность этого алгоритма линейна, и он выполняет свою функцию –вычленяет из переменной s все целочисленные аргументы. На практике, это является часто употребимым алгоритмом, поскольку очень часто данные представлены в виде неструктурированных цепочек, которые необходимо обработать. [10] Представленная реализация не очень безопасна, поскольку не контролирует переполнение контейнера а, однако её можно усовершенствовать, применив следующий рассмотренный алгоритм:
2.2 МЕТОД ГОРНЕРА
Очень часто необходимо работать с разными системами счисления или контролировать формат входных данных, проще всего это сделать с помощью алгоритмов метода горнера
Function gorner10(var S:string; Base:integer;):integer;
Var I,a:integer;
Begin
A:=0;
For i:=1 to length(s) do
If ((ord(s[i])>=48) and (ord(s[i]<=57)) then
A:=a*Base+ord(s[i])-48;
Else if ((ord(s[i])>=65) and (ord(s[i])<=91)) then A:=a*Base+ord(s[i])-65+10;
Gorner:=a;
End;
Данный алгоритм переводит число, представленное в строке в любой системе счисления в систему счисления с основанием 10. [10] Данный алгоритм также имеет линейную сложность и достаточно мощный, чтобы сделать проверку на корректность ввода. Обратный алгоритм Горнера (на жаргоне «анти-горнер») выглядит так:
Function agorner(var a,base:integer):string
Var s:string;
I,tmp,count:integer;
Begin
Tmp:=a;
Count:=0;
While (tmp div Base>0)begin tmp:=tmp div Base; inc(count); end;
For i:=0 to count do
Begin
If (a mod Base<=9) then s[count-i+1]:=chr(a mod Base +48) else s[count-i+1]:=chr(a mod Base +65);
End;
Agorner:=s;
End;
У обратной функции горнера уже квадратичная сложность, поэтому считается, что это не самый лучший алгоритм перевода из десятичной системы в другую, однако, в случае вырожденности основания в какую-то степень двойки данный факт может быть частично невелирован с помощью логических операций, а так же безопасность, которую гарантирует этот метод опережает схожие методы. [8]
2.3 МЕТОД ЛОГИЧЕСКОЙ ПЕРЕСТАНОВКИ ЭЛЕМЕНТОВ
Данный метод является наиболее быстрым и безопасным методом для перестановки двух переменных
Program swap;
Var a,b:integer;
Begin
A:=9;
B:=5;
A:=a xor b;
B:=a xor b;
A:= a xor b;
End.
У алгоритма постоянная сложность и он не расходует дополнительной памяти, а также полностью безопасен. [2]
2.4 МЕТОДЫ СОРТИРОВКИ МАССИВОВ
Очень часто в программе требуется отсортировать массив, существует целая масса способов сделать это, каждый из которых показывает хорошие показатели в определённых условиях. Далее будут рассмотрены только два стандартных алгоритма: самый быстрый и простой в написании и чья сложность возрастает с наименьшей скоростью (однако, это не значит, что он является самым лучшим). [5] Под самым быстрым и простым в написании имеется в виду метод сортировки пузырьком. Своё название он получил благодаря идеи, что в нём заложена –при сравнении двух элементов самый лёгкий (меньший) идёт наверх, а тяжёлый (больший) вниз (определение верха и низа у массива считается тонкостью реализации…), поэтому, в худшем случае сложность этого алгоритма –квадратичная. [1] Предположим у нас есть массив M[1..N], тогда реализация будет:
begin
for j:=1 to N-1 do
for i:=1 to N-j do
if M[i] > M[i+1] then
swap(M[i],M[i+1])
end;
Преимущество данного алгоритма –скорость реализация. В большинстве проектов (особенно небольших) оптимизация – это отдельный этап разработки, который наступает уже после релиза исходного продукта, поэтому скорость написания и сложность понимания алгоритмов также считаются важными показателями. [9] В случае же, когда данных действительно много, или же просто нет необходимости в выборе подходящего под конкретную задачу алгоритма, обычно предпочитают пользоваться методом «быстрой сортировки», поскольку сложность алгоритма в этом случае логарифмическая, что является наименьшей среди прочих. [6]
procedure quicksort(var mas: array[1..n] of integer; first, last: integer);
var f, l, mid, count: integer;
begin
f:=first;
l:=last;
mid:=mas[(f+l) div 2];
repeat
while mas[f]<mid do inc(f);
while mas[l]>mid do dec(l);
if f<=l then
begin
count:=mas[f];
mas[f]:=mas[l];
mas[l]:=count;
inc(f);
dec(l);
end;
until f>l;
if first<l then quicksort(A, first, l);
if f<last then quicksort(A, f, last);
end;
На практике, программисты порой даже не думают о том, какую именно сортировку им использовать, а используют одну из указанных двух, особенно это актуально с учётом постоянно растущих мощностей вычисления и улучшения алгоритмов работы минификаторов данных. [3]
Последний алгоритм, который будет рассмотрен –это возведение числа в степень. Стандартные методы возведения числа в степень работают недостаточно эффективно, а соответствующей перегрузки нет в стандарте pascal, поэтому обычно пользуются следующим математическим приёмом:
X^y=exp(ln(X) * Y)
С математической точки зрения, это работает, поскольку при взятии экспоненты от натурального логарифма получается логарифмическое выражение, а по свойству логарифма степень выражения можно вынести в множитель логарифма. Через эту логику реализовано возведение в степень в других языках программирования. [1]
Данных алгоритмов обычно оказывается достаточно для комфортной работы на языке программирования pascal, и хотя само по себе программирование как область научного знания приводит практически любую задачу к набору стандартных алгоритмов, которые были бы эффективны в рамках данного языка и чья алгоритмическая сложность была бы минимальна и я бы соврал, если бы сказал, что мы разобрали хотя бы сколько-нибудь ощутимую часть от всех стандартных алгоритмов –всё-таки в прикладном программировании чаще всего предпочитают опираться на совсем базовые алгоритмы или библиотечные функции, чтобы создать свою собственную реализацию какой-то задачи. И я точно могу сказать, что приведённых алгоритмов обычно оказывается достаточно для собственных реализаций. [5]
ГЛАВА 3. РАЗРАБОТКА ПРИКЛАДНЫХ ПРОГРАММ В СРЕДЕ FREE PASCAL
Итак, чтобы проиллюстрировать, что приведённых теоретических сведений достаточно, чтобы чувствовать себя программистом, способным реализовывать прикладные задачи будут решены некоторые прикладные задачи. Под прикладными имеются в виду задачи, которые могли бы быть частью какой-то большой программы или которые являлись самодостаточными проектами в очень локальном промежутке. [7] Примером таких программ может служить методы реализующие логику длинной арифметики (без учёта оптимизаций), хотя такую программу сложно назвать прикладной, поскольку существуют специальные библиотеки, которые реализуют длинную арифметику, всё-таки может случиться так, что её необходимо будет реализовать с нуля. Итак, под длинной арифметикой понимают случаи, когда исходное число слишком велико, чтобы поместиться в стандартный контейнер и над таким числом необходимо провести стандартные математические операции (сложение, вычитание, умножение и деление). [4] Поскольку стандартные контейнеры недостаточно велики для хранения таких длинных чисел, то придётся написать с нуля и структурный вид контейнера числа и операции чтения и записи числа, ну и само собой всю арифметику.
Const MaxDig=1000;
Osn=10000;
Type Tlong=Array[0..MaxDig] Of Integer;
Одним из вариантов хранения такого числа является массив, каждый элемент которого –одна цифра такого числа, само собой для компактности (нам всё равно необходимо реализовывать арифметику с нуля) основание системы счисления должно быть максимально большим. [6] Несложно математически показать, что оно должно быть максимальной степенью двойки для максимальной эффективности по памяти (по скорости такое решение неочевидно, однако, если брать в расчёт «оптимальность дальнейших реализуемых алгоритмов», тогда нет никакой разницы в какой системе счисления хранить числа), которая не превышает заданного типа, однако, это сильно усложняет программу, (а мы не гонимся за эффективностью), поэтому для простоты возьмём просто степень числа 10. [8] Также для оптимизации, в 0 элементе будем хранить фактическую длину числа,а само число будет располагаться в обратном порядке. Далее необходимо реализовать функцию чтения:
Procedure ReadLong(Var A:Tlong);
Var ch:char;i:Integer;
Begin
FillChar(A,SizeOf(A) , 0) ;
Read(ch);
While Not(ch In ['0'..'9']) Do Read(ch);
{пропуск не цифр во входном файле}
While ch In ['0'..'9'] Do Begin
For i:=A[0] DownTo 1 Do Begin
A[i+l]:=A[i+l]+(LongInt(A[i])*10) Div Osn;
A[i]:=(LongInt(A[i])*10) Mod Osn;
End;
A[1]:=A[l]+Ord(ch)-Ord('0' ) ;
If A[A[0]+1]>0 Then Inc(A[0]);
Read(ch) ;
End;
End;
И сразу же функцию записи, с учётом особенности хранения числа:
Procedure WriteLong(Const A:Tlong);
Var ls,s:String;
i:Integer;
Begin
Str (Osn Div 10,Is) ;
Write(A[A[0]];{выводим старшие цифры числа}
For i:=A[0]-l DownTo 1 Do Begin
Str(A[i],s) ;
While Length(s)<Length(Is) Do s:='0'+s;
{дополняем незначащими нулями}
Write (s) ;
End;
Writein;
End;
Теперь, когда у нас есть все необходимые обслуживающие функции, можно приступить к непосредственной реализации арифметики. [10] Не будем мудрить в плане алгоритмов (для достаточно эффективных алгоритмов можно обратиться к книге алгоритмические приёмы программирования, там в разделе описания алгоритмов для целочисленной арифметики можно найти множество эффективных алгоритмов, которые и легли в основу реализаций специализированных библиотек), мы же будем реализовывать алгоритм «в лоб» -реализация алгоритмов арифметики столбиком, прямиком со школьной скамьи.
Procedure SumLongTwo(A,B:Nlong; Var C:Tlong);
Var i,k:Integer;
Begin
FillChar(C,SizeOf (C),0) ;
If A[0]>B[0] Then k:=A[0] Else k:=B[0];
For i:=l To k Do
Begin С [i+1]:=(C[i]+A[i]+B[i]) Div Osn;
C[i]:=(C[i]+A[i]+B[i]) Mod Osn;
End;
If C[k+l]=0 Then C[0]:=k Else C[0]:=k+l;
End;
Далее нам потребуются функции сравнения двух чисел, приведём одну из возможных реализаций:
Function Eq(A,B:TLong):Boolean;
Var i:Integer;
Begin
Eq:=False;
If A[0]OB[0] Then Exit
Else Begin
i:=l;
While (i<=A[0]) And (A[i]=B[i]-) Do Inc(i);
Eq:==(i=A[0]+l) ;
End;
End;
Function More(A,B:Tlong):Boolean;
Var i:Integer;
Begin If A[0]<B[0] Then More:=False
Else If A[0]>B[0] Then More:=True
Else Begin
i : =A [ 0 ] ;
While (i>0) And (A[i]=B[i]) Do Dec(i);
If i=0 Then More:=False
Else If A[i]>B[i] Then More:=True
Else More:=False;
End;
End;
Function Less(A,B:Tlong):Boolean;{A<B}
Begin
Less:=Not(More(A,B) Or Eq(A,B));
End;
Function More_Eq(A,B:Tlong):Boolean;
Begin
More_Eq:=More(A,B) Or Eq(A,B);
End;
Function Less_Eq (A, B:Tlong) : Boolean;
Begin
Less_Eq:-Not(More(A,B)) ;
End;
На практике, в программировании часто удобно пользоваться приёмом, что при сравнении двух чисел выдаётся число (а не булевая переменная), которая и отражает результат сравнения. Реализуем такую, с учётом сдвига чисел.
Function More(Const А, В: Tlong;
Const sdvig: Integer): Byte;
Var i: Integer;
Begin
If A[0]>(B[0]+sdvig) Then More:=0
Else If A[0]<(B[0]+sdvig) Then More:=l
Else Begin
i:=A[0];
While (i>sdvig) And
(A[i]=B[i-sdvig]) Do Dec(i);
If i=sdvig Then Begin
More:=0;
For i:=l To sdvig Do If A[i]>0 Then Exit;
More:=2;
End
Else More:=Byte(A[i]<B[i-sdvig]) ;
End;
End;
Перейдём к умножению двух длинных чисел.
Procedure Mul(Const A: TLong;Const К:
Longlnt;Var С: TLong) ;
Var i: Integer;
{результат - значение переменной С}
Begin
FillChar (С, SizeOf (С), 0) ;
If K=0 Then Inc(С[0]){умножение на ноль}
Else Begin
For i:==l To A[0] Do Begin
C[i+l]:=(LongInt(A[i])*K+C[i]) Div Osn;
C[i]:=(LongInt(A[i])*K +C[i]) Mod Osn;
End;
If C[A[0]+1]>0 Then C[0]:=A[0]+1
Else C[0]:=A[0] ;
End;
End;
Реализуем вычитание двух чисел:
Procedure Sub (Var A: TLong;
Const B: TLong;
Const sp: Integer);
Var i,j: Integer;
Begin
For i:=l To B[0] Do Begin Dec(A[i+sp], B[i]);
j:=i;
while (A[j+sp]<0) and (j<=A[0}) Do
Begin
Inc(A[j+sp], Osn) ;
Dec(A[j+sp+l]);Inc(j) ;
end;
End;
i : =A [ 0 ] ;
While (i>l) And (A[i]=0) Do Dec(i);
A[0]:=i;
End;
И наконец самое сложное – реализация деления двух длинных чисел, которое также будет реализовано через «алгоритм столбика». [2] Сам алгоритм можно разбить на 2 этапа: подбор очередной цифры, которая пойдёт частное и получение очередного числа – делимого. Разобьём эти 2 этапа на функции:
Function FindBin(Var Ost: Tlong;Const В:
TLong;Const sp: Integer): Longint;
Var Down, Up: Word;
C: TLong;
Begin
Down:=0;Up:=0sn;
While Up-l>Down Do Begin
Mul(В, (Up+Down) Div 2, С);
Case More(Ost, C, sp) Of
0: Down:=(Down+Up) Div 2;
1: Up:== (Up+Down) Div 2;
2: Begin Up:=(Up+Down) Div 2;
Down:=Up; End;
End;
End;
Mul(B, (Up+Down) Div 2, C);
If More (Ost.C,0)=0 Then Sub(Ost, C, sp)
Else begin Sub (C,Ost,sp); Ost:=C;
end;
FindBin:=(Up+Down) Div 2;
End;
Procedure MakeDel(Const А, В: TLong;
Var Res, Ost: TLong);
Var sp: Integer;
Begin
Ost:=A;
sp : =А [ 0 ] -В [ 0 ] ;
If More(А, В, sp)=l Then Dec(sp);
Res [0]:=sp+l;
While sp>=0 Do Begin
Res [sp+1]:=FindBin(Ost, B, sp);
Dec(sp) ;
End;
End;
Вот мы и получили полный набор инструментариев для реализации длинной арифметики. Как видно, нами активно использовались вещи, описанные в предыдущих главах, что лишь очередной раз подтверждает их пользу. [6]
Реализуем ещё одну программу, которая также может являться частью какой-то более большой программы: предположим в каком-то фрагменте нам стало необходимо найти определитель матрицы. [3] Реализуем программу, которая выполняет это:
program opred;
uses crt;
const n=3;
type
Tmatr=array [1..n,1..n] of real;
var a:Tmatr;
det:real;
procedure Per(k,n:integer;var a:Tmatr; var p:integer);
var i,j:integer;z:real;
begin
z:=a[k,k];i:=k;p:=0;
for j:=k+1 to n do
begin
if abs(a[j,k])>z then
begin
z:=abs(a[j,k]);i:=j;
p:=p+1;
end;
end;
if i>k then for j:=k to n do
begin
z:=a[i,j];a[i,j]:=a[k,j];a[k,j]:=z;
end;
end;
function znak(p:integer):integer;
begin
if p mod 2=0 then
znak:=1 else znak:=-1;
end;
procedure opr(n:integer;var a:Tmatr;var det:real);
var k,i,j,p:integer;
r:real;
begin
det:=1;
for k:=1 to n do
begin
if a[k,k]=0 then per(k,n,a,p);
det:=znak(p)*det*a[k,k];
for j:=k+1 to n do
begin
r:=a[j,k]/a[k,k];
for i:=k to n do
begin
a[j,i]:=a[j,i]-r*a[k,i];
end;
end;
end;
end;
В программе используется вырожденный случай, когда необходимо найти определитель матрицы 3x3, однако этот алгоритм достаточно мощный, чтобы работать с матрицами больших размерностей. [1]
ЗАКЛЮЧЕНИЕ
При подготовке данной работы была определена цель –изучить основы программирования на языке pascal и представить выжимку из этих сведений в виде обзорной курсовой работы. Реализации этой цели способствовало решение следующих задач:
Были представлены и изучены основные самодостаточные методичные данные для изучения программирования на языке pascal
Были разобраны основные синтаксические конструкции языка с теоретической и практической стороны
Были изучены основополагающие алгоритмы, необходимые для решения базовых задач по программированию
Были применены полученные знания для разработки прикладных программ
Ход решения, а также результат выполнения этих задач можно видеть в основной части этой работы. В первой главе были представлены основные синтаксические моменты языка pascal без оглядки на какую-то конкретную ide и система описанных в ней знаний может служить методическим пособием по изучению языка pascal на начальном этапе. В рамках второй главы были рассмотрены основополагающие алгоритмы, необходимые для комфортного решения прикладных задач, описанные там алгоритмы также могут служить методическим пособием для людей, которые только начали изучать данный язык. Наконец в третьей главе были использованы эти знания на практике, результатом стало не только подтверждение самодостаточности этих методов для решения огромного комплекса прикладных задач, но создание независимых программ, которые, при дальнейшем изучении языка, могут понадобиться для реализации более крупных проектов.
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ
- Фаронов В. В. Турбо Паскаль 7.0. Начальный курс. Учебное пособие. – М.: Издательство «ОМД Групп», 2003. – 616с.
- Алексеев Е. Р., Чеснокова О. В. Free Pascal и Lazarus: Учебник по программированию. – М.: ALT Linux, ДМК-пресс, 2010. – 442с.
- Потапахин В. В. Turbo Pascal: решение сложных задач. – СПб.: БХВ-Петербург, 2006. – 208с.
- Федоренко Ю. Алгоритмы и программы на Turbo Pascal. Учебный курс. – СПб.: Питер, 2001. – 240с.
- Павловская Т. А. Паскаль. Программирование на языке высокого уровня: Учебник для вузов. – СПб.: Питер, 2010. – 464с.
- Культин Н. Turbo Pascal в задачах и примерах. – СПб.: БХВ-Петербург, 2006. – 259с.
- Шпак Ю. А. Turbo Pascal 7.0. на примерах. – К.: Издательство «ЮНИОР», 2003. – 498с.
- Черкасов М. А. Практический курс программирования на Паскале. – М: МАИ, 2005. – 186с.
- Семакин И. Г., Шестаков А. П. Основы программирования: Учебник. –М.: Мастерство, 2002. – 432с.
- Суркова Е. В. Лабораторный практикум по программированию на языке Pascal. Задания и примеры. – Ульяновск.: УлГТУ, 2007. – 56с.
- Проектирование системы защиты видеонаблюдения в ООО "Хост"
- Рынок ценных бумаг ( Основные понятия, виды и классификации рынка ценных бумаг )
- Ипотека в гражданском праве ( Институт ипотеки в римском праве )
- Оценка эффективности управления персоналом
- Функции менеджмента (Понятие функций менеджмента)
- Прибыль и рентабельность производственной организации, на пример реально существующей организации ( Сущность и значение прибыли )
- Бухгалтерский учет, анализ и аудит. Финансы акционерных обществ.
- История развития программирования в России (Общие теоретическо-исторические особенности развития программирования, как прикладной дисциплины)
- Спортивные команды. Спортивные сборные команды и особенности их правового статуса
- Жизненный цикл организации и управление организацией
- Организация и разработка бизнес-плана в организации
- Вариант 21. Модель клиент-сервер