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

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

Тема 5.1 Алгоритм и его свойства. Способы записи алгоритма

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

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

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

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

2) Определенность (или детерминированность). Это свойство состоит в том, что каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует дополнительных указаний или сведений о решаемой задаче.

3) Результативность (или конечность). Это свойство состоит в том, что алгоритм должен приводить к решению задачи за конечное число шагов.

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

Кон

 

Часть алгоритма от слова алг до слова нач называется заголовком, а часть, заключенная между словами нач и кон – телом алгоритма.

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

Примеры предложений алг:

алг объем_и_площадь_цилиндра (аргвещ R, H, резвещ V, S)

алг диагональ (аргцел N, аргцелтаб A[1:N, 1:N], резлит otvet)

 

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

алг произведение (аргцел n, m, резцел s)

начцел i

|    ввод n, m

|    s:=0

|    i:=0

|    нцпока i<n

|    |    s:=s+m

|    |    i:=i+1

|    кц

|    вывод s

кон

Тема 5.2 Базовые алгоритмические структуры

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

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

· линейной алгоритмической структуры;

· разветвляющейся алгоритмической структуры;

· циклической алгоритмической структуры.

Линейная алгоритмическая структура

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

 

Тема 5.3 Типовые алгоритмы

Тема 5.4 Рекурсивные алгоритмы

Обращение к подпрограммам

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

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

 

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

 

алг Alg(аргвещ X, Y, Z, резвещ D)                 алг F1(аргвещ Arg, резвещ Res)

нач                                                                      нач

|    ввод X, Y, Z                                                 |    Res:=Arg*Arg

|    A:=F1(X)                                                       кон

|    B:=F2(Y,Z)                                                        

|    C:=F2(A,B)                                                    алг F2(аргвещ Arg1, Arg2, резвещ Res)

|    D:=A+B+C                                                    нач

|    вывод D                                                       |    Res:=Arg1*Arg2

кон                                                                           кон

 

 

Схема алгоритма:

 

 

Понятие рекурсии

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

a:=a+1.

 

Классическим примером рекурсивного алгоритма является функция вычисление факториала целого числа N! = 1·2·3·…·N, N ≥ 0, 0! = 1.

 

алг Факториал(аргцел N, резцел F)

Нач

|    если N=0

|    |    то F:=1

|    |    иначе F:=Факториал(N-1)*N

|    все

Кон

 

Результатом работы следующего алгоритма:

 

Алг

Нач

|    A:=Факториал(5)

|    вывод A

Кон

 

является значение A=120=5!.

 

Из рекурсивной функции необходимо предусмотреть выход, иначе вызов такой функции может привести к «зависанию» алгоритма. В рассмотренном примере условием выхода из рекурсии является проверка условия N=0, при выполнении которого функция возвращает 1. Однако данное условие неработоспособно, если будет введено отрицательное значение (N<0) аргумента функции. В этом случае функция F будет бесконечно вызывать саму себя, поэтому для предотвращения бесконечной рекурсии здесь необходимо предусмотреть и проверку условия N<0, при выполнении которого должно выдаваться сообщение об ошибке ввода.

Виды рекурсии

Рекурсия бывает прямой и косвенной:

· прямой называется рекурсия, когда обращение к самому себе содержится в самом алгоритме (функции);

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

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