Основы алгоритмизации (для лабораторных работ по гидрологии)

Введение

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

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

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

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

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

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

Из каких же действий состоит собственно алгоритм?

 

Алгоритмические действия

 

Для написания любого алгоритма обработки данных достаточно следующих девяти элементарных действий и простейших конструкций:

1. объявление переменной (указание имени и типа) – «объявить»,

2. присвоение значения переменной – «=»,

3. вычисление выражения и присвоение итогового значения переменной – «вычислить»,

4. ввод значения и занесение в переменную – «ввод»,

5. вывод значения переменной (на экран дисплея, печать и т.д.) – «вывод»,

6. выполнение действий по условию –

7. «если <условие> то <действие 1> иначе <действие 2>»,

8. повторное выполнение группы действий –

9. «цикл … [n раз]: начало <действия> конец»,

10. объявление процедуры –

11. «процедура <имя процедуры> …: начало <действия> конец»,

12. вызов и выполнение процедуры –

13. «выполнить процедуру».

Действия производятся над одной переменной, массивом переменных и группой переменных и/или элементов массива.

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

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

Рассмотрим в качестве примера набор алгоритмических действий для определения среднего слоя атмосферных осадков в регионе по показаниям метеостанций.

1. начало
2. объявление переменных:

n – число станций в регионе,

Xi - величина осадков на i-ой станции,

REZ – результат вычислений – средняя арифметическая величина слоя осадков

1. задание n различных значений переменной Xi и суммирование их

REZ = SUM (Xi), i=1,n

1. вычисление среднего арифметического: REZ = REZ / n
2. вывод результатов
3. конец

 

Здесь все действия кроме третьего являются элементарными, т.е. могут быть реализованы одной командой какого-то языка программирования (скобки «начало» и «конец» не учитываются). Пункт третий в этом наборе может быть реализован несколькими способами. Можно объявить n переменных, присвоить им значения, а затем вычислить сумму значений.

1. x1 = …

2. x2 = …

….

n. xn = …

n+1. REZ = x1+x2+….+xn

Этот способ неудобен тем, что число переменных и действий зависит от числа задаваемых значений: под каждое значение выделяется переменная и выполняется действие «присвоение значения переменной». Тот же результат может быть получен с помощью четырех действий:

 

1. n=…

2. REZ=0

3. ввести значение в переменную x

4. REZ= REZ +x

Повторять 3 и 4 действия n раз.

 

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

 

1. n=….

2. REZ =0

3. цикл ввода n значений: начало

3.1. ввод значения в переменную х

3.2. REZ=REZ + x

4. конец цикла

 

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

Рассмотрим второй вариант «цикла по условию»:

 

1. REZ=0

2. цикл ввода: начало

2.1. ввод значения в переменную х

2.2. если х = пусто, то выход из цикла

2.3. REZ=REZ +x

3. конец цикла

 

Конструкцию цикла удобно использовать, когда вводится большой объем данных. «Цикл по условию» выбирают, если число вводимых значений не известно. Для ввода известного небольшого числа значений целесообразно использовать одну команду ввода, например:

 

1. ввод трех значений в переменные х1, х2, х3

2. REZ= x1+x2+x3

 

 

Замена действий присвоения вводом позволяет применить данный набор действий к различным исходным данным { xi }, i=1,n. Причем при повторном выполнении с одними и теми же значениями исходных данных должен получиться одинаковый результат, определенный и однозначный.

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

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

1. начало

2. объявление переменных: n, x, REZ

3. выполнение процедуры А ввода и суммирования значений в REZ

4. REZ = REZ / n

5. вывод результатов

6. конец

 

1. процедура А: начало
2. присвоение начальных значений: n=…., REZ=0
3. цикл ввода n значений: начало

3.1. ввод х

3.2. REZ = REZ + x

1. конец цикла
2. конец процедуры

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

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

 

Мы подошли к более точному определению понятия «алгоритм обработки данных». Это набор правил или действий, направленных на решение задачи преобразования данных. Алгоритм должен отвечать определенным требованиям, прежде всего, конечность процесса преобразования исходных данных в выходные (за конечное число шагов). Кроме того, алгоритм должен характеризоваться массивностью, определенностью, однозначностью.

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

Свойство определенности предполагает высокие требования к точности формулировок во избежание различных толкований отдельных действий и алгоритма в целом. Например, чтобы обеспечить определенность исходного алгоритма в примере, необходимо выбрать способ реализации третьего пункта «задание значений …», объявить переменную n цикла (чтобы ввод не продолжался бесконечно), необходимо отразить, что каждой станции соответствует только одно значение осадков.

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

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

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

n – целое, 0<n<&

xi – действительное число с точностью до m знаков после запятой,

х>0, 0 < i < n

 

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

 

Первый вариант – число станций n известно заранее и задано.

 

1. процедура А: начало

2. присвоение начальных значений: n=…, REZ=0

3. цикл ввода n значений: начало

ввод значений в переменную х

если х > 0, то округлить х с точностью до m; REZ=REZ+x

4. конец цикла

5. конец процедуры А

 

Второй вариант – число станций n неизвестно и ввод продолжается до тех пор, пока не будет введено «пустое значение» (пробел).

 

 

1. процедура А: начало

2. присвоение начальных значений: i=1, REZ=0

3. цикл ввода: начало

3.1. ввод значения в переменную х

3.2.если х=пусто, то выход из цикла

3.3.если х>0, то округлить х с точностью до m; REZ=REZ+x

3.4.i=i+1

3.5.если i=1000, то вывод сообщения о превышении ограничения на число станций и выход из программы

4. конец цикла ввода

5. конец процедуры А

 

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

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

1. начало

2. объявление переменных:

n – число станций в регионе

Y – величина осадков на станциях за текущий период

X[n] – массив осадков на станциях за предыдущий период

REZ1 – результат по поступившим данным за текущий период

REZ2 – результат по накопленным и скорректированным данным на текущий период

3. выполнить процедуру ввода начальных значений в массив x[n]

4. если n=0 и массив пуст, то выход из программы

5. присвоение начальных значений: i=1, REZ1=0, REZ2=0

6. цикл ввода значений осадков за текущий период: начало

ввод значения в переменную Y

6.1.если Y=пусто, то выход из цикла

6.2.если Y <>0, X[i] = Y; REZ1=REZ1+Y

6.3.i=i+1

6.4.если i>n, то вывод сообщения об ошибке (число введенных значений превышает число станций) и выход из программы

7. конец цикла ввода

8. если REZ>0, то REZ1=REZ1 / i

9. цикл суммирования осадков на текущую дату, i=1,n: начало

9.1.REZ2=REZ2 + X[i]

9.2.если X[i] <> 0,то i=i+1

10. конец цикла

11. REZ2=REZ2 / i

12. вывод результатов

13. конец

 

ОДЗ обеспечивается и контролируется в пунктах 4; 5; 6.3; 6.5; 9.1. Пункт 6.5, в частности, гарантирует конечность процесса обработки данных.

Описанные пять требований – массовость, определенность, однозначность, конечность, контроль ОДЗ – являются основными при оценке алгоритма. Не менее важно, хоть и очевидно, требование «читабельности». Алгоритм должен содержать точное описание переменных и необходимые пояснения ко всем действиям. Из описания переменной должно явствовать ее назначение, не следует использовать одну переменную в разных целях. Действия должны быть также четко сформулированы. Если действие не является элементарным, рекомендуется представлять его в виде процедуры. Как же выделяются процедуры?