Билет2 . Вопрос1

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

1. АЛГОРИТМ.

Понятие алгоритма является одним из основных в информатике. Слово “алгоритм” происходит от имени узбекского математика аль-Хорезми, что означает “из Хорезма”. Длительное время алгоритмом пользовались только математики, понимая под алгоритмом описание решения задачи. Начиная с 30-годов 20 века понятие алгоритма становится объектом математического изучения. Возникла новая математическая дисциплина - теория алгоритмов. Несколько позже развитие ЭВМ и их широкое применение сделали понятие алгоритма одним из базовых понятий информатики и ВТ.

АЛГОРИТМ - это конечная последовательность чётко сформулированы правил и команд, предназначенных для решения конкретной задачи.

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

ПРИМЕРЫ АЛГОРИТМОВ :

- вычислительных : - правило возведения числа в степень;

- извлечение корня из n-степени;

- сложение, умножение, деление дробей;

- решение линейных, квадратных, биквадратных;

- нахождение S и V фигур;

- невычислительных ( бытовых ) : - рецепт приготовления блюд;

- правило пользования лифтом,

междугородним телефоном;

- инструкция по использованию электро приборов;

2. СПОСОБЫ ОПИСАНИЯ АЛГОРИТМОВ.

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

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

- псевдокода;

- блок схем;

- программ и т.д.;

2.1. СЛОВЕСНОЕ ОПИСАНИЕ АЛГОРИТМА.

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

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

ПРИМЕР : Найти наибольшего из трёх заданных чисел a, b, c.

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

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

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

НЕДОСТАТКИ СЛОВЕСНОГО СПОСОБА :

- отсутствие наглядности;

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

ДОСТОИНСТВА : С его помощью можно описать любые алгоритмы, в том числе и вычислительные.

СПЕЦИАЛЬНЫЕ СОГЛАШЕНИЯ ДЛЯ СЛОВЕСНОЙ ЗАПИСИ АЛГОРИТМОВ:

• 1. Знак присваивания, слева от которого записывают ту переменную, которой присваивается значение, записанное справа от знака присваивания. Например, х:=х+1

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

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

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

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

Пример алгоритма построения треугольника по трём сторонам:

• 1. Начало.

• 2. На произвольной прямой выбрать точку А. Раствором циркуля, равным а, отложить отрезок АВ=а.

• 3. Из точки А провести окружность радиуса в.

• 4. Из точки В провести окружность радиуса с.

• 5. Конец.

2.2. ГРАФИЧЕСКИЙ СПОСОБ ОПИСАНИЯ АЛГОРИТМА.

Является достаточно наглядным и простым способом описания алгоритма.

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

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

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

Последовательность блоков и линий образуют блок-схему алгоритма .

ПРАВИЛА ИЗОБРАЖЕНИЯ БЛОК- СХЕМ АЛГОРИТМА.

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

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

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

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

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

Пример нахождения максимума трех чисел.

2.3. ОПИСАНИЕ АЛГОРИТМОВ С ПОМОЩЬЮ ПРОГРАММ.

Алгоритм, записанный на языке программирования называется программой.

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

Пример программы на языке программирования Паскаль:

PROGRAM RR;

VAR A,B,C, max: INTEGER;

BEGIN

WRITE(‘ ВВЕДИТЕ A, B, C');

READLN(A,B,C);

IF A>B THEN max:=A

ELSE max:=B;

IF C>max THEN max:=C;

WRITELN(max);

END.