Виды алгоритмов. 1_алгоритм. Алгоритм и его свойства
 Скачать 1.86 Mb.
|
|
Основы алгоритмизации По страничкам истории... Слово «алгоритм» происходит от имени великого среднеазиатского ученого 8–9 вв. Аль-Хорезми. Из математических работ Аль-Хорезми до нас дошли только две – алгебраическая и арифметическая. Вторая книга долгое время считалась потерянной, но в 1857 в библиотеке Кембриджского университета был найден ее перевод на латинский язык. В ней описаны четыре правила арифметических действий, практически те же, что используются и сейчас. Первые строки этой книги были переведены так: «Сказал Алгоритми. Воздадим должную хвалу Богу, нашему вождю и защитнику». Так имя Аль-Хорезми перешло в «Алгоритми», откуда и появилось слово «алгоритм». Тема: Алгоритм и его свойства Пример 1. Решение квадратного уравнения:1.Найти дискриминант по формуле: 2. Найти первый корень по формуле x1=(-b+√D)/2a 3. Найти второй корень по формуле x2=(-b-√D)/2a 4. Записать ответ. Пример 2. Выключение компьютера:Нажать кнопку В открывшемся меню выбрать В меню Выключение компьютера выбрать Определение:Алгоритм – понятное и точное предписание исполнителю совершить определенную последовательность действий для достижения поставленной цели за конечное число шагов. Исполнитель алгоритма - система, способная выполнить действия, предписываемые алгоритмом. Характеристики исполнителя:Сpеда — это «место обитания» исполнителя. Система команд – некоторый строго заданный список команд. После вызова команды исполнитель совеpшает соответствующее элементаpное действие. Отказы исполнителя возникают, если команда вызывается пpи недопустимом для нее состоянии сpеды. Выберите примеры исполнителей:Свойства алгоритма:Понятность - исполнитель алгоритма должен знать, как его выполнять. Свойства алгоритма:Дискpетность — алгоpитм должен пpедставлять пpоцесс pешения задачи как последовательное выполнение пpостых шагов. Свойства алгоритма:Опpеделенность — каждое пpавило алгоpитма должно быть четким и однозначным. Свойства алгоритма:Pезультативность - алгоpитм должен пpиводить к pешению задачи за конечное число шагов. Свойства алгоритма:Массовость – алгоpитм pешения задачи pазpабатывается в общем виде, т.е. он должен быть пpименим для некотоpого класса задач, pазличающихся лишь исходными данными. Является ли пример алгоритмом для вас? Почему?Вы вышли к доске, взяв мел в правую руку, вам сказали написать слово «информатика» на китайском языке. Способы записи алгоритмов:словесный (запись на естественном языке); графический (изображения из графических символов); программный (тексты на языках программирования). Определение:Блок-схема – это графическое изображение алгоритма в виде определенным образом связанных между собой нескольких типов блоков. Типы блоков:блок начала (конца) блок ввода (вывода) блок действия блок условия Линейный алгоритм Линейный алгоритм – это алгоритм, в котором команды выполняются последовательно одна за другой. Запись линейного алгоритма в виде блок-схемы:действие 1 действие n … начало конец Алгоритмическая структура «ветвление» Разветвляющийся алгоритм –Разветвляющийся алгоритм – это алгоритм, в котором та или иная серия команд выполняется в зависимости от истинности условия. ВетвлениеВетвление Полное если <условие> то <серия команд 1> иначе <серия команд 2> Неполное если <условие> то <серия команд 1> Запись полного ветвления в виде блок-схемы:условие серия команд 1 серия команд 2 да нет Запись неполного ветвления в виде блок-схемы:условие серия команд 1 да нет Условия в разветвляющихся алгоритмах Определение:Условие – это высказывание, которое может быть либо истинным, либо ложным. Условия простые сложные Простое условиеВключает в себя одно предложение; два числа, две переменных или два арифметических выражения, которые сравниваются между собой Например: Идет дождь; 5>4; x*y=3+8). Сложное условиеПоследовательность простых условий, объединенных между собой знаками логических операций И (AND), ИЛИ (OR). Например: (10>0) AND (8>9); (x=10) OR (x>=0). Задание:Построить блок-схему разветвляющегося алгоритма, используя сложное условие. Принадлежит ли точка x отрезку [a, b]? Задания:Задания: Лежитли x вне отрезка [a, b]; Принадлежит ли x отрезку [a, b] или отрезку [c, d]; Является ли k трехзначным числом; Какое из чисел a, b, c является меньшим; Есть ли среди чисел a, b, c взаимно противоположные; Равны ли треугольники со сторонами a1, b1, c1 и a2, b2, c2; Является ли четырехугольник со сторонами a, b, c и d ромбом. Ответы:(x < a) and (x > b); ((x>=a) and (x<=b)) or ((x>=c) and (x<=d)); (k > 99) and (k < 1000); (c < a) and (b > a); (a=-b) or (a=-c) or (b=-c); (a1=a2) and (b1=b2) and (c1=c2); (a=b) and (c=d) and (b=c). Алгоритмическая структура «выбор» Определение:Выбор - это такая алгоритмическая структура, в которой выполняется одна из нескольких последовательностей команд при истинности соответствующего условия. Полный выборпри условие 1: действия 1 при условие 2: действия 2 . . . . . . . . . . . . при условие N: действия N иначе действия N+1 Неполный выборпри условие 1: действия 1 при условие 2: действия 2 . . . . . . . . . . . . при условие N: действия N Запись полного выбора в виде блок-схемы:условие 1 да условие n серия команд 1 серия команд n да … нет нет серия команд n+1 Запись неполного выбора в виде блок-схемы:условие 1 да нет условие 2 условие n серия команд 2 да серия команд 1 серия команд n да … нет нет Алгоритмическая структура «цикл» Определение:Цикл - это такая алгоритмическая структура, в которой серия команд (тело цикла) выполняется многократно. Цикл с предусловием пока истинно условие, предписывает выполнять тело цикла. Словесный способ записи: пока условие тело цикла Запись цикла с предусловием в виде блок-схемы:условие тело цикла да нет Цикл с постусловием предписывает выполнять тело цикла до тех пор, пока не выполнится условие выхода из цикла. Словесный способ записи тело цикла до условие Запись цикла с постусловием в виде блок-схемы:условие тело цикла да нет Цикл со счетчиком предписывает выполнять тело цикла для всех значений некоторой переменной (параметра цикла) в заданном диапазоне. Словесный способ записи для i от i1 до i2 тело цикла Запись цикла со счетчиком в виде блок-схемы:счетчик тело цикла да нет |