Алгоритмы. Алгоритмы и способы их описания
 Скачать 0.93 Mb.
|
|
Тема: Алгоритмы и способы их описания Вопросы: 1. Понятие алгоритма. Способы записи алгоритмов. Свойства алгоритмов. 2. Формальное исполнение алгоритма 3. Основные алгоритмические конструкции и их описание средствами языков программирования. 4. Основные типы алгоритмических структур: линейный алгоритм, ветвление, цикл. Существует несколько определений понятия алгоритма. Приведем два самых распространенных. Алгоритм – последовательность чётко определенных действий, выполнение которых ведёт к решению задачи. Алгоритм, записанный на языке машины, есть программа решения задачи. Алгоритм — это предписание некоторому исполнителю выполнить конечную последовательность действий, приводящую к некоторому результату. Алгоритм – это совокупность действий, приводящих к достижению результата за конечное число шагов. Вообще говоря, первое определение не передает полноты смысла понятия алгоритм. Используемое слово "последовательность" сужает данное понятие, т.к. действия не обязательно должны следовать друг за другом – они могут повторяться или содержать условие. В программировании алгоритм является фундаментом программы, а основным исполнителем — компьютер. На стадии тестирования алгоритма исполнителем может быть сам программист. Способы записи алгоритмов: Существует несколько способов записи алгоритмов. На практике наиболее распространены следующие формы представления алгоритмов: 1. словесная (запись на естественном языке); 2. псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.); 3. графическая (изображения из графических символов – блок-схема); 4. программная (тексты на языках программирования – код программы). Рассмотрим подробно каждый вариант записи алгоритмов на примере следующей задачи. Требуется найти частное двух чисел. Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке. Ответ при этом получает человек, который выполняет команды согласно словесной записи. Пример словесной записи: 1. задать два числа, являющиеся делимым и делителем; 2. проверить, равняется ли делитель нулю; 3. если делитель не равен нулю, то найти частное, записать его в ответ; 4. если делитель равен нулю, то в ответ записать "нет решения". Словесный способ не имеет широкого распространения, так как такие описания: строго не формализуемы; страдают многословностью записей; допускают неоднозначность толкования отдельных предписаний. Псевдокод занимает промежуточное место между естественным и формальным языками. С одной стороны, он близок к обычному естественному языку, поэтому алгоритмы могут на нем записываться и читаться как обычный текст. С другой стороны, в псевдокоде используются некоторые формальные конструкции и математическая символика, что приближает запись алгоритма к общепринятой математической записи.Преимущество блок-схем — в наглядности алгоритма. Приведем основные управляющие структуры псевдокода в табл. 1.1. Таблица 1.1. Базовые управляющие структуры псевдокода Название структуры Псевдокод Присваивание переменная = число Ввод ввод(переменная) Вывод вывод(переменная) вывод("фраза") Ветвление если условие то действие1 иначе действие2 Повторение пока условие начало пока действие конец пока Пример псевдокода: алг Нахождение частного двух чисел начало вывод ("задайте делимое и делитель") ввод (делимое, делитель) если делитель ≠ 0 то частное = делимое / делитель вывод(частное) иначе вывод("нет решения") кон алг Нахождение частного двух чисел Графическая реализация алгоритма представляет собой блок-схему. Блок-схема состоит из блоков определенной формы, соединенных стрелками. Ответ при этом получает человек, который выполняет команды согласно блок-схеме Программная реализация алгоритма – это компьютерная программа, написанная на каком-либо алгоритмическом языке программирования, например: С++, Pascal, Basic и т.д. Программа состоит из команд определенного языка программирования. Отметим, что одна и та же блок-схема может быть реализована на разных языках программирования. Ответ при этом получает ЭВМ, а не человек Основными свойствами алгоритма являются: - Дискретность (от лат. discretus — разделенный, прерывистый) — представление алгоритма в виде последовательности шагов; - Массовость — применимость алгоритма к некоторому множеству исходных данных; - Определенность (детерминированность, от лат. determinate — определенность, точность) — за конечное число шагов либо должен быть получен результат, либо доказано его отсутствие. - Любое действие алгоритма должно быть строго и недвусмысленно определено в каждом случае. Например, алгоритм проезда к другу, если к остановке подходят автобусы разных маршрутов, то в алгоритме должен быть указан конкретный номер маршрута 5. Кроме того, необходимо указать точное количество остановок, которое надо проехать, скажем, три. - Однозначность — при повторном применении алгоритма к тем же исходным данным должен быть получен тот же результат. - Конечность – каждое действие в отдельности и алгоритм в целом должны иметь возможность завершения. - Результативность – алгоритм должен приводить к достоверному решению. - Понятность – исполнитель должен знать, как выполнить алгоритм Из перечисленных свойств лишь дискретность является обязательным свойством алгоритма. Можно привести примеры, когда невыполнение свойств массовости, определенности и однозначности не позволяет говорить об отсутствии алгоритма. Основная цель алгоритмизации – составление алгоритмов для ЭВМ с дальнейшим решением задачи на ЭВМ. Примеры алгоритма: 1. Любой прибор, купленный в магазине, снабжается инструкцией по его использованию. Данная инструкция и является алгоритмом для правильной эксплуатации прибора. 2. Каждый шофер должен знать правила дорожного движения. Правила дорожного движения однозначно регламентируют поведение каждого участника движения. Зная эти правила, шофер должен действовать по определенному алгоритму. 3. Массовый выпуск автомобилей стал возможен только тогда, когда был придуман порядок сборки машины на конвейере. Определенный порядок сборки автомобилей – это набор действий, в результате которых получается автомобиль. Блок-схемы Различают три основных вида алгоритмов: 1. линейный алгоритм, 2. разветвляющийся алгоритм, 3. циклический алгоритм. Линейный алгоритм – это алгоритм, в котором действия выполняются однократно и строго последовательно. Самый простой пример реализации линейного алгоритма – путь из университета домой. Словесный способ записи данного алгоритма: 1. выйти из университета на остановку; 2. подождать нужный автобус; 3. сесть на нужный автобус; 4. оплатить проезд; 5. выйти на требуемой остановке; 6. дойти до дома. Очевидно, что данный пример относится к линейному алгоритму, т.к. все действия следуют одно за другим, без условий и повторений. Разветвляющийся алгоритм – это алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий. Самый простой пример реализации разветвляющегося алгоритма – если на улице идет дождь, то необходимо взять зонт, иначе не брать зонт с собой. Приведенный выше пример псевдокода по нахождению частного двух чисел также относится к разветвляющемуся алгоритму. Циклический алгоритм – это алгоритм, команды которого повторяются некое количество раз подряд. Самый простой пример реализации циклического алгоритма – при чтении книги будут повторяться одни и те же действия: прочитать страницу, перелистнуть и т.д. В цикле с постусловием проверка условия выхода из цикла выполняется после очередного действия. Цикл "для" является модификацией цикла "пока" для ситуации, когда заранее известно количество повторений некоторых действий. Запись в блоке заголовка цикла показывает пример описания заголовка цикла, в котором действия повторяются столько раз, сколько целых значений приобретает параметр цикла i от своего начального значения 1 до конечного N с шагом 1. Обычно шаг не указывается, если он равен 1. В языках программирования имеются команды, реализующие показанные выше структуры. При разработке блок-схемы допускается делать любые записи внутри блоков, однако эти записи должны содержать достаточно информации для выполнения очередных действий. Краткие итоги Любая задача может быть разбита на элементарные действия. Для любой математической задачи или ситуации из жизни можно составить алгоритм решения. Алгоритм может быть описан словесно, псевдокодом, графически или программно. Задача всегда решается с помощью базовых типов алгоритма – линейного, разветвляющегося или циклического. Вопросы 1. Что такое алгоритм? 2. В чем состоит задача алгоритмизации? 3. Какими свойствами обладает алгоритм? 4. Какие виды алгоритма бывают? Упражнения 1. Составьте алгоритмы по походу в магазин за яблоками. Используйте линейный и разветвляющийся алгоритмы. Реализуйте их словесно. 2. Составьте алгоритм по нахождению корней квадратного уравнения через дискриминант. Используйте разветвляющийся алгоритм. Реализуйте его псевдокодом. Пример 1 Разработать блок-схему алгоритма Евклида, определяющего наибольший общий делитель (НОД) двух натуральных чисел A и B. В основе алгоритма Евклида лежит правило: НОД(A,B)= НОД(min(A,B), |A-B|), где НОД(A,B) — наибольший общий делитель двух натуральных чисел A и B. Основной идеей решения задачи является многократное применение указанного выше правила, после которого большее из чисел очередной пары уменьшается. Решение получено, когда числа оказываются равны друг другу. Поскольку количество повторений заранее неизвестно, в алгоритме следует применить цикл "пока" с предусловием (рис. 7). Упражнения. Составьте алгоритмы решения задач линейной структуры 1. Найдите площадь треугольника по трем сторонам a=2, b=3, c=6 2. найдите объем четырехугольной пирамиды, если высота пирамиды h=5, стороны основания a=4, b=6 (в основании лежит прямоугольник). Составьте алгоритм разветвляющейся структуры 3. В правильной треугольной пирамиде известны сторона основания a и угол A (в градусах) наклона боковой грани к плоскости основания; найти объем и площадь полной поверхности пирамиды, используя формулы: V=S ocн · H/2; где |