Тема 3. Алгоритмизация

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

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

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

Массовость - алгоритм должен позволять решать не одну конкретную задачу, а множество задач этого класса.

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

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

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

Дискретность – расчленение сложных операций на более легкие.

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

· словесный

· формульно-словесный

· с помощью блок-схем

Словесный – содержание этапов вычислений задается на естественном языке в произвольной форме с требуемой детализацией.

Рассмотрим пример словесной записи алгоритма для решения следующей задачи.

Дана последовательность чисел. Требуется проверить, все ли числа данной последовательности принадлежат интервалу [А; В].

1. Начало

2. Выбираем первое число. Переход на п.3.

3. Проверяем: выбранное число принадлежит интервалу [А; В]? Если да, то переход на п.4, если нет, то переход на п.7.

4. Проверяем: все числа последовательности просмотрены? Если да, то переход на п.6, если нет, то переход на п.5.

5. Выбираем следующий элемент. Переход на п.3.

6. Вывод на экран сообщения «Все элементы принадлежат интервалу [А; В]». Переход на п.8.

7. Вывод на экран сообщения «Не все элементы принадлежат интервалу [А; В]». Переход на п.8.

8. Конец

При этом способе отсутствует наглядность вычислительного процесса.

Формульно-словесный – задание инструкций с использованием математических символов и выражений в сочетании со словесными пояснениями.

Рассмотрим пример формульно-словесной записи алгоритма вычисления площади тре­угольника по трем сторонам.

1. Вычислить полупериметр треугольника

Переход на п.2.

2. Вычислить

Переход к п.3.

3. Вывести S, как искомый результат и прекратить вы­числения.

При использовании этого способа может быть достигнута любая степень детализации, более наглядно, но не строго формально.

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

Рассмотрим пример записи алгоритма с помощью блок-схем для решения следующей задачи:

Дана последовательность чисел. Требуется проверить, все ли числа данной последовательности принадлежат интервалу [А; В]. Последовательность действий описана на рисунке 1.

Рис.1

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

Рис.2.Основные блоки блок-схемы

Основные структуры алгоритмов:

1. последовательность (линейная структура)

2. цикл с предусловием

3. цикл с постусловием

4. ветвление

5. сокращенное ветвление

6. множественный выбор