Урок 17

---

 

 

                                           Словесные способы записи алгоритм

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

Пример 1. Словесное описание алгоритма нахождения наибольшего общего делителя (НОД) пары натуральных чисел (алгоритм Евклида).

Чтобы найти НОД двух чисел, составьте таблицу из двух столбцов и назовите столбцы X и У. Запишите первое из заданных чисел в столбец X, а второе — в столбец У. Если данные числа не равны, за­мените большее из них на результат вычитания из большего числа меньшего. Повторяйте такие замены до тех пор, пока числа не ока­жутся равными, после чего число из столбца X считайте искомым результатом.

Построчная запись. Это запись на естественном языке, но с со­блюдением некоторых дополнительных правил:

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

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

Пример 2. Построчная запись алгоритма Евклида.

1. Обозначить первое из заданных чисел X, второе обозначить У.
2. Если X = У, то перейти к п. 8.
3. Если X > У, то перейти к п. 4, иначе перейти к п. 6.
4. Заменить X на X - У.
5. Перейти к п. 2.
6. Заменить У на У - X.
7. Перейти к п. 2.
8. Считать X искомым результатом.

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

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

2.2.2. Блок-схемы

Наилучшей наглядностью обладают графические способы записи алгоритмов; самый распространённый среди них — блок-схема.

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

Рассмотрим некоторые условные обозначения, применяемые в блок-схемах.

Выполнение алгоритма всегда начинается с блока начала и окан­чивается при переходе на блок конца (рис. 2.2, а). Из начального блока выходит одна линия связи; в конечный блок входит одна ли­ния связи.

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

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

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

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

 

Рис. 2.2. Обозначения на блок-схемах

Пример 3. Запись алгоритма Евклида с помощью блок-схемы (рис. 2.3).

 

 

 

Рис. 2.3. Запись алгоритма Евклида с помощью блок-схемы

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

2.2.3. Алгоритмические языки

Алгоритмические языки — формальные языки, предназначен­ные для записи алгоритмов. Каждый из них характеризуется:

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

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

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

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

алг  <название   алгоритма>

 нач

<последовательность   команд>

кон

Пример 4. Алгоритм, позволяющий из полного сосуда ёмкостью 12 л отлить половину, пользуясь двумя пустыми сосудами ёмкостью 8 и 5 л.

алг переливания

нач

наполнить сосуд ёмкостью 8 л из сосуда ёмкостью 12 л

наполнить сосуд ёмкостью 5 л из сосуда ёмкостью 8 л

вылить всё из сосуда ёмкостью 5 л в сосуд ёмкостью 12 л

вылить всё из сосуда ёмкостью 8 л в сосуд ёмкостью 5 л

наполнить  сосуд ёмкостью 8 л из сосуда ёмкостью 12 л

долить из сосуда ёмкостью 8 л в сосуд ёмкостью 5 л

вылить всё из сосуда ёмкостью 5 л в сосуд ёмкостью 12 л

кон

По ссылке http://www.niisi.ru/kumir/ вы можете скачать систему КуМир (Комплект учебных Миров), в которой используется школьный алгоритмический язык, со встроенными исполнителями Робот, Чертёжник, Водолей и др. Кумир работает в операционных системах Windows и Linux.

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

САМОЕ ГЛАВНОЕ

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

Вопросы и задания

1. Ознакомьтесь с материалами презентации к параграфу, содержащейся в электронном приложении к учебнику. Что вы можете сказать о формах представления информации в презентации и в учебнике? Какими слайдами вы могли бы дополнить презентацию?
2. Каковы основные способы записи алгоритмов?
3. Чем вызвано существование многих способов записи алгоритмов?
4. Дайте словесное описание алгоритма сложения двух обыкновенных дробей а/Ь и c/d.
5. Представьте в виде построчной записи алгоритм решения следующей задачи:  «Имеются четыре арбуза различной массы. Как, пользуясь чашечными весами без гирь, путём не более пяти взвешиваний расположить их по возрастанию веса?».
6. Представьте с помощью блок-схемы алгоритм решения следующей задачи: «Из трёх монет одинакового достоинства одна фальшивая (более лёгкая). Как её найти с помощью одного взвешивания на чашечных весах без гирь?».
7. Запишите на алгоритмическом языке алгоритм построения окружности заданного радиуса г, проходящей через заданные точки А и Б.
8. В среде КуМир запишите и выполните алгоритм переливаний (пример 4) для исполнителя Водолей.
9. Подготовьте    краткую    биографическую    справку    о    Маркове А. А. (младшем).