Тема 10. Основы алгоритмизации.

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

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

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

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

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

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

Существуют различные формы (способы) представления алгоритмов. Основными среди них являются:

1. Словесное описание алгоритма на естественном языке (вербальная форма).

2. Построчная запись алгоритма (более строгое описание на естественном языке).

3. Представление алгоритма в виде блок-схемы.

4. Способ изображения алгоритма с помощью структурограммы (схема Насси-Шнейдермана).

5. Запись алгоритма на каком-либо языке программирования.

Рассмотрим особенности каждой из этих форм на примере алгоритмизации задачи нахождения наибольшего общего делителя (НОД) двух целых положительных чисел методом последовательного вычитания (алгоритм Евклида).

Вербальное представление алгоритма.

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

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

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

1. Начало.

2. Ввод m, n.

3. Если mn, перейти к пункту 4, иначе - к пункту 7.

4. Если mn, перейти к пункту 5, иначе - к пункту 6.

5. m=m-n; перейти к пункту 3.

6. n=n-m; перейти к пункту 3.

7. НОД=m.

8. Вывод результата.

9. Конец.

Представление алгоритма в виде блок-схемыотличается высокой степенью наглядности. Блок-схема состоит из соединенных между собой стрелками (линиями потока информации) блоков различного вида, начертание которых регламентируется ГОСТом. Применительно к рассматриваемой задаче блок-схема алгоритма выглядит:

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