Определения элементов цикла
Рассмотрим формальные определения терминов, приведенных выше.
Инвариантом называется условие, которое выполняется на каждом шаге цикла, включая значение переменных до начала выполнения цикла и после выполнения цикла. Это условие может быть записано в виде математического отношения, связывающего между собой переменные, участвующие в цикле.
Предусловием называется состояние переменных перед выполнением цикла. Это условие должно совпадать с инвариантом, в который подставили некоторые конкретные значения переменных. Во многих случаях предусловие цикла не совпадает с данными задачи. В таких случаях нужно произвести некоторые действия (которые чаще всего заключаются в присвоении значений переменным), которые приводят к выполнению предусловия. Эти действия называются инициализацией цикла.
Постусловием называется состояние переменных после выполнения цикла. Это условие также должно совпадать с инвариантом, в который подставили некоторые конкретные значения переменных. При этом постусловие должно соответствовать условию решения задачи. В некоторых случаях нужно сделать еще несколько действий вне цикла для достижения условия решения.
Частью постусловия является условие окончания (или условие выполнения) цикла. Эта часть постусловия должна дать возможность определить, что инвариант пришел к состоянию предусловия.
Телом цикла называются действия внутри цикла. Эти действия должны, во-первых, приблизить условие окончания цикла, во-вторых, сохранить инвариант на каждом шаге. Обычно тело цикла записывается по примерно следующему алгоритму: определяется шаг цикла, который приближает предусловие, затем определяются действия, которые обеспечивают условие инварианта после шага цикла.
После определения всех условий цикла и тела вместе с шагом цикл можно записать на языке высокого уровня.
Пример формального построения цикла
Рассмотрим
задачу. Допустим, необходимо подсчитать
сумму ряда
Остаток ряда, начиная с члена меньше
некоторого параметра eps,
нужно отбросить.
Для решения этой задачи нужно построить цикл, на каждом шаге которого прибавлялось бы по одному слагаемому.
На
каждом шаге цикла должны быть справедливы
следующие условия (инвариант цикла).
Обозначим i номер
шага цикла. Тогда слагаемое, которое
нужно прибавить, определяется по
формуле:
.
Переменная, в которой мы будем накапливать
сумму, должна попадать под условие:
.
На нулевом шаге для выполнения инварианта переменные должны иметь следующие значения: i = 0; p = 1; s = 1 – это предусловие цикла.
Цикл нужно закончить, при p < eps – условие окончания цикла, или цикл должен продолжаться до тех пор, пока p ≥ eps – условие выполнения цикла.
Определив все условия цикла, можно записать тело цикла.
Для
того чтобы приблизиться к окончанию
цикла, переменную i
нужно увеличить:
.
Чтобы сохранить инвариант, переменную p нужно изменить следующим образом:
.
Учитывая,
что
,
получим второе соотношение:
.
Мы
получили два соотношения для вычисления
:
через старое значение i
и через новое
.
Следует отметить, что выбор соотношения
зависит от порядка вычисления.
Выведем формулу для вычисления s:
Теперь можно записать цикл на языке С:
int main()
{
float eps = 0.001;
int i=0;
float s=1, p=1;
for(;p>eps;i++)
{
p=p/(i+1);
s=s+p;
}
printf("e=%f",s);
}
Для упрощения записи программы инициализация переменных цикла выполняется при их объявлении.