Понятие алгоритма Урок 1 Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы» - презентация

1 Понятие алгоритма Урок 1 Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

2 Алгоритм Единого «истинного» определения понятия «алгоритм» нет. «Алгоритм это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность». (Д. Э. Кнут) «Алгоритм это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи». (А. Колмогоров) «Алгоритм это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату». (А. Марков) «Алгоритм точное предписание о выполнении в определённом порядке некоторой системы операций, ведущих к решению всех задач данного типа». (Философский словарь / Под ред. М. М. Розенталя) «Алгоритм строго детерминированная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных исполнителю команд». (Николай Дмитриевич Угринович, учебник «Информатика и информ. технологии») 2 Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

3 Алгоритм -четко определенная последовательность действия, позволяющая из исходного набора данных придти к конечному результату за конечное число шагов. В 2013 году будет отмечаться 1230-летний юбилей со дня рождения величайшего средневекового ученого Средней Азии Мухамеда ибн Мусы аль-Хорезми. С именем этого ученого связано понятие алгоритма. Алгоритм может представлять собой некоторую последовательность вычислений, а может - последовательность действий нематематического характера. Для любого алгоритма справедливы общие закономерности - свойства алгоритма. 3 Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

4 Свойства алгоритма Различные определения алгоритма в явной или неявной форме содержат следующий ряд общих требований: 1.Дискретность 2.Детерминированность (определённость) 3.Понятность 4.Завершаемость (конечность) 5.Массовость (универсальность) 6.Результативность 4 Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

5 Свойства алгоритма Дискретность поочередное выполнение команд алгоритма за конечное число шагов приводящее к решению задачи. командой Запись алгоритма распадается на отдельные указания исполнителю выполнить некоторое законченное действие. Каждое такое указание называется командой. Команды алгоритма выполняются одна за другой. После каждого шага исполнения алгоритма точно известно, какая команда должна выполняться следующей. Алгоритм представляет собой последовательность команд (также инструкций, директив), определяющих действия исполнителя (субъекта или управляемого объекта). Таким образом, выполняя алгоритм, исполнитель может не вникать в смысл того, что он делает, и вместе с тем получать нужный результат. В этом случае говорят, что исполнитель действует формально, то есть отвлекается от содержания поставленной задачи и только строго выполняет некоторые правила, инструкции. 5 Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

6 Свойства алгоритма Детерминированность (определённость) свойство, когда каждое действие (операция, указание, шаг, требование) должно пониматься в строго определённом смысле, чтобы не оставалась места произвольному толкованию. чтобы каждый, прочитавший указание, понимал его однозначно. Таким образом: алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. любое действие должно быть строго и недвусмысленно определено в каждом случае 6 Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

7 Свойства алгоритма Понятность алгоритм для исполнителя должен включать только те команды, которые ему (исполнителю) доступны, которые входят в его систему команд. системой команд исполнителя У каждого исполнителя имеется свой перечень команд, которые он может исполнить. Совокупность команд, которые могут быть выполнены исполнителем, называется системой команд исполнителя. 7 Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

8 Свойства алгоритма Завершаемость (конечность) при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов. 8 Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

9 Свойства алгоритма Массовость (универсальность). Алгоритм обеспечивает решения всего класса задач данного типа. Алгоритм должен быть применим к разным наборам исходных данных. Свойство массовости не является необходимым свойством алгоритма. Оно скорее определяет качество алгоритма. 9 Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

10 Свойства алгоритма Результативность – свойство, при котором любой алгоритм в процессе выполнения должен приводить к определённому результату. Отрицательный результат также является результатом. 10 Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

11 Формы представления алгоритмов На практике наиболее распространены следующие формы представления алгоритмов: словеснаясловесная (записи на естественном языке); графическаяграфическая (изображения из графических символов); псевдокодыпсевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.); программнаяпрограммная (тексты на языках программирования). 11 Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

12 Формы представления алгоритмов Словесный способ Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке. Например. Например. Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел. 1.задать два числа; 2.если числа равны, то взять любое из них в качестве ответа и остановиться, в противном случае продолжить выполнение алгоритма; 3.определить большее из чисел; 4.заменить большее из чисел разностью большего и меньшего из чисел; 5.повторить алгоритм с шага 2. Описанный алгоритм применим к любым натуральным числам и должен приводить к решению поставленной задачи. Словесный способ не имеет широкого распространения по следующим причинам: такие описания строго не формализуемы; страдают многословностью записей; допускают неоднозначность толкования отдельных предписаний. 12 Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

13 Формы представления алгоритмов Графический способ Графический способ представления алгоритмов является более компактным и наглядным по сравнению со словесным. блок-схемой Такое графическое представление называется схемой алгоритма или блок-схемой. При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. В блок-схеме каждому типу действий (вводу исходных данных, вычислению значений выражений, проверке условий, управлению повторением действий, окончанию обработки и т.п.) соответствует геометрическая фигура, представленная в виде блочного символа. Блочные символы соединяются линиями переходов, определяющими очередность выполнения действий. 13 Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

14 Формы представления алгоритмов 14 п/п Блок, пример заполнения блока Характеристика блока 1 Блок «начало», «конец» 2Блок «Действие» 3Блок «ввод», «вывод» 4Блок «условие» начало x=(a+b)/3 Ввод a,b a>b ДаНет Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

15 Формы представления алгоритмов блок-схемы. Пример алгоритма, представленного в виде блок-схемы. 15 Абонент ответил? Телефонный разговор конец начало Снимите телефонную трубку Нажмите на рычаг Дождитесь длинного гудка Наберите номер ДаНет Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

16 Виды алгоритмов Все имеющиеся алгоритмы можно разделить на три вида: линейные алгоритмы; алгоритмы ветвления; циклические алгоритмы. 16 Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

17 Виды алгоритмов Линейные алгоритмы - описание действий, которые выполняются однократно в заданном порядке. 17 Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

18 Виды алгоритмов Разветвляющийся алгоритм - алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий 18 Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

19 Виды алгоритмов Циклический алгоритм Обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла. 19 Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

20 Задания Старинная русская задача. Крестьянин стоит на левом берегу реки с волком, козой и капустой. Ему нужно перевезти все это на правый берег. Но его лодка слишком мала: он может взять только одного пассажира – либо волка, либо капусту, либо козу. Как тут поступить? 20 Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

21 Задания Старинная русская задача Словесный алгоритм 1). Перевези капусту 2). Переправься 3). Перевези волка 4). Перевези козу 5). Перевези капусту 6). Переправься 7). Перевези козу. 21 Блок-схема Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

22 Задания Пример 1. Пример 1. Некий злоумышленник выдал следующий алгоритм за алгоритм получения кипятка: 1.Налить в чайник воду. 2.Открыть кран газовой горелки. 3.Поставить чайник на плиту. 4.Ждать, пока не закипит вода. 5.Поднести спичку к горелке. 6.Зажечь спичку. 7.Выключить газ. Исправьте алгоритм, чтобы предотвратить несчастный случай. 22 Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

23 Задания Помоги роботу заполнить таблицу по заданному алгоритму. 23 Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

24 Домашнее задание На «5». Три рыцаря с тремя оруженосцами подошли к реке. Они нашли маленькую лодку, в которой через реку могут переправиться только 2 человека. Каждый оруженосец так предан своему хозяину, что он отказывается оставаться на берегу или в лодке с другими рыцарями в отсутствие хозяина. Но готов быть один или с другими оруженосцами. Как они вшестером могут перебраться через реку?Задания 1.Придумать систему команд для исполнителя в данной задаче 2.Написать в этой системе команд программу, решающую поставленную задачу 3.Нарисовать блок-схему 4.Построить граф 24 Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

25 Домашнее задание На «4». Имеются два кувшина емкостью 3 л и 8 л. Представьте алгоритмы в словесной и графической формах, выполняя которые можно набрать из реки 7 л воды. Разрешается пользоваться только этими кувшинами. 25 Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

26 Понятие алгоритма Урок 2. Ветвления Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

27 27 Начало P=(a+b)/2 S=ab Вывод S, P Конец Даны стороны прямоугольника a и b. Найти его площадь S, и периметр Р. Начало Ввод (a, b) P=2(a+b) S=ab Вывод S, P Конец С ошибкамиПравильно Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

28 28 Этот оператор используется для выполнения одного из двух возможных вариантов алгоритма. Условный оператор если если логическое_условие верно, то то выполняется оператор_1, иначе иначе оператор_2; Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

29 29 Условие неполное условие Оператор Вход Выход Да(нет)Нет (Да) Типы ветвлений Условие полное Оператор 2Оператор 1 условие Вход Выход Да(нет) Нет (Да) Формат полного оператора ветвления: Формат неполного оператора ветвления: Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

30 Задания 1. Помоги роботу заполнить таблицу по заданному алгоритму. 30 начало Ввод а a

31 Задания: 2. Из двух заданных целых чисел выбрать наибольшее. Математическая модель: Данные: x, y Результат: 31 Варианты: Если x=5, y=8, то max=8 Если x=6, y=1, то max=6 Если x=5, y=5, то max=5 Начало Ввод (x, y) x>y max:=xmax:=y Вывод (max) Конец Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

32 Задания: 3. Дано целое число. Если оно является однозначным, то умножить его на 100. Вывести полученное число. 4. Дано целое число. Если оно является положительным, то прибавить к нему 1, в противном случае вычесть из него два. Вывести полученное число. 5. Даны три стороны одного треугольника и три стороны другого треугольника. Определить, будут ли эти треугольники равновеликими, то есть имеют ли они равные площади. Вывести соответствующее сообщение. 32 Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

33 Домашнее задание На «5». Из банка на выплату зарплаты привезли a рублей. Хватит ли этой суммы, если на предприятии n работников, их средняя зарплата s рублей, а в кассе ещё имеется остаток k рублей? 33 На «4». Дано два целых натуральных числа. Вывести сообщение о количество положительных или отрицательных чисел в исходном наборе. Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

34 Понятие алгоритма Урок 3. Выбор Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

35 35 Часто возникают ситуации, когда приходится осуществлять выбор одного из нескольких альтернативных путей выполнения программы. Несмотря на то, что такой выбор можно организовать с помощью разветвляющегося алгоритма, удобнее воспользоваться специальным оператором выбора. Его формат: выбор выражение из вариантов: вариант1: действие1; вариант2: действие2; … вариантN: действиеN; выбор селектором Выражение, которое записывается после ключевого слова выбор, называется селектором. Алгоритм выбора Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

36 Возможен алгоритм, состоящий из одной или большего количества констант или диапазонов, разделенных запятыми, причем недопустимо более одного упоминания вариантов.. Его формат: выбор выражение из вариантов: Вариант1, вариант2, вариант3 : действие1; вариант4: действие2; … вариантN: действиеN; иначе Из перечисленного множества операторов будет выбран только тот, перед которым записан вариант, совпадающий со значением селектора. Если такого варианта нет, выполняется оператор, следующий за словом иначе (если он есть). 36 Алгоритм выбора выбор выражение из вариантов: Вариант1, вариант2, вариант3 : действие1; вариант2: действие2; … вариантN: действиеN; Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

37 37 Алгоритм выбора начало конец ввод M да нет M = 1? нет M = 2? да нет N = 7? да начало ввод M M = 1? начало ввод M M = 2? M = 1? начало ввод M N = 2? N = 1? начало ввод N ошибка ввода Вывод «понедельник» Вывод «вторник» Вывод «воскресенье» Алгоритм вывода названия дня недели по его номеру. Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

38 Задания: 1. Колдун должен сделать очередной ход. По нажатию на любую клавишу генерируется случайное число от 1 до 10, и программа печатает, какое заклинание произнёс колдун. Например, 1- удар молнии; 2 – огненный шар … 2. Микки-Маус подходит к стене с отверстиями. Над каждым отверстием стоит номер. Некоторые ходы ведут в ловушку, некоторые – к запасам зерна, сыра, муки и т. д. Нужен алгоритм, который по введённому номеру сообщает, куда попадёт Микки- Маус. 3. Перечислить названия животных, имеющихся в зоопарке. При вводе номера животного сообщается кличка животного, рацион (чем его кормят служащие зоопарка), и что ему могут давать посетители. 38 Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

39 Домашнее задание На «5». Даны два целых числа: D (день) и M (месяц), определяющие правильную дату. Вывести знак Зодиака, соответствующий этой дате: «Водолей» ( ), «Рыбы» ( ), «Овен» ( ), «Телец» ( ), «Близнецы» ( ), «Рак» ( ), «Лев» ( ), «Дева» ( ), «Весы» ( ), «Скорпион» ( ), «Стрелец» ( ), «Козерог» ( ). 39 На «4». Составьте алгоритм программы«Консультант» в магазин обуви, которая сообщает, какая обувь находится на той или иной полке по введенному номеру с клавиатуры. полки Вид обуви 1сапоги 2мужские туфли 3кроссовки 4мужские туфли 5женские туфли кроссовки 10кроссовки 11кроссовки 12кроссовки Григорьева О.Ю. МОУ «Лицей 11 им. Александровой Т.И. г. Йошкар-Олы»

40