Презентация на тему "алгоритмы и способы их описания". Презентация к уроку информатики базовые алгоритмические структуры Базовая структура "ветвление"

Чтобы пользоваться предварительным просмотром презентаций создайте себе аккаунт (учетную запись) 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

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

Попробуйте сформулировать известную русскую пословицу по ее блок-схеме

Определить результат работы алгоритма, представленного в виде блок-схемы

Составьте блок-схему по высказыванию «Если мысль нельзя выразить простыми словами, значит, она ничтожна и надо ее отбросить.»

Составить блок-схему к задаче: В корзине имеются белые и черные шары. Нужно белые шары положить в белую коробку, а черные – в черную.

Домашнее задание: Создать в рабочей тетради блок-схему к любой известной русской пословице.

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

Первая базовая структура - следование
состоит из цепочки блоков без
разветвлений.

Ветвление

да
нет
условие

Частный случай ветвления
условие

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

Цикл

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

Цикл с постусловием

Цикл с предусловием

Параметрический цикл

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

i:= in
Тело
цикла
i:= i + di
нет
да
i > ik

i:=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)

Алгоритмы могут описывать процессы преобразования самых разных объектов. Само слово «алгоритм» происходит от «algorithmi» - латинской формы написания имени выдающегося математика IX века аль-Хорезми, который сформулировал правила выполнения арифметических операций.
Алгоритм - набор команд, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное число действий.

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

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

2. Детерминированность (определённость). В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных.

3. Понятность - алгоритм должен включать только те команды, которые доступны исполнителю и входят в его систему команд.

4. Завершаемость (конечность) - при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов.

5. Массовость (универсальность). Алгоритм должен быть применим к разным наборам исходных данных.

6. Результативность - завершение алгоритма определёнными результатами.

Способы записи алгоритмов:

1. Словесный способ записи

Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке .

Пример

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

где S – площадь прямоугольника; а, b – длины его сторон.

Очевидно, что a, b должны быть заданы заранее, иначе задачу решить невозможно.

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

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

Начало алгоритма.
Задать численное значение стороны a.
Задать численное значение стороны b.
Вычислить площадь S прямоугольника по формуле S=a*b.
Вывести результат вычислений.
Конец алгоритма.

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

2. Графический способ

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

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

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

Элемент блок-схемы

Наименование

Блок вычислений (вычислительный блок)

Вычислительные действия или последовательность действий

Логический блок (блок условия)

Блок ввода-вывода данных

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

Общее обозначения ввода (вывода) данных (вне зависимости от физического носителя)

Начало (конец)

Начало или конец алгоритма, вход или выход в подпрограмме

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

Элемент блок-схемы

Наименование

Процесс пользователя (подпрограмма)

Вычисление по стандартной программе или подпрограмме

Блок модификации

Функция выполняет действия, изменяющие пункты (например, заголовок цикла) алгоритма

Соединитель

Указание связи прерванными линиями между потоками информации

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

Пример

Алгоритм вычисления площади прямоугольника

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

3. Псевдокоды

полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.

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