Алгоритмизация и программирование (стр. 1 )

Алгоритмизация и программирование

Определение алгоритма

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

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

Рассмотрим простую задачу нахождения максимального числа в списке из N действительных чисел R(1), R(2), ..., R(N). Основная идея алгоритма заключается в том, чтобы перебирать по очереди все числа списка и запоминать наибольшее до сих пор встретившееся число. К тому моменту, когда весь список будет проверен, запомнится наибольшее число.

Algorithm MAX. Даны N действительных чисел в одномерном массиве R(1), R(2), . . ., R(N), найти такие М и J, что M = R(J) = maxR(K), 1 < K < N. В случае, когда два или более элементов R имеют наибольшее значение, запоминается наименьшее значение J.

Шаг 0. [Установка в начальное состояние] M := R(1), J := 1.

Шаг 1. [N = 1?] If N = 1 then STOP fi.

В этом алгоритме fi и od используются соответственно для обозначения конца конструкций If и Do.

Шаг 2. [Проверка каждого числа] For K := 2 to N Do Шаг 3 od; STOP.

Шаг 3. [Сравнение] If M < R(К) then M := R(K); J := K fi (теперь M - наибольшее число из проверенных, а К - его номер в массиве).

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

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

Блок –схема – это графическое представление алгоритма, дополненное элементами словесной записи. Каждый пункт алгоритма отображается на блок-схеме некоторой геометрической фигурой-блоком.

Символика блок-схем:

Операторы ввода-вывода. В операторах ввода – вывода записываются имена тех переменных, значения которых должны вводиться в оперативную память или выводиться из нее.

Ввод А, В, С	Если в программе встречается этот оператор, то процессор переходит в режим ожидания до тех пор, пока через клавиатуру не будут введены три числа, разделенные запятыми или пробелами. После ввода последнего числа надо нажать <Enter>. Числа кодируются, т. е. переводятся из обычного вида во внутренний код ЭВМ. Закодированные числа помещаются в ячейки памяти с символическими именами А, В, С.
Печать ‘x = ’	Печатаются символы x =.
Печать x, y	Из ячеек с именами x и y выбираются числа. Они преобразуются из машинного кода к обычному виду (декодируются и выводятся на экран монитора).
Печать ‘x = ‘, x	Если x имеет значение, равное 5, то на экран выводится строка x = 5

Операторы присваивания.

С = А+В	Содержимое ячеек памяти с символическими адресами A и Β суммируются. Результат записывается в ячейку с символическим адресом C.
X = X+DX	Содержимое ячеек памяти с символическими адресами X и DX суммируется. Старое значение ячейки X будет стерто, будет записано новое значение переменной X.
I = I+1	Говорят, что значение переменной I увеличилось на 1
Y = sin(x)	В ячейке с символическим адресом x записано значение угла, по которому вычисляется значение синуса и результат записывается в ячейку Y
5 = 2+3	Ошибка, т. к. слева от символа = не может стоять константа.
А+В=С	Ошибка, т. к. слева от знака = может находиться только переменная

Разветвление

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

Подпрограмма

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

Соединитель

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

Комментарии можно записывать возле любого блока.

Рассмотрим пример алгоритма – алгоритм отыскания минимума и максимума в любой конечной последовательности из n вещественных случайных чисел а1, а2, а3, а4, ….,аn. При небольшом количестве чисел достаточно беглого взгляда, чтобы указать максимум и минимум. Однако, если n велико, задача усложняется. Поэтому необходимо придерживаться определенной системы. Например, взять в качестве начального значения как для максимума, так и для минимума первое число, далее последовательно перебирать числа и сравнивать каждое из них с установленным к текущему моменту значением максимума. Если очередное число превышает максимум, считать его новым значением максимума (прежнее значение «забыть»), после чего можно переходить к новому числу. Если анализируемое число не больше максимума, то сравнить его с установленным е текущему моменту значением минимума. Если число оказывается меньше минимума, считать его новым значением минимума и перейти к следующему числу; если число не меньше минимума, просто перейти к анализу следующего числа. Перебрав таким образом все числа, получим окончательное значение максимума и минимума. Блок – схему этого алгоритма можно представить следующим образом.

Из рассмотренных выше блоков можно собирать различные структуры. Основные понятия и правила построения структур не зависят от конкретного содержания программы.

Структурная блок-схема – это блок-схема, которая может быть выражена как композиция из четырех элементарных блок-схем: композиции, выбора (альтернатива), цикл с предусловием, цикл с постусловием

Структурное программирование – процесс разработки алгоритмов с помощью структурных блок-схем.

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

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

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

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

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