Руководство по УВП (I курс)

vk.com/club152685050

5.3.3 Разработка алгоритмов решения задачи

Принято различать логическое и физическое проектирование.

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

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

отдельная программа или программная система, состоящая из нескольких взаимосвязанных программ. Затем переходят к разработке алгоритмов программ.

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

Различают последовательности действий (вычислений) линейной,

разветвленной и циклической структуры.

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

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

то действительных корней нет.

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

vk.com/club152685050

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

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

• циклические процессы, для которых количество повторений известно

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

•циклические процессы, завершающиеся по достижении или нарушении некоторых условий - итерационные циклы;

•циклические процессы, из которых возможны два варианта выхода:

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

Формальное описание алгоритмов осуществляют с использованием схем алгоритмов и псевдокодов.

На изображение схем алгоритмов существует ГОСТ 19.701-90,

согласно которому каждой группе действий ставится в соответствие блок особой формы.

Некоторые часто используемые обозначения приведены в табл. 1.

	Основные элементы схем алгоритма						Таблица 1
	Наименование		Обозначение				Функция
						Элемент	отображает		вход	из
						внешней среды или выход из нее
	Блок начало-конец					(наиболее	частое	применение		−
	(пуск-остановка)					начало и конец программы). Внутри
						фигуры		записывается
						соответствующее действие.
						Выполнение одной		или	нескольких
						операций, обработка данных любого
	Блок вычислений					вида (изменение значения данных,
						формы		представления,
	(вычислительный
						расположения). Внутри фигуры
	блок)
						записывают	непосредственно сами
						операции, например, операцию
						присваивания a = 10*b + c.

vk.com/club152685050

Отображает

решение

или

функцию

переключательного типа

с

одним

входом и двумя или более

альтернативными

выходами,

из

которых только один может быть

выбран после вычисления условий,

определенных

внутри

этого

элемента.

Вход

в

элемент

обозначается

линией,

входящей

обычно

в

верхнюю

вершину

элемента. Если выходов два или три

то

обычно

каждый

выход

обозначается линией, выходящей из

Логический блок

оставшихся

вершин

(боковых и

(блок условия)

нижней). Если выходов больше трех,

то их следует показывать одной

линией,

выходящей

из

вершины

(чаще нижней) элемента, которая

затем

разветвляется.

Соответствующие

результаты

вычислений

могут

записываться

рядом с линиями, отображающими

эти пути. Примеры решения: в

общем случае − сравнение (три

выхода:

>,

<,

=);

в

программировании

−

условные

операторы if (два выхода: true, false)

и case (множество выходов).

Символ

отображает

выполнение

процесса, состоящего из одной или

нескольких

операций,

который

определен в другом месте программы

Предопределенный

(в

подпрограмме,

модуле).

Внутри

процесс

символа

записывается

название

процесса и передаваемые в него

данные.

Например,

в

программировании

−

вызов

процедуры или функции.

Преобразование данных в форму,

пригодную для обработки (ввод) или

отображения

результатов обработки

Данные

(вывод).

Данный

символ

не

(ввод-вывод)

определяет

носителя

данных

(для

указания

типа

носителя

данных

используются

специфические

символы).

vk.com/club152685050

Символ состоит из двух частей − соответственно, начало и конец цикла − операции, выполняемые внутри цикла, размещаются между ними. Условия цикла и приращения записываются внутри символа начала

Граница цикла или конца цикла − в зависимости от типа организации цикла. Часто для

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

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

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

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

Для рисования схем алгоритмов удобно использовать программу Microsoft Office Visio.

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

vk.com/club152685050

и не сверху вниз, то стрелка в конце линии обязательна, в противном случае

ееможно не ставить.

Вслучае, когда схема алгоритма не умещается на листе, используют соединители. При переходе на другой лист или получении управления с другого листа в комментарии указывается номер листа, например «с листа 3» «на лист 1».

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

• следование - обозначает последовательное выполнение действий

(рис. 2, а);

• ветвление - соответствует выбору одного из двух вариантов действий

(рис. 2, б);

• цикл-пока - определяет повторение действий, пока не будет нарушено условие, выполнение которого проверяется в начале цикла (рис. 2, в).

Начало		Начало
Действие 1		Условие
Действие 2	Действие 1	Действие 2
Конец		Конец
а		б

Начало

Условие

Действие

Конец

в

Рис. 2. Базовые алгоритмические структуры

Помимо базовых структур используют три дополнительные структуры,

производные от базовых:

vk.com/club152685050

•выбор - выбор одного варианта из нескольких в зависимости от значения некоторой величины (рис. 3, а);

•цикл до - повторение некоторых действий до выполнения заданного условия, проверка которого осуществляется после выполнения действий в цикле (рис. 3, в);

•цикл с заданным числом повторений (счетный цикл) - повторение некоторых действий указанное число раз (рис. 3, д).

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

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

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

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

Для каждой структуры используют свою форму описания, которая, в

общем случае может быть произвольной.

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

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

vk.com/club152685050
				нет
			Код=Код 1
					нет
	Код	Код 3		Код=Код 2
Код 1			Да
	Код 2			Да
Действие 1	Действие 2	Действие 3	Действие 1	Действие 2	Действие 3
	а			б
				Действие
	Действие
				Условие	нет
нет	Условие			Да
	Да
			Действие
	в			г
				i=n1
	i=n1,n2,h
				i<=n2
	Действие	д	е	Да	нет
				Действие
Рис.3. Дополнительные структуры и их				i=i+1
реализация через базовые структуры

vk.com/club152685050

5.3.4 Реализация

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

5.3.5 Тестирование разработанных программных модулей

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

Правильный подбор тестовых данных - отдельная и достаточно сложная задача. Для поиска логических ошибок также можно использовать отладчик:

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

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

5.3.6 Пример разработки алгоритма

Для разработки алгоритма в структурном программировании эффективно использование метода пошаговой детализации.

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

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

vk.com/club152685050

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

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

Для разработки алгоритма программы, которая находит значение аргумента х по заданному значению функции у.

Шаг 1 Определяем общую структуру программы.

Программа:

Ввести выражение для функции

Ввести у, n, E.

Вывести график функции

Определить х.

Вывести x, у.

Конец.

Шаг 2. Детализируем операцию определения х.

Определить х:

Определить х1 такое, что f(xl) < у.

Определить х2 такое, что f(x2) > у.

Определить х на интервале [х1, х2].

Все.

Шаг 3. Детализируем операцию определения х1.

Значение х1 должно быть подобрано так, чтобы выполнялось условие f(xl) < у. Известно, что x > О, следовательно, можно взять некоторое значение х, например, х1=1, и последовательно уменьшая его, например в два раза, определить значение х1, удовлетворяющее данному условию.

Определить х1:

vk.com/club152685050

х1:=Xm

цикл-пока f(xl) > у

х1:=х1/2

все-цикл

Все.

Щаг 4. Детализируем операцию определения х2.

Значение х2 определяем аналогично х1, но исходное значение будем увеличивать в два раза.

Определить х2:

х2:=0.1

цикл-пока f(x2) < у

х2:=х2*2

все-цикл

Все.

Шаг 5. Детализируем операцию определения х.

Определение х выполняется последовательным сокращением отрезка

[х1, х2].

Определить х:

цикл-пока x2-xl>E

Сократить отрезок [х1, х2].

все-цикл

Все.

Шаг 6. Детализируем операцию сокращения интервала определения х.

Сокращение отрезка достигается делением пополам и отбрасыванием

половины, не удовлетворяющей условию f(x1) <= у<= f(x2)

Сократить интервал определения х:

xt:=(xl +х2)/2