ПОНЯТИЕ АЛГОРИТМА И ЕГО СВОЙСТВА
Каждый из нас постоянно решает множество задач: как быстрее добраться на работу, как лучше спланировать дела текущего дня и многие другие. Решение каждой задачи всегда делится на простые действия, составляющие алгоритм.
Алгоритм — это любая последовательность действий, приводящая к решению поставленной задачи.
Слово «алгоритм» появилось в Средние века, когда европейцы познакомились со способами выполнения арифметических действий в десятичной системе счисления, описанными узбекским математиком Мухаммедом бен Муса аль-Хорезми («аль-Хорезми» — человек из города Хорезми; в настоящее время город Хива в Хорезмской области Узбекистана). Слово «алгоритм» есть результат европейского произношения слов «аль-Хорезми».
Алгоритм характеризуется следующими свойствами: дискретностью, массовостью, определенностью, результативностью.
Дискретность — это свойство, означающее следующее: каждый алгоритм состоит из отдельных законченных действий, т. е. «делится на шаги».
Массовость — применимость алгоритма ко всем задачам рассматриваемого типа при любых исходных данных.
Определенность — свойство алгоритма, заключающееся в строгом определении содержания и порядка выполнения отдельных шагов.
Результативность — свойство, состоящее в том, что любой алгоритм должен находить решение за конечное число шагов.
Существует несколько способов описания алгоритмов: словесное описание, блок-схема, алгоритмический язык и программа.
Словесное описание представляет структуру алгоритма на естественном языке. Например, любой прибор бытовой техники (утюг, электропила, дрель и т. п.) имеет инструкцию по эксплуатации, т. е. словесное описание алгоритма, в соответствии с которым данный прибор должен использоваться.
Запись алгоритма осуществляется в произвольной форме на естественном языке, например русском. Этот способ описания не имеет широкого распространения, так как строго не формализуем, допускает неоднозначность толкования при описании некоторых действий, страдает многословностью.
Блок-схема — описание структуры алгоритма с помощью геометрических фигур с линиями-связями, показывающими порядок выполнения отдельных инструкций. Этот способ имеет ряд преимуществ. Благодаря наглядности он обеспечивает «читаемость» алгоритма и явно отображает порядок выполнения отдельных команд. В блок-схеме каждой формальной конструкции соответствует определенная геометрическая фигура или связанная линиями совокупность фигур. К основным геометрическим фигурам, используемым для построения блок-схем, относятся следующие.
Блоки, характеризующие начало и конец алгоритма:
Блок, отображающий процесс {оператор), предназначенный для описания отдельных действий:
Блок, содержащий проверку условия, или условный блок:
Блок, описывающий цикл с параметром:
Блок ввода/вывода с произвольного носителя информации:
Описание алгоритма в словесной форме или в виде блок-схемы допускает некоторый произвол при изображении команд. Вместе с тем оно позволяет человеку легко понять суть дела и исполнить алгоритм.
Алгоритмический язык, именуемый как псевдокод, — это запись алгоритмов, во многом напоминающая запись алгоритма на естественном языке и языке программирования. При описании алгоритма на псевдокоде используются следующие конструкции:
нп — начало цикла; кп_ — конец цикла; для — цикл с параметром; если — условие; то — результат выполнения условия; иначе — результат невыполнения условия; всё — конец условия; пока — условие цикла.
Рассмотрим примеры блок-схем трех основных видов алгоритмов: линейного, разветвляющегося и циклического. Линейным называется алгоритм, в котором все этапы решения задачи выполняются строго последовательно.
Блок-схема линейного алгоритма нахождения периметра прямоугольного треугольника Рпри известных длинах его катетов a, b изображена на рис. 5.1.
Разветвляющийся алгоритм — это такой алгоритм, в котором выбирается один из нескольких возможных путей вычислительного процесса. Каждый подобный путь называется ветвью алгоритма. Признаком разветвляющегося алгоритма является наличие условия.
Различают неполное (если-то) и полное (если—то-иначе) виды ветвления.
Неполное ветвление предполагает наличие оператора только на одной ветви (то; Да; Истина), на другой ветви оператор отсутствует и управление сразу переходит к точке слияния
Полное ветвление позволяет организовывать две ветви в алгоритме (то или иначе; Да илиНет; Истина или Ложь), каждая из которых ведет к общей точке их слияния (рис. 5.26).
Циклическим, или просто циклом, называют такой алгоритм, в котором получение результата обеспечивается многократным выполнением одних и тех же операций. Группа повторяющихся операций называется телом цикла.
Широкое применение получили три типа циклов: цикл с параметром, цикл с предусловием и цикл с постусловием.
Цикл с параметром используется в тех случаях, когда известна величина k, т. е. количество элементов или шагов цикла.
Количество шагов цикла с предусловием заранее не определено. В нем сначала проверяется выполнение условия. Если оно Истинно (Да), то исполняется тело цикла, после чего вновь проверяется условие. Указанные действия проверяются до тех пор, пока условие не примет значение Ложно (Нет).
Цикл с постусловиемотличается от цикла с предусловием расположением условия и тем, что тело цикла всегда будет выполнено хотя бы один раз. Тело этого цикла будет выполняться, пока условие Ложно (Нет).
Для повышения производительности и качества работы каждый язык программирования имеет структурированный тип данных — массив.
Массивом называется упорядоченная совокупность однотипных величин, имеющих общее имя, элементы которой различаются порядковыми номерами, именуемыми индексами.
Дата добавления: 2016-06-15; просмотров: 3646;