Способы записи алгоритмов. (Учебник: информатика 8 кл./авторы: Л.Л. Босова, А.Ю. Босова)

 2.2. СПОСОБЫ ЗАПИСИ АЛГОРИТМОВ

Существуют различные способы записи алгоритмов.

Основными среди них являются:
• словесные;
• графические;
• на алгоритмических языках.

Андрей Андреевич Марков (младший), 1903-1979.

Алгоритмы должны содержать предписание двух видов:

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

Словесное описание.

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

Построчная запись.

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

- каждое предписание записывается с новой строки;

- предписания (шаги) алгоритма нумеруются;

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

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

БЛОК-СХЕМА представляет собой графический документ, дающий представление о порядке работы алгоритма.

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

Алгоритмические язык – формальные языки, предназначенные для записи алгоритмов.

            Каждый из них характеризуется:

- Алфавитом – набором используемых символов;

- Синтаксисом – системой правил, по которым из символов алфавита образуются правильные конструкции языка;

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

Школьный алгоритмический язык.

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

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

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

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

нач

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

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

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

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

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

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

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

кон

ЗАДАЧА № 5. Представьте в виде построчной записи алгоритм решения следующей задачи: «Имеются четыре арбуза различной массы. Как, пользуясь чашечными весами без гирь, путём не более пяти взвешиваний расположить                  их по возрастанию веса?».

1.      Начало.

2.      Обозначим арбузы цифрами 1, 2, 3, 4. Нужно сравнить их вес.

3.      Сравнить по весу 1 пару арбузов: взвесить 1 и 2, определить 1 > 2 или 2 > 1 (взвешивание 1).

4.      Сравнить по весу 2 пару арбузов: взвесить 3 и 4, определить 3 > 4 или 4 > 3 (взвешивание 2).

5.      Сравнить более тяжёлый арбуз из 1 пары (п.3) с более тяжёлым арбузом                из 2 пары (п.4) – это позволит найти самый тяжёлый арбуз. (взвешивание 3).

6.      Сравнить более лёгкий арбуз из 1 пары (п.3) с более лёгким арбузом из 2 пары (п.4) – это позволит найти самый лёгкий арбуз. (взвешивание 4).

7.      Сравнить два оставшихся арбуза – в зависимости от результатов взвешивания они получат второе и третье места. (взвешивание 5).

8.      Расставить арбузы в порядке возрастания веса от самого лёгкого до самого тяжёлого.

9.      Конец. (работа была выполнена за 5 взвешивания).

ЗАДАЧА № 6. Представьте с помощью блок-схемы алгоритм решения следующей задачи: «Из трёх монет одинакового достоинства одна фальшивая (более лёгкая). Как её найти с помощью одного взвешивания на чашечных весах без гирь?».

Задача № 7. Запишите на алгоритмическом языке алгоритм построения окружности заданного радиуса r, проходящей через заданные точки А и В.

алг построение окружности

нач

Задать радиус r на циркуле и зафиксировать его

Построить окружность радиусом r с центром в точки А

Построить окружность радиусом r с центром в точки В

Определить точку пересечения окружностей

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

кон

ЗАДАНИЕ 9.

Андре́й Андре́евич Ма́рков

 (9 [22] сентября 1903, Санкт-Петербург – 11 октября 1979, Москва) – советский математик, сын известного русского математика А. А. Маркова, основоположник советской школы конструктивной математики.

Окончил 8 Петроградскую гимназию в 1919 году.  В 1924 году -Ленинградский государственный университет. В 1928 году аспирантуру в Астрономическом институте.

Учёная степень доктора физико-математических наук присвоена без защиты диссертации                     в 1935 году. Член-корреспондент АН СССР с 1953 года.

В 1933-1955 годах работал в Ленинградском университете (с 1936 г. – профессор):                         с 1936 по 1942 год и с 1943 по 1953 год – заведующий кафедрой геометрии. До июля 1942 года находился в блокадном Ленинграде.

С 1959 по 1979 год – заведующий кафедрой математической логики Московского государственного университета.

Одновременно в 1939-1972 работал  в Математическом институте имени Стеклова АН СССР.

В 1950-х годах создал  в Вычислительном Центре АН СССР лабораторию математической логики и структуры машин, которой руководил около двадцати лет.

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

Доказал неразрешимость проблемы равенства в ассоциативных системах (1947), проблемы гомеоморфии в топологии (1958), создал школу конструктивной математики и логики в СССР, автор понятия нормального алгоритма.

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

            СЛОВЕСНОЕ ОПИСАНИЕ является запись алгоритма в виде набора высказываний на обычном разговорном языке, а ФОРМАЛЬНЫЙ ЯЗЫК (алгоритмический язык), предназначенный для записи алгоритмов, характеризуется:

- Алфавитом – набором используемых символов;

- Синтаксисом – системой правил, по которым из символов алфавита образуются правильные конструкции языка;

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

Скачано с www.znanio.ru