Урок №14. Свойства алгоритма. Способы записи алгоритма.
Есть три свойства, которыми обладают все алгоритмы. Это значит, что если какое-то описание действий не обладает хотя бы одним из этих свойств, то это уже не алгоритм.
1. Дискретность — алгоритм состоит из отдельных команд, каждая из которых выполняется ограниченное (не бесконечное) время.
2. Понятность — алгоритм содержит только команды, входящие в систему команд исполнителя, для которого он предназначен.
3. Определённость — при каждом выполнении алгоритма с одними и теми же исходными данными должен быть получен один и тот же результат. Другими словами, исполнитель должен однозначно понимать команду и последовательность выполнения команд и выполнять их каждый раз одинаково.
Алгоритмы часто используются для решения массовых задач, т. е. задач, которые нужно уметь решать при разных исходных данных. Примеры таких задач: найти наибольшее из двух чисел; подсчитать количество слов в тексте и т. п. В таких случаях иногда говорят ещё о некоторых дополнительных свойствах алгоритмов.
4. Конечность (результативность) — для любых допустимых исходных данных алгоритм должен заканчиваться с некоторым результатом. Если задача не имеет решения, алгоритм должен остановиться и сообщить об этом.
5. Корректность — для любых допустимых исходных данных алгоритм должен приводить к правильному решению задачи.
6. Массовость — алгоритм можно использовать для решения множества однотипных задач с различными исходными данными (при этом писать алгоритм заново не нужно!). Поэтому обычно для составления алгоритма задачу надо решить «в буквах», вводя имена для исходных данных.
Подчеркнём, что в отличие от свойств 1-3 свойства 4-6 — необязательные. Они выполняются не для всех алгоритмов. Например, при некоторых исходных данных работа алгоритма может никогда не заканчиваться. В этом случае результат работы алгоритма не определён; говорят, что алгоритм зациклился.
Обычно алгоритмы сравнивают по времени выполнения или по количеству действий. При этом лучшим считается тот алгоритм, который быстрее приводит к правильному результату (требует меньше действий исполнителя). Кроме того, нужно учитывать ещё и количество памяти, которое требуется для работы алгоритма. Поэтому выбор алгоритма зависит от особенностей задачи, которую вы решаете.
Пример
Рассмотрим один из методов нахождения всех простых чисел, не превышающих некоторое натуральное число п. Этот метод называется «решето Эратосфена» по имени предложившего его древнегреческого учёного Эратосфена (III в. до н. э.).
Для нахождения всех простых чисел, не больших заданного числа п, следуя методу Эратосфена, нужно выполнить такие шаги:
- Выписать подряд все натуральные числа от 2 до п (2, 3, 4, …, п).
- Заключить в рамку 2 — первое простое число.
- Вычеркнуть из списка все числа, делящиеся на последнее найденное простое число.
- Найти первое неотмеченное число (отмеченные числа — зачёркнутые числа или числа, заключённые в рамку) и заключить его в рамку — это будет очередное простое число.
- Повторять шаги 3 и 4 до тех пор, пока не останется неотмеченных чисел.
Рассмотренная последовательность действий является алгоритмом, так как она удовлетворяет свойствам:
- дискретности — процесс нахождения простых чисел разбит на шаги;
- — каждая команда понятна ученику 8 класса, выполняющему этот алгоритм;
- определённости — каждая команда трактуется и выполняется исполнителем однозначно; имеются указания об очерёдности выполнения команд;
- результативности — через некоторое число шагов достигается результат;
- массовости — последовательность действий применима для любого натурального п.
Рассмотренные свойства алгоритма позволяют дать более точное определение алгоритма.
Словесное описание. Самой простой является запись алгоритма в виде набора высказываний на обычном разговорном языке. Словесное описание имеет минимум ограничений и является наименее формализованным. Однако все разговорные языки обладают неоднозначностью. Чтобы избежать двусмысленности, тексты алгоритма приходится делать очень подробными. Алгоритм в словесной форме может оказаться очень объёмным и трудным для восприятия.
Пример 1
Словесное описание алгоритма нахождения наибольшего общего делителя (НОД) пары натуральных чисел (алгоритм Евклида):
«Чтобы найти НОД двух чисел, составьте таблицу из двух столбцов и назовите столбцы X и Y. Запишите первое из заданных чисел в столбец X, а второе — в столбец Y. Если данные числа не равны, замените большее из них на результат вычитания из большего числа меньшего. Повторяйте такие замены до тех пор, пока числа не окажутся равными, после чего число из столбца X считайте искомым результатом».
Построчная запись. Это запись на естественном языке, но с соблюдением некоторых дополнительных правил:
- каждое предписание записывается с новой строки;
- предписания (шаги) алгоритма нумеруются;
- исполнение алгоритма происходит в порядке возрастания номеров шагов, начиная с первого (если не встречается никаких специальных указаний).
Кроме слов естественного языка, предписания могут содержать математические выражения и формулы.
Пример 2
Построчная запись алгоритма Евклида:
- Обозначить первое из заданных чисел X, второе обозначить Y.
- Если X = Y, то перейти к п. 8.
- Если X > Y, то перейти к п. 4, иначе перейти к п. 6.
- Заменить X на X — Y.
- Перейти к и. 2.
- Заменить Y на Y — X.
- Перейти к и. 2.
- Считать X искомым результатом.
Построчная запись алгоритма позволяет избежать ряда неопределенностей; её восприятие не требует дополнительных знаний. Вместе с тем использование построчной записи требует от человека большого внимания.
Наибольшей наглядностью обладают графические способы записи алгоритмов; самый распространённый среди них — блок-схема.
Блок-схема представляет собой графическое изображение, дающее представление о порядке работы алгоритма. Здесь предписания изображаются с помощью различных геометрических фигур, а последовательность выполнения шагов указывается с помощью линий, соединяющих эти фигуры. Линии связи справа налево и снизу вверх изображаются со стрелками. Направления линий связи слева направо и сверху вниз считаются стандартными, эти линии можно изображать без стрелок.
Рассмотрим некоторые условные обозначения, применяемые в блок-схемах.
Выполнение алгоритма всегда начинается с блока начала и оканчивается при переходе на блок конца (рис. 3.2, а). Из начального блока выходит одна линия связи; в конечный блок входит одна линия связи.
Внутри блока данных (рис. 3.2, б) перечисляются величины, значения которых должны быть введены (исходные данные) или выведены (результаты) в данном месте алгоритма. В блок данных входит одна линия связи, и из блока выходит одна линия связи.
В блоке обработки данных (рис. 3.2, в) содержится описание тех действий, которые должны быть выполнены при переходе на этот блок (выполнение определённой операции или группы операций, приводящее к изменению значения, формы или размещения информации). В блок обработки данных входит одна линия связи, и из блока выходит одна линия связи.
Проверка условия изображается с помощью блока принятия решения, внутри которого записывается это условие (рис. 3.2, г). В блок принятия решения входит одна линия, а выходят две линии, около которых записываются результаты проверки условия.
Комментарии (рис. 3.2, д) используются для добавления пояснительных записей, делающих блок-схему более понятной.
Пример 3
Приведём запись алгоритма Евклида с помощью блок-схемы (рис. 3.3).
Рис. 3.3. Запись алгоритма Евклида с помощью блок-схемы
Создание детальной блок-схемы сложного алгоритма — трудоёмкая задача. Кроме того, блок-схема, не умещающаяся на одном стандартном листе, теряет своё основное преимущество — наглядность. При разработке сложных алгоритмов блок-схемы удобно использовать в качестве средства для наглядного представления решения задачи в общем виде.
Языки программирования — формальные языки, предназначенные для записи компьютерных программ, т. е. алгоритмов, исполнителем которых является компьютер. Каждый из них характеризуется:
- алфавитом — набором используемых символов;
- синтаксисом — системой правил, по которым из символов алфавита образуются правильные конструкции языка;
- семантикой — системой правил, строго определяющей смысл и способ употребления конструкций языка.
Языков программирования очень много. На уроках информатики в 8-9 классах вы сможете познакомиться с одним из языков программирования. Кроме того, желающие смогут попробовать свои силы в программировании на Школьном (учебном) алгоритмическом языке, который также называют русским алгоритмическим языком или алгоритмическим языком КуМир.
Школьный алгоритмический язык был введён в употребление академиком А. П. Ершовым в 1985 году.
Андрей Петрович Ершов (1931-1988) — выдающийся советский учёный, инициатор введения курса информатики в школы нашей страны. Его работы оказали огромное влияние на формирование и развитие вычислительной техники во всём мире.
Для записи алгоритмов на Школьном алгоритмическом языке используется некоторое ограниченное множество слов, смысл и способ употребления которых заданы раз и навсегда. Это так называемые служебные слова: алг (алгоритм), нач (начало),
кон (конец) и др. При записи алгоритмов в книгах служебные слова выделяются жирным шрифтом, в тетради и на доске — подчёркиванием.
В общем виде программу на Школьном алгоритмическом языке можно представить так:
алг <название алгоритма>
нач
<последовательность команд>
кон
С основными конструкциями Школьного алгоритмического языка вы познакомитесь, работая с Роботом, Черепахой, Чертёжником и другими исполнителями, встроенными в систему программирования КуМир.
Эти же конструкции мы будем использовать при записи алгоритмов на псевдокоде — смеси русского языка и Школьного алгоритмического языка.
Пример 4
Алгоритм на псевдокоде, позволяющий из полного сосуда ёмкостью 12 л отлить половину, пользуясь двумя пустыми сосудами ёмкостью 8 и 5 л:
Такая форма записи, ориентированная на исполнителя-человека, помогает понять или изложить сущность того или иного алгоритма. Запись на псевдокоде более формализована, чем другие словесные способы записи алгоритмов. Это позволяет стандартизировать, придать единую форму записи всем алгоритмам, с которыми вы будете иметь дело.