АЛГОРИТМЫ

Что такое алгоритм? Что такое алгоритм? Это последовательность действий. Это последовательность действий. Для исполнителя Кто такой исполнитель? Тот, который исполняет команды алгоритма Для кого?

Вот алгоритм, который составила мачеха для Золушки: Перемой-ка всю посуду. Да натри полы повсюду, Дров на месяц наколи, Кофе на год намели, Посади среди цветов Сорок розовых кустов, И, пока не подрастут, Подметай дорожки тут

Исполнитель - это объект, умеющий выполнять определенный набор действий. (человек, животное, робот, компьютер). Система команд исполнителя (СКИ) – это все команды, которые исполнитель умеет выполнять. Среда исполнителя – обстановка, в которой функционирует исполнитель.

Алгоритм содержит несколько шагов. Шаг – отдельное законченное действие.

Алгоритм – это конечная система команд, адресованных исполнителю, четко и однозначно задающих процесс решения задачи во всех деталях

Происхождение термина «АЛГОРИТМ» связывают с именем известного узбекского математика и астронома ІХ века Мухаммеда аль-Хорезми

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

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

Задание Назови исполнителей следующих видов работ: уборка мусора во дворе; уборка мусора во дворе; обучение детей в школе; обучение детей в школе; вождение автомобиля; вождение автомобиля; ответ у доски; ответ у доски; приготовление пищи; приготовление пищи; печатание документа на принтере. печатание документа на принтере. Сформулируй СКИ для каждого из этих исполнителей, назови среду каждого исполнителя.

Способы описания алгоритма: Словесный (письменно или устно); Словесный (письменно или устно); Графический (стрелками, рисунками, блок – схемами); Графический (стрелками, рисунками, блок – схемами); Программный. Программный.

Алгоритм Эратросфена 1. Выписать все натуральные числа от 1 до N. Вычеркнуть Подчеркнуть наименьшее из неотмеченных чисел. 3. Вычеркнуть все числа, кратные подчеркнутому на предыдущем шаге. 4. Если в списке имеются еще не отмеченные числа, то перейти к шагу Все подчеркнутые числа – простые.

Задача. Переправа. К берегу реки, где была лодка, вмещающая только двух человек, подошли два разбойника и два путешественника. Разбойники не решались напасть на путешественников. В случае если на берегу останется один путешественник и два разбойника, они нападут на него. Как надо переправиться через реку разбойникам и путешественникам, чтобы последние смогли избежать нападения? К берегу реки, где была лодка, вмещающая только двух человек, подошли два разбойника и два путешественника. Разбойники не решались напасть на путешественников. В случае если на берегу останется один путешественник и два разбойника, они нападут на него. Как надо переправиться через реку разбойникам и путешественникам, чтобы последние смогли избежать нападения? Обозначения: П1 – первый путешественник П2 – второй путешественник; П2 – второй путешественник; Р1 – первый разбойник; Р1 – первый разбойник; Р2 – второй разбойник. Р2 – второй разбойник.

Первый берег Второй берег Нач.П1 П2 Р1 Р2 1П2 Р2П1 Р1 П2 Р2П1 Р1 2П2 Р2 П1Р1 П1 П2 Р2Р1 3Р2П1 П2 Р1 Р2П1 П2 Р1 4Р2 Р1П1 П2 Р1 Р2П1 П2 5Р1 Р2 П1 П2 Кон.П1 П2 Р1 Р2

Блок-схема Начало или конец алгоритма Команда алгоритма Ввод или вывод данных Проверка условия... Повторение действий (цикл)

Виды алгоритмов: Линейный – содержит несколько шагов и все шаги выполняются последовательно друг за другом; Линейный – содержит несколько шагов и все шаги выполняются последовательно друг за другом; Разветвляющийся – порядок выполнения шагов изменяется в зависимости от некоторых условий; Разветвляющийся – порядок выполнения шагов изменяется в зависимости от некоторых условий; Циклический – определенная последовательность шагов повторяется несколько раз в зависимости от заданной величины (параметра цикла). Циклический – определенная последовательность шагов повторяется несколько раз в зависимости от заданной величины (параметра цикла).

Алгоритмические задачи Задание. Волк, коза и капуста. Старик должен переправить на лодке через реку волка, козу и капусту. Лодка может выдержать только старика и одного «пассажира». В каком порядке старик перевезёт «пассажиров»? Не забудь, что волк может съесть козу, а коза – капусту. Найди два варианта решения.

Задание. Переправа. (д/з) Два мальчика и двое взрослых должны переправиться на другую сторону реки на плоту, который выдерживает либо двух мальчиков, либо одного мальчика и одного взрослого. Как осуществить переправу? Найди несколько способов решения этой задачи. Два мальчика и двое взрослых должны переправиться на другую сторону реки на плоту, который выдерживает либо двух мальчиков, либо одного мальчика и одного взрослого. Как осуществить переправу? Найди несколько способов решения этой задачи. Обозначения: 1 м – один мальчик; 2 м – два мальчика; 2 м – два мальчика; 1 в – один взрослый. 1 в – один взрослый.

Команда 1 Команда 2 Команда N Линейные (простые)

2. Разветвляющиеся Условие Серия 1Серия 2 Да Нет а) Полное ветвление

2. Разветвляющиеся Условие Серия 1 Да Нет б) Неполное ветвление

3. Циклические Счетчик цикла Серия команд а) арифметический цикл

б) Логический цикл с предусловием Условие Да Нет Серия команд

в) Логический цикл с послеусловием Условие Да Нет Серия команд