Е

Е.П. Емельченков, В.И. Мунерман, Т.А.Самойлова, В.Н.Федоров

Раздел 2. Информация. Алгоритмы. Первые шаги программиста.

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

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

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

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

Рис. 36
Другим способом записи алгоритмов является их графическое представление в виде блок-схем. Этот способ очень широко использовался до середины шестидесятых годов. Блок-схемы более наглядны и строги, чем словесная запись. Алгоритм из примера 8, представленный в виде блок-схемы приведен на рисунке 36.

Блок-схема всегда начинается специальным блоком

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

Прямоугольник имеет единственный вход и единственный выход.

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

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

Блок-схемы долго служили программистам, но их очевидные недостатки требовали разработки более совершенных способов описания алгоритмов. В числе недостатков блок-схемы – ее слабая информативность. Невозможно вместить в небольшой прямоугольник сколь-нибудь содержательный текст, приходится прибегать к сокращениям, записывать формулы без комментариев, что усложняет понимание алгоритма. Блок-схема хороша, когда она располагается на одном, сравнительно небольшом листе бумаги. Стоит ей перейти на другой лист, как чтение ее становится чрезвычайно трудным занятием, поскольку читать приходится во всех направлениях вдоль и поперек.

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

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

Описание любого алгоритма начинается заголовком, в котором

дается краткое описание реализуемого этим алгоритмом действия.

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

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

алг Алгоритм поиска простых чисел "Решето Эратосфена"

Единственное требование к заголовку алгоритма - это краткость в сочетании с понятностью.

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

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

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

Целые	Вещественные
0	*-120.0*
-3	*120.0*
*16737*	*2.7´10³***

Число 2.7´10³=2700 записано в экспоненциальной форме. В языках программирование основание системы счисления (в нашем примере 10), обычно, заменяют буквой Е (2.7´Е³).

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

Например, 'Например'- это строка символов и 'это строка символов' - тоже строка. Строкой символов может быть любая подсказка, например, 'Нажмите Esc для завершения или F1 для получения справки'.

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

Для задания типа данных мы используем выделенные слова цел, вещ и лит.

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

Треугольник со сторонами a, b, c разделен на два треугольника биссектрисой угла, противоположного стороне c. Найти отношение периметров этих треугольников, если сторона b в два раза больше стороны a.

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

1. Биссектриса делит сторону треугольника на отрезки, пропорциональные двум другим его сторонам.

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

где a₁ и b₁ отрезки на которые биссектриса делит сторону с.

На псевдокоде алгоритм имеет следующий вид.

алг Вычисление отношения периметров треугольников