Алгоритмические структуры

Основы алгоритмизации

Алгоритм

Понятие алгоритма такое же основополагающее для информатики, как и понятие информации. Название "алгоритм" произошло от латинской формы имени величайшего среднеазиатского математика Мухаммеда ибн Муса ал-Хорезми (Alhorithmi), жившего в 783—850 гг. В своей книге "Об индийском счете" он изложил правила записи натуральных чисел с помощью арабских цифр и правила действий над ними "столбиком", знакомые теперь каждому школьнику. В XII веке эта книга была переведена на латынь и получила широкое распространение в Европе.

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

Основными свойствами алгоритма являются:

• дискретность — представление алгоритма в виде последовательности шагов;
• массовость — применимость алгоритма к некоторому множеству исходных данных;
• определенность — за конечное число шагов либо должен быть получен результат, либо доказано его отсутствие;
• однозначность — при повторном применении алгоритма к тем же исходным данным должен быть получен тот же результат.

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

• словесная (запись на естественном языке);
• графическая (изображения из графических символов);
• псевдокоды (описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.);
• программная (тексты на языках программирования).

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

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

1) овалов, кодирующих начало и конец, вход и выход из алгоритма;

2) параллелограммов, описывающих ввод и вывод данных;

3) прямоугольников, в которых описывается действие с данными;

	Действие

4) ромбов, определяющих проверяемые алгоритмом условия;

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

Алгоритмические структуры

Следование – действия выполняются строго в том порядке, в котором записаны. Образуется последовательностью действий, следующих одно за другим.

Задача.

Вычислить и вывести значение функции . Исходные данные x и а ввести с клавиатуры.

Ветвления – в зависимости от справедливости проверяемого условия (да или нет), алгоритм может пойти по одной из двух возможных ветвей. Происходит выбор одного из альтернативных путей работы алгоритма. Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран.

Задача.

Даны два действительных числа. Заменить первое число нулем, если оно меньше или равно второму, и удвоить числа в противном случае.

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

Циклические структуры бывают трех типов:

с параметром цикла - выполнять тело цикла для всех значений некоторой переменной (параметра цикла) в заданном диапазоне;

с предусловием - выполнять тело цикла до тех пор, пока выполняется условие;

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

Задача.

Составить программу расчета значений функции на интервале [a;b] в n равностоящих точках. Границы интервала и количество точек ввести с клавиатуры.

Представлены три блок-схемы:

а) с параметром цикла;

б) с предусловием;

в) с постусловием;

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

Задача.

Вывести на экран таблицу умножения.

ПРИМЕР.

Пусть перед вами стоит задача перейти дорогу по пешеходному переходу на котором имеется светофор.

Помимо вышеописанного представления алгоритмов (при помощи блок-схем) существуют и другие виды описания алгоритмов. Одним из таких видов является словесное описание. Его особенностью является обязательная нумерация каждого шага алгоритма.

1 Почтальон Печкин стучит в дверь – «тук – тук»

2 Если Галчонок слышит стук, то переход к шагу 3, иначе переход к шагу 1

3 Галчонок спрашивает: «Кто там?»

4 Если Печкин слышит вопрос, то переход к шагу 5, иначе переход к шагу 1

5 Печкин отвечает: «Это я почтальон Печкин. Я принес записку про вашего мальчика»

6 Если Галчонок открывает дверь, то переход к шагу 7, иначе переход к шагу 1.

7 Почтальон Печкин вручает конверт с письмом.

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

МАССИВЫ.

Массив – это одно- или многомерная таблица данных одного типа. Каждая ячейка таблицы имеет свой индекс (в одномерном случае) или набор индексов (в многомерном). Массив называют структурой данных со случайным доступом, поскольку к любому элементу массива можно обратиться, просто указав его индексы, т.е. все элементы одинаково доступны в любой момент времени. Массив определяется, прежде всего, общим типом его элементов и их количеством. Количество элементов массива, в свою очередь, определяется количеством индексов и диапазоном их изменения.