Базовые структуры алгоритмовНаложим некоторые ограничения на
структуру блок-схемы.
Будем строить алгоритм, используя только
три фрагмента определенной
конфигурации.
Назовем их базовыми структурами
алгоритмов.
состоит из цепочки блоков без
разветвлений.
Ветвление
данет
условиеЧастный случай ветвления
условиеВетвление применяется в тех случаях,
когда необходимо выбрать один из
двух путей решения задачи.
Цикл
Цикл применяется в тех случаях, когдадля решения задачи необходимо
многократно повторять одни и те же
действия.Цикл с постусловиемЦикл с предусловием
Параметрический цикл
Параметрический цикл управляетсяпараметром.
Параметр цикла – это переменная,
которая монотонно меняется в цикле,
и от неё зависит критерий выхода из
цикла.i:= in
Тело
цикла
i:= i + di
нет
да
i > iki:=in
i>ik
Тело
цикла
i:=i+di
Проектирование сложных алгоритмов
Метод проектирования алгоритмов «сверху – вниз»
Метод состоит из следующих шагов:исходная задача разбивается на подзадачи,
связанные некоторым алгоритмом;
этот алгоритм отлаживается;
каждая подзадача рассматривается как
задача;
процесс продолжается до тех пор, пока
исходная задача не будет полностью
решена.
Пример
Задано уравнение ax2 + bx + c = 0 и функцияf(x).
Если уравнение имеет два действительных
корня x1 и x2, построить таблицу значений
функции на отрезке , состоящую из n
точек.Алгоритм верхнего уровня
Ввод a,b,c
Решение
уравнения
нет
х1,х2
найдены
да
Ввод n
Построение
таблицы
Нет решения
STOPАлгоритм, реализующий подзадачу решения
квадратного уравнения
d:=b2 – 4ac
нет
D>0
да
X1=(- b + √ d)/2/а
X2= (- b - √ d)/2/аАлгоритм построения таблицы значений
функции
h=(x2-x1)/(n-1)
x = x1
i=1
Вывод x, f(x)
x=x+h
i = i +1
да
нет
i >nТаким образом, решение поставленной
задачи состоит из алгоритма верхнего
уровня и двух подзадач.
Алгоритм, связывающий подзадачи
Решение
уравнения
Построение
таблицы f(x)
Алгоритм и алгоритмические структуры
Мосина А.Ю.
Алгоритм – это строго определенная последовательность действий при решении задачи.
Алгоритм содержит несколько шагов.
Шаг алгоритма – это каждое отдельное действие алгоритма.
«Алгоритм – это порядок действий».
Исполнитель – это объект выполняющий определенный набор действий.
Исполнителем может быть человек, робот, животное, компьютер.
Система команд исполнителя (СКИ) – это совокупность команд, которые может выполнять исполнитель.
Среда исполнителя – обстановка, в которой функционирует исполнитель.
- Разрабатывает алгоритмы: человек
- Исполняют алгоритмы: люди и устройства – компьютеры, роботы, станки, спутники, сложная бытовая техника, детские игрушки.
- Исполнитель решает задачу по заданному алгоритму, строго следуя по предписаниям (программе) не вникая и не рассуждая, почему он так делает.
Задание: Назови исполнителей следующих видов работы:
Уборка мусора во дворе
Обучение детей в школе
Вождение автомобиля
Ответ у доски
Приготовление пищи
Печатание документа на принтере
Конечность – каждое действие в отдельности и алгоритм в целом должны иметь возможность завершения
Результативность – получение результата за конечное количество шагов
Дискретность (прерывность, раздельность) – разбиение алгоритма на шаги
Детерминированность (определенность, точность) – каждое действие должно строго и недвусмысленно определено
Массовость – использование алгоритма для решения однотипных задач
Свойства АЛГОРИТМА
Классификация алгоритмов по форме представления :
Словесные
Табличные
Графические (блок-схемы)
Программные
Блок-схема – графическое представление алгоритма в виде последовательности связанных между собой функциональных блоков ( стандартных графических элементов ), каждый из которых соответствует выполнению одного или нескольких действий.
Основные условные обозначения в блок-схемах
Условное обозначение
Назначение блока
Начало или конец алгоритма
Ввод или вывод данных.
Внутри блока перечисляются данные через запятую.
Процесс.
Внутри блока записываются матем. формулы и операции для обработки данных.
Проверка условия.
Внутри блока записываются логические условия. Имеет два выхода Да(+) и Нет(-).
Направление.
Классификация алгоритмов по структуре:
Линейный (следование)
Разветвленный (ветвление, выбор, альтернатива)
Циклический (повтор)
Вспомогательный
Комбинированный
Линейный алгоритм
Линейный алгоритм – это алгоритм, шаги которого выполняются последовательно друг за другом.
(Пример: алгоритм сбора портфеля).
Базовая структура линейного алгоритма:
Серия команд 1
Серия команд 2
Серия команд N
Задача
Вычислить периметр произвольного треугольника по его трем сторонам.
Решение:
1 этап: Постановка задачи.
Исходные данные : А, B, C – стороны произвольного треугольника
Выходные данные : P – периметр треугольника.
2 этап: Математическая модель.
P=A+B+С
3 этап: Составление алгоритма
Начало
Ввод
Вывод
Конец
№ 1 И спользуя блок-схему алгоритма , вычислите значение функции Y при X=2,
начало
ввод: X
Z = 8 * X
- РЕШЕНИЕ:
- X = 2
- Z = 8 * 2 = 16
- Z = √16 = 4
- Z = 4 – 1 = 3
- Y = 3 * 2 = 6
- Y = 6 / 3 = 2
Z = Z - 1
Y = 3 * X
Y = Y / Z
вывод: Y
Чтобы пользоваться предварительным просмотром презентаций создайте себе аккаунт (учетную запись) Google и войдите в него: https://accounts.google.com
Подписи к слайдам:
Урок-зачёт Алгоритм, его свойства и основные алгоритмические структуры
Ничто не приближает человека к богам настолько, как совершение добрых дел. Марк Тулий Цицерон
План зачёта «Письмо потомкам» Самостоятельная работа Решение задач Домашнее задание
Что такое алгоритм? Алгоритм – описание последовательности действий, направленных на получение из данных за конечное число дискретных шагов с помощью команд, понятных. детерминированной исходных результата исполнителю
Свойства алгоритма: - исполнитель алгоритма должен знать, как его выполнять; - выполняемый алгоритм должен приводиться к результату за конечное число шагов; - любой алгоритм должен состоять из конкретных действий, следующих в определенном порядке; - один и тот же алгоритм можно использовать с различными исходными данными. Понятность Конечность Дискретность Массовость
Формы представления алгоритмов Словесная устная. Словесная письменная Графическая (блок-схема):
Блок- схема Блок-схема – это совокупность, каждая из которых описывает какое-либо действие в алгоритме. геометрических фигур
– начало / конец алгоритма. – ввод / вывод данных. – вычисление (выполнение действия). – проверка условия (принятие решения).
Основные типы алгоритмических структур: Линейная Разветвляющаяся Циклическая
«Развилки» бывают в полной и неполной форме
Циклический алгоритм бывает «цикл со счётчиком», «цикл с предусловием» и «цикл с постусловием»
Вычислить площадь и периметр прямоугольника. начало конец S = a*b Ввести a, b Вывести S , Р Р = (a + b)*2
Вычисления значения гипотенузы прямоугольного треугольника, если известны значения его катетов начало Ввести a, b с = √ a 2 + b 2 Вывести с конец
Вычислить функцию, заданную в зависимости от значения аргумента начало Х
Составить блок-схему определения значения функции у = √ х, при х – неотрица тельном. начало Х > = 0 у = √ х не сущ-ет конец
Сумма чисел из промежутка от 5 до 10 начало а от 5 до 10 s = s + a S = 0 конец начало s = s + a a
Произведение всех чисел из промежутка от 5 до 10 начало а от 5 до 10 s = s * a S = 1 конец начало s = s * a a
Вся наша жизнь – это алгоритм сложной структуры. Надо стремиться к тому, чтобы каждое наше действие было обдуманным и приводило к правильному, достойному результату!
Попробуйте сформулировать известную русскую пословицу по ее блок-схеме
Попробуйте сформулировать известную русскую пословицу по ее блок-схеме
Определить результат работы алгоритма, представленного в виде блок-схемы
Составьте блок-схему по высказыванию «Если мысль нельзя выразить простыми словами, значит, она ничтожна и надо ее отбросить.»
Составить блок-схему к задаче: В корзине имеются белые и черные шары. Нужно белые шары положить в белую коробку, а черные – в черную.
Домашнее задание: Создать в рабочей тетради блок-схему к любой известной русской пословице.