48564

ОСНОВЫ АЛГОРИТМИЗАЦИИ

Книга

Информатика, кибернетика и программирование

ОСНОВЫ АЛГОРИТМИЗАЦИИ Понятие алгоритма Основы алгоритмического языка Паскаль

Русский

2013-12-12

825 KB

10 чел.

93


Х

А

выход

АЛГОРИТМ

вход

(1+1/x)/(1+a),

C [m , n].

значение

МП

отличие

a 

окно

C

задано,

C

С

f

C

x

C0    

C0+d0    

C0-d0    

f (x)

Ci =

Ci =

C0

M1

M0

y

x

f (x)

C2

C1

C3

Рис.1.4 – Метод хорд

a

b

C0

C1

A

B

f (x)

y

x

f (x)

C0-d

C0+d

C0

X

тело

процедуры

n

2

1

m

2

1

столбцы

строки

Претендент

Эталон

<=

<

>

>

·

·

·

·

·

i+h

i

i+2h

 1·  2· 3·  4·  5· 6·  7·  8· 9· 10· 11·  12·   13· 14·

H:= (H-1) DIV 2 – работает не для всех Н. Можем перескочить через 1. (Н=2, Н-1=1, (Н-1) DIV 2 = 0.

9

Z

·

> опорного

< опорного

Z

·

25

N/2

N/2

1 при n=0,

n*(n-1)! при n>0.

1

2

3

A

B

C

A – откуда

В - куда

0

0

1

1

2

1

2

3

4

1

0

2

1

3

5

x

3 

fk 

fi 

x 

3 

f2 

f1 

окно

~ 

3 

fk 

fi 

x 

3 

f2 

f1 

окно

fk 

3 

f2 

f1 

окно

x

fk 

3 

f2 

f1 

окно

fk 

3 

f2 

f1 

окно

окно

f3 

f2 

f1 

g 

3 

c 

d 

окно

a 

g 

3 

c 

d 

# 

окно

d 

f 

b 

c 

d 

e 

#

 

окно

d 

f 

b 

c 

d 

e 

# 

 

 

Рис.3.1 – Определение глубины рекурсии

f

C

i

=

-

³

 

)

)

,

-

1

1

-

1

-

i

i

i

i

-

0

 

(

'

(

1

СОДЕРЖАНИЕ

[1]
ВВЕДЕНИЕ

[2]
1. ОСНОВЫ АЛГОРИТМИЗАЦИИ

[2.1] 1.1. Понятие алгоритма

[2.2] 1.2. Элементы структурного программирования

[2.3] 1.3. Основы алгоритмического языка Паскаль

[2.3.1] 1.3.1. Допустимые символы (алфавит)

[2.3.2] 1.3.2. Объекты программы на Паскале

[2.3.3] 1.3.3. Запись алгоритмов на Паскале

[2.4] 1.4. Рекуррентные алгоритмы

[2.5] 1.5. Алгоритмы нахождения корней функции

[2.6] 1.6. Проверка правильности алгоритмов

[2.7] 1.7. Процедуры и функции

[2.8] 1.8. Массивы

[2.9] Контрольные вопросы и задания

[3] 2. АЛГОРИТМЫ ИНФОРМАЦИОННОГО ПОИСКА

[4] И СОРТИРОВКИ

[4.1] 2.1. Задача поиска и ее разновидности

[4.2] 2.2. Задача сортировки

[4.2.1] 2.2.1. Основные понятия

[4.2.2] 2.2.2. Особенности сортировки массивов. Простые

[4.2.3]                      методы сортировки массивов

[4.2.3.1] Таблица 2.1 – Числовой массив. Все элементы различны

[4.2.3.2] Таблица 2.2 – Числовой массив. Есть повторяющиеся элементы

[4.2.3.3] Таблица 2.3 – Массив строк. Упорядочение по алфавиту

[4.2.3.4] Таблица 2.4 – Пример сортировки простым выбором

[4.2.3.5] Таблица 2.5 – Пример сортировки простым обменом

[4.2.3.6] Таблица 2.6 – Пример сортировки простыми вставками

[4.2.4] 2.2.3. Алгоритм Шелла

[4.2.4.1] Таблица 2.7 – Пример сортировки методом Шелла

[4.2.5] 2.2.4. Алгоритм Хоара

[4.3] Контрольные вопросы и задания

[5] 3. Рекурсивные алгоритмы

[5.1] 3.1. Понятие рекурсии

[5.2] 3.2. Примеры рекурсивных алгоритмов. Прямая

[5.3]             и косвенная рекурсии

[5.4] 3.3. Преимущества и недостатки рекурсивного

[5.5]             описания алгоритма

[5.6] Контрольные вопросы и задания

[6] 4. Обработка нечисловых массивов

[6.1] 4.1. Упорядочение символьных данных

[6.2] 4.2. Строковый тип данных в Паскале

[6.3] 4.3. Перекодировка символов

[6.4] Контрольные вопросы и задания

[7] 5. Работа с нестандартными

[8] и структурированными данными

[8.1] 5.1. Записи. Перечислимый и интервальный типы

[8.2]       данных

[8.3] 5.2. Множества

[8.4] 5.3. Файловые типы данных

[8.4.1] 5.3.1. Определения

[8.4.2] 5.3.2. Общие процедуры и функции

[8.4.3] 5.3.3. Текстовые файлы

[8.4.4] 5.3.4. Стандартные текстовые файлы

[8.5] Контрольные вопросы и задания

[9] Список литературы


ВВЕДЕНИЕ

Под программированием в настоящее время понимается теория и практика создания программ для ЭВМ. Появившись всего около 50 лет назад, ЭВМ проникают весьма активно во все стороны жизни человечества – от управления космическими кораблями и целыми отраслями промышленности до настольных игр.

Сам принцип программного управления открыл еще в 1823 г. профессор Кембриджского университета Ч. Бэббидж в проекте своей Аналитической машины, а первым программистом была дочь Байрона, леди Лавлейс. Однако впервые ЭВМ с хранимой в памяти программой появилась в 1949 г. в Англии (машина EDSAC), затем  в США, в СССР (МЭСМ) – в 1952 г.

Созданию универсальных ЭВМ предшествовали изобретения  в области  механических счетных устройств, начиная с Паскаля (1645 г.) и Лейбница (1694 г.); открытия в математике: двоичная арифметика Лейбница, математическая логика Джорджа Буля (1847 г.), теория алгоритмов (сложилась к 40-м годам 20-го века). Кроме того, появление ЭВМ было бы невозможно и без развития средств электросвязи, радиотехники и электротехники.

За время существования профессии программиста сущность его труда изменилась коренным образом. В 50-х годах программы писали в командах ЭВМ (в машинных кодах”). При этом вся информация переводилась в двоичную систему счисления. Это очень тяжелый и напряженный труд, требующий от человека особой аккуратности. Облегченно вздохнули программисты при появлении в 1956 г. специального языка для решения вычислительных задач. Это был FORTRAN (Formula Translator). С тех пор были разработаны другие, более совершенные языки, или специализированные применительно к какой-то конкретной области: КОБОЛ, АЛГОЛ, ПЛ/1, ЛИСП, СИМУЛА, ПАСКАЛЬ, СИ, АДА, ПРОЛОГ и др.

Неузнаваемо изменилась и вычислительная техника: от первых ЭВМ на радиолампах, затем – на транзисторах, до современных машин на интегральных схемах. Уже выпускаются ЭВМ на одном кристалле кремния 6х6 мм, схема которых эквивалентна сотням тысяч радиодеталей.

Меняется в последние годы и методика обучения программированию. Если раньше основное внимание уделялось изучению систем команд ЭВМ, то сейчас главным  становится освоение наиболее прогрессивных методов разработки алгоритмов решения задач и их проверки на ЭВМ. Наиболее перспективной является методология (технология) структурного программирования.


1. ОСНОВЫ АЛГОРИТМИЗАЦИИ

1.1. Понятие алгоритма

Очевидно, знания, полученные при изучении курса Информатика в школе, позволяют ответить на вопрос: Что такое алгоритм?

Понятие алгоритма является одним из основных понятий современной математики. Слово происходит от имени узбекского математика IX в. Мухаммеда из Хорезма (по-арабски – “Аль-Хорезми”). Его работы по арифметике и алгебре были переведены на латинский язык в XII в. и оказали большое влияние на развитие математики в Европе. Сформулированные им правила выполнения четырех арифметических действий получили название “алгоризм”, которое впоследствии трансформировалось в “алгоритмус”, затем в “алгорифм” и “алгоритм”. Однако еще раньше Евклид открыл правило нахождения наибольшего общего делителя (НОД) двух целых чисел, явившееся первым алгоритмом.

Интуитивное понятие алгоритма, которым люди пользуются уже много лет (но есть еще и строгое), можно выразить следующим образом:

алгоритм – это заданная определенным образом последовательность действий, приводящая за конечное число шагов к достижению поставленной цели (к решению поставленной задачи).

Здесь мы ввели понятие действия. В дальнейшем будем считать тождественными понятия

действие ≡ инструкция ≡ оператор.

Действия (инструкции, операторы) выполняются некоторым исполнителем. Для нас

исполнитель ≡ процессор.

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

  1.  действия должны быть понятны исполнителю;
  2.  разные исполнители должны одинаково понимать одни и те же  действия.

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

Алгоритм перехода улицы со светофором:

        1) ждать, пока не загорится зеленый свет;

        2) перейти половину улицы и при этом смотреть налево;

  1.  перейти вторую половину улицы и при этом смотреть направо.

Алгоритм не очень точен. Очевидно, п.п. 2) и 3) содержат еще и подразумеваемые действия на случай, если вдруг появится машина. Следовательно, алгоритм будет по-разному выполняться разными исполнителями.

Богатым сборником алгоритмов является кулинарная книга. Например, следующий алгоритм.

Как варить кашу:

        1)  поставить на огонь воду;

   2)  ждать, пока не закипит;

        3)  посолить;

   4)  насыпать крупу;

        5)  ждать, пока не закипит;

   6)  убавить огонь;

  1.  ждать 20 минут.

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

Один и тот же алгоритм может быть записан несколькими способами. В практике программирования распространены:

  •  словесная запись на естественном языке;
  •  схемы алгоритмов, блок-диаграммы;
  •  решающие таблицы;
  •  алгоритмические языки (формальные языки).

Первый, второй и третий способы предназначены для человека, последний – для исполнителя-машины. Такая  запись называется программой.

В последнее время все большее распространение получает еще один способ записи алгоритмов – псевдокод. Это удобный язык, промежуточный между естественным и алгоритмическим языками. Он позволяет программисту пользоваться как конструкциями алгоритмического языка, так и произвольными словесными и формульными конструкциями там, где сразу сложно воспользоваться алгоритмическим языком.

1.2. Элементы структурного программирования

В 1965 г. итальянские ученые Бом и Джакопини выполнили ряд работ, определяющих количество и характер действий, которыми следует пользоваться при записи произвольных алгоритмов. Одновременно  с ними профессор Эйндховенского университета (Нидерланды)   Э. Дейкстра начал пропагандировать новый стиль программирования, который постепенно утвердился во всем мире и получил название структурного программирования. Это не язык, а стиль, его основные принципы состоят в том, чтобы пользоваться при записи алгоритмов (программ) ограниченным набором конструкций. Эти конструкции называются базовыми управляющими конструкциями структурного программирования.

Рассмотрим эти конструкции на примерах алгоритмов для вычислений по формулам.

Пример 1. Х = А2-1.      вход – А,

         выход – Х

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

  1.  Задать значение для А.
  2.  Умножить А на А, запомнить результат.
  3.  Из результата п.2 вычесть 1, запомнить результат в переменной Х.

Здесь у нас появилось важное действие – запоминание. Будем называть его присваиванием. Это фундаментальное понятие. Оно связано с понятием память. Любой исполнитель имеет память: человек – лист бумаги или клетки головного мозга, ЭВМ – ячейки памяти.

  Чтобы различать разные значения, их располагают в разных участках памяти. Под переменные значения отводится свободное место в памяти. Следовательно, можно сказать:Результат присвоить переменной Х.

Этот пример определяет нам первую базовую конструкцию структурного программирования – следование: если в записи алгоритма друг за другом написаны несколько действий, то они будут выполняться последовательно.

Последовательный алгоритм – такой, в котором действия выполняются в том порядке, в каком они написаны (в естественном порядке).

Однако такой последовательности не всегда достаточно для выполнения алгоритма. Рассмотрим следующий пример.

Пример 2.

  0, x ≤ 0 вход  - x,

 f =   выход – f.

 x2, x > 0

Записать алгоритм вычисления f можно следующим образом.

  1.  Задать значение х.
  2.  Если х ≤ 0

то  2.1. задать f = 0

иначе  2.2. задать f = x * x.

Получили новую конструкцию, которая задает разветвление в порядке выполнения действий. Такая конструкция называется условной (соответственно алгоритм – условным) или конструкцией ЕСЛИ – ТО – ИНАЧЕ, по-английски IF – THEN – ELSE. Запись в общем виде:

ЕСЛИ условие

ТО последовательность действий 1

ИНАЧЕ последовательность действий 2.

Упрощенная или усеченная форма:

ЕСЛИ условие

ТО последовательность действий.

Пример 3. Подсчитать сумму нечетных чисел от 1 до 25.

вход – пустой,

выход – S.

Алгоритм вычисления S .

  1.  Задать S равным 0.
  2.  Задать n равным 0.
  3.  Пока n ≤ 12 выполнять

3.1.  к S добавить 2*n + 1

3.2.  увеличить n на 1

Алгоритм будет работать до тех пор, пока выполняется условие п.3.

Здесь мы получили третью базовую конструкцию – циклическую. Она означает следующее: пока истинно некоторое условие, – делай то-то и то-то.  Называется она конструкцией ПОКА – ДЕЛАЙ, по-английски WHILE – DO. Соответствующий алгоритм называется циклическим алгоритмом.  Он задает многократное выполнение одних  и тех же действий. Запись в общем виде:

ПОКА условие ВЫПОЛНИТЬ

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

Последовательность может выполняться 0,1,…,∞ раз.

Этих трех конструкций (трех типов алгоритмов) достаточно для написания алгоритмов любой сложности.

С появлением ЭВМ появилась возможность реализовывать алгоритмы очень больших размеров. В этих случаях прибегают к такому приему: вначале записывают алгоритм не с помощью простейших действий, а более крупными блоками, а затем каждый из блоков постепенно расписывают на более мелкие, доходя в конце концов до элементарных действий. Такой метод называется методом пошаговой детализации.

Блочная структура программы – тоже принцип структурного программирования.

Рассмотрим алгоритм еще с одной точки зрения. Если не вдаваться в его структуру, то любой алгоритм можно представить в виде черного ящика:

Вход – совокупность переменных и их значений, которые используются алгоритмом для вычислений.

Выход – совокупность переменных и значений, которые получены после вычислений.

Укажем входы и выходы наших примеров (см.с. 8,9).

Таким образом, для записи алгоритма можно использовать словесную форму, например, на русском языке, что мы и делали. Однако для записи алгоритма естественный язык приспособлен плохо: он неоднозначен и длинен. Кроме того, алгоритм должен выполняться не только человеком, но и машиной, которая не способна вдуматься в смысл написанного, но, следуя формально записанным на специальном языке указаниям, способна выполнить алгоритм абсолютно точно. Поэтому и разрабатывают специальные формальные алгоритмические языки.

Правила, описывающие алгоритмический язык, распадаются на две части: семантику и синтаксис.

Семантика – смысловая часть описания языка. Она определяет, как понимать (человеку) и выполнять (машине) алгоритмы.

Синтаксис – набор формальных правил написания алгоритмов на алгоритмическом языке.

1.3. Основы алгоритмического языка Паскаль

Рассмотрим только самые основы языка Паскаль, т.к. литература, описывающая его детали, вполне доступна. Язык назван в честь Блеза Паскаля, известного французского философа, математика и физика. Разработан профессором Института Информатики Швейцарской высшей политехнической школы Никлаусом Виртом. Первое сообщение  о нем поступило в 1971 г. Окончательный стандарт – в 1979 г. Паскаль  современный язык, он содержит все базовые конструкции структурного программирования. Язык прост и очень удобен для обучения программистов. Вместе с тем он обладает большими возможностями при обработке данных разных типов.

Все формальные языки, в том числе и Паскаль, должны быть организованы так, чтобы программу, записанную на данном языке, можно было легко ввести в машину (например, с клавиатуры) и вывести (например, на экран дисплея). Поэтому набор знаков каждого языка всегда ограничен в силу ограниченности клавиатуры.

1.3.1. Допустимые символы (алфавит)

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

Цифры – только арабские.

Знаки арифметических операций: +, -, *, /. Дополнительными являются две операции для целых данных (операндов):

DIV – деление нацело с отбрасыванием остатка (нахождение целой части результата);

MOD – нахождение остатка от деления.

 Знаки логических отношений и логических операций: <, <=, =, <>, >=, >, AND, OR, NOT.

Специальные символы: (  ) [  ]  .  :  ,  ;  ..      и т.д.

При записи алгоритма следует помнить правило: вся программа есть одна длинная строка. Разбиение ее на части необходимо лишь для нашего удобства. Многоэтажные формулы или переменные с индексами должны быть записаны в одну строку:

Это ограничение также связано с тем, что машина может читать только последовательность знаков.

1.3.2. Объекты программы на Паскале

Любой алгоритм оперирует некоторыми объектами (например, числами, переменными). Переменная обозначается  идентификатором – это ее имя.

Правила записи идентификатора: он начинается с буквы и содержит одну букву или несколько букв и цифр: X, A1B28, ELENA.

В Паскале длина идентификатора не ограничивается, но при этом значимыми являются первые 63 символа.

В ходе вычислений переменная изменяет свое значение. Поэтому можно дать следующее определение переменной.

Переменная – это такой объект, который имеет постоянное имя и переменное значение.

Константа  имеет постоянное значение и тем отличается от переменной. Она может быть просто числом (и не только), а может иметь имя.

Любой объект характеризуется еще и типом. Тип – это тот или иной класс (вид) значений. Тип определяет, каким значением может обладать объект, и какие операции могут быть произведены над ним.

В Паскале определены следующие стандартные типы объектов.

  1.  Целый.                                      для  численных
  2.  Вещественный.   (арифметических) объектов
  3.  Логический.
  4.  Литерный (символьный).

Есть и нестандартные типы, но о них скажем позднее.

Целый (INTEGER) – применим для объектов, принимающих только целые значения: 0, 13, +193, –100. Над переменными целого типа определены все арифметические операции. Они принимают всегда точное значение в интервале [-32768, 32767].

Вещественный (REAL) – это приближенные действительные значения, причем точность приближения зависит от конкретного устройства, на котором производятся вычисления по данному алгоритму. Любое число записывается с определенной точностью. Например, для логарифмической линейки точность представления чисел – 3 верных десятичных знака, для карманного микрокалькулятора – 6 знаков, для ЭВМ – 9 или даже 16 знаков. Переменная может получить значение в результате вычисления некоторого выражения. При этом значение выражения 0.1*10 может быть равно 0.999999999999 или 1.000000000001. (Поэтому не имеет смысла проверять вещественные данные на равенство). Итак, вещественные объекты предназначены для приближенной записи значений, например,

10.25    -0.25    0.5825    58.25E-02  (58.25*10-2).

Диапазон представления вещественных чисел 1075. Над вещественными объектами выполняются все стандартные операции: +, -, *, /.

Логический (BOOLEAN) – это объекты, которые могут принимать значения истина (TRUE) или ложь (FALSE). Логические значения могут получаться как результат операций сравнения (отношений) над целыми и вещественными (=, <>, <, >, …). Над логическими объектами определены специальные логические операции: AND (логическое умножение), OR (логическое сложение), NOT (логическое отрицание).

Литерный или символьный (CHAR) – это сокращение от  CHARACTER (символ, литера). Значениями объектов этого типа являются все символы алфавита Паскаля, взятые в апострофы: ‘A’, ‘1’, ‘+’, ‘”’ (апостроф удваивается), ‘ ‘  (пробел).

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

VAR  R1, R2, R3: INTEGER;

 X1, X2, Y1: REAL;

 EQUAL: BOOLEAN;

 WORD1: CHAR;

CONST N = 100;  (может быть описана и константа, если у нее есть имя)

VAR – служебное слово (от variable переменная).

1.3.3. Запись алгоритмов на Паскале

Действия, необходимые для выполнения алгоритма, осуществляются в алгоритмическом языке инструкциями – операторами.

Рассмотрим основные операторы языка Паскаль.

Присваивание

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

Х := А + 1 / (1 – А);

Х := Х – 1; здесь, в отличие от алгебраического уравнения, Х уменьшается на 1. Присваивание означает занесение требуемого значения в место памяти (МП), выделенное для переменной X.

Общий вид (формат) оператора присваивания:

<идентификатор переменной> := <выражение (формула)>

Формула (выражение) состоит из переменных, констант, знаков операций. Основное правило – формула должна быть линейна. При записи выражения может использоваться вызов процедуры. В математике известно понятие функции. Процедура – обобщение этого понятия, предполагающее, что некоторая совокупность значений вычисляется в зависимости от каких-либо аргументов: sin(x), cos(x) и т. д. Процедуры для вычисления таких функций, как правило, предусмотрены в алгоритмическом языке, они считаются заданными. Вызов такой процедуры есть запись идентификатора процедуры и ее аргументов. Для вычисления значения можно записать

X := SIN (A), а также использовать любую из стандартных функций:     COS (X), LN (X), SQRT (X),  EXP (X), ABS (X) и т.д. При этом

 

F := (1 – SQRT(X)) / (SIN (2 * X) – COS (X / 2)).

В разных языках возможны различные обозначения одних и тех же функций.

Вопрос о согласовании типов в выражении рассмотрите самостоятельно.

Условный оператор

Предназначен для записи условного (разветвляющего) алгоритма. Он полностью совпадает с базовой конструкцией структурного программирования. Общий вид оператора:

IF <условие> THEN <действие 1>

  ELSE  <действие 2>  может отсутствовать.

Оператор цикла

Предназначен для записи циклического алгоритма. Он также совпадает с соответствующей базовой конструкцией. Общий вид оператора:

WHILE  <условие> DO <действие>

Скажем несколько слов  о записи условий: 0 ≤ Х ≤ 1 на Паскале записать нельзя. Нужно применять логические связки(операции): AND, OR, NOT, например,

 (0 <= X) AND (X <= 1),

 X >= 0.

Для разделения последовательно идущих операторов в Паскале используется знак ;.

Если некоторую последовательность действий нужно рассматривать как одно действие, используются так называемые операторные скобки:

 BEGIN последовательность операторов END

 (начало)                                                  (конец)

Алгоритм, записанный в форме, пригодной для выполнения ЭВМ, называется программой.

                  Программа на Паскале (общая структура)

PROGRAM <идентификатор> (INPUT, OUTPUT);{INPUT, OUTPUT  имена стандартных файлов ввода и вывода. В современных версиях языка Паскаль их указание необязательно}

{Раздел описаний:}

VAR X, Y, Z: REAL; I, J: INTEGER;

{Может быть несколько групп повторений описаний типа.}

BEGIN

……………….. тело программы

……………….. (операторы)

END.

               Ввод данных и вывод результатов

Для этих целей в языке есть специальные операторы. Правильнее говорить – процедуры ввода-вывода.

Ввод осуществляется с помощью процедуры ввода, обращение к которой имеет вид:

 READ (<список переменных (ввода)>);

Список ввода состоит из имен вводимых переменных, разделенных запятыми. Например, в программе встретилось выражение READ (x).    При этом происходит обращение к клавиатуре. Программа ждет, пока на клавиатуре не будет набрано значение переменной х, которое мы хотим ввести. Выполнение оператора ввода имеет смысл присваивания переменным тех значений, которые вводятся с клавиатуры.

 READ (x);   x :=2.5;

Отличие состоит в том, что задание переменной значения с помощью оператора ввода более универсально. Оператор ввода позволяет программе общаться с внешним миром.

Как записывать значения на экране?

        INTEGER и REAL. Это должны быть допустимые константы соответствующего типа. Они отделяются друг от друга по крайней мере одним пробелом.

целые

-

5

5

1

2

вещественные

-

5

.

0

1

.

5

1

Е

-

1

0

-

2

.

3

Е

5

        CHAR. Данные этого типа записываются без апострофов и без пробелов.

VAR C, D: CHAR;

 READ (C, D);   C := ‘A’;

      D := ‘+’;

A

+

Вывод данных осуществляется с помощью процедуры вывода, обращение к которой имеет вид:

 WRITE (<список значений>);

Список вывода содержит имена переменных, выражения и константы. Например, WRITE (X, 29);

Значения из списка последовательно выводятся на экран дисплея или на принтер (печатающее устройство).

Вывод – другое средство общения программы с внешним миром.

В Паскале разрешена печать арифметических и символьных (литерных) данных, причем выражением для вывода может быть строка литер, заключенная в апострофы. При печати апострофов не будет.

Пример.

 PROGRAM P (INPUT, OUTPUT);

VAR A, B, X: REAL;

BEGIN

 WRITE (‘Введи A’);

 READ (A);

 WRITE (‘Введи B’);

 READ (B);

 X := A*B-A;

 WRITE (‘X=’,X);

END.

Значения выводятся в той форме, в какой они описаны, например,

- 2.300000Е+05 - для вещественных чисел.

Для удобства чтения можно указать формат выводимых данных:

 WRITE (X:2);  - для целых,

 WRITE (Y:10:2);           - для вещественных (10 – общее количество цифр, 2 – количество цифр в дробной части).

Все выводимые данные печатаются в одну строку. Если нужно перейти на следующую строку до окончания предыдущей, пользуются оператором WRITELN, общий вид которого

WRITELN (<список вывода>);

Оператор осуществляет переход к новой строке после печати значений списка.

1.4. Рекуррентные алгоритмы

Известно, что далеко не все математические задачи имеют точное аналитическое решение. Гораздо большее число задач можно решить приближенно с помощью численных алгоритмов. Численными называют алгоритмы, оперирующие приближенными числами (то есть объектами типа REAL).

Большое количество численных алгоритмов основано на рекуррентных последовательностях (то есть связано с вычислением рекуррентных последовательностей).

Рекуррентная последовательность – это такая бесконечная числовая последовательность x0, x1, …, xn, … , что

 xi = f (i, xi-1, xi-2, … , xi-p) для i p

x0 = a0, задание рекуррентной 

x1 = a1, последовательности

…… ,

xp-1 = ap-1

Например, если p = 1, то получим последовательность

 xi = f (i, xi-1),  i ≥ 1,

x0 = a0.

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

       Задача 1. Вычисление N-го элемента последовательности.

Для простоты рассмотрим случай, когда p = 1.

N – номер элемента (должен быть задан).

I – номер очередного элемента.

I, N – целые.

Схема алгоритма будет следующая:

X := A0;

I := 1;

WHILE I<=N DO

 BEGIN

 X := f (I, X);

 I := I + 1;

 END;

Чтобы дойти до N-го элемента, цикл проработает N раз.


Задача 2. Вычисление суммы конечного числа элементов рекуррентной последовательности:

Процесс вычисления суммы можно представить как процесс нахождения члена SN рекуррентной последовательности:

S0 = 0;

Si = Si-1 + xi = f1(i, Si-1 ),  1 ≤ i ≤ N

Тогда получим следующий алгоритм.

S := 0;

I := 1;

X := a0;

WHILE I <= N DO

 BEGIN

 S := S + X;

 X := f (I, X);

 I := I + 1;

 END;

Если мы знаем, сколько раз должен проработать цикл, можно использовать другой оператор цикла: FOR. Его общая запись:

FOR I := <начальное значение> TO <конечное значение> DO (с шагом 1) или

FOR I := < конечное значение > DOWNTO < начальное значение > DO (с шагом -1).

Задача 3. Вычисление бесконечных сумм:

Задача вычисления бесконечной суммы имеет смысл, когда эта сумма сходится к некоторому конечному значению. Так, например,

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

Такое представление функции называется её разложением в ряд.

Любое вещественное число можно представить с помощью конечного числа цифр, то есть всегда приближенно. Следовательно, и бесконечную сумму можно вычислить только приближенно, с заданной точностью. Ограничимся конечным числом элементов суммы. Для нахождения критерия окончания вычислительного процесса используем тот факт, что при увеличении номера i эти элементы убывают по абсолютной величине. Поэтому одним из распространенных критериев является следующий: включать в сумму только те члены последовательности, которые по модулю больше или равны некоторой наперед заданной величине ε.

Тогда

, где N – таково,

что  

Таким образом, сумма всех отброшенных элементов будет либо меньше, либо ненамного больше ε.

Часто в таких суммах можно последующий элемент вычислить с помощью предыдущего. Тогда нужно выразить (i+1)-й через i-й или i-й через       (i-1)-й, а не считать непосредственно каждый элемент.

Пример для еt.

 

то есть        формула пересчета.

Тогда алгоритм запишется следующим образом.

S := 1; I := 1; T:=1; x:=1;

WHILE  ABS (x) >= Eps   DO

BEGIN

  x := x * T / I;

  S := S + x;

  I := I + 1;

END;

Подумайте над следующим вопросом. Почему для вычисления бесконечных сумм нельзя использовать цикл типа FOR?

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

1.5. Алгоритмы нахождения корней функции

Корнем функции f(x) является решение уравнения f (x) = 0. На практике в редких случаях можно записать в явном виде x как некоторую функцию g от коэффициентов  уравнения.

Однако почти всегда мы можем решить задачу приближенно, численными методами. Это можно сделать практически для любой функции. Предположим, что приближенное значение корня известно. Это точка С0 (рис.1.1).

Рис. 1.1– Численное нахождение корня функции

Задача численного нахождения корня состоит в том, чтобы из данной точки С0 найти более точное   значение  Cn,   построив  определенным   образом последовательность шагов. При этом мы должны быть уверены, что точное значение корня будет лежать в области Cn±d ( значение d известно). Если d достаточно мало, то точность можно считать удовлетворительной. Рассмотрим наиболее распространенные методы нахождения корней функции.

            Метод дихотомии (деления отрезка пополам)

Для реализации метода кроме начального приближения C0 должна быть задана величина d0 такая, что в отрезок [C0-d0, C0+d0] корень попадает заведомо (рис.1.2).

Рис.1.2 – Метод дихотомии

Все более точное значение корня мы будем получать, вычисляя элементы рекуррентных последовательностей:

С0, С1, …, Сi, …

d0, d1, …, di, …

Критерием перехода к новой точке является результат анализа: пересекает ли график функции f (x) ось абсцисс левее или правее предыдущей точки.

И тогда

если правее;

если левее.

Чтобы выяснить это обстоятельство, вычислим f (C0) и f (C0+d0), а потом сравним их знаки. Если эти знаки одинаковы, то график проходит через ось Х левее точки C0, если разные, то между C0 и C0+d0.

Формально проверку можно провести следующим образом:

f (C0)*f (C0+d) > 0   знаки одинаковые,

f (C0)*f (C0+d) < 0   знаки разные,

f (C0)*f (C0+d) = 0   корень найден (случай редкий, рассматривать

                                              не будем).

Тогда рекуррентные последовательности для Ci и di:

если  f (ai-1)*f (ai-1 + di-1) < 0 ;

иначе;

где С0, d0заданы.

Один из критериев окончания вычислительного процесса состоит в  следующем. Нужно задать некоторое малое число ε и считать корень найденным, когда абсолютная величина di станет меньше ε. Таким образом, число ε – заданная точность нахождения корня с помощью нашего приближенного метода. Возможны другие критерии.

Алгоритм нахождения корней методом дихотомии.

READ (C, D, EPS);

A:=F (C); B:=F(C+D);

WHILE D>=EPS DO

BEGIN

  D:=D/2;

  IF A*B<0 THEN C:=C+D;

  ELSE BEGIN

 C:=C-D;

 B:=A;

 END;

  A:=F(C);

END;

Если функция имеет несколько корней, то есть на отрезке 2d график несколько раз пересекает ось Х, то метод позволяет найти один корень. Метод работает довольно медленно, но сходится всегда.

                   Метод Ньютона (метод касательных)

Для работы метода не обязательно задавать отрезок, содержащий корень уравнения f(x)=0. Достаточно знать лишь начальное приближение корня x=C0. Иллюстрация работы метода приведена на рис.1.3.

Рис.1.3 – Метод касательных

Проводим касательную к кривой y = f (x) в т. М0 и находим точку её пересечения с осью Х. Это и будет новое приближение х=С1. В точке М1 снова проводим касательную к f (x) и т.д. 

Уравнение касательной, проведенной к кривой y=f (x) в т. М0(C0, f(C0)):

y – f (C0) = f ′ (C0)(x-C0), откуда

y = f (C0)+f′(C0)(x-C0).

  Полагаем y=0 и находим x=C1:

Аналогично находим С2 и т.д.

Таким образом, рекуррентная последовательность для С будет иметь вид:

       

Метод касательных хорошо работает для достаточно гладких функций. Для окончания итерационного процесса можно использовать условие  или . Алгоритм, реализующий данный метод, запишите самостоятельно.

       

             Метод хорд (линейной интерполяции)

Пусть нам известно, что корень находится внутри отрезка [a, b] (рис.1.4). Вычисляем значения f(a), f(b) и проводим прямую, соединяющую точки A и B (хорду). Точка С0,  в которой прямая AB пересекается с осью Х, есть начальное приближение к корню. Сравниваем знаки f(C0) и f(b). 

Если они одинаковы, то переходим к отрезку [a, C0], иначе к [C0, b]. Для нового отрезка проделываем то же самое, находя в результате точку С1, и т.д. Таким образом, на каждом

отрезке приближенно заменяем кривую f(x) отрезком прямой, с чем и связано название метода. Отрезок постепенно сужается, однако не путем деления пополам (во многих случаях – быстрее). Чтобы построить рекуррентную последовательность для Сi, нужно знать уравнение прямой AB:

.

В точке пересечения прямой с осью абсцисс значение y=0, откуда получим x=C0:

.

После нахождения границ нового отрезка вычисляем по той же формуле С1 и т.д. Алгоритм, реализующий метод хорд, напоминает алгоритм для метода дихотомии, но значения Сi вычисляются по другой формуле.

Алгоритм нахождения корней методом хорд.

Задать значение EPS;

READ (A,B); Y:=F(A);

IF Y*F(B)>0 THEN WRITELN (‘неверные данные’);

ELSE BEGIN

 FA:=Y;

 FB=F(B);

 WHILE ABS(Y)>=EPS DO

  BEGIN

  X:=A-(B-A)*FA/(FB-FA);

  Y:=F(X);

  IF Y*FB<0 THEN BEGIN

     A:=X; FA:=Y;

          END

  ELSE BEGIN

   B:=X; FB:=Y;

            END;

  END;

 WRITELN(X);

END

 

                                             Метод итераций

Для использования этого метода уравнение f(x)=0 нужно представить в виде g(x)-x=0 или

x=g(x).       (1)

Пусть известно начальное приближение корня x=C0. Подставляем это значение в правую часть уравнения (1). Получим C1=g(C0). Новое значение C1 снова подставляем в (1) и т.д. Алгоритм будет сходиться при условии, что . Рекуррентная последовательность:

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

Оценка трудоемкости алгоритмов

Мы рассмотрели несколько алгоритмов отыскания корней функции.

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

Оценим трудоемкость (по числу шагов) метода дихотомии. Критерием окончания вычислений является достижение интервалом d (то есть погрешностью вычисления корня) заданной величины. Пусть нужно уменьшить d в M раз. Возникает вопрос: сколько раз при этом должен  проработать цикл? Обозначим число выполнений цикла через N. Так как

di=di-1/2, то для M=1 N=0, для M=2 N=1, для M=4 N=2, для M=8 N=4, для M=16 N=4 и т.д. Следовательно,

M = 2N , откуда

N= log2M – округляем до ближайшего целого в большую сторону.

Таким образом оказывается, что для M=1000 N=10, а для M=1 000 000

N=20.

Можно сказать, что такой алгоритм достаточно хорош. Проработав 20 раз, он улучшит точность результата в 1 000 000 раз. Такие алгоритмы называются алгоритмами с логарифмической трудоемкостью. К ним относится метод дихотомии.

1.6. Проверка правильности алгоритмов

Цель создания любого алгоритма – выполнение некоторых вычислений. При этом требуется, чтобы алгоритм при допустимых значениях входных параметров вычислял верные значения на выходе. Как убедиться, что результат будет правильным при любых допустимых входных значениях? Вопрос о правильности алгоритмов – один из основных вопросов программирования как науки о составлении алгоритмов.

Актуальность вопроса можно проиллюстрировать на таком примере: пусть вероятность того, что алгоритм, занимающий 1 страницу текста, верен, равна 0.9 (из 10 операторов 1 неверный, для начинающих программистов правильнее было бы 9 из 10). Для алгоритма, занимающего 2 страницы – 0.92=0.81, 3 страницы – 0.93 и т.д. Для современных ЭВМ часто длина программы ≈ 100 страниц. Вероятность правильной работы при этом 0.9100=0.000027 – ничтожно мала.

Говорят, что ошибки в программах появились раньше, чем сами машины. Можно выделить три источника ошибок.

       “Описки”, то есть ошибки, появившиеся из-за невнимательности и незначительных нарушений синтаксиса языка.

       Алгоритмические ошибки. Возникают из-за неправильного понимания сути алгоритма или неправильного выражения мыслей. Это более серьезные ошибки.

       Ошибки, возникающие при работе с такими значениями данных, на которые не рассчитана программа. То есть ошибки из-за неправильных данных. Например, 20! – слишком большое число, 1/(20!) – слишком маленькое. Такие ошибки нужно предвидеть.

Методы борьбы с различными группами ошибок различны.

       Большая часть “описок” обнаруживается на этапе перевода (автоматического) нашего алгоритма в команды ЭВМ – на так называемом этапе трансляции.

Другая часть “описок”, а также некоторые алгоритмические ошибки, может быть найдена путем тестирования. Исторически первым методом проверки правильности алгоритма (программы) явилось тестирование: программа вводится в ЭВМ с заранее подобранными входными данными, и полученные результаты сравнивают с заранее известными правильными результатами (подсчитанными для этих входных данных вручную). Это – тест (проверяющая задача): алгоритм + данные + контрольный пример. Такое тестирование желательно повторить несколько раз.

Если результат совпадает с известным, это дает некоторые основания считать программу верной. Даже при хорошем тестировании  в программе могут остаться ошибки. Для того, чтобы рассеять все сомнения, нужно выполнить все возможные варианты (то есть провести расчет со всеми возможными входными данными). Например, нужно сложить два числа из 10 цифр каждое. Тогда нам придется проверить 1020 вариантов. Это практически невозможно, хотя бы по следующим причинам.

Пусть одна операция сложения выполняется за 1 мкс = 10-6 с. Тогда

         1020*10-6=1014 с,

         1014/60 ≈ 1.7*1012 мин.,

         ≈ 2.78*1010 час.,

         ≈1.16*109 суток,

         ≈3.17*107 лет = 31 700 000 лет.

На основе подобных рассуждений Э. Дейкстра (голландский профессор, классик современного программирования) сформулировал такой закон (закон Дейкстры):

тестированием можно обнаружить ошибки в программе, но никогда нельзя доказать их отсутствие.

        Чтобы убедиться в правильности программы, отсутствии в ней алгоритмических ошибок, нужно уметь проверять правильность структуры алгоритма. Такая аналитическая проверка называется верификацией алгоритма. При использовании этого метода нужно для каждого алгоритма и каждой фразы в нем абстрагироваться от индивидуальных значений переменных и сформулировать условия, которым они должны удовлетворять до и после выполнения алгоритма. Для любого алгоритма можно определить, каким условиям должны удовлетворять входные данные и результат. Это условия подобные тем, которые задаются в операторах IF и WHILE.

Условие на входе называется предусловием, на выходе – постусловием.

Задача состоит в том, чтобы доказать, что входное предусловие алгоритм за конечное число шагов переводит в постусловие.

Наиболее распространенными методами доказательства являются:

  •  перечисление (перебор вариантов) – для IF-THEN-ELSE и последовательных алгоритмов;
  •  математическая индукция – для WHILE-DO.

       Проиллюстрируем использование метода перебора вариантов на примере алгоритма дихотомии. Входные данные: C, D, EPS. (функция f – фиксирована и не относится к входным данным).

Предусловие:

(D>0) AND (EPS>0) AND (f (C-D)*f (C+D) ≤ 0).            (*)

Постусловие:

(D <= EPS) AND (EPS >0) AND (D>0) AND (f (C-D)*f (C+D) ≤ 0).       (**)

Требуется доказать, что алгоритм, имеющий на входе условие (*) на выходе получит условие (**).

Алгоритм:

WHILE D>EPS DO

BEGIN

IF f (C)*f(C+D) >0

THEN C:=C-D/2

ELSE C:=C+D/2;

D:=D/2

END;

Пусть выполняется условие

 f (C)*f (C+D) >0.                                                                                   (2)

Тогда в результате одного выполнения цикла получим новые значения Cнов и Dнов:

Cнов = C - D/2,

Dнов = D/2.

Проверим постусловие:

f (Cнов- Dнов)*f (Cнов+ Dнов) = f (C-D/2-D/2)* f (C-D/2+D/2) =

=f (C-D)*f (C)≤0 (из (*) и (1)).     (3)

Таким образом мы доказали, что внутри цикла действует предусловие

 (f (C-D)*f (C+D)≤0) AND (D>0)

и такое же постусловие. Доказательство провели методом перебора вариантов.

Выберите второй вариант условия f (C) *f (C-D) ≤0 и докажите то же самое.

Доказательство по методу математической индукции строится на переборе вариантов, зависящих от некоторого натурального числа n, где n=n0, n0+1, n0+2,…,∞.

Пусть P(n) – некоторое проверяемое условие.

Схема метода математической индукции:

  1.  непосредственной подстановкой проверяем, что P(n0)  выполняется;
  2.  предполагаем, что P верно для некоторого n=k, k≥n0;
  3.  доказываем, что из предположения п.2) следует, что P будет верно для n=k+1.

Пример.

Докажем, что вычисление по рекуррентной последовательности

f (0) = 1,

f (n) = f (n-1)*n,

где n>0, даст в результате значение f(n)=n!.   

  1.  f (0) =1  0! = 1 - выполняется.
  2.  предполагаем, что f (k) = k!
  3.  убедимся, что из п.2 следует f (k+1) = (k+1)!

Действительно, f (k+1) = f (k)*(k+1) = k!*(k+1) = (k+1)!, что и требовалось доказать.

Для циклических алгоритмов под величиной n обычно понимают количество повторений цикла. В частном случае оно может быть равно нулю.

Применим метод математической индукции к доказательству правильности алгоритма дихотомии.

       n = 0. D ≤ Eps. Цикл не работает ни разу. Сравним пред- и постусловия. Они отличаются именно на это неравенство. Непосредственной проверкой мы убедились, что при n =0 предусловие переходит в постусловие.

       Предположим, что цикл проработал k раз (n = k ≥ 0), после чего постусловие стало истинным.

       Положим n = k +1. Докажем истинность постусловия.

Так как цикл проработал на 1 раз больше k, то после k выполнений цикла еще сохранялось условие D>Eps, а часть постусловия совпадала с предусловием:

 (f (C-D)*f (C+D)≤0) AND (D>0) AND (Eps>0)   (***)

После (k+1)-го выполнения цикла условие (***) сохраняется (доказали методом перечисления). И, кроме того, так как цикл после (k+1)-го раза больше работать не будет, то должно выполниться D ≤ Eps. Таким образом получили (после k +1-го шага):

 (D ≤ Eps) AND (***) – совпадает с заданным постусловием.

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

Для доказательства правильности больших алгоритмов разбиваем их на части и для каждой части формулируем пред- и постусловия. Постусловие для одной части является предусловием для следующей. Доказываем правильность алгоритма в целом, затем отдельно для каждого внутреннего алгоритма.

       Ошибки из-за неправильных данных представляют собой совокупность таких входных данных, при которых программа неработоспособна.

Например, отрицательный интервал d в программе поиска корней функции. Или функция, которая не имеет корня (рис. 1.5).

    

Рис. 1.5 – Пример функции, не имеющей корня

Для избежания таких ошибок целесообразен следующий подход.

На входе программы делаются специальные проверки на правильность данных. Затем либо выдаётся сообщение о том, что данные неверны, либо проводятся вычисления. Схема такой проверки выглядит следующим образом.

IF  данные верны

THEN выполнить алгоритм

ELSE выдать сообщение о неправильности данных.

В этом состоит суть метода программной защиты от неправильных данных. Данные могут быть неверны и из-за ошибок при вводе. Поэтому  чем больше входных данных, тем жестче должна быть их проверка.

1.7. Процедуры и функции

Часто в программе некоторую последовательность действий приходится повторять несколько раз в разных местах программы. Чтобы программисту не приходилось тратить усилия и время на копирование этих инструкций, в каждом языке программирования высокого уровня, в том числе и в Паскале, предусмотрены средства, позволяющие выделить такие повторяющиеся куски программы в автономные алгоритмы или подпрограммы. Такое выделение позволяет, кроме того, упростить процесс проверки правильности алгоритма программы: всегда легче проверить несколько простых алгоритмов, чем один сложный.

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

Процедура – автономно выделенный алгоритм, который можно использовать как в разных местах одной программы, так и в разных программах.

Различают две разновидности процедур.

Процедуры,  вычисляющие  одно    значение.   Их   называют    процедурами-функциями или просто функциями. Стандартные (встроенные) функции присутствуют в любом языке: ABS(X), SQR(X), SQRT(X) и т.д. Имена функций используются в выражениях.

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

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

Описание процедуры (функции) состоит из заголовка и тела процедуры.

       

Функция:

FUNCTION <имя> (<список переменных и типов>): <тип>;

<описание внутренних (локальных) переменных>;

BEGIN

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

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

<имя> :=<значение>;

END;

В заголовке функции обязательно должно присутствовать служебное слово FUNCTION и после списка переменных (аргументов) – тип самой функции, то есть тип возвращаемого ею значения. Переменные в заголовке функции называются формальными параметрами (ФРП). Это аргументы функции. Локальные переменные – это те, которые нужны для организации вычислительного процесса в самой процедуре и не являются ее входами.

Пример.

FUNCTION Y (x, z : REAL):REAL;

BEGIN

Y := x * x + z * z;

END;

Как использовать функцию в программе, то есть, как вызвать функцию? Для этого нужно указать в выражении (в правой части оператора присваивания) ее имя и список переменных или значений, которые в конкретной ситуации являются аргументами функции:

A := Y (25.5, T);

B := 2*Y(C, D) / (Y (3.2, 2.7)+1);

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

Формальные и фактические параметры обязательно должны совпадать по количеству и по типу.

Входом алгоритма процедуры-функции является список параметров, выходом – вырабатываемое его значение.

       Процедура:

PROCEDURE <имя>(<список параметров и их типов>);

<описание внутренних переменных>;

BEGIN

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

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

END;

Особенность процедуры состоит в том, что как ее вход, так и выход  определяются непосредственно списком формальных параметров. Часть из них входные, часть – выходные. Запись их в списке ФРП несколько различается. Дело в том, что ФРП могут быть нескольких разновидностей:

а) параметры-значения.

Для них в списке ФРП указывается: <список имен>:<имя типа>. По окончании работы процедуры их значения утрачиваются. Поэтому для выходных переменных такой тип непригоден;

б) параметры-переменные.

Для них в списке ФРП предусмотрена конструкция:

 VAR <список имен> : <имя типа>.

К этой разновидности относятся выходные переменные;

в) параметры-функции и параметры-процедуры.

Описываются в списке следующим образом:

FUNCTION <имя> (<список имен и типов>):<имя типа>

или

 PROCEDURE <имя> (<список имен и типов>)

Пример. Процедура обмена значениями между двумя переменными.

PROCEDURE OB (VAR X,Y : REAL);

VAR Z: REAL;

BEGIN

Z:=X; X:=Y; Y:=Z;

END;

Для того чтобы использовать в программе процедуру (вызвать ее), существует так называемый оператор процедуры. Его структура: <имя процедуры> (<список ФКП>). Принципиальное отличие от вызова функции – место оператора процедуры в программе. Он записывается в последовательности инструкций как полноправный оператор, например,

A:=2.5; B:=3*(C-D/2);

OB(A, B);

После вызова переменные А и В поменяются значениями. Смысл понятий ФРП и ФКП для процедуры тот же, что и для функции.

Замечание.  Процедуры или функции могут вообще не иметь формальных параметров.

При использовании процедур или процедур-функций общая схема программы:

 PROGRAM …;

 Описания переменных

Описания процедур

 BEGIN

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

END.

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

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

Пусть нужно вычислить сумму: , (где f – некоторая функция), описав вычисления как процедуру-функцию. Описание функции:

 FUNCTION SUM (A, B : INTEGER; FUNCTION F (I :INTEGER): REAL): REAL;

VAR I :INTEGER; S: REAL;

BEGIN

 S:=0;

 FOR I:=A TO B DO

  S:=S+F(I);

 SUM:=S;

END;

Для того чтобы  использовать функцию SUM, нужно описать функцию f(i). Пусть . Тогда возможно следующее описание функции:

 FUNCTION T (I: INTEGER): REAL;

BEGIN

 T:=1/I/I

END;

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

 Z:= SUM (1, 10, T);  или

Z1:= SUM (1, N, T1); где T1 – другая функция, например Т1= .

В одной программе может быть много разных вызовов функции со своими конкретными ФКП.

В Турбо Паскале существует так называемый процедурный тип данных, который позволяет, как и в случае массива, объявить сначала тип, а в заголовке процедуры или функции определить переменную этого типа. Описание процедурного типа выглядит следующим образом.

 TYPE proc = PROCEDURE (список ФРП и типы);

 TYPE func = FUNCTION (список ФРП и типы): тип функции;

Обязательное правило: программа при использовании данных процедурного типа должна компилироваться с ключом {$F+}.

Программа для нашего примера.

PROGRAM SUMMA;

VAR W: INTEGER; Z1, Z2: REAL;

TYPE func = FUNCTION (I: INTEGER): REAL;

{$F+} {формирование дальних” адресов для подпрограмм (адрес сегмента и смещения), эквивалентно директиве FAR}                                           

FUNCTION T1 (I: INTEGER): REAL;

BEGIN

            T1:= 1/I/I

       END;

FUNCTION T2 (I: INTEGER): REAL;

BEGIN

T2:=1/I/I/I;

END;

{$F-} {формирование ближнихадресов (только смещения), эквивалентно директиве NEAR}

FUNCTION SUM (A, B: INTEGER; F: FUNC): REAL;

<Описание функции SUM (см. выше)>

{Основная программа:}

BEGIN

READLN (N);

Z1:= SUM(1, N, T1);

Z2:= SUM(1, N, T2);

WRITELN (Z1, Z2)

END.

По умолчанию используется ключ {$F-}.

Если при выполнении программы встретился оператор процедуры или указатель функции, то ЭВМ работает в следующем порядке.

По имени процедуры (функции) находится соответствующее описание в разделе описаний программы.

Производится сопоставление списка ФРП и ФКП. Должны обязательно совпадать их число и типы.

В случае совпадения выполняется тело процедуры (функции) с фактическими параметрами.

После работы тела процедуры (функции) осуществляется возврат в основную последовательность операторов программы:

- к следующему оператору после работы процедуры;

- в точку вызова – после работы функции.

1.8. Массивы

Часто в задачах бывает необходимо рассматривать не только одиночные (скалярные) объекты (константы, переменные), но некоторую совокупность элементов. Такой совокупностью является массив.

Массивпронумерованная совокупность объектов одного типа:

( х1,   х2, …, хn), где 1, 2, …, n – номера (индексы) элементов.  

       Например, точка на плоскости характеризуется двумя координатами (х1, х2) : (2.5, 5), в пространстве – тремя (х1, х2, х3): (3.1, 0, -2.3).

В n-мерном пространстве вектор (точка) имеет n координат.

Это примеры одномерных массивов. Они имеют одну степень нумерации (один индекс).

Двумерные массивы называются матрицами. В них используется двойная нумерация: по строкам и столбцам.

Можно рассматривать и массивы большей размерности.          

Пусть каждая плоскость параллелепипеда – матрица. Тогда весь параллелепипед представляет собой трехмерный массив. В памяти ЭВМ все ячейки пронумерованы. Номером ячейки является ее адрес. Поэтому можно считать ячейки памяти одномерным массивом.

       В программе массив имеет следующее описание:

VAR M: ARRAY [1..5, 1..10] OF REAL;

Переменная M представляет собой матрицу, для которой m=5,  n=10.Границы изменения индексов должны быть заданы целыми числами.

Любой элемент массива используется в программе так же, как переменная, только с указанием индекса (номера), например,

 A:= M[3, 7] - 2; M[1, 1]:=0;

Рассмотрим несколько задач, связанных с массивами.

Задача 1. Суммирование элементов массива

Рассмотрим одномерный массив А из n элементов. Для вычисляемой суммы необходимо зарезервировать некоторую переменную и перед началом вычислений занести в нее 0.

Алгоритм вычислений:

 S:= 0;

FOR I:= 1 TO N DO

 S:= S+A[I];

Методом математической индукции можно доказать, что такой алгоритм действительно вычислит сумму n элементов массива.

Задача 2. Вычисление среднего значения m массива 

 . Следовательно, нужно накопленную в задаче 1 сумму разделить на N .

Задача 3. Сформировать массив, в котором ai = i2

FOR I:=1 TO N DO

 A[I]:=I*I;

С помощью массивов решаются многие задачи линейной алгебры.

Задача 4. Найти скалярное произведение двух векторов

1, а2, …, аn), (b1, b2, …, bn)   (длина их должна быть одинакова).

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

 S:= 0;

FOR I:=1 TO N DO

 S:= S+A[I]*B[I];

Задача 5. Определение суммы векторов

Каждая компонента вектора суммы ci = ai + bi, следовательно,

FOR I:=1 TO N DO

 C[I]:=A[I]+B[I];

Задача 6. Вычисление произведения двух матриц

Пусть даны две матрицы: A:= || aij || m*p, и B:= || bij || p*n.

Их  произведение есть матрица 

C:=A*B= || Cij || m*n, где -скалярное произведение вектора-строки с номером i на вектор-столбец с номером j. Алгоритм:

FOR I:=1 TO M DO

 FOR J:=1 TO N DO

 BEGIN

  S:=0;

   FOR K:=1 TO P DO

   S:=S+A[I,K]*B[K,J]; {вычисление одного

        элемента матрицы}

   C[I,J]:=S

 END;

Контрольные вопросы и задания 

  1.  Дайте интуитивное определение понятия “алгоритм”.
  2.  Каковы основные способы записи алгоритмов?
  3.  Каковы основные принципы и конструкции структурного  программирования?
  4.  Для исполнителя, умеющего выполнять только одну операцию на каждом шаге, опишите порядок вычисления трехчлена y=x3+bx2 +c.
  5.  Приведите пример алгоритма, где использовался бы условный переход.

  1.  Составьте алгоритм вычисления значения функции f(n) по формуле

    если n<m/2,

    если n = m/2,

    если n > m/2.

  1.  Составьте алгоритм вычисления суммы четных чисел из интервала [M, N], где M и N – нечетные. Пометьте входы и выходы алгоритма.
  2.  В чем заключается метод пошаговой детализации при составлении алгоритмов?
  3.  Что представляет собой алфавит языка Паскаль?
  4.   Чем характеризуются объекты программы на Паскале?
  5.   Назовите основные операторы языка Паскаль.
  6.   Охарактеризуйте константы как объекты программы. Укажите интервалы значений.
  7.   Что представляют собой переменные как объекты программы? Дайте  определение идентификатора, приведите примеры.
  8.   Приведите примеры описаний переменных различных типов с записью значений в виде констант.
  9.   Дайте определение выражения. Приведите примеры арифметических выражений. Поясните правила записи и приоритеты операций.
  10.   Поясните смысл оператора присваивания. Приведите примеры операторов присваивания с выражениями.
  11.   Приведите примеры логических выражений. Поясните правила их вычисления.
  12.   Что представляет собой структура программы на Паскале? Приведите примеры.
  13.   Как вводить данные и выводить результаты в программе на Паскале?
  14.   Дайте определение рекуррентной последовательности. Приведите примеры.
  15.   Охарактеризуйте основные задачи, решаемые на заданной рекуррентной последовательности.
  16.   Запишите алгоритм вычисления члена рекуррентной последовательности с заданным номером.
  17.   Запишите алгоритм вычисления суммы конечного числа элементов рекуррентной последовательности.
  18.   В чем состоит смысл задачи вычисления бесконечной суммы рекуррентной последовательности? Приведите алгоритм решения этой задачи.
  19.   На чем основаны приближенные методы вычисления корней функции?
  20.   В чем суть метода дихотомии? Запишите его алгоритм операторами Паскаля.
  21.   На чем основан поиск корня функции методом касательных? Приведите алгоритм.
  22.   Поясните смысл метода линейной интерполяции и запишите его алгоритм операторами Паскаля.
  23.   Как оценить трудоемкость алгоритмов отыскания корней функции?
  24.   Каковы основные источники ошибок в программе и в чем состоят методы борьбы с ними?
  25.   Каким образом можно доказать правильность алгоритма, не прибегая к тестированию? Приведите примеры.
  26.   Дайте определение процедуры. Какие разновидности процедур существуют в языке Паскаль?
  27.   В чем состоят различия в описании и вызове процедуры и функции?
  28.   Какова связь между формальными и фактическими параметрами процедуры (функции)?
  29.   Перечислите разновидности формальных параметров, поясните их смысл и приведите примеры.
  30.   Что называют массивами данных? Приведите примеры алгоритмов обработки массивов.

        

                                

2. АЛГОРИТМЫ ИНФОРМАЦИОННОГО ПОИСКА

И СОРТИРОВКИ

Алгоритмы информационного поиска и сортировки настолько тесно связаны друг с другом, что образуют, фактически, отдельный класс алгоритмов. Класс этот особенно интересен тем, что может использоваться при решении очень многих задач. С  другой стороны, он имеет свою ярко выраженную специфику, связанную с тем, что внешне тривиальные задачи найти и упорядочить допускают разнообразные решения.

2.1. Задача поиска и ее разновидности

Задача поиска состоит в отыскании в последовательности  элемента (или нескольких элементов) с заданными свойствами его значения. Например, найти элемент с наибольшим (наименьшим) значением или найти элемент с заданным значением. Подобные задачи возникают очень часто при составлении алгоритмов разной сложности. Постоянно решаются они машинами в различных информационно-поисковых системах. Конечно, поиск там более сложен, чем в тех задачах, которые мы сейчас рассмотрим, но идея остается той же самой.

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

  1.  Найти минимальное значение элементов последовательности (все элементы разные).
  2.  Найти номер минимального элемента последовательности (все элементы разные).
  3.  Найти минимальный элемент и его номер в последовательности  с совпадающими элементами.
  4.  Найти номер элемента с заданным значением (все элементы разные).

Обозначим исследуемую последовательность x1 , x2 , x3 , …,xN   и составим алгоритмы решения каждой из предложенных задач.

  1.  Рассмотрим задачу А как задачу определения размера самого маленького яблока из лежащих в ящике, разделенном на ячейки.

Сделаем из мягкой проволоки рамку размером в любое произвольное яблоко. Таким образом, мы задались произвольным размером, который назовем эталоном. Берем следующее яблоко и пытаемся протащить его через рамку. Если оно не проходит, значит оно больше эталона. Такое яблоко нас не интересует, и мы его отбрасываем. Если же окажется, что очередное яблоко меньше эталона, то это уже претендент на наименьшее. Изменим эталон до размера этого яблока, подкрутив проволоку, и продолжим сравнение. Когда мы таким образом пропустим все яблоки через рамку, ее размер и будет размером наименьшего.

Аналогично можно найти и наибольшее яблоко, но тогда рамку нужно увеличивать каждый раз до размеров большего яблока.

Распространим эту идею на поиск минимального элемента в последовательности. Поиск будем проводить путем  сравнения всех элементов последовательности с эталонной переменной, которой присвоим значение любого элемента последовательности. (О том, какой элемент лучше выбрать для этой цели, скажем позже).

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

Запишем пошаговую разработку алгоритма. Главное его свойство: все действия выполняются одинаково для всех элементов последовательности. Значит, основой его будет следующий цикл.

  1.  Инициализация цикла.
  2.  Пока есть элементы делай

Начало

  1.  Сравнить эталон с очередным элементом последовательности
    1.  Перейти к следующему элементу.

Конец.

Анализируем п.1. Нужно задать номер того элемента, с которого начнется сравнение, и определить эталон. Если в качестве эталонной переменной MIN выберем x1, то можно начать цикл с элемента номер 2. Тогда

  1.  I:=2; MIN:=X[1];

Условие п.2. означает, что текущий номер элемента I не превысил заданную длину последовательности: I≤N.

Шаг 2.1. – условный оператор. Его особенность – в отсутствии действий после иначе, поэтому можем записать укороченную форму оператора

2.1.  IF X[I]<MIN

THEN MIN:=X[I];

Шаг 2.2. – в увеличении индекса I на 1:

2.2.  I:=I+1;

Объединяя шаги детализации, получим алгоритм:

Ввод (последовательность Х);

I:=2; MIN:=X[1];

WHILE I<=N DO

BEGIN

 IF X[I]<MIN

 THEN MIN:=X[I];

 I:=I+1;

END;

Вывод (MIN);

  1.  Для отыскания номера минимального элемента тоже можно провести аналогию с яблоками в ящике, разделенном на ячейки. Каждая ячейка имеет номер, и нас интересует, в которой лежит самое маленькое яблоко. Понятно, что для определения номера мы все равно должны искать минимальный элемент по алгоритму А. Добавим к этому запоминание номера ячейки, из которой берется яблоко, меньшее эталона. Тогда параллельно с изменением рамки будет меняться запоминаемый номер. В конце концов он окажется равным номеру ячейки с наименьшим яблоком.

Поэтому алгоритм в задаче B имеет такую же структуру, что и в задаче А. Процесс отыскания минимума и его номера можно совместить в одном цикле. Как только в результате сравнения пришли к выводу, что нужно изменить эталон, то есть предположили, что новое значение может быть минимальным, нужно тут же зафиксировать номер этого элемента, следуя тому же предположению. Следовательно, в алгоритме появится новая переменная NOM – номер минимального элемента. При этом на шаге инициализации цикла нужно не забыть присвоить NOM начальное значение 1 на случай, если выбранный в качестве эталона первый элемент и окажется минимальным. Поэтому алгоритм будет иметь вид:

Ввод (последовательность Х);

I:=2; MIN:=X[1]; NOM:=1;

WHILE I<=N DO

BEGIN

 IF X[I]<MIN

 THEN

    BEGIN

MIN:=X[I];

NOM:=I;

    END;

 I:=I+1;

END;

Вывод (NOM);

Полученный алгоритм легко превратить в алгоритм определения номера максимального элемента, изменив условие на противоположное (в этом случае лучше назвать эталонную переменную MAX).

  1.  Если стоит задача нахождения максимального (или минимального) элемента и его номера в последовательности с совпадающими значениями, то нужно оговорить особо, какой именно - первый или последний из одинаковых элементов считать искомым. (Первое встреченное самое большое яблоко или последнее из самых больших).

Структура алгоритма в обоих случаях остается неизменной. Отличие будет отражаться только на сравнении эталонной переменной с текущим элементом массива. Поясним на численном примере.

Номер элемента

1

2

3

4

5

6

7

8

Последовательность

21

4

22

11

5

23

9

12

По алгоритму В:

 MIN:=2; NOM:=1;  начальные значения.

 MIN:=1; NOM:=4; эти значения останутся до конца.

Таким образом, алгоритм В решает задачу отыскания минимального (первого по порядку следования) элемента и его номера. Если мы хотим определить последний по порядку следования элемент и его номер, то в сравнении текущего элемента с эталоном должны изменить условие, а именно: MIN>=X[I].Тогда переприсваивание будет происходить и в случае равенства.  

  1.  Пусть задана последовательность x1 , x2 , x3 , …,xN и переменная P, которая называется поисковой. Известно, что все элементы последовательности имеют разные значения. Требуется определить номер элемента, значение которого равно значению переменной P. Так как сравнение вещественных величин на равенство не имеет смысла, будем считать, что массив X и переменная P – целые (они могут быть и литерными).

Одна из особенностей задачи состоит в том, что в последовательности может не оказаться элемента со значением P. Эту ситуацию нужно обязательно предусмотреть при конструировании алгоритма.

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

D1. Неупорядоченная последовательность

Просматриваем последовательно все элементы (книги на полке) и сравниваем их с поисковым значением (автора и название книги – с требованием). Когда обнаружится искомый элемент (книга), запомним его номер (место книги на полке).

Основой алгоритма является, таким образом, цикл.

  1.  Инициализация цикла.
  2.  Пока есть элементы делай

 Начало

 2.1. Сравнить очередной элемент с поисковой переменной

Конец

  1.  При инициализации цикла, как обычно, задаем исходное значение 1 индексу I элемента. Результат работы алгоритма – номер К найденного элемента. Вспомним, что наш алгоритм должен однозначно реагировать на ситуацию, когда искомого значения в последовательности нет. Резонно в этом случае считать К=0. Сделать это присваивание нужно до входа в цикл, иначе придется обременять алгоритм дополнительными проверками. Итак, шаг 1:
  2.  I:=1; K:=0;
  3.  Условие 2 – сравнение текущего номера с длиной последовательности: I<=N

2.1 На основе сравнения мы должны сделать выбор: продолжать сравнение или закончить цикл. Запишем

        если X[I]= то 

        начало

2.1.1. запомнить номер элемента

2.1.2. закончить цикл

конец

 иначе 

2.1.3. перейти к следующему сравнению

Поясним п.п. 2.1.1, 2.1.2 и 2.1.3.

2.1.1. K:=I

2.1.2. Так как цикл будет работать только при I ≤ N, достаточно присвоить I значение, большее N, и цикл завершится, например:

2.1.2 I:=N+1;

2.1.3. I:=I+1;

В итоге получаем алгоритм на псевдокоде.

Ввод (последовательность X);

I:=1;

K:=0;

WHILE I<=N DO

BEGIN

 IF   X[I]=P   

   THEN

  BEGIN

     K:=I; I:=N+1;

  END;

    ELSE I:=I+1;

END;

Вывод (К);

При составлении алгоритма на Паскале следует помнить, что цикл работает неопределенное число раз, поэтому нельзя использовать оператор FOR.

D2. Упорядоченная последовательность

Если последовательность упорядочена, то есть значения элементов возрастают (убывают) с увеличением номера элемента, то к ней можно применить другой алгоритм поиска. Договоримся рассматривать случай с возрастающей последовательностью.

Идея алгоритма: выбираем элемент Хс из середины последовательности и сравниваем с поисковым значением P. Если он не равен Р, то выясним, справа или слева от выбранного элемента находится искомый:

если Xc < P, то справа,

если Xc > P, то слева.

Соответствующий промежуток снова делим пополам и так далее. То есть получим не что иное, как метод дихотомии.

Пусть А – индекс наименьшего, а В – индекс наибольшего элемента последовательности (а затем и выделяемой ее части). Основа алгоритма – цикл, который выполняется неопределенное число раз. В этом цикле производим деление интервала индексов [A,B] пополам, получаем индекс С и сравниваем элемент с номером С с поисковой переменной Р. В зависимости от результата сравнения перевычисляем А или В. Повторяем действия до тех пор, пока А и В не совпадут. Затем делаем проверку X[A]=P и по ее исходу формируем результат.

  1.  Инициализация цикла
  2.  Пока А и В не совпадают делай

начало

2.1. вычислить С

2.2. сравнить X[C] с поисковой переменной P

конец

  1.  Проверить совпадение выделенного элемента с поисковым значением.
  2.  A:=1; B:=N – присвоение начальных значений.
  3.  Так как А – индекс меньшего элемента, В – большего, то их несовпадение будет означать, что А<В .

2.1. Так как А+В может быть нечетным числом, то для вычисления С нужно воспользоваться либо операцией деления нацело DIV, либо функцией выделения целой части INT.

C:=(A+B) DIV 2

2.2. Сравнение производим с помощью условного оператора

 если  X[C]<P

2.2.1. то   пересчитать А  

2.2.2. иначе  пересчитать В

2.2.1 и 2.2.2 очень ответственны. От правильности пересчета зависит окончание работы цикла. По условию 2 цикл прекратит свою работу при А=В. Как достичь этого?

Пусть мы уже сделали пересчет несколько раз и достигли соотношения А+1=В. Значит при очередном сравнении будем искать нужный элемент среди двух, расположенных рядом: X[A] и X[B]. Согласно шагу 2.1 вычисленное значение С при этом будет равно А. То есть сравнение 2.2 в этом случае выполнится как X[A]<P. Если условие истинно, то искомый элемент, возможно, есть X[B]. Тогда нужно сделать так, чтобы А стало равно В, то есть

2.2.1. A:=C+1;

Если же X[A]<P – ложно, то искомый элемент, возможно, есть X[A].  Тогда для завершения цикла полагаем

2.2.2. B:=C;

Легко  проверить, что такие присваивания не противоречат выбранному нами алгоритму на любом шаге работы цикла.

  1.  Проверка необходима, так как в цикле мы не делаем проверки на совпадение какого-либо элемента с поисковым, а только определяем, меньше этот элемент или не меньше Р. Теперь надо убедиться в том, что найденный элемент является искомым. Поэтому

3.IF X[A]=P

  THEN  K:=A

  ELSE K:=0;

Полностью алгоритм запишется следующим образом.

Ввод (последовательность Х);

A:=1; B:=N;

WHILE A<B DO

    BEGIN

 C:=(A+B) DIV 2;

 IF X[C]<P

 THEN A:=C+1;

 ELSE B:=C;

   END;

IF X[A]=P

THEN K:=A;

ELSE K:=0;

Вывод (К);

Все описанные алгоритмы поиска в одномерном массиве легко обобщаются на случай массива произвольной размерности. Так, алгоритм поиска минимального элемента и его номера в матрице:

Ввод (матрица А);

min := A[1,1];

nom1 := 1;

nom2 := 1;

FOR I:=1 TO M DO

 FOR J:=1 TO N DO

IF A[I,J]<min

THEN

  BEGIN

 min :=A[I,J];

 nom1:=I;

 nom2:=J;

  END;

Вывод (min, nom1, nom2);

2.2. Задача сортировки

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

2.2.1. Основные понятия

Под сортировкой понимают процесс перестановки элементов данного множества в определенном порядке. Цель сортировки – облегчить поиск элементов в упорядоченном множестве. В этом смысле элементы сортировки присутствуют почти во всех задачах. Упорядоченные объекты содержатся в телефонных книгах, в оглавлениях, в библиотеках, в словарях, на складах и так далее (почти всюду, где их приходится разыскивать).

Поэтому методы сортировки очень важны, особенно при обработке данных. При кажущейся простоте задачи именно с сортировкой связаны многие фундаментальные приемы построения алгоритмов, которые и интересуют нас прежде всего. Сортировка является идеальным примером огромного разнообразия алгоритмов, выполняющих одну и ту же задачу. Многие из них являются в некотором смысле оптимальными, большинство имеет какие-то преимущества перед остальными. Поэтому на примере сортировки мы убеждаемся в необходимости сравнительного анализа алгоритмов. С помощью сортировки можно прекрасно иллюстрировать многие принципы программирования и ситуации, возникающие в других задачах. Создается впечатление, что можно построить целый курс программирования, выбирая примеры только из сортировки.

Очень часто выбор алгоритма зависит от структуры данных. В случае сортировки эта зависимость настолько сильна, что методы сортировки обычно разделяют на две группы: сортировка массивов и сортировка файлов (последовательных). Эти две группы часто называют внутренней и внешней сортировкой, так как массивы располагаются во «внутренней» (оперативной) памяти ЭВМ, а файлы – во «внешней», более медленной, но более вместительной (ленты, диски). Пример – сортировка пронумерованных карточек. Представление карточек в виде массива соответствует ситуации, когда все они  располагаются перед сортирующим (на столе) и каждая карточка видна и доступна. Представление карточек в виде файла предполагает, что они сложены стопкой и видна только верхняя карточка из стопки.

Пусть даны элементы а1, а2, …аN. Сортировка означает перестановку этих элементов в таком порядке ак1, ак2, …аkN, что при заданной функции упорядочения f справедливо отношение

f (ak1) ≤ f (ak2) ≤ … ≤ f (akN).

Обычно функция упорядочения не вычисляется по какому-то специальному правилу, а содержится в каждом элементе в виде явной компоненты (поля). Ее значение называется ключом элемента (key). Прочие компоненты – это все существенные данные об элементе. С точки зрения же алгоритмов сортировки ключ – единственная существенная компонента, и нет необходимости определять остальные.

Метод сортировки называется устойчивым, если относительный порядок элементов с одинаковыми ключами не меняется при сортировке. Устойчивость сортировки часто бывает желательна, если элементы упорядочены по каким-то вторичным ключам, то есть по другим свойствам.

2.2.2. Особенности сортировки массивов. Простые 

                     методы сортировки массивов

Основное требование к методам сортировки массивов – экономное использование памяти. Это означает, что упорядочение нужно проводить на том же месте, то есть методы, которые пересылают элементы из массива А в массив В, нам не интересны. Таким образом, выбирая метод сортировки по критерию экономии памяти, классификацию алгоритмов можно проводить по их эффективности, то есть быстродействию. Удобной оценкой такой эффективности является количество С необходимых сравнений ключей и М пересылок элементов. С и М являются некоторыми функциями от числа элементов n.

Хотя хорошие алгоритмы сортировки требуют порядка n * log 2 n сравнений, обсудим вначале несколько несложных и очевидных методов сортировки, называемых простыми методами, которые требуют С ~ n2.

Причины такого рассмотрения состоят в следующем:                               

  1.  на простых методах разъяснять свойства большинства принципов сортировки;
  2.  программы, основанные на этих методах, легки для понимания и коротки (программа тоже занимает место в памяти ЭВМ!);
  3.  при достаточно малых значениях n простые методы работают быстрее.

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

Рассмотрим эти методы для простейшего случая упорядочения числовых массивов (последовательностей) по возрастанию (убыванию) значений элементов. В этом случае ключ f (ai) = ai (табл.2.1 – табл.2.3).

Таблица 2.1 – Числовой массив. Все элементы различны

Номер элемента

1

2

3

4

5

Исходная последовательность

7

12

1

49

3

Упорядоченная по возрастанию последовательность

1

3

7

12

49

Таблица 2.2 – Числовой массив. Есть повторяющиеся элементы

Номер элемента

1

2

3

4

5

Исходная последовательность

4

21

171

22

172

Упорядоченная по возрастанию последовательность

21

22

4

171

172

Таблица 2.3 – Массив строк. Упорядочение по алфавиту

Номер элемента

1

2

3

4

5

Исходная последовательность

МИР

СОН

ТУР

КОЛ

ЕЛЬ

Упорядоченная по возрастанию последовательность

ЕЛЬ

КОЛ

МИР

СОН

ТУР

Сортировку можно рассматривать и как самостоятельную задачу (например, получение упорядоченного по алфавиту списка сотрудников какого-либо учреждения), и как вспомогательную для облегчения последующего поиска.

Следует отметить, что все методы сортировки рассчитаны на обработку одномерных массивов. При необходимости двумерный массив всегда можно представить как одномерный путем пересчета индексов.

Будем для определенности упорядочивать массив А1, А2, … , АN по возрастанию. Переход к алгоритмам упорядочения по убыванию не составляет труда. Рассмотрим три алгоритма, представляющие каждую из перечисленных групп методов сортировки.

                                         Простой выбор

Это очень естественный способ сортировки, который обычно первым приходит на ум человеку, впервые столкнувшемуся с этой задачей.

Идея метода такова. Найдем в последовательности элемент с наименьшим значением и поменяем его местами с первым элементом. Затем проделаем те же действия с оставшимися N-1 элементами, затем с N-2 и так далее до тех пор, пока не останется один элемент – последний. Он будет наибольшим.

Проиллюстрируем процесс (табл.2.4).

Таблица 2.4 – Пример сортировки простым выбором

Номер элемента

1

2

3

4

5

6

7

8

Исходная последовательность

72

14

6

98

17

51

25

33

После выбора среди 8 элементов

6

14

72

98

17

51

25

33

7 элементов

6

14

72

98

17

51

25

33

6 элементов

6

14

17

98

72

51

25

33

5 элементов

6

14

17

25

72

51

98

33

4 элементов

6

14

17

25

33

51

98

72

3 элементов

6

14

17

25

33

51

98

72

                                   2 элементов

6

14

17

25

33

51

72

98

Упорядоченная последовательность

6

14

17

25

33

51

72

98

Для составления алгоритма снова воспользуемся методом пошаговой детализации. Отметим, что для получения результата нам нужно N-1 раз находить минимальное значение в последовательности, длина которой каждый раз уменьшается. Кроме того, так как минимальный элемент нужно менять местами с определенным элементом последовательности, то номер минимального элемента нужно запоминать.

Обобщенно наш алгоритм можно записать так.

  1.  I:=1;
  2.  Пока I ≤ N-1

 Начало

  1.  найти минимальный элемент и его номер в последовательности AI, …, AN.
    1.  поменять местами AI и минимальный элемент.
    2.  I:=I+1;

Конец

Алгоритм поиска минимального элемента и его номера мы рассмотрели ранее, поэтому

2.1.

 K:=I;

X:=A[I];

J:=I+1;

WHILE J<=N DO

BEGIN

 IF A[J]<X

 THEN BEGIN

  X:=A[J];

  K:=J;

 END;

 J:=J+1;

END;

В результате значением Х будет значение минимального элемента среди АI, ... AN, а значением К - номер этого элемента. Поэтому п. 2.2. можно записать конкретнее:

  2.2. поменять местами элементы Ai и Ak

Это можно сделать так:

2.2. C:=A[I]; А[I]:=A[K]; A[K]:=C;

Однако в нашей ситуации дополнительная переменная С не нужна, так как ее роль играет Х из п. 2.1. Поэтому запишем:

   2.2. A[K]:=A[I]; A[I]:=X;

Мы сэкономили на одном присваивании, а так как действие выполняется в цикле, то это немало.

Теперь запишем полностью алгоритм сортировки простым выбором.

Ввод (последовательность А);

I:=1;

WHILE I<=N-1 DO

BEGIN

K:=I;

X:=A[I];

J:=I+1;

WHILE J<=N DO

 BEGIN

  IF A[J]<X

  THEN

  BEGIN

  X:=A[J];

   K:=J;

  END;

  J:=J+1;

 END;

A[K]:=A[I];

A[I]:=X;

I:=I+1;

END;

                                            Простой обмен

Обмен (перестановка двух элементов в памяти) присущ любому алгоритму сортировки. Но в этом методе он является основной операцией.

Идея алгоритма состоит в многократных попарных сравнениях соседних элементов последовательности и перестановке их в заданном порядке.

Пусть задана следующая последовательность:

Номер элемента

1

2

3

4

5

Значение элемента

7

49

1

12

3

Будем рассматривать последовательность от конца к началу (можно и наоборот). Сравниваем 4-й и 5-й элементы и меняем их местами (расположены не в порядке возрастания). Затем сравниваем 3-й с новым 4-м оставляем на месте. 2-й и 3-й меняем. 1-й и 2-й меняем. Получим следующую последовательность

Номер элемента

1

2

3

4

5

Значение элемента

1

7

49

3

12

В результате таких обменов минимальный элемент перешел на первое место в последовательности. Поэтому в следующий просмотр его не включаем, просматриваем N-1 элемент точно так же и т.д. В результате (N-1)-го просмотра получим упорядоченную последовательность.

Если вообразить, что элементы последовательности это пузырьки воздуха в резервуаре с водой, каждый с весом, равным значению элемента, то каждый проход с обменами по последовательности соответствует «всплыванию» пузырька на соответствующий его весу уровень. Благодаря такой аналогии сортировку простым обменом называют также сортировкой методом «пузырька».

На рис.2.1 первые два элемента уже упорядочены и «всплывает» третий. Знак <= (а не <) показывает условие прекращения сравнений. Этим достигается устойчивость сортировки «пузырьком».

Рис. 2.1 – Иллюстрация метода «пузырька»

Рассмотрим численный пример (табл.2.5).

Таблица 2.5 – Пример сортировки простым обменом

Номер элемента

1

2

3

4

5

6

7

8

Исходная последовательность

72

14

6

98

17

51

25

33

4 обмена

После просмотра      8 элементов

6

72

14

17

98

25

51

33

3 обмена

7 элементов

6

14

72

17

25

98

33

51

2 обмена

6 элементов

6

14

17

72

25

33

98

51

2 обмена

5 элементов

6

14

17

25

72

33

51

98

1 обмен

4 элементов

6

14

17

25

33

72

51

98

1 обмен

3 элементов

6

14

17

25

33

51

72

98

2 элементов

6

14

17

25

33

51

72

98

Упорядоченная последовательность

6

14

17

25

33

51

72

98

Основой алгоритма, реализующего данный метод, является цикл, выполняющийся N-1 раз. Границы для параметра цикла I могут быть равны 1 и N-1 или 2 и N. Вначале приведем обобщенную запись алгоритма.

  1.  I:=2;
  2.  WHILE I<=N DO

BEGIN

2.1. сравнить попарно элементы AN, AN-1, ... , AI, AI-1

2.2. I:=I+1;

END;

Детализируем п.2.1. Для попарного сравнения элементов нужен цикл с границей, зависящей от I, так как при каждом новом проходе последовательности ее длина укорачивается. Поэтому

2.1.1. J:=N;

2.1.2. WHILE J>=I DO

BEGIN

2.1.2.1. Сравнить AJ и AJ-1 и при необходимости поменять их местами.

2.1.3. J:=J-1;

END;

Пункт 2.1.2.1. записать довольно просто.

2.1.2.1. IF A[J-1]>A[J]

 THEN

  BEGIN

  X:=A[J-1];

A[J-1]:=A[J];

A[J]:=X;

END;

Объединим наши шаги детализации в алгоритм.

Ввод (последовательность А);

I:=2;

WHILE I<=N DO

BEGIN

J:=N;

WHILE J>=I DO

BEGIN

 IF A[J-1]>A[J]

 THEN

 BEGIN

  X:=A[J-1]; A[J-1]:=A[J];

A[J]:=X;

 END;

J:=J-1;

END;

I:=I+1;

END;

Вывод (последовательность А);

                                

Простые вставки

Пусть в заданной последовательности А1, А2, ... , АN первые I-1 элементов уже отсортированы. Найдем в этой части место для I-го элемента. Для этого будем сравнивать его по порядку со всеми элементами, стоящими левее него, до тех пор, пока не найдется некоторый AK<=AI. Затем сдвинем часть последовательности AK+1, ... , AI-1 на один элемент вправо и на освободившееся место поставим AI. Знак <= позволяет обеспечить устойчивость сортировки.

После того, как проделаем эти действия для всех элементов от 2-го до N-го, получим отсортированную последовательность. Важно отметить, что при сравнении может оказаться , что условие АK<=AI не выполнится, так как АK может быть меньше всех левых элементов. Тогда нужно сдвинуть все элементы А1, ... , АI-1 вправо и поставить АI на первое место.

Рассмотрим пример, иллюстрирующий работу метода (табл.2.6).

Таблица 2.6 – Пример сортировки простыми вставками

Номер элемента

1

2

3

4

5

6

7

8

Исходная последовательность

72

14

6

98

17

51

25

33

После вставки элемента        № 2

14

72

6

98

17

51

25

33

   3

6

14

72

98

17

51

25

33

4

6

14

72

98

17

51

25

33

5

6

14

17

72

98

51

25

33

6

6

14

17

51

72

98

25

33

7

6

14

17

25

51

72

98

33

8

6

14

17

25

33

51

72

98

Упорядоченная последовательность

6

14

17

25

33

51

72

98

В основе алгоритма лежит цикл, определяющий, для какого элемента ищем место в упорядоченной левой части последовательности.

 Ввод (последовательность А);

  1.  I:=2;
  2.  WHILE I ≤ N DO

BEGIN

  1.  Найти место AK+1 для AI в упорядоченной части последовательности;
    1.  Сдвинуть элементы AK+1, …, AI вправо;
    2.  Поставить элемент  A[I] на нужное место;
    3.  I:=I+1;

END;

Вывод (последовательность А);

Детализируем п. 2.1. Нужно сравнивать AI последовательно со всеми левыми соседями до элемента AK ≤ AI. Если такового не окажется, остановиться на первом элементе. Это циклические действия, причем удобнее оформить цикл по текущему номеру элемента. Тогда получим:

2.1.1. Инициализация цикла;

2.1.2. WHILE J>0 DO

  BEGIN

2.1.2.1. сравнить элементы AI и AJ;

  END;

При реализации п.2.1.1 мы должны предусмотреть 3 момента:

  1.  значение AI нужно запомнить, так как потеряется при сдвиге;
  2.  нужно зафиксировать номер I-1, т.к. с этого элемента начнется сравнение;
  3.  если AI – минимальный элемент из A1, …, AI, он должен встать на первое место. Поэтому п. 2.1.1:

2.1.1. X:=A[I];

 J:=I-1;

 K:=0;

2.1.2.1. По результатам сравнения нужно сделать вывод: продолжать его или закончить цикл. Закончить цикл можно, положив J = 0.

2.1.2.1.IF A[J]<=A[I] THEN

           BEGIN

             K:=J;

             J:=0;

           END;

          ELSE J:=J-1;

2.2. Для сдвига последовательности нужно просматривать ее из конца в начало и последовательно сдвигать элементы. Это делается так:

J:=I;

WHILE J>K+1 DO

BEGIN

A[J]:=A[J-1];

J:=J-1;

END;

2.3. A[K+1]:=X;

Теперь запишем  весь алгоритм.

Ввод (последовательность А);

I:=2;

WHILE I ≤ N DO

BEGIN

 X:=A[I];

J:=I-1;

K:=0;

WHILE J>0 DO

BEGIN

 IF A[J]<=A[I] THEN

BEGIN

  K:=J;

  J:=0;

END

ELSE J:=J-1;

            END;

J:=I;

WHILE J>K+1 DO

BEGIN

 A[J]:=A[J-1];

 J:=J-1;

END;

A[K+1]:=X;

I:=I+1;

END;

Вывод (последовательность А);

Проведем анализ трудоемкости простых алгоритмов сортировки на примере алгоритма простых вставок.

Число сравнений ключей Ci на i-ом просмотре последовательности:

Сi min = 1, Ci max = i-1, тогда Ci cp = .

Общее число сравнений (по формуле для суммы арифметической прогрессии ) равно

C min = N-1,

C cp = ,

C max = .

Число же перестановок (присваиваний элементов)    Mi  = Ci +2.

Поэтому общее число присваиваний равно

M min = 3(N –1),   (Mi min = 3)

M cp = , (Mi cp = ),

M max = , (Mi max = i + 4).

Аналогично можно проанализировать и два других. Самый медленный – пузырек.

Везде получим, что

С ~ N 2,  M ~ N 2.

Для больших N это слишком много. Поэтому возникли улучшенные алгоритмы. Один из них – алгоритм Шелла.

2.2.3. Алгоритм Шелла

Алгоритм предложен в 1959 году как усовершенствование метода простых вставок. Является самым простым среди улучшенных алгоритмов сортировки. Может работать и как улучшенный метод простого обмена («пузырька»).

В «пузырьке» сравниваем соседние элементы. Но если в массиве элементы стоят очень далеко от своего истинного места,   то  придется   совершить   очень

                                                        много перестановок.

Идея метода состоит в следующем: сначала переставлять элементы на большие расстояния, а затем расстояния сужать. Расстояние между сравниваемыми элементами задается с помощью вспомогательной величины h – шага перестановки элементов. На каждом этапе рассматриваются ai и ai+h.

При заданных h и начальном значении i все рассматриваемые на данном этапе элементы образуют цепочку. Если изменить i, то получим другие цепочки:

При уменьшении шага h количество цепочек уменьшается, а длина их возрастает. На самом последнем этапе h=1 (обязательно!), и весь массив представляет собой одну цепочку. «Пузырек» - частный случай алгоритма Шелла при h=1.

Для нашего массива получим следующий процесс сортировки (табл.2.7).

Таблица 2.7 – Пример сортировки методом Шелла

Номер элемента

1

2

3

4

5

6

7

8

Исходная последовательность

72

14

6

98

17

51

25

33

После сортировки при      h=4

17

14

6

33

72

51

25

98

h=2

6

14

17

33

25

51

72

98

h=1

6

14

17

25

33

51

72

98

Упорядоченная последовательность

6

14

17

25

33

51

72

98

Таким образом, мы видим, что внешне процесс существенно усложняется: вместо одной сортировки необходимо несколько (при каждом h – несколько цепочек и для каждой нужно провести сортировку). В чем же преимущество?

Дело в том, что на каждом шаге либо сортируется относительно мало элементов (на первых этапах), либо элементы уже довольно хорошо упорядочены и требуют сравнительно немного перестановок (на последующих этапах). Это важно, так как перестановки (присваивания) – более медленные операции, чем сравнения. Почему в конце концов массив окажется упорядоченным? Потому что последнее значение шага h=1 и весь массив окончательно упорядочивается как одна цепочка.

Алгоритм Шелла запишем теперь в виде процедуры. В ней следует учесть два важных момента.

  1.  Выбор начального значения h. Это самостоятельная достаточно интересная задача. Исследования показывают, что одно из лучших hнач =  (скобки означают округление результата до целого значения в большую сторону).
  2.  Выбор формул пересчета для h. В общем случае неизвестно, какие расстояния дают наилучшие результаты. Но был замечен такой факт: значения h не должны быть множителями друг друга. Это связано с тем, что желательно, чтобы различные цепочки как можно чаще пересекались друг с другом. В нашем примере этого не происходит. Кнут показал [5], что целесообразно использовать

hj-1 = 2hj +1  (в обратном порядке: 1, 3, 7, 15, …)

или

hj-1 = 3hj +1 (1, 4, 13, 40, …)

Теперь запишем весь алгоритм.

CONST N = …;

TYPE MAS = ARRAY [1..N] OF REAL;

PROCEDURE SHELL (N: INTEGER; VAR A: MAS);

VAR H, I: INTEGER;

BEGIN

H:=(N+2) DIV 3;

WHILE H>0 DO

BEGIN

 FOR I:=1 TO H DO

 BEGIN

  Упорядочение алгоритма пузырька с шагом Н, начиная         с i-го элемента

 END;

 IF H>5

 THEN H:= (H-1) DIV 2;

 ELSE IF H=1

  THEN H:=0

  ELSE H:=1

END

END;

Алгоритм Шелла до сих пор полностью не исследован. Его анализ поставил ряд трудных математических проблем, которые пока так и не решены (как, например, проблема выбора h).

При надлежащем выборе h трудоемкость алгоритма Шелла в худшем случае ~ n3/2. В среднем ~ (log2 n)2n. Это намного лучше, чем n2.

n = 100, n2 = 104, n3/2 = 103, (log2 n)2n ~ 49n = 49*102

n = 10000, n2 = 108, n3/2 = 106, (log2 n)2n ~ 142n = 142*104

На  практике   алгоритм   Шелла   целесообразнее   применять,   если

n ≤ (1÷5)103 элементов. Теоретически показано, что трудоемкость оптимального алгоритма сортировки должна быть ~ n log2 n.

Для небольших n нецелесообразно применять сложные алгоритмы. Но при больших n улучшенные алгоритмы имеют преимущества.

Рассмотрим алгоритм, который является в среднем оптимальным. Это алгоритм Хоара.

2.2.4. Алгоритм Хоара

Алгоритм Хоара был разработан в 1961 – 62 гг. Это так называемая быстрая сортировка, представляющая собой улучшенный метод, основанный на обмене. Несмотря на то, что обычный обмен в среднем является самой неэффективной процедурой, его улучшение, о котором будем говорить, приводит к самому лучшему в настоящий момент алгоритму сортировки для массивов. Алгоритм основан на разделении массива опорным элементом.

Возьмем из массива какой-либо элемент Z (опорный) и будем сравнивать его поочередно со всеми остальными. Если Mi ≤ Z – переставляем Mi в начало последовательности.

 Mi ≥ Z – в конец. В результате получим:

Z стоит на своем месте.

Получим массив, частично упорядоченный. К его левой и правой части применим ту же операцию и т.д. Продолжаем действия до тех пор, пока части не станут пустыми или состоящими из одного элемента. Теперь массив полностью упорядочен.

Алгоритм Хоара запишем в виде процедуры.

PROCEDURE HOARE (A, B: INTEGER; VAR M: MAS);

VAR

Z: REAL;

D,C: INTEGER;

BEGIN

Z:=M[A]; - опорный элемент – №1 в последовательности (или ее части);

D:=B+1; - временные границы просматриваемой

C:=A; части (сужаются);

WHILE C+1 < D DO - пока вся последовательность не просмотрена;

IF M[D-1] > Z - сравнение текущего элемента с опорным (начинаем сравнивать с конца массива);

THEN D:=D-1 - элемент стоит на своем месте, переходим к следующему     элементу;

ELSE

BEGIN

M[C]:=M[D-1]; - элемент, больший опорного, заносится в начало последовательности;

C:=C+1;

M[D-1]:=M[C]; - соответственно элемент из начала последовательности переносится в конец, освобождая место для Z;

END;

M[C]:=Z; - опорный элемент заносится на свое место;

IF C>A+1 - в левой части больше 1 элемента;

THEN HOARE (A, C-1, M); -применяем алгоритм к левой части;

IF C+1<B - в правой части больше 1 элемента;

THEN HOARE (C+1, B, M); -применяем алгоритм к правой части;

END;

Пусть исходная последовательность:

Номер элемента

1

2

3

4

5

6

7

8

Исходная последовательность

25

98

6

72

7

88

14

51

Процесс ее разделения

14

98

6

72

7

88

98

51

14

7

6

72

6

88

98

51

14

7

6

72

72

88

98

51

14

7

6

72

88

98

51

Исходные значения: A=1,  B=8,  Z=25,  D=9,  C=1.

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

Разделение массива выполняется за число шагов, равное длине последовательности.

Тогда число шагов на этапах:

  1.  2 по N / 2    Всего получим m этапов.
  2.  4 по N / 22   2m ≥ N
  3.  8 по N / 23   m = [log2 N]

……….    

  1.  N по N / N

На каждом этапе суммарное число сравнений Ci ≤ N. Тогда общее число сравнений C ≤ N log2 N.

В этих условиях алгоритм Хоара является оптимальным по быстродействию. Если при делении какая-то часть последовательности окажется больше другой, то количество этапов m > [log2 N]. Следовательно, трудоемкость алгоритма окажется выше. Экспериментально получено, что средняя величина трудоемкости Cср = N log2 N * 1.4.

Эффективность алгоритма Хоара существенно зависит от выбора опорного элемента. В ряде случаев алгоритм может оказаться очень плохим. Вероятность плохой ситуации уменьшается, если брать опорный элемент из середины последовательности: Z:= M[(A+B) DIV 2];

Выбор начального элемента в качестве опорного является неудачным.

Контрольные вопросы и задания 

  1.  В чем состоит задача информационного поиска? Каковы ее разновидности?
  2.  Запишите алгоритм отыскания минимального элемента и его номера в последовательности с различными и повторяющимися элементами.
  3.  Запишите алгоритмы отыскания элемента с заданным значением в неупорядоченной и упорядоченной последовательностях.
  4.  В чем состоит задача сортировки?
  5.  Чем отличается сортировка в массивах от сортировки в файлах?
  6.  Что такое устойчивая сортировка?
  7.  Назовите основные разновидности методов сортировки в массивах.
  8.  На чем основан метод сортировки простым выбором? Запишите алгоритм, реализующий этот метод.
  9.  Какова идея метода простого обмена? Запишите его алгоритм.
  10.   Поясните смысл метода простых ставок. Запишите алгоритм сортировки этим методом.
  11.   Как оценить трудоемкость методов сортировки?
  12.   Что представляет собой метод сортировки Шелла?
  13.   Оформите алгоритм Шелла в виде процедуры.
  14.   В чем состоит идея метода сортировки Хоара?
  15.   Составьте процедуру, реализующую алгоритм Хоара.

3. Рекурсивные алгоритмы

3.1. Понятие рекурсии

Объект называется рекурсивным, если он содержит сам себя или определен с помощью самого себя.

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

 <цифра> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |,

<буква>  ::= A| B | …| Z,

<целое число без знака> ::= <цифра> | <целая часть><цифра>,

<идентификатор> ::= <буква> | <идентификатор><буква> | <идентификатор><цифра>.

Две последние формулы рекурсивны.

Рекурсивным может быть и определение функции. Так, например, факториал: f(n) = n! Одним из способов определения такой функции является рекурсивный способ:

 

n! =

3.2. Примеры рекурсивных алгоритмов. Прямая

            и косвенная рекурсии

Язык Паскаль позволяет создавать процедуры и функции, обладающие свойством рекурсивности, то есть содержащие в своем описании вызов самих себя. Так для вычисления n! мы можем составить такое рекурсивное описание функции.

Пример 1.

FUNCTION FACT (N: INTEGER): INTEGER;

BEGIN

IF N=0

THEN FACT:=1

ELSE FACT:=N*FACT(N-1)

END;

Пример 2.Выдать на печать в обратном порядке цифры целого положительного числа N.

PROCEDURE REVERSE (N: INTEGER);

BEGIN

WRITE (N MOD 10);

IF (N DIV 10) 0

THEN REVERSE (N DIV 10)

END;

Проанализируем работу  программы. Пусть N=153. Тогда печатаем число 3 и проверяем на равенство нулю целой части деления:

целая часть 153/10 равна 15, снова обращаемся к REVERSE, печатаем 5,

целая часть 15/10 равна 1, снова обращаемся  к REVERSE, печатаем 1.

Таким образом, однократное обращение извне к процедуре REVERSE вызвало троекратное ее срабатывание. Условие полного окончания работы должно содержаться в самой процедуре. Иначе произойдет зацикливание.

Посмотрим теперь, как происходит процесс вычисления при рекурсивном описании алгоритма в примере 1.

Пусть в основной программе происходит вызов функции FACT (3). Тогда при входе в процедуру-функцию в употребление вводится некоторая локальная переменная N, соответствующая этому параметру-значению, после чего выполняются операторы процедуры. Так как здесь N=3, то выполняется оператор

 FACT:= 3*FACT (2).

В процессе выполнения этого оператора мы снова обращаемся к функции FACT для вычисления FACT(2). При этом снова вводится в употребление локальная переменная, соответствующая этому параметру-значению. Но это уже другая переменная, например, N1. Ей присваивается значение N1=2 и так как N1≠0, то выполняется оператор

 FACT:= 2*FACT (1).

При его выполнении для вычисления FACT(1) снова требуется обращение к функции FACT, что требует введения новой локальной переменной N2 со значением N2=1, и выполнится оператор

 FACT:= 1*FACT (0).

При этом каждый раз завершение вычисления выражения в правой части оператора присваивания откладывается. При очередном обращении к процедуре-функции получим N3=0, и в теле процедуры выполняется оператор FACT:=1.

После этого завершится выполнение оператора FACT:= 1*FACT (0), то есть получим FACT(1)=1.

После этого завершится выполнение оператора FACT:= 2*FACT (1), что даст нам FACT(2)=2, и, наконец, закончится вычисление FACT:= 3*FACT (2), что даст FACT(3)=6.

Таким образом, в момент рекурсивного вызова мы как бы запомнили состояние алгоритма в момент исходного вызова (сфотографировали). Это нужно, чтобы после завершения рекурсивного вызова продолжить выполнение алгоритма от первичного вызова. Это запоминание делается автоматически, но следует об этом знать. При каждом вторичном вызове рекурсивной процедуры требуется память для запоминания внутренних переменных.

Сколько может быть вторичных вызовов до первого завершения самого последнего вызова? Количество повторных вызовов называют глубиной рекурсии –  это важная характеристика алгоритма.

Попытайтесь самостоятельно подсчитать глубину рекурсии для алгоритма Хоара в наиболее благоприятном и наименее благоприятном случаях.

Пример 3.

Интересный пример рекурсии – игра ханойские башни”. Здесь применение рекурсии очень уместно.

Имеется 3 стержня и N дисков разного размера.

Пусть вначале все диски находятся на стержне А в порядке убывания размера.

Задача состоит в том, чтобы переместить диски на стержень В в том же порядке.

Правила перемещения.

  1.  На каждом шаге только один диск (верхний) перемещается с одного стержня на другой.
  2.  Диск большего размера нельзя помещать на меньший диск.
  3.  Стержень С можно использовать как промежуточный.

Пусть N=1. Тогда единственная перекладка: А→В.

          N=2:  А→С,

 А→В,

 С→В.

         N=3:  A→В,

А→С,

В→С,

А→В,

С→А,

С→В,

А→В.

При большем N записать последовательность перекладок уже сложно.

Для составления алгоритма рассуждаем следующим образом (по методу математической индукции).

  1.  При N=1 перекладка очевидна (А→В).
  2.  При N>1. Допустим, что умеем перекладывать N-1 колец правильным образом. Тогда нужно переложить N-1 кольцо с А на С, затем одно с А на В, а затем всю пирамиду с С на В (диск A освободился). В свою очередь, чтобы переложить N-1 кольцо, надо научиться перекладывать N-2 и так далее до 1.

Отсюда непосредственно получим рекурсивную процедуру, в которой основной оператор

WRITE (A, B);  перекладывать

PROCEDURE HANOY (N, A, B, C: INTEGER);

BEGIN

IF N=1

THEN WRITELN (A, B);

ELSE

BEGIN

HANOY (N-1, A, C, B);

WRITELN (A, B);

HANOY (N-1, C, B, A)

END

END;

Проверим: для N=1 процедура напечатает  1 2

 для N=2: 1 3

1 2

3 2

         Для N=3 проверьте работу процедуры самостоятельно.

Почему так называется игра? По легенде где-то недалеко от Ханоя расположена пирамида из 64 золотых колец. Эти кольца перекладывают жрецы храма. Как только они закончат этот процесс, наступит конец света. Можно приблизительно подсчитать, когда это случится. Пусть L(N) – количество перекладок. Тогда при

 N = 1,  L (N) = 1

 N = 2,  L (N) = 3

 N = 3,  L (N) = 3 + 1 + 3 = 7

…………………

 N = k,  L (N) = 2k-1.

Для количества колец N=64 L(N)=264-1. Если одно перекладывание занимает 1 секунду, то 264 секунд ≈ 1012 лет (около 1 триллиона лет до конца света).

Существует 2 формы рекурсивных процедур (или функций):

  1.  прямая рекурсия,
  2.  косвенная рекурсия.

В случае прямой рекурсии процедура содержит вызов этой же процедуры (как в наших примерах).

В случае косвенной рекурсии процедура вызывает другую процедуру, которая сама либо с помощью других процедур, вызывает исходную. Например

А→В→А.

Но тогда возникает проблема: где и как описать вызываемую процедуру? По правилам языка Паскаль каждый вызываемый модуль (процедура, функция) должен быть описан до его вызова. Но если А вызывает В, а В вызывает А, то получается замкнутый круг. Выходят из положения так: один из модулей, вызывающих друг друга, описывается предварительно следующим образом

 PROCEDURE P (<список формальных параметров>); FORWARD;

или

 FUNCTION S (<список формальных параметров >):<тип>; FORWARD;

Здесь FORWARD – ключевое слово (в переводе означает – передний, вперед). Оно указывает транслятору, что текст процедуры Р помещен ниже. При этом список формальных параметров, а также тип результата (для FUNCTION) указываются только в этом предварительном описании, а в заголовке последующего текста – опускаются.

Пусть при работе функция А вызывает функцию В, а В – функцию А. Тогда эти модули можно описать так:

FUNCTION A (X: INTEGER): REAL; FORWARD;

FUNCTION B (Y: INTEGER): REAL;

BEGIN

……….

B := A(I)+3.5

END;

FUNCTION A;

BEGIN

………

A:=B(D)-1.8

END;

3.3. Преимущества и недостатки рекурсивного 

            описания алгоритма

Любое рекурсивное определение функции можно заменить нерекурсивным. Точно также и любой рекурсивный алгоритм можно заменить нерекурсивным. Так для вычисления n! нерекурсивная функция будет описана следующим образом:

FUNCTION FACT (N: INTEGER): INTEGER;

VAR K,I: INTEGER;

BEGIN

K:=1;

FOR I:=1 TO N DO K:=K*I;

FACT:=K;

END;

      Рекурсивность – это не свойство функции, а свойство ее описания. Какое же из описаний лучше?

В общем случае рекурсивное описание короче и нагляднее, но требует больших затрат машинного времени (за счет повторных обращений к процедуре) и большей памяти (за счет дублирования локализованных в процедуре переменных). Чему отдать предпочтение – следует решать в конкретном случае.

Каждый рекурсивный алгоритм нужно оценивать с точки зрения времени работы. Если сам алгоритм даже при нерекурсивном описании содержит много действий, то в нем относительное увеличение времени за счет рекурсии будет небольшим.

Если в алгоритме мало действий, то доля дополнительных команд может оказаться слишком большой. Например, в алгоритме для n! рекурсивная процедура гораздо медленнее, поэтому целесообразнее использовать его нерекурсивную форму, а именно – итеративную (рекуррентную).

Есть и другие рекурсивные схемы, которые можно и должно переводить в нерекурсивную, итеративную форму. Пример – вычисление чисел Фибоначчи по рекуррентной последовательности:

а0 = 0,

а1 = 1,

……

аn = аn-1 + аn-2, n>1

При рекурсивном подходе получим программу

FUNCTION FIB (N: INTEGER): INTEGER;

BEGIN

IF N=0

THEN FIB:=0

ELSE

IF N=1

THEN FIG:=1

ELSE FIB:= FIB(N-1)+FIB(N-2)

END;

Обращение к функции FIB(N) приводит к рекурсивным вызовам этой процедуры. Найдем глубину рекурсии нашего алгоритма для значения N=5. Тогда получим схему, изображенную на рис. 3.1.

Из схемы видно, что при N>1 каждое обращение к FIB ведет к 2-м дальнейшим обращениям, то есть общее число обращений растет почти экспоненциально. Поэтому такая программа плоха и непригодна.

Итеративная схема вычислений чисел Фибоначчи введением всего двух вспомогательных переменных    X = аi и Y = аi-1 позволяет избежать повторного вычисления одних и тех же

                                                           значений.

FUNCTION FIB (N: INTEGER): INTEGER;

VAR X, Y, Z, I: INTEGER;

BEGIN

I:=1;

X:=1;

Y:=0;

WHILE I<N DO

BEGIN

Z:=X;

X:=X+Y;

Y:=Z;

I:=I+1

END;

FIB:=X

END;

Поэтому  вывод можно сделать следующий. Если задача имеет очевидное итеративное решение, то рекурсии следует избегать. Однако это не значит, что от рекурсии нужно избавляться всегда и любой ценой. Для алгоритма Хоара, например, потери во времени на практике являются небольшими. Многие сложные алгоритмы описываются в рекурсивной форме более наглядно, поэтому целесообразно их описывать именно так.

Контрольные вопросы и задания

  1.  Что такое рекурсия?
  2.  Приведите примеры рекурсивных алгоритмов. Объясните их работу.
  3.  Что понимают под глубиной рекурсии? Как она вычисляется?
  4.  В чем состоит различие между прямой и косвенной рекурсией?
  5.  Как описать процедуры, связанные косвенной рекурсией? Приведите примеры.
  6.  Каковы достоинства и недостатки рекурсивного описания алгоритма?
  7.  В каких случаях целесообразно использовать рекурсию?
  8.  Проанализируйте алгоритм игры «Ханойские башни». Запишите его в форме процедуры.

4. Обработка нечисловых массивов

4.1. Упорядочение символьных данных

Мы с вами рассмотрели алгоритмы сортировки для числовых массивов. Не менее интересно применение этих методов и для нечисловых массивов. Таких, например, в которых записаны тексты. Такие массивы (тексты) мы уже умеем выводить. Для того, чтобы хранить тексты, нужно использовать массивы символьных данных (CHAR).

VAR C: CHAR; (CHARACTER – знак, символ, значок).

Значениями такой переменной являются символьные константы: ‘A’, ‘+’, ‘(‘, ‘.’, ‘1’ и т.д.

Можно записать:

С:= ‘(‘;

или

IF C=’(‘ THEN < действие>;

С = ‘(‘ – логическое выражение, значением которого является “истина” или “ложь”.

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

C < ‘O’, C<=’O’ или С<B (В – тоже переменная типа CHAR).

Каким образом сравниваются символьные данные? Для выяснения этого вопроса обратимся к их внутреннему представлению. Известно, что все символьные значения перенумерованы и представлены в ЭВМ своими номерами (кодами), то есть целыми числами. Так, например, код символа ‘0’ равен 48 (в кодировке ASCII), код символа ‘  ‘ равен 32 (меньше любого печатного символа).

Для записи кодов в памяти отводится 8 бит (1 байт). В них могут быть записаны числа:

0000 0000 = 0,

0000 0001 = 1,

0000 0010 = 2,

……….…

1111 1111 = 255 = 28-1

При сравнении символов сравниваются их коды. Поэтому  

‘    ‘ < ‘0’ - “истина”,

‘1’   > ‘0’ - “истина”.

В международной системе кодирования латинские буквы упорядочены.

‘A’ < ‘B’ < ‘C’ < ‘D’ < …< ‘Z’

48 –57 : 0 9

65 – 90 : A Z

97 –122 : a z

Отдельно упорядочиваются коды прописных и строчных букв.

Если имеем массив символьных данных

 VAR C1: ARRAY [1..100] OF CHAR;

то присвоив его элементам  некоторые значения, а потом упорядочив их, получим элементы, расставленные в порядке возрастания (убывания) кодов этих символов.

На практике часто используют строки символов. Интересен вопрос упорядочения этих строк: ‘ALFA’, ‘ABBA’ – какая из строк должна стоять раньше по алфавиту?

Используем принцип лексикографической упорядоченности (он используется в словарях). Формально этот принцип реализуется так:

два символа строки сравнивают с первой буквы слева направо так, что если очередные буквы равны, то сравнивают следующие по порядку буквы. Если очередная буква первого слова меньше той же буквы во втором слове, то считают, что первое слово меньше второго слова. Следовательно,

  ‘ABBA’ < ‘ALFA’.

Если одно из слов короче, то продолжим сравнение, дополняя короткое слово пробелами. В международной кодировке пробел меньше любой буквы. Поэтому

  ДОМ < ‘ДОМИК’.

Можно расширить область применения алгоритмов сортировки и поиска на массивы символьных строк. Для этого нужно рассматривать отдельные строки как одномерные массивы:

 VAR S: ARRAY [1..10] OF CHAR;

Для набора таких строк будем иметь двумерный массив

 VAR SM: ARRAY [1..1000, 1..10] OF CHAR;

Тогда нужно сравнивать весь массив S с какой-либо строкой матрицы SM.

Рассмотрим алгоритм сравнения двух символьных строк. Пусть С1, С2 – строки из 10 символов. Основой алгоритма является оператор цикла.

VAR C1, C2: ARRAY [1..10] OF CHAR;

                 I: INTEGER;

I:=1;

WHILE I<=10 AND C1[I]=C2[I] DO

I:=I+1;

Какое постусловие будет выполняться после завершения такого цикла? Возможны две ситуации:

  1.  строки равны между собой и тогда цикл завершится по условию I>10.
  2.  строки не равны; в этом случае найдется такое 1 ≤ I ≤ 10, что        С1[I] C2[I].

Объединяя обе ситуации в одно постусловие, получим

 (I>10) V (1≤ I ≤ 10 C1[I] C2[I]).

Причем, это значение I – наименьшее, для которого выполняется      C1[I] C2[I]. На основе этого постусловия делаем следующий вывод:

IF I>10

THEN строки равны

ELSE IF C1[I]<C2[I]

 THEN строка С1 меньше С2

 ELSE  строка С2 меньше С1

Применим алгоритм "пузырька" для сортировки символьных строк. Пусть N = 1000 – количество строк, причем  все строки разные. Тогда алгоритм можно записать в следующем виде (он несколько отличается от рассмотренного ранее, т.к. предполагает однократный просмотр последовательности строк).

VAR M: ARRAY [1..1000, 1..10] OF CHAR;

……………………………

J:=1;

WHILE J<N DO

BEGIN

I:=1;

WHILE I<=10 AND M[J, I] = M[J+1, I] DO

I:=I+1;

IF I<=10 AND M[J, I] < M[J+1, I]

THEN J:=J+1;

ELSE BEGIN {поменять местами строки}

FOR I:=1 TO 10 DO

BEGIN

C:=M[J, I];

M[J, I]:= M[J+1, I];

M[J+1, I]:=C;

END;

IF J<1

THEN J:=J-1;

ELSE  J:=J+1;

END

END;

Самостоятельно составьте:

  1.  алгоритм поиска в неупорядоченном массиве строк;
  2.  алгоритм поиска в упорядоченном массиве строк.

4.2. Строковый тип данных в Паскале

При решении задач на ЭВМ часто возникает необходимость в использовании строк, представляющих собой последовательность литер (символов). Мы знаем, что такие строки – константы применяются при печати заголовков, пояснений (комментариев) и т.д. Кроме задач вычислительного характера, где строки играют вспомогательную роль (как та, о которой упомянули), существует ряд задач, где строки литер (символов) являются основными объектами обработки. Это задачи лексического и синтаксического анализа программы, задача трансляции и т.д.

Вспомним, что строка-константа – это произвольная последовательность литер, заключенная в одиночные апострофы, например,

Таблица    значений    аргумента    и   функции

Если внутри литерной строки-константы (будем теперь называть ее строковой константой) нужно использовать литеру (апостроф), то она удваивается

 Д’’Артаньян

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

 packed array [1..N] of char;

PACKED ARRAY [1..N] OF CHAR;

то есть как упакованный одномерный массив, компонентами которого являются литеры. Часто такие массивы называют просто строками. При этом существенно, что N>1. То есть не существует пустых и однолитерных строк.

Строковый тип, как обычно, можно задавать двояко: либо в разделе типов, либо непосредственно при описании переменных:

 TYPE INFORM = PACKED ARRAY [1 .. 12] OF CHAR;

VAR STR1: INFORM;

 STR2: PACKED ARRAY [1 .. 12] OF CHAR;

Таким образом, переменные STR1 и STR2 имеют один и тот же тип и длину.

Все свойства массива переносятся и на строки. В частности, длина строки (количество компонент) определяется статически в задании типа. Значение полной переменной строкового типа определено, если определены значения всех ее компонент. Для ссылки на отдельные компоненты, как обычно, используют переменные с индексами, например,

STR1[4], STR2[12] и т.д.

Но есть и особые свойства, присущие только строкам.

  1.  Строковой переменной можно присвоить значение строковой константы, например,

 STR1:= ‘Язык     Паскаль

 STR2:=’LET    IT    BE!’

Так как пробел – тоже символ, им можно дополнять строку, чтобы придать значения неопределенным компонентам:

 STR1:=’Строка                 ‘;

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

=, <>, <, <=, >, >=.

Сравнение производится посимвольно слева направо. Пусть сравниваются два значения:

 ‘с1 с2 … с nи ‘d1 d2 … d n

Тогда

 ‘с1 с2 … с n’ = ‘d1 d2 … d n’,  если  с i = d i     i = 1, 2, … n.

‘с1 с2 … с n’ < ‘d1 d2 … d n’,  если k (0 < k < n), что с i = d i     i = 1, 2, … k,

но с k+1 < d k+1.

Аналогично

 ‘с1 с2 … с n’ > ‘d1 d2 … d n’,  если   k (0 < k < n), что с i = d i     i = 1, 2, … k,

но с k+1 > d k+1.

Строки различной длины сравнивать нельзя.

  1.  Значения строковых переменных можно сравнивать даже в том случае, если строковые типы имеют разные имена, но длины строк одинаковы. Например,

TYPE

STROKA = PACKED ARRAY [1 .. 9] OF CHAR;

SLOVO = PACKED ARRAY [1 .. 9] OF CHAR;

VAR

S1: STROKA;

S2: SLOVO;

S3: PACKED ARRAY [1 .. 9] OF CHAR;

T, R: BOOLEAN;

Тогда возможен следующий фрагмент программы:

S1:= ’АЛЕКСАНДР’;

S2:= S1;

S3:=’ЕКАТЕРИНА’;

T:= S2 = S1;

R:= S2 < S3;

В Турбо Паскале специально выделен строковый тип данных STRING. Переменные такого типа описываются, например, так:

VAR STR: STRING[14];

Строка – это последовательность символов произвольной длины (до 255 символов). Строку можно рассматривать как массив символов и выполнять операции над элементами строки как над элементами массива:

STR[5] := ‘+’;

STR[7]:= STR[1];

S:= STR[14]; {VAR S: CHAR}

Размер строки можно не указывать, тогда автоматически он считается равным 255 символам.

VAR MaxStr : STRING;

Можно описать константу строкового типа:

CONST January: STRING[10] = ‘Январь’;

В Турбо Паскале существует ряд операций над строками как над единым целым.

  1.  Строковой переменной можно присвоить значение строковой константы:

VAR STR, STR1, STR2: STRING[80];

STR1:= ‘Язык Паскаль’;

STR2:=’Let It Be’;

STR3:=’Yesterday’;

  1.  Значения строковых переменных можно сравнивать. Сравнение, как и в случае символьного массива, производится слева направо до первого несовпадения. Можно сравнивать строки разной длины. При этом отсутствующие символы в более короткой строке считаются пробелами (пробел меньше любого символа).

STR2 > STR2

Пусть VAR T, R: BOOLEAN; тогда возможны следующие операторы:

STR1:= ’АЛЕКСАНДР’;

STR2:=’ЕКАТЕРИНА’;

T:= STR2 = STR1;

R:= STR2 > STR1;

  1.  Конкатенация (объединение) двух строк. Обозначается символом ‘+’. Если

STR1:= ’Турбо ’;

STR2:= ‘Паскаль’;

STR:= STR1 + STR2; то значением STR является ‘Турбо Паскаль’.

Для работы со строками в Турбо Паскале предусмотрены следующие процедуры и функции.

Процедуры:

  1.  DELETE (S, Pos, L);

S – строка, Pos – номер первого удаляемого символа, L – число удаляемых символов.

Удаляет из строки S   L элементов, начиная с позиции Pos. 

  1.  INSERT (ST, S, Pos)

Вставляет подстроку ST в строку S, начиная с позиции Pos.

  1.  STR ( X, S);

X – выражение целого или вещественного типа,

S – строка.

Процедура преобразует число в X в последовательность символов S.

  1.  VAL ( S, V, Code);

S – строка,

V – переменная целого или вещественного типа.

Процедура преобразует строку символов S в число V (с представлением в двоичной форме).

Code – код ошибки:

0 – если представление числа правильное;

номер неправильного символа в случае ошибки.

Функции:

  1.  COPY ( S, Pos, L);

Выделяет в строке S подстроку длины L, начиная с позиции Pos.

 L, Pos – целые, S – строка, COPY: строка. Пусть

 S := ‘ABCDEFGH’;

S1 := COPY (S, 3, 4); тогда S1 = ‘CDEF’.

  1.  LENGTH (S) – целого типа

S – строка.

Функция определяет текущую длину строки S.

LENGTH (S) = 8;

При использовании данных типа STRING процедуры сортировки и поиска внешне ничем не отличаются от аналогичных процедур в числовых массивах.

4.3. Перекодировка символов

Перекодировка символов – это переход от одного набора кодов к другому. Для чего нужна перекодировка символов? Цель может быть различной. Например, сравнение строк, содержащих прописные и строчные буквы латинского и русского алфавитов. Чтобы не изменять ничего в самой строке, нужно научиться делать сравнение через другую систему кодов. Для этого нужно знать:

  1.  сколько имеется различных кодов для символов;
  2.  какие коды приписаны тем или иным символам.

Принятая в настоящее время для ПК в России 8-битовая система кодировки (1 байт) содержит 256 кодов (0 .. 255). При этом коды символов с номерами 32 – 127 соответствуют стандартным кодам ASCII (American Standard Code for Information Interchange). Коды символов от 128 до 241, включающие русские буквы и символы псевдографики, соответствуют так называемойальтернативнойкодировке. Коды букв в принятой системе следующие.

 A – Z : 65 – 95,

a – z  : 97 – 122,

 А – Я : 128 – 159, (А – П : 128 – 143, Р – Я : 144 – 159),

а – п :           160 – 175, р – я : 224 – 239,

Ё, ё :          240, 241,  Е, е: 133, 165.

Нам нужно отождествить все большие и малые буквы, а также буквы Е, е, Ё и ё. Для этой цели нужно завести таблицу перекодировки, которая представляет собой массив Т[0 .. 255]. Номер элемента массива Т соответствует старому коду, значение – новому коду.

При сравнении символов в Паскале фактически сравниваются их коды, выдаваемые функцией ord. Например, при сравнении С1<С2 сравниваются

 ord (C1) < ord (C2).

Чтобы сравнить коды в новой системе кодировки, будем сравнивать новые коды литер

 T [ord (C1)] < T [ord (C2)].

         символ

          старый код

         новый код

Для решения нашей задачи нужно таблицу перекодировки (массив Т) заполнить следующим образом. В приведенной таблице первая строка показывает значение элемента массива, вторая – его номер.

0

1

2

96

65

90

123

159

128

163

0

1

2

96

97

122

123

159

160

175

176

223

144

159

133

133

242

255

176

223

224

239

240

241

242

255

const T: array [0 .. 255] of Integer = (0, 1, 2, …);

С учетом перекодировки лексикографическое сравнение строк будет иметь следующий алгоритм.

FUNCTION SCOMP (VAR S1, S2: STRING): INTEGER;

VAR I,R,N1,N2: INTEGER;

BEGIN

N1:= LENGTH (S1);

N2 := LENGTH (S2);

R:=0;

I:=1;

WHILE (I<=N1) AND (I<=N2) AND ( T [ ORD ( S1[I] ) ] = T [ ORD          ( S2[I] ) ] ) DO

I:=I+1;

IF (I<N1) AND (I<N2) THEN

BEGIN

IF T [ ORD ( S1[I] ) ] < T [ ORD ( S2[I] ) ] THEN R:=-1;

ELSE R:=1;

END

ELSE

IF (I<N1) THEN R:=-1;

ELSE IF (I<N2) THEN R:=1

SCOMP:=R;

END;

Таким образом, результат равен:

0, если строки равны

-1, если S1 < S2,

1, если S1 > S2.

С помощью функции SCOMP мы можем организовать дихотомический поиск в упорядоченном массиве А строк из N элементов. Ищем значение A[I], равное строке P. Если такого значения нет, то I=0.

B:=1;  L:=N;  {временные границы}

WHILE B<L DO

BEGIN

C:= (B+L) DIV 2;

IF SCOMP (A[C], P) < 0

THEN B:=C+1;

ELSE  L:=C;

END;

IF SCOMP (A[B], P) =0

THEN I := B;

ELSE  I := 0;

Контрольные вопросы и задания

  1.  Какой принцип лежит в основе упорядочения символьных данных?
  2.  Оформите в виде процедуры алгоритм упорядочения символьных строк, заданных массивами символов.
  3.  Оформите в виде процедуры алгоритм поиска в неупорядоченном массиве символьных строк, заданных массивами символов.
  4.  Оформите в виде процедуры алгоритм поиска в упорядоченном массиве символьных строк, заданных массивами символов.
  5.  Что представляет собой строковый тип данных Паскаля?
  6.  Какие операции над строками допустимы в Паскале?
  7.  Назовите основные процедуры и функции для работы со строками в Паскале.
  8.  Напишите процедуру сортировки символьных строк методом простого обмена.
  9.  Напишите процедуру сортировки символьных строк методом простого выбора.
  10.   Напишите процедуру поиска заданной строки в неупорядоченном массиве символьных строк.
  11.   Напишите процедуру поиска заданной строки в упорядоченном массиве символьных строк.
  12.   Для каких целей используется и как осуществляется перекодировка символов?

5. Работа с нестандартными

и структурированными данными

5.1. Записи. Перечислимый и интервальный типы

      данных

       Мы рассмотрели типы данных, которые принято называть простыми (INTEGER, REAL, CHAR, BOOLEAN). Паскаль характерен тем, что имеет хорошо развитую концепцию типов данных, позволяющую создавать достаточно сложные структуры, объединяющие данные различных типов.

Подробное изучение структур данных предусмотрено дисциплиной "Структуры и алгоритмы обработки данных в ЭВМ" (для специальности 220400). Здесь же мы рассмотрим лишь основы структурирования данных

В частности, в Паскале существует возможность объединения компонент, принадлежащих разным произвольным типам, в один составной или комбинированный тип. Это так называемый производный тип Паскаля, называемый записью (RECORD). Записи часто используются при создании различного рода информационных систем.

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

- телефоны, дата рождения – целые числа;

- остальные данные – символьные строки.

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

Каждая запись содержит фиксированное число компонент, называемых ее полями. Каждому полю записи дается свое имя, и задается тип значения этого поля. При этом никаких ограничений на тип поля записи не накладывается, поэтому компонентой поля записи может быть в свою очередь тоже запись и т.д. Таким образом, значение комбинированного типа может иметь иерархическую структуру.

Остановимся на простейшем случае, когда структура, задаваемая комбинированным типом, имеет один уровень иерархии.

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

а + bi, где a, b- вещественные, i2 = -1.

Так как в Паскале нет соответствующего стандартного типа данных, то его можно создать, используя запись. Она будет содержать 2 поля:

  1.  действительная часть числа (значение а);
  2.  мнимая часть числа (значение b).

Каждое поле будет иметь тип REAL. Описание типа выглядит так:

 TYPE COMPL  = RECORD

     RE: REAL;

     IM: REAL;

    END;

Оно говорит о том, что любое значение типа COMPL есть структура данных, являющаяся записью, состоящей из двух компонент (полей), одной из которых дано имя RE, а другой IM, и каждая из компонент есть значение типа REAL. Описания, заключенные между служебными словами RECORD и END, образуют список полей, а каждое из описаний списка называется секцией записи. Более точное определение с помощью металингвистических формул:

<список полей>  ::= <секция записи>{;<секция записи>},

<секция записи> ::= <имя поля>{,<имя поля>}:<тип поля>.

В нашем описании список полей состоит из двух секций, разделенных символом ‘;’, а каждая секция определяет одно поле. Поскольку оба поля имеют один и тот же тип, их можно объединить в одну секцию записи:

TYPE COMPL  = RECORD

     RE, IM: REAL;

   END;

Теперь, как обычно, можно в разделе переменных ввести переменные типа COMPL, например,

VAR X, Y: COMPL;

X, Y называются полными переменными. Значением каждой из них является структура (запись). Чтобы присвоить этим переменным конкретное значение, нужно присвоить значения обеим компонентам структуры. Для ссылок на компоненты структуры используется частичная переменная вида

 <имя полной переменной>.<имя поля>

Например, мы хотим переменной Х присвоить значение 5.65 + 0.77i. Для этого надо задать значения полям с именами RE и IM:

 X.RE := 5.65;

 X.IM := 0.77;

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

 Y := X;

Для полных переменных существует только одна операция – присваивание.

Пример. Программа вычисления суммы, разности и произведения двух комплексных чисел: U = X+Y, W = X-Y, V=X*Y, где X, Y, U, W, V – комплексные переменные.

PROGRAM COMPLAR (INPUT, OUTPUT);

TYPE COMPL = RECORD RE, IM: REAL; END;

VAR X, Y, U, W, V: COMPL;

BEGIN

READ (X.RE, X.IM, Y.RE, Y.IM);

U.RE := X.RE + Y.RE; U.IM :=X.IM +Y.IM;

W.RE:= X.RE  - Y.RE; W.IM:=X.IM - Y.IM;

V.RE := X.RE*Y.RE – X.IM*Y.IM;

V.IM := X.RE*Y.IM + X.IM*Y.RE;

WRITELN (‘X+Y= ’, U.RE,’+’, U.IM, ’*i’);

WRITELN (‘X-Y= ‘, W.RE, ‘-‘, W.IM, ‘*i’);

WRITELN (‘X*Y= ‘, V.RE, ‘*’, V.IM, ‘*i’)

END;

В общем случае комбинированный тип определяется следующим образом.

TYPE

T = RECORD

S1: T1;

S2: T2;

…….

Sn: Tn;

END;

Здесь S1, …, Sn имена компонент (полей) записи, T1, …, Tn – их типы. Типы полей могут быть самые разные, например,

TYPE DATE = RECORD

DAY: 1 .. 31;

MON: (JAN, FEB, APR, MAR, MAY, JUN, JUL, AUG, SEP, OCT, NOV, DEC);

   YEAR: INTEGER;

  END;

Здесь в списке полей описания присутствуют, кроме известного нам стандартного простого типа данных INTEGER, два так называемых простых нестандартных типа.

  1.  (JAN, FEB, APR, MAR, MAY, JUN, JUL, AUG, SEP, OCT, NOV,

DEC) – скалярный или перечисляемый (перечислимый) тип данных. При определении этого типа просто перечисляют все возможные значения переменных этого типа.

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

Над переменными перечислимого типа можно выполнять только операции отношения. При этом считается, что значения упорядочены в соответствии с порядком их следования в списке описания типа. То есть

 FEB < OCT,

APR > JAN, и т.д.

Для данных перечислимого типа (так же, как и для целых) определены стандартные функции

 PRED (<аргумент>) – предшествующий элемент (PREDECESSOR – предшественник);

 SUCC(<аргумент>) – последующий элемент (SUCCESSOR – преемник). Например,

 PRED (JUN) = MAY;

SUCC (FEB) = MAR;

Если к данным перечислимого типа применить функцию ORD, то получим порядковый номер этого значения в списке определения перечислимого типа (номер первого элемента равен 0). Таким образом,

 ORD (MAR) = 2.

Данные перечислимого типа нельзя использовать в операторах READ и WRITE (в списке ввода-вывода).

Можно организовать цикл, например,

 FOR K:=MAR TO DEC DO <оператор> 

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

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

Этот тип данных мы используем при описании массива: тип индекса – всегда интервальный, с целыми границами.

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

Возвращаясь к нашему примеру, мы можем ввести в употребление некоторую переменную типа DATE

VAR D: DATE;

Чтобы определить значение этой переменной, нужно присвоить значения всем ее полям (то есть всем частичным переменным), например:

 D.DAY:=1;

D.MON:=MAR;

D.YEAR:=1990;

Используя приведенные описания, можно решить, например, следующую задачу. Пусть требуется определить число дней в месяце для любого года. Тогда надо описать еще одну переменную интервального типа:

 VAR NDAY: 28 .. 31;

Фрагмент программы, решающей нашу задачу, будет выглядеть так:

IF (D.MON = SEP) OR (D.MON = NOV) OR (D.MON =APR) OR (D.MON =JUN)

THEN NDAY:=30

ELSE IF (D.MON <> FEB)

 THEN NDAY:=31

ELSE IF (D.YEAR MOD 4 = 0) AND (D.YEAR MOD 100 <> 0) OR (D.YEAR MOD 400 = 0)

THEN NDAY := 29

ELSE  NDAY := 28;

(Високосным считается каждый год, число которого делится на 4, кроме годов, числа которых оканчиваются на два нуля, но не делятся на 4: 1700, 1800 и т.д.)

5.2. Множества

Кроме массивов и записей в Паскале имеется еще одна фундаментальная структура данных: множество. В математике это одно из основных понятий. Необходимость введения множественного типа возникает при решении ряда задач, в которых упорядоченность элементов массива в соответствии с их местоположением (индексом) является излишне строгим требованием к структуре данного.

Пусть, например, выигрышные номера в игре "3 из 15" – 3, 7, 11. При этом неважно, в каком порядке назовет их игрок: 7, 11, 3 или 11, 3, 7. В любом случае они будут угаданы. Если же рассматривать эти последовательности как массивы, то они будут разными, так как нарушен порядок их взаимного расположения (задачу можно решать и через массивы, но алгоритм будет длиннее). Для определения таких данных удобно использовать множественный тип.

Служебное слово для описания такого типа: SET (множество). Множество – любой неупорядоченный набор объектов одного типа. Объекты называют элементами множества. Тип объектов, из которых состоит множество, называют базовым типом. На базовый тип в Паскале накладывается ограничение: это может быть любой простой (скалярный) тип, кроме REAL, то есть INTEGER, CHAR, BOOLEAN, интервальный и перечислимый. В практических реализациях языка возможны и другие ограничения, например, на число элементов множества.

Определение типа выглядит так:

 TYPE <имя> = SET OF <базовый тип>;

Пример.

CONST  OGR = 15;

TYPE VID = 1 .. OGR;

       LOTOCART = SET OF VID;

VAR POSL1, POSL2 : LOTOCART;

Здесь базовый тип задается как интервальный. Переменные POSL1 и POSL2 – два множества, элементами которых могут быть целые числа из ограниченного диапазона от 1 до 15.

Значения переменных множественного типа задаются как заключенные в квадратные скобки последовательности выражений базового типа, отделяемые друг от друга запятыми. Так, для нашего примера значениями переменных POSL1 и POSL2 могут быть такие конкретные множества:

 [1, 7, 11, 5] - множество из четырех элементов,

 [13, 15] - множество из двух элементов,

 [9]  - множество из одного элемента,

 []  - пустое множество.

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

Над переменными множественного типа могут выполняться те же операции, что и над множествами. При этом знаки операций:

+ - объединение множеств,

* - пересечение множеств,

  -  - разность множеств.

Операции отношения:

= - равенство множеств (совпадение их элементов);

 <> - неравенство множеств;

 >= - множество содержит  операции

 <= - множество содержится включения

Удобной операцией для данных множественного типа является операция IN – проверка на принадлежность элемента множеству. Это двуместная операция. В ней первый операнд – базового типа, а второй – множественного. Результат операции равен TRUE, если первый операнд является элементом второго и FALSE – в противном случае. Эта операция помогает в программе обходиться без проверки длинных и сложных условий. В отличие от множества, для проверки вхождения какого-либо элемента в массив нужно сравнивать его со всеми элементами массива.

Ранги операций над множествами:

+, - - тот же, что и для операции сложения,

* - тот же, что и  для операции умножения.

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

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

Рассмотрим несколько примеров выражений с данными множественного типа (множественных выражений):

 [1, 2, 5, 6, 7]*[2 .. 6] + [3, 9]   равно [2, 3, 5, 6, 9],

( [3, 4, 5] + [1, 3, 6, 7] ) * [5 .. 7] – [6]  равно [5, 7].

Пусть множественный тип задан как SET OF 1 .. 3. Тогда значениями переменной этого типа являются

 [ ], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3].

Если множество задано как SET OF BOOLEAN, то этот тип определяет совокупность значений:

 [ ], [TRUE], [FALSE], [TRUE, FALSE].

Пусть переменная М описана как SET OF 1 ..10 и выполнен оператор

 M := [2, 3, 5, 7];

Тогда возможны выражения

 6 in M    - равно FALSE

[3, 5, 7] <= M   - равно TRUE

M = [1, 2, 3, 7]   - равно FALSE

[ ] <= M    - равно TRUE

(7 in M) and ([7] <= M)  - равно TRUE

В большинстве версий языка Паскаль в процедуре WRITE нельзя называть переменные множественного типа.

       

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

Пример 1. В заданной последовательности символов (литер), состоящей из букв латинского алфавита и оканчивающейся точкой, определить общее число вхождений в нее букв A, E, C, H.

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

PROGRAM COUNT (INPUT, OUTPUT);

VAR

CHISBK: INTEGER;

LITERA: CHAR;

BEGIN

CHISBK := 0;

READ  (LITERA);

WHILE LITERA <> ‘.’ DO

BEGIN

IF LITERA IN [‘A’, ’E’, ‘C’, ‘H’]

THEN CHISBK:=CHISBK+1;

READ (LITERA);

END;

WRITELN (‘Общее число вхождений равно : ’CHISBK’)

END.

Пример 2. Найти и напечатать в убывающем порядке все простые числа из диапазона 2 .. 201.

Существует метод, называемый "решето Эратосфена" и заключающийся в следующем. Из последовательности чисел вычеркивают числа, делящиеся на 2, затем на 3, на 5 и т.д., пока не кончится последовательность. Мы используем его в следующем варианте. Пусть No – множество анализируемых чисел, Pr – множество простых чисел. Начальные значения множеств:

 No = [2, 3, 4, 5, 6, 7, 8, 9, 10, …, 201],

Pr = [].

Рассмотрим первое число из No. Это 2 – простое число. Заносим его в Pr, а из No удаляем 2 и все числа, делящиеся на 2. Тогда получим

 No = [3, 5, 7, 9, 11, … , 201],

Pr = [2].

Теперь из No берем наименьшее число 3 – оно простое – и добавляем его в Pr, а из No удаляем 3 и все числа, кратные трем. Получим

 No = [5, 7, 11, … , 199]

Pr = [2, 3]

В конце концов, множество No станет пустым, а в Pr перейдут все простые числа. Остается их просмотреть и напечатать в порядке убывания.

Удаление и добавление чисел запишется с помощью операторов

 No :=No – [K];

Pr := Pr  + [K];

а вся программа:

PROGRAM PROSTCHIS (OUTPUT);

CONST

N = 201;

TYPE

MNOCHIS = SET OF 2 .. N;

VAR

Pr, No : MNOCHIS

P,K: 2 .. N;

BEGIN

No:= [2 .. N];   - присвоение начальных значений;

Pr := [ ];

P:=2;       - первое простое число;  REPEAT

WHILE NOT (P IN No) DO P:= P+1; - выбор в No наименьшего числа;

Pr:=Pr+[P];        - занесение найденного числа в Pr;

K:=P;

REPEAT

No:=N-[K];       - удаление из No числа Р и всех кратных  ему,     

K:=K+P;

UNTIL K>N;

UNTIL No = [ ];

FOR K:=N DOWNTO 2 DO  - печать простых чисел в

IF K IN Pr THEN WRITE (K);    обратном порядке

WRITELN;

END.

5.3. Файловые типы данных

Мы знаем, что в ЭВМ происходит постоянный обмен информацией между внутренней памятью ЭВМ и внешними устройствами (терминалами). Свойства этих устройств различны. Различен и характер информации, которая поступает в ЭВМ. Одни наборы данных настолько велики, что поместить их целиком в оперативной памяти ЭВМ невозможно. Другие данные не могут быть полностью помещены в память компьютера, так как они порождаются в процессе работы программы. Запись информации на внешний носитель особенно желательна, если объем информации велик и если в дальнейшем предполагается использовать эту информацию в других программах. Поэтому, естественно, нужны языковые средства, позволяющие одинаковым образом работать с разными наборами данных. Таким средством в Паскале является файловая структура данных.

5.3.1. Определения

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

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

Файл – это последовательность компонент одного и того же типа, причем количество компонент в файле заранее не оговаривается, компоненты файла не имеют индексов. До некоторой компоненты можно “добраться”, только перебрав все предыдущие. Вспомним задачу сортировки. Карточки лежат стопкой на столе, открыта только верхняя. Слово “файл” в переводе означает “картотека”, “подшивка”.

Условно файл можно изобразить как некоторую ленту, у которой есть начало, а конец не фиксируется. Элементы файла записываются на ленту последовательно друг за другом:

f

Здесь fимя файла, f1 , f2 , f3 , …– его элементы. Файл во многом напоминает магнитную ленту, начало которой заполнено записями песен, а конец свободен. Новую песню можно поместить только после последней. Аналогично новые элементы файла могут быть записаны только в его конец.

В программировании существует несколько разновидностей файлов, отличающихся способом доступа к компонентам файла. Мы рассмотрим простейший из способов доступа, состоящий в том, что по файлу можно двигаться только последовательно, начиная с первого элемента. Т.е. чтобы дойти, например, до пятого элемента файла, необходимо, начав с первого элемента, пройти через предыдущие четыре. Такие файлы называются файлами последовательного доступа или последовательными файлами. У последовательного файла доступен всегда лишь очередной его элемент. Если в ходе выполнения программы необходим какой-либо из предыдущих элементов, то нужно вернуться в начало файла и последовательно пройти все его элементы до нужного.

Файловый тип в Паскале – это единственный тип значений, посредством которого данные, обрабатываемые программой, могут быть получены извне, а результаты могут быть переданы во внешний мир. Это единственный тип значений, который связывает программу с внешними устройствами ЭВМ.

Длиной файла называется число записанных в нем компонент. Файл с нулевой длиной (не содержащий компонент) называют пустым.

Файловый тип данных описывается в программе на Паскале следующим образом:

TYPE <имя типа> = FILE OF < тип компонент>;

<имя типа> - произвольный идентификатор,

< тип компонент> - любой тип Паскаля, кроме файлового, а также

кроме типа, содержащего в себе файловый тип.

Переменные файлового типа описываются обычным образом. Например:

1. TYPE N = FILE OF REAL;

   VAR F : N;

2. TYPE TEX = FILE OF SET OF CHAR;

   VAR I, O : TEX;

3. TYPE morze = (point, dash);

   TYPE informat = FILE OF morze;

   VAR telegram : informat;

В Турбо Паскале можно использовать файл без типа, при определении которого не указывается тип компонент. В этом случае работа с файлом осуществляется на физическом уровне в соответствии с внутренним форматом его данных. При этом реальные компоненты файла могут иметь различный тип. Определение нетипизированного файла:

TYPE untyp = FILE;

Файловый тип может быть непосредственно задан при описании переменных в разделе переменных:

VAR letter : FILE OF CHAR;

 5.3.2. Общие процедуры и функции

Каждый тип данных в Паскале определяет некоторое допустимое множество значений и множество операций над ними. Над значениями файлового типа в стандарте языка Паскаль не определены никакие операции, в том числе операции присваивания или сравнения. Все операции можно производить только с компонентами (элементами) файла. Поэтому множество операций определяется типом компонент.

Для доступа к отдельным компонентам файла в Паскале введены специальные процедуры. Чтобы пояснить их действие, введем понятие “окно”, аналогичное понятию “указатель”. Окно определяет позицию доступа, т.е. ту позицию файла, которая доступна для чтения или записи. Позиция, следующая за последней компонентой файла, помечается специальным маркером, определяющим конец файла. Если файл пустой, то помечается его первая позиция.

        Процедура REWRITE (f) устанавливает файл с именем f в начальное состояние режима записи, т.е. окно устанавливается на первую позицию файла, и файл переходит в режим записи. Если в файле были записаны ранее какие-либо элементы, то они становятся недоступными:

f

         Процедура WRITE (f, x) записывает в файл с именем f (в ту позицию, на которую указывает окно) очередную компоненту, равную значению выражения x, после чего окно сдвигается на следующую позицию файла. При этом тип выражения x должен совпадать с типом компонент файла f.

f      f

Состояние файла f до    Состояние файла f после

выполнения процедуры   выполнения процедуры

С помощью этих двух процедур осуществляется запись компонент в файл. Процедуру REWRITE (f) можно применять к одному и тому же файлу сколько угодно раз.

        Процедура RESET (f) переводит файл f в режим чтения и устанавливает окно для чтения в первую позицию файла:

f

         Процедура READ (f, v) присваивает переменной v значение текущей компоненты файла f (той, на которую указывает окно) и передвигает окно на следующую позицию файла. Т.е. считывает одну компоненту.

f         v

Состояние файла f и переменной v до выполнения процедуры

f         v

Состояние файла f и переменной v после выполнения процедуры

Чтение с помощью процедуры READ (f,v) можно производить только после выполнения RESET (f), т.е. после установки файла в режим чтения.

Замечание. Работа с каждым файлом может происходить либо только в режиме записи, либо только в режиме чтения. Использовать один и тот же файл одновременно и для записи, и для чтения нельзя!

В большинстве задач с файлами необходимо последовательно перебрать все компоненты и произвести определенную их выборку. Поэтому обычно возникает необходимость определить, указывает ли окно на какую-либо компоненту файла или оно уже вышло за пределы файла и указывает на маркер в конце файла.

Для определения этого факта в Паскале существует стандартная логическая функция EOF (f) (end of file). Её значения:

TRUE – если окно указывает на маркер конца файла f ;

FALSE – в противном случае.

Если значение EOF (f) равно TRUE, то обращение к процедуре READ недопустимо, т.е. приведет к ошибке.

Пример 1. Имеется символьный файл. Вывести из него все заглавные латинские буквы.

PROGRAM word (SYMB, OUTPUT);

TYPE V=FILE OF CHAR;

VAR SYMB: V; S: CHAR;

BEGIN RESET (SYMB);

 WHILE NOT EOF(SYMB) DO

 BEGIN READ (SYMB, S);

  IF (S<=’Z’) AND (S>=’A’)

  THEN WRITELN (S)

 END

END.

В Турбо Паскале операции над файлами полностью реализованы в виде стандартных процедур и функций, которые можно разбить на четыре группы.

  1.  Установочные и завершающие операции.
  2.  Собственно ввод-вывод.
  3.  Перемещения по файлу.
  4.  Специальные операции.

Рассмотрим операции каждой из этих групп.

  1.  Установочные и завершающие операции

       Стандартная процедура ASSIGN (f, name) устанавливает связь между конкретным физическим файлом на диске и переменной файлового типа, являющейся представителем этого файла в программе. Здесь

f – имя файловой переменной,

name – строковое выражение, образующее символическое имя файла.  Оно строится по правилам MS-DOS и может, например, включать в себя путь к нужному файлу.

Примеры:

  1.  ASSIGN (f, ‘d:\mydir\myfile.dta’);
  2.  VAR  f: FILE OF REAL;

n: STRING;

WRITE (‘введи имя файла’);

READLN (n);

ASSIGN (f, n).

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

Процедуры RESET, REWRITE уже известны. Перед их выполнением файловая переменная должна быть связана с конкретным дисковым файлом с помощью процедуры ASSIGN.

Выполнение этих процедур подразумевает поиск файла на внешнем носителе, образование специальных системных буферов для обменов с ним и установку текущего указателя файла на его начало (т.е. на нулевой элемент).

Процедура CLOSE (f) завершает действия с файлом. При этом ликвидируются внутренние буфера, образующиеся при открытии этого файла. После этого файловую переменную f можно связывать с каким-либо другим дисковым файлом, если это нужно.

2. Собственно ввод-вывод

К этой группе операций относятся уже известные нам процедуры READ и WRITE. Они могут вызываться с различным числом параметров, имеющих различные типы (для текстовых файлов).

3. Перемещения по файлу

Эта группа содержит две процедуры и три функции.

Процедуры:

 SEEK (f, num)устанавливает окно (указатель) файла f на позицию с номером num. После выполнения процедуры SEEK дальнейшие операции чтения и записи производятся с этой позиции;