Способы записи алгоритмов: Методические указания к выполнению лабораторной работы

Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

Саратовский государственный технический университет

Балаковский институт техники, технологии и управления

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

Методические указания к выполнению лабораторной работы по курсу «Информатика» для студентов специальности 230201, направления 654700 очной формы обучения

Одобрено

редакционно-издательским советом

Балаковского института техники,

технологии и управления

Балаково 2008

ЦЕЛЬ РАБОТЫ – ознакомиться с понятием алгоритма, видами алгоритмов, способами записей алгоритмов, стандартами составления блок-схем, основами алгоритмического языка.

ОБЩИЕ ПОНЯТИЯ

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

Понятие алгоритма, свойства алгоритма

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

Алгоритм должен обладать следующими свойствами:

1. Конечность – алгоритм должен быть закончен за конкретное число шагов.

2. Понятность – алгоритм должен быть составлен на языке, понятном исполнителю.

3. Доступность – алгоритм должен содержать команды, только входящие в систему команд исполнителя.

4. Последовательность – действия и команды исполнителя должны находиться в строго определенном порядке.

Рассмотрим основные характеристики алгоритма:

1. Базовость – один алгоритм должен применяться для решения множества однотипных задач.

2. Определенность – все переменные и константы, входящие в алгоритм должны быть строго определены.

3. Разрешимость – алгоритм должен завершаться выводом решения поставленной задачи или сообщением, что решение невозможно.

Виды алгоритмов

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

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

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

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

Например:

А=В?– простое условие в прямой форме;

А¹В? – простое условие с отрицанием;

А=В И В=С? – составное условие со связкой И;

А=В ИЛИ В=С? – составное условие со связкой ИЛИ;

А¹В И В=С ИЛИ А=С? – составное условие со связками И, ИЛИ и отрицанием.

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

Например, условия A>B и A£B являются взаимоисключающими, так как при истинности первого условия мы можем сделать вывод о ложности второго или из ложности первого условия вытекает истинность второго.

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

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

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

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

Цикл с предусловием изначально формирует условие повторения действия или последовательности действий (тела цикла). Соответственно, тело цикла будет повторяться до тех пор, пока сформированное условие истинно.

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

Таким образом, условия, формируется в цикле с предусловием и в цикле с постусловием прямо противоположны. Тело цикла при использовании цикла ПОКА может ни разу не выполниться, в то время как, тело цикла при использовании цикла ДО обязательно выполниться хотя бы один раз.

Недостатки циклов с предусловием и постусловием следующие:

- Перед началом цикла необходимо дополнительно прописывать начальное значение переменной цикла;

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

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

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

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

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

Основные элементы блок-схем, их описание и размеры приведены в приложении 1.

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

На алгоритмическом языке начало и конец алгоритма отображаются следующим образом:

нач

тело алгоритма

кон

Рис.1. Отображение начала и конца алгоритма на блок-схеме

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

ввод <имя переменной>

вывод <имя переменной>

Рис.2. Элемент отображения ввода и