Алгоритмы и его свойства Введение в программирование 10 класс Захарова О.Н.
Алгоритм Алгоритм – это строго детерминированная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных исполнителю команд.
Алгоритм приготовления чая Подготовить исходные величины – чай, воду, чайник, ложку. Налить в чайник воду. Поставить чайник на огонь. Довести до кипения и снять с огня. Всыпать в чайник 2 ложки чая. Поставить чайник на огонь. Довести воду до кипения (но не кипятить), снять с огня. Процесс прекратить.
Задание Составить алгоритм оценки знаний по результатам теста из 10 вопросов, согласно следующему правилу: если правильные ответы на 10 вопросов, то выставляется оценка 5, при 9 и 8 правильных ответах – оценка 4, при правильных ответах не более чем на 5 вопросов - оценка 2, в остальных случаях – оценка 3.
1) Формулировка задачи в математическом виде:
2) Алгоритм "Оценка" Ввод значения ot. Если ot = 10, то ocenka = 5, иначе (проверить условие) Если ot >= 8, то ocenka = 4, иначе (проверить условие) Если ot >= 6, то ocenka = 3, иначе ocenka = 2,. Вывести значение ocenka.
Исполнители алгоритмов Объект, выполняющий инструкции, последовательности команд, предписания алгоритма исполнителем. Исполнитель - объект, который выполняет алгоритм. Исполнителем может быть человек, машина, робот, компьютер... Формальный исполнитель – исполнитель выполняющий команды определенного алгоритма без анализа действий и ситуации. Компьютер – формальный исполнитель алгоритмов.
Основные характеристики исполнителя: Алгоритм, записанный на «понятном» компьютеру языке программирования, называется программой.
Свойства алгоритмов: 1. Дискретность (разбиение алгоритма на последовательность отдельных законченных действий). 2. Выполнимость и понятность команд (алгоритм должен содержать команды, входящие в систему команд исполнителя и записанные на понятном для исполнителя языке). 3. Детерминированность (однозначность) (строгое и недвусмысленное определение любого действия в каждом случае). 4. Массовость (возможность использования алгоритма с разными исходными данными). 5. Результативность (возможность получения из исходных данных результата за конечное число шагов). 6. Конечность. (завершение работы алгоритма в целом за конечное число шагов).
Свойства Пример выполнения свойства Пример невыполнения свойства Дискретность Казнить нельзя, помиловать! Казнить, нельзя помиловать Однозначность На дубе ларец, а в ларце утка, а в утке яйцо, в яйце игла, в игле смерть Кощея. Поди туда, не знаю куда, принеси то, не знаю что. Массовость Каждой дочери отец привёз по дорогому подарку Принц мог жениться только на настоящей принцессе Понятность Инструкция по-русски Инструкция на японском языке Конечность Мама сварила кашу в горшочке Каша уже заполнила все улицы, а горшочек всё варил кашу. Результативность Мышка хвостиком махнула, яйцо и разбилось Баба била-била не разбила.
Виды алгоритмов 1. Линейный алгоритм (описание действий, которые выполняются однократно в заданном порядке); 2. Циклический алгоритм (описание действий, которые должны повторятся указанное число раз или пока не выполнено задание); 3. Разветвляющий алгоритм (алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий) 4. Вспомогательный алгоритм (алгоритм, который можно использовать в других алгоритмах, указав только его имя).
Представления алгоритма Словесный, письменный на естественном языке; Графический (блок-схема, которая составляется из стандартных графических объектов); С помощью алгоритмического языка.
ПРИМЕР Составить алгоритм поиска площади круга радиусом R а) Словесно-пошаговый. 1. Ввод значения r 2. Вычислить s= r 2 3. Записать в ответ значение s. 4. Конец.
Последовательность команд Вид графического объекта Назначение Начало и конец алгоритма Функциональный блок - выполняемое действие Блок условия - условие выполнения действий Счетчик кол-во повторов Блок ввода-вывода данных Последовательность выполнения действий Начало Конец Данные Условие Счетчик б) Графический (в виде блок-схемы)
начало Ввод r S:= 3.14*r 2 Вывод s конец
в) Алгоритмический язык алг ЗАДАЧА (вещ r,s) арг r рез s нач ввод r s:= 3.14*r 2 вывод s кон
Команда присваивания При записи вычислительных алгоритмов удобно использовать специальный знак присваивания : = Y: = X. (Читается: "Y присвоить X"). ПРИМЕР: Y: = K; Y: = 37; X: =X+1 (возьми то, что хранится в X, добавь 1 и результат опять положи в X) B: =Ура! Скоро каникулы!, B – является символьной или литерной переменной, ее значением является текст.
Пример записи алгоритма в виде блок-схемы Задача: определить расстояние, пройденное человеком, если известно время движения, а так же известно, что движение было равномерным. Условие задачи: заданы скорость движения и время. Нужно найти путь. Математическая модель: S = v * t Начало S = v * t Конец V, t S
Домашнее задание Задачи: 1. Представить схематически алгоритм решения задачи по нахождению периметра прямоугольника.