Алгоритм.�Основные типы алгоритмических структур.

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

IХ в. Мухаммеда аль-Хорезми узбекский математик

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

Аль Хорезми  «АЛГОРИФМ»  «АЛГОРИТМ»

Понятие алгоритма

Алгоритм — это метод (способ) решения задачи, записанный

по определенным правилам, обеспечивающим однозначность

его понимания и механического исполнения при всех

значениях исходных данных (из некоторого множества

значений)

Алгоритм — точное предписание, определяющее

вычислительный процесс, ведущий от варьируемых

начальных данных к искомо­му результату.(в толковом

словаре по информатике (1991 г.)

Алгоритм  –последовательность действий, описывающая

процесс преобразования объекта из начального состояния в

конечное, записанная с помощью понятных исполнителю

команд.

Примеры алгоритмов

• Инструкция по эвакуации во время пожара
• Решение математических задач
• Рецепт блюда
• ПДД
• Распорядок дня

Вывод: Алгоритм – это способ фиксации и

передачи знаний, накопленных человечеством

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

Исполнителя характеризуют :

• Среда (или обстановка)
• Элементарные действия
• Система команд - строго заданный набор команд
• Отказы - команда вызывается при недопустимом состоянии среды

Исполнитель выполняет алгоритм формально

Свойства алгоритмов

• Понятность алгоритма
• Дискретность алгоритма
• Определенность алгоритма
• Результативность алгоритма
• Массовость алгоритма

Для создания алгоритма необходимо знать:

• полный набор исходных данных задачи (начальное состояние объекта)

• цель создания алгоритма (конечное состояние объекта)

• систему команд исполнителя (то есть набор команд, которые исполнитель понимает и может выполнить)

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

• Описание словами и формулами
• Описание на алгоритмическом языке
• Графическое описание

Описание алгоритма словами и формулами

Пример 1

Правила (алгоритм) перехода пешеходом дороги на нерегулируемого пешеходном переходе

• Подойти к краю догори
• Посмотреть налево
• Убедиться, что нет транспортного средства
• Перейти дорогу до середины
• Посмотреть направо
• Убедиться, что нет транспортного средства
• Перейти дорогу

Описание алгоритма словами и формулами

Пример 2

Вычисление площади круга, если известен его радиус

• Ввести значение радиуса R, перейти в п. 2.
• Вычислить S=  r 2 , перейти в п. 3.
• Вывести (отпечатать) значение S, перейти в п. 4.
• Вычисления прекратить.

Описание алгоритма на алгоритмическом языке

Пример

Задача на расчет площади круга (при исходных дан­ных r = 8 м) на

алгоритмическом языке будет выглядеть:

Алгоритм-программа на языке ВАSIС

10 R1 = 8

20 Р = 3.14

30 R2 = R1 * R1

40 S = Р*R2

50 РRINT S

60 END

Программа – это алгоритм, записанный на языке

Программирования.

Графическое описание алгоритма

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

Параллелограмм, предназначен для описания ввода или вывода данных, имеет один вход вверху и один выход внизу.

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

Ромб , служит для обозначения условий в алгоритмических структурах «ветвление» и «выбор», имеет один вход верху и два выхода (налево, если условие выполняется, и направо, если условие не выполняется).

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

Графическое описание алгоритма

Пример

Даны длины сторон треугольника A, B, C. Найти площадь треугольника S. Составьте блок-схему алгоритма решения поставленной задачи.

Правила построения схемы алгоритма

• Выявить исходные данные, результаты, дать им имена
• Выбрать порядок (метод) решения задачи
• Разбить метод решения задачи на этапы
• Изобразить каждый этап в виде соответствующей блок-схемы и указать стрелкам порядок их выполнения
• В полученной схеме предусмотреть выдачу результатов или сообщений об их отсутствии

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

Разветвляющиеся

Циклические

Линейные

Линейные алгоритмы

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

Действие 1

Действие 2

Действие n

Разветвляющиеся алгоритмы

Блоки выполнятся в зависимости от некоторого логического условия

Условие

Нет

Условие

Да

Да

Нет

Действие 2

Действие 1

Действие 1

Неполное ветвление

Полное ветвление

Пример: Вычислите модуль числа х

Математическая запись :

Блок-схема

Начало

Ввод х

х

F=-х

F=x

Вывод х

Конец

Циклические алгоритмы

Многократно повторяемые участки вычислительного процесса

Переменная, изменяемая в цикле – параметр цикла

Виды циклов

а – с заданным числом повторений

б - с неизвестным числом повторений ( с предусловием)

в – с неизвестным числом повторений ( с постусловием)

Домашнее задание

Составьте алгоритм в виде блок-схемы нахождения:

Вариант 2

Вариант 1

среднего арифметического трех чисел

меньшего из двух чисел

Домашнее задание

Составьте алгоритм в виде блок-схемы нахождения:

Вариант 1

Вариант 2

среднего арифметического трех чисел

меньшего из двух чисел

НАЧАЛО

НАЧАЛО

ВВОД а , b

ВВОД a, b, c

a

Sr:=(a+b+c)/3

min:=b

min:=a

ВЫВОД Sr

ВЫВОД а , b

КОНЕЦ

КОНЕЦ