Файл: Алгоритмизация как обязательный этап разработки программы (Современное понятие программного обеспечения).pdf

Еще один пример: разработка алгоритмов для АСУ ТП. Там сплошная алгоритмизации. Есть, например, методики расчета ТЭП (технико-экономических показателей), но их надо в процессе алгоритмизации переложить на язык блок-схем, затем программистам предстоит переложить порядок действий с языка блок-схем (алгоритмов) на алгоритмический язык, понятный ЭВМ.

Пошаговая программа «подключения потока» («on-line»)

Шаг 1

Подать команду на открытие:

клапана на общем входе в предварительный фильтр очистки B10/20-AA500;
клапана F10/20-AA503 на входе в ФСД для нагнетания давления.

Проверить условия:

открыт клапан на входе в предварительный фильтр очистки B10/20-AA500;
открыт клапан F10/20-AA503 на входе в ФСД для нагнетания давления;
давление F10/20-CP001 в ФСД больше 0,50 бар.

При выполнении выше перечисленных условий перейти к выполнению шага 2, иначе – действия прекратить.

Шаг 2

Подать команду на открытие:

основного клапана F10/20-AA502 на входе в ФСД;
клапана F10/20-AA515 отбора проб на выходе ФСД.
клапана F10/20-AA516 на выходе из ФСД на ВСАС рециркуляционых насосов промывки.

Подать команду на закрытие:

клапана F10/20-AA503 нагнетания давления в ФСД.

Подать команду на включение:

насоса рециркуляционой промывки F31/32-AP001.

Проверить условия:

открыт основной клапан F10/20-AA502 на входе в ФСД;
открыт клапан F10/20-AA515 отбора проб на выходе из ФСД.
открыт клапан F10/20-AA516 на выходе из ФСД на всас рециркуляционых насосов промывки;
закрыт клапан F10/20-AA503 нагнетания давления в ФСД;
включен насос рециркуляционой промывки F31/32-AP001;
перепад давления на ФСД ниже 3 бар (F10/20-CP001, F10/20-CP002);
расход на рециркуляционную промывку выше 100000 кг/ч, (100м3/ч) (F00-CF001).

При выполнении выше перечисленных условий перейти к выполнению шага 3. И так далее...

Обычные технологические инструкции часто являются предварительным этапом алгоритмизации. В исполнительных инструкциях объектами являются физические объекты – например, задвижки и клапана, а действиями являются физические действия – например, открыть и закрыть. В вычислительных инструкциях объектами являются математические объекты – например, формулы, обрабатываемы значения или таблицы значений, а действиями являются математические действия – например, вычисления по формулам и обработка таблиц. [16] Кроме этого, в инструкциях могут быть проверки выполнения логических условий: например, достигнуто ли нужное давление в емкости или не является ли делитель нулем.

Таким образом, в данной главе были рассмотрены такие понятия, как «программное обеспечение» и «алгоритм».

ГЛАВА 2. ПРИЕМЫ АЛГОРИТМИЗАЦИИ

2.1 Алгоритмические конструкции

Для записи алгоритмов существуют разные способы: текстово-формульная запись, блок-схема, машина Тьюринга, машина Поста, программа на алгоритмическом языке и др. Каждый алгоритм записывается в системе команд исполнителя. Вне зависимости от выбранной формы записи элементарные шаги алгоритма объединяются в алгоритмические конструкции (структуры): последовательные, ветвящиеся, циклические, вспомогательные алгоритмы и рекурсивные. В 1966 году Бом и Джакопини доказали, что для записи любого сколь угодно сложного алгоритма достаточно трех основных алгоритмических конструкций: последовательных, ветвящихся, циклических. [3, 8]

Алгоритм P (или его часть) реализован через последовательную алгоритмическую конструкцию (следование), если каждый шаг алгоритма выполняется один раз, причем после каждого i-го шага выполняется (i + 1)-й шаг, если i-й шаг — не конец алгоритма. Такой алгоритм или часть алгоритма еще называют линейным. [17]

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

перевези Козу;
вернись на исходный берег;
перевези Волка;
вернись на исходный берег с Козой;
перевези Капусту;
вернись на исходный берег;
перевези Козу.

Алгоритм P реализован с использованием ветвящейся алгоритмической конструкции (ветвления), если на каком-либо шаге последовательное выполнение алгоритма прерывается, и выбор следующего шага определяется входными данными алгоритма. Ветвление задает выполнение либо одной, либо другой группы операторов в зависимости от выполнения какого-либо условия, затем исполнение алгоритма выходит на общее продолжение. Для конкретных входных данных ветвящаяся алгоритмическая конструкция сводится к последовательной алгоритмической конструкции. Ветвление бывает полным и неполным. В случае неполного ветвления при невыполнении условия никакие действия не выполняются. [17]

Пример 2. Запишем в словесной форме алгоритм решения уравнения ax2 + bx + c = 0, где a, b, c — произвольные действительные числа, а x — искомая величина. Если a 0, то для нахождения корней используются известные формулы, при этом существование корней зависит от знака дискриминанта квадратного уравнения. Если a = 0, то уравнение становится линейным. Однако при b = 0 оно вырождается в равенство c = 0. Поэтому, если c действительно равно 0, то все действительные числа являются корнями такого уравнения, в противном случае — корней нет. Ниже приведена блок-схема данного алгоритма.

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

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

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

Следование не имеет специальной формы записи, а выражается в том, что входящие в него шаги записываются последовательно, а управление после выполнения очередного шага этой конструкции переходит к следующему. В текстовой форме записи — это просто последовательная запись пунктов, соответствующих шагам алгоритма. В блок-схемах — это последовательная запись блоков действия, соединенных стрелкой, направленной от предыдущего блока к следующему. На процедурном языке программирования данная конструкция выражается просто последовательной записью инструкций (операторов языка программирования). [15]

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

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

2.2 Практические приемы алгоритмизации

Рассмотрим практические примеры, на примере следующей программы: пользовательское приложение «RSS Viewer», с помощью которого пользователь сможет загружать актуальные новости из различных новостных RSS источников.

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

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

На рисунке 1 показана диаграмма переходов состояния программы.

Рисунок 1 – Диаграмма переходов состояния

Представленная диаграмма описывает переходы программы из одного состояния в другое, учитывая условия перехода и действия, выполняющиеся при переходе.

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

Рисунок 2 – Диаграмма вариантов использования

Разделим программу на предметные области (классы). В данных классах при необходимости выделим атрибуты. В качестве атрибутов представим некоторые, существенные с точки зрения решаемой задачи характеристики объектов.

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

На рисунке 3 представлена концептуальная модель данной системы.

Рисунок 3 – Концептуальная модель предметной области

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

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

Всё выше описанное можно представить в виде общего алгоритма программы, которое можно изобразить в виде блок-схемы (рисунок 4)

Рисунок 4 – Блок схема алгоритма

Рассмотрим примеры создания простейших алгоритмов на примере некоторых программ на Python.

1. Программа на Python для поиска факториала числа.

Факториал числа является произведением всех целых чисел от 1 до этого числа. Например, факториал 6 (обозначается как 6!) Равен 1 * 2 * 3 * 4 * 5 * 6 = 720. Факториал не определен для отрицательных чисел, а факторный нуль - один, 0! = 1. Подробный код программы показан в листинг кода 1.

Листинг кода 1.

# Программа для поиска факториала числа

# Ввод числа

num = int(input("Введите число: "))

factorial = 1

# проверка числа

if num < 0:

print("Факториала не существует для отрицательных чисел")

elif num == 0:

print("Факториал нуля равен 1")

else:

for i in range(1,num + 1):

factorial = factorial*i

print("Факториал",num," = ",factorial)

Алгоритм программы заключается в том, что здесь число, в котором находится факториал, хранится в num и мы проверяем, является ли число отрицательным, нулевым или положительным с использованием if...elif...else оператора. Если число положительное, мы используем for цикл и range() функцию для вычисления факториала.

2. Программа Python для поиска второго по величине числа в списке.

Программа берет список и печатает второе по величине число в списке.

Подробный код программы показан листингом кода 2.

Листинг кода 2.

a=[]

n=int(input("Введите количество чисел:"))

for i in range(1,n+1):

b=int(input("Введите элемент:"))

a.append(b)

a.sort()

print("Второй по величине элемент:",a[n-2])

Выполняемые шаги: