Алгоритмы и способы их описания

Размещено на http://www.allbest.ru/

Алгоритмы и способы их описания

Введение

Алгоритм - понятное и точное предписание совершить определенную последовательность действий, направленных на достижение указанной цели или решение поставленной задачи.

Термин "алгоритм" происходит от имени узбекского ученого Аль-Хорезми, который в своем труде «Арифметический трактат» изложил правила арифметических действий над числами в позиционной десятичной системе счисления. Эти правила и назвали алгоритмами. Таким образом, изучаемые в школе правила сложения, вычитания, умножения, деления, возведения в степень и т. д. - все это алгоритмы. Многие правила и инструкции представляют собой подробнейшие указания, годные во всевозможных ситуациях.

Свойства алгоритмов

· Дискретность - алгоритм должен быть разбит на шаги (отдельные законченные действия).

· Определенность - у исполнителя не должно возникать двусмысленностей в понимании шагов алгоритма (исполнитель не должен принимать самостоятельные решения).

· Результативность (конечность) - алгоритм должен приводить к конечному результату за конечное число шагов.

· Понятность - алгоритм должен быть понятен для исполнителя.

· Эффективность - из возможных алгоритмов выбирается тот алгоритм, который содержит меньше шагов или на его выполнение требуется меньше времени .

Виды алгоритмов

Виды алгоритмов как логико-математических средств в зависимости от цели, начальных условий задачи, путей ее решения, определения действий исполнителя подразделяются следующим образом:

· механические алгоритмы, иначе детерминированные;

· гибкие алгоритмы, иначе вероятностные и эвристические.

Механический алгоритм задает определенные действия, обозначая их в единственной и достоверной последовательности, обеспечивая тем самым однозначный требуемый или искомый результат, если выполняются те условия процесса или задачи, для которых разработан алгоритм.

Эвристический алгоритм - это такой алгоритм, в котором достижение конечного результата программы действий однозначно не предопределено, так же как не обозначена вся последовательность действий исполнителя. В этих алгоритмах используются универсальные логические процедуры и способы принятия решений, основанные на аналогиях, ассоциациях и опыте решения схожих задач.

Алгоритм применительно к вычислительной машине - точное предписание, т. е. набор операций и правил их чередования, при помощи которого, начиная с некоторых исходных данных, можно решить любую задачу фиксированного типа.

В процессе алгоритмизации исходный алгоритм разбивается на отдельные связанные части, называемые шагами, или частными алгоритмами.

Различают четыре основных типа частных алгоритмов:

· линейный алгоритм;

· алгоритм с ветвлением;

· циклический алгоритм;

· вспомогательный, или подчиненный, алгоритм.

Линейный алгоритм - набор инструкций, выполняемых последовательно во времени друг за другом.

Алгоритм с ветвлением - алгоритм, содержащий хотя бы одно условие, в результате проверки которого ЭВМ обеспечивает переход на один из двух возможных шагов.

Циклический алгоритм - алгоритм, предусматривающий повторения одного и того же действия над новыми исходными данными. Необходимо заметить, что циклический алгоритм легко реализуется посредством двух ранее рассмотренных типов алгоритмов.

Вспомогательный, или подчиненный, алгоритм - алгоритм, ранее разработанный и целиком используемый при алгоритмизации конкретной задачи. алгоритм словесный блок схема программа

На всех этапах подготовки к алгоритмизации задачи широко используется структурное представление алгоритма в виде блок-схем.

Блок-схема - графическое изображение алгоритма в виде схемы связанных между собой с помощью стрелок (линий перехода) блоков - графических символов, каждый из которых соответствует одному шагу алгоритма. Внутри блока приведено описание совершаемых в нем действий.

Приведем схемы основных конструкций алгоритмов:

Способы описания алгоритмов

Выбор средств и методов для записи алгоритма зависит прежде всего от назначения (природы) самого алгоритма, а также от того, кто (что) будет исполнителем алгоритма.

Алгоритмы записываются в виде:

· словесных правил,

· блок-схем,

· программ.

Словесный способ описания алгоритмов - это, по существу, обычный язык, но с тщательным отбором слов и фраз, не допускающих лишних слов, двусмысленностей и повторений. Дополняется язык обычными математическими обозначениями и некоторыми специальными соглашениями.

Алгоритм описывается в виде последовательности шагов. На каждом шаге определяется состав выполняемых действий и направление дальнейших вычислений. При этом если на текущем шаге не указывается, какой шаг должен выполняться следующим, то осуществляется переход к следующему шагу.

Пример. 

Составить алгоритм нахождения наибольшего числа из трех заданных чисел a, b, c.

1. Сравнить a и b. Если a>b,то в качестве максимума t принять a, иначе (a<=b) в качестве максимума принять b.

2. Сравнить t и c. Если t>c, то перейти к шагу 3. Иначе (t<c) принять в качестве максимума c (t=c).

3. Принять t в качестве результата.

Недостатки словесного способа описания алгоритмов:

· отсутствие наглядности,

· недостаточная точность.

Достоинства словесного способа описания алгоритмов:

1. С его помощью можно описать любые алгоритмы, в том числе и вычислительные.

2. Специальные соглашения, используемые для записи словесных алгоритмов.

· Для задания значения исходных данных используют указание ВВЕСТИ.

· Для запоминания промежуточного результата используют вспомогательные переменные.

· Для задания значений переменным используется знак присваивания ( := ). Слева от него записывают ту переменную, которой присваивается значение выражения, находящегося справа от знака присваивания. Например,х:=х+1.

· Для указания начала и конца алгоритма используют указания НАЧАЛО и КОНЕЦ.

· Все шаги нумеруют.

Графический способ описания алгоритмов - это способ представления алгоритма с помощью общепринятых графических фигур, каждая из которых описывает один или несколько шагов алгоритма.

Внутри блока записывается описание команд или условий.

Для указания последовательности выполнения блоков используют линии связи (линии соединения ).

Существуют определенные правила описания алгоритмов в виде блок-схем:

1. В блок-схеме можно использовать строго определенные типы блоков:

2. Стрелки на линиях связи можно не ставить при направлении сверху вниз и слева направо; противоположные направления обязательно указывают стрелкой на линии.

3. Для удобства блоки могут помечаться метками (буквами или цифрами).

4. Внутри блока ввода/вывода пишется ВВОД или ВЫВОД и перечисляются имена данных, подлежащих вводу/выводу.

5. Внутри блока действия для присваивания переменных значений используется знак присваивания.

Описание алгоритмов с помощью программ - алгоритм, записанный на языке программирования, называется программой.

Словесная и графическая формы записи алгоритма предназначены для человека. Алгоритм, предназначенный для исполнения на компьютере, записывается на языке программирования (языке, понятном ЭВМ). Сейчас известно несколько сот языков программирования. Наиболее популярные: Си, Паскаль, Бейсик и т. д. Пример.

Составить алгоритм нахождения наибольшего числа из трех заданных чисел a, b, c. program MaxFromThree; var a, b, c, result: Real; begin Write ('Введите a, b, c'); ReadLn (a, b, c); if a>b then result := a else result := b; if c>result then result := c; WriteLn ( ' Максимальное из трех чисел равно:', result :9:2) end.

Список литературы

1. Порублев Илья Николаевич, Ставровский Андрей Борисович Алгоритмы и программы. Решение олимпиадных задач. -- М.: «Вильямс», 2007.

2. Вычислительная техника и программирование. Под ред. А.В.Ретрова. - М.: Высшая школа, 1990

3. Кузнецов А.А. и др. Основы информатики. - М.: Дрофа, 1998

4. Кушниренко А.Г. и др. Информатика. - М.: Дрофа, 1998

5. Лебедев Г.В., Кушниренко А.Г. 12 лекций по преподаванию курса информатики. - М.: Дрофа, 1998

6. Шауцукова Л.З. Информатика 10 - 11. М.: Просвещение, 2000

Размещено на Allbest.ru