1.2.1. Алгоритмы. Виды алгоритмов. Описание алгоритмов. Формальное исполнение алгоритмов. Канд. пед. наук, доцент И.В. Попова Магнитогорск, 2009 1. - презентация

1 Алгоритмы. Виды алгоритмов. Описание алгоритмов. Формальное исполнение алгоритмов. Канд. пед. наук, доцент И.В. Попова Магнитогорск,

2 Алгоритм – это система команд для исполнителя, полное и точное указание исполнителю выполнить то или иное действие или решить поставленную задачу. 2 Крестьянину нужно перевезти через реку волка, козу и капусту. Но лодка такова, что в ней может поместиться только крестьянин, а с ним или один волк, или одна коза, или одна капуста. Но если оставить волка с козой, то волк съест козу, а если оставить козу с капустой, то коза съест капусту. Как перевез свой груз крестьянин? Е.И. Игнатьев. В царстве смекалки, или Арифметика для всех: Опыт математической хрестоматии. -СПб.: Тип. А.С. Суворина, 1911.

3 Решение 3

4 Исполнитель алгоритма 4 Человек - далеко не единственный возможный исполнитель алгоритмов. Все живые существа и даже отдельные клетки исполняют различные алгоритмы. Созданные человеком устройства – роботы- манипуляторы и станки с программным управлением.

5 Свойства алгоритмов Дискретность - алгоритм разбивается на мелкие шаги. Точность (Определенность) – команды(шаги) алгоритма должны быть точно определены, чтобы не было команд типа – пойди туда не знаю куда, найти то не знаю что; Результативность – в конце алгоритма должен быть представлен либо результат выполнения алгоритм, либо сообщение, что алгоритм невыполним; Массовость – применения алгоритма к классу задач( пример решение квадратного уравнения); Понятность – команды алгоритма должны быть понятны. 5

6 Способы задания/формы представления алгоритма словесный, (недостаток– многословность, возможна неоднозначность–«он встретил ее на поле с цветами»), табличный (физика, химия и т. д.), на школьном алгоритмическом языке; графический (блок-схемы).блок-схемы 6 начало конец a,b P:=0 P := Р + а I:=1..b a*b =, P Алгоритм 1. Задача 1

7 Виды алгоритмов Следования (линейный) Ветвления (развилка) Циклический Вспомогательный 7

8 Линейный алгоритм –алгоритм, в котором все действия выполняются последовательно. Образуется из последовательности действий, следующих одно за другим: 8 Школьный алгоритмический язык Язык блок-схем Действие 1 действие действие n

9 Алгоритм ветвления В зависимости от условия (да или нет) выполняется то или иное действие альтернативных путей работы алгоритма. Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран. Ветвление бывает полным или неполным. Структура ветвление существует в четырех основных вариантах: если-то; (неполное) если-то-иначе; (полное) выбор; (не полное) выбор-иначе. (полное) 9

10 Ветвление 10 Школьный алгоритмический язык Язык блок-схем Если-то если условие то действия Все Если-то-иначе если условие то действия 1 иначе действия 2 Все

11 Выбор 11 Школьный алгоритмический языкЯзык блок-схем Выбор выбор при условие 1: действия 1 при условие 2: действия при условие N: действия N Все Выбор-иначе выбор при условие 1: действия 1 при условие 2: действия при условие N: действия N иначе действия N+1 Все

12 Цикл Обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла. 12 Школьный алгоритмический языкЯзык блок-схем Цикл с предусловием (пока). Предписывает выполнять тело цикла до тех пор, пока выполняется условие, записанное после слова пока. нц пока условие тело цикла (последовательность действий) Кц Цикл с параметром(для). Предписывает выполнять тело цикла для всех значений некоторой переменной (параметра цикла) в заданном диапазоне. нц для i от i1 до i2 тело цикла (последовательность действий) Кц

13 Основные структуры алгоритмического языка Алфавит это фиксированный для данного языка набор основных символов, т.е. "букв алфавита", из которых должен состоять любой текст на этом языке никакие другие символы в тексте не допускаются. Синтаксис это правила построения фраз, позволяющие определить, правильно или неправильно написана та или иная фраза. Семантика определяет смысловое значение предложений языка. Являясь системой правил истолкования отдельных языковых конструкций, семантика устанавливает, какие последовательности действий описываются теми или иными фразами языка и, в конечном итоге, какой алгоритм определен данным текстом на алгоритмическом языке. 13

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

15 Общий вид алгоритма алг название алгоритма (аргументы и результаты) дано условия применимости алгоритма надо цель выполнения алгоритма нач описание промежуточных величин | последовательность команд (тело алгоритма) кон 15 Заголовок Тело алгоритма (арг, рез) и тип значения (цел, вещ, сим, лит или лог) всех входных (аргументы) и выходных (результаты) переменных.

16 Пример записи алгоритма на школьном алгоритмическом языке алг Нахождение расстояния (арг вещ v,t, рез вещ S) дано | Скорость и время надо | Расстояние нач цел i ввод v,t; S:=v*t; вывод "S = ", S кон 16

17 Блок-схема распространенный тип схем, описывающий алгоритмы или процессы, изображая шаги в виде блоков различной формы, соединенных между собой стрелкам 17 Правила выполнения схем определяются ГОСТ Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения. Данные – 10 шт.Процессы – 7 шт. Линии – 4 шт. Специальные символы – 4 шт.

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

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

20 Символы процесса. Граница цикла Символ, состоящий из двух частей, отображает начало и конец цикла. Обе части символа имеют один и тот же идентификатор. Условия для инициализации, приращения, завершения и т.д. помещаются внутри символа в начале или в конце в зависимости от расположения операции, проверяющей условие. 20

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

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

23 Пример блок-схемы Вычисление факториала числа N 23

24 Литература Интернет-версия издания: Шауцукова Л.З. Информатика: Учебник для классов. М.: Просвещение, 2000 Информатика. Задачник-практикум в 2-х томах./ Под ред. И.Семакина: Том 1. – М.: Лаборатория базовых знаний