Технология структурного программирования.
При разработке алгоритмов обычно используют метод пошаговой детализации (поэтапно):
1. На первом этапе описываются решения поставленной перед программой задачи, выделяются подзадачи.
2. В последующих этапах описывается решение каждой подзадачи, выделяя при этом новые подзадачи. Так происходит до тех пор, пока решение подзадач не будет очевидным. Рекомендовано решение каждой задачи описывать при помощи 1 - 2 конструкций не более, чтобы более четко представлять структуру программы.
Например: Требуется разработать программу, которая с определенной точностью eps находит значение аргумента x по заданному значению функции y при известном значении n
Где: n>1, x>0
При n>1 функция является монотонно возрастающей, значение аргумента x можно определить с помощью метода половинного деления. В чем заключается это метод?
1. Находим отрезок [x1, x2], который удовлетворяет условию: f(x1)<=y<=f(x2).
lign="left">2. Делим полученный отрезок пополам: xt=(x1+x2)/2 и определеяем в какой половине отрезка находится x. Для этого сравниваем два значения: f(x1) и y.
3. Полученный отрезок вновь делим пополам, процесс повторяется до тех пор, пока разность x1 и x2 не станет меньше заданного значения eps.
При разработке алгоритма данной программы используем метод пошаговой детализации.
1 этап. Общая структура программы:
Программа:
Ввести y, n, eps
Определить x
Вывести x, y
Конец.
2 этап. Детализируем операцию определения x:
Определить x
Определить x1 такое, что f(x1)<=y
Определить x2 такое, что f(x2)>=y
Определить x на интервале [x1, x2]
Все.
3 этап. Детализируем операцию определения x1. Значение x1 подбираем таким образом, чтобы выполнялось условие f(x1)<=y. Известно, что x>0, следовательно, берем любое значение x, например x1=1 и будем его пследовательно уменьшать, допустим в 2 раза. Таким образом определим значение x1, удовлетворяющее данному условию:
Определить x1:
x1:=1
цикл - пока f(x1)>y
x1:=x1/2
Все - цикл
Все
4 этап. Детализируем операцию определения x2. Значение x2 определяем аналогично x1, но исходное значение будем последовательно увеличивать в 2 раза.
Определить x2:
x2:=1
цикл - пока f(x2)< y
x2:=x2*2
Все - цикл
Все.
5 этап. Детализируем операцию определения x. Определение x выполняется последовательным сокращением отрезка [x1, x2].
Определить x:
цикл - пока x2-x1>eps
сократить отрезок [x1, x2]
все - цикл
Все.
6 этап. Детализируем операцию сокращения отрезка [x1, x2]. Интервал определения x сокращаем делением пополам и отбрасываем половину, которая не удовлетворяет условию f(x1)<=y<=f(x2):
Сократить интервал определения x:
xt=(x1+x2)/2
если f(xt)>y
то x2:=xt
иначе x1:=xt
все - если
Все.
Таким образом, за 6 этапов разработан следующий алгоритм:
Программа:
Ввести y, n, eps
x1:=1
цикл - пока f(x1)>y
x1:=x1/2
все - цикл
x2:=1
цикл - пока f(x2)< y
x2:=x2*2
все - цикл
цикл - пока x2-x1>eps
xt:=(x1+x2)/2
если f(xt)>y
то x2:=xt
иначе x1:=xt
все - если
все - цикл
Вывести xt, y
Конец.
Таким образом, на каждом этапе решается простая задача, что облегчает разработку алгоритма.
Достоинства метода пошаговой детализации:
1. Сохраняется концептуальная целостность программы: от сложного к простому.
2. Проектирование программы, кодирование, проверку и документирование можно делать параллельно.
3. В каждый момент времени (даже в начале разработки) имеется работающий вариант программы.
4. Фразы естественного языка, будучи закомментированными, служат хорошим путеводителем по программе.
В процессе создания программы особое внимание нужно уделять разработке алгоритмов. Такой подход поможет избежать ошибок, допущенных при проектировании программного продукта. Наличие подобных ошибок потребует массу времени на исправление, возврат на предыдущие этапы разработки с целью их доработки.
Базовые структуры: следование, развилка, цикл.
Следование -одна из самых важных структур. Она означает, что два действия должны быть выполнены друг за другом.
Пример 1. Пешеход шел по пересеченной местности. Его скорость движения по равнине v1 км/ч, в гору — v2 км/ч и под гору — v3 км/ч. Время движения соответственно t1, t2 и t3 ч. Какой путь прошел пешеход?
| 1. Ввести v1, v2, v3, t1, t2, t3. 2. S1 := v1 * t1. 3. S2 := v2 * t2. 4. S3 := v3 * t3. 5. S := S1 + S2 + S3. 6. Вывести значение S. 7. Конец. |
Для проверки работоспособности алгоритма необходимо задать значения входных переменных, вычислить конечный результат по алгоритму и сравнить с результатом ручного счета.
Развилка.Достаточно часто то или иное действие должно быть выполнено в зависимости от значения логического выражения, выступающего в качестве условия. В таких случаях используется развилка.
Пример 2. Дано натуральное число n. Если число нечётное и его удвоение не приведет к выходу за 32767 (двухбайтовое целое число со знаком), удвоить его, иначе — оставить без изменения.
Чтобы удовлетворить условию удвоения, число n должно быть нечетным и меньше 16384.
| 1. Ввести число n 2. Если число n нечетное и меньше 16384, то n := n * 2 3. Вывод n 4. Конец |
Рассмотренный пример иллюстрирует неполную развилку. Также следует отметить, здесь логическое выражение, являющееся условием, содержит 2 операнда.
Циклы. Если какие-либо операторы необходимо выполнить несколько раз, то их не переписывают каждый раз заново, а организуют цикл.
Пример 1. Подсчитать количество нечетных цифр в записи натурального числа n.
Пример 2. Дана последовательность, общий член которой определяется формулой
Вычислить при n>2 сумму тех ее членов, которые больше заданного числа e.
При решении задачи находится очередной член последовательно и, если он больше e, добавляется к сумме.
| 1. Ввести e 2. S := 0 3. A := 1/4 4. n := 3 5. Сравнить А с e. Если A>=e, переход к п. 10 6. S := S + A 7. A := (n-1)/(n*n) 8. n := n + 1 9. Переход к п. 5 10. Вывод S 11. Конец |
В рассмотренных выше примерах количество повторений заранее неизвестно. В первом оно зависит от количества цифр в записи натурального числа, во втором — от числа e.
Вложенность базовых структур.
Логическая структура программы может быть выражена комбинацией трех базовых структур: СЛЕДОВАНИЕ, РАЗВЕТВЛЕНИЕ, ЦИКЛ.
Характерной особенностью этих структур является наличие в них одного входа и одного выхода.
Важнейшей базовой структурой, вытекающей из принципа обеспеченности переменной, является структура СЛЕДОВАНИЕ, означающая, что два действия должны быть выполнены друг за другом. Каждое действие может означать одно единственное действие или включать в себя несколько действий. Алгоритм, содержащий только структуры СЛЕДОВАНИЕ, называется линейным алгоритмом.
Приведенная последовательность операторов не допускает никакой перестановки, так как при перестановке нарушается принцип обеспеченности переменных, и расчет заданной функции становится невозможен.
Структурограмма СЛЕДОВАНИЕ
Структура РАЗВЕТВЛЕНИЕ обеспечивает в зависимости от результата проверки условия выбор одного из альтернативных путей работы алгоритма. Каждый из путей ведет к общему выходу, так что работа алгоритма продолжается независимо от того, какой путь выбран.