Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Пример построения циклаРассмотрим функцию вычисления факториала:
int fact(int x) { if(x==0) return 1; if(x==1) return 1; int y=fact(x-1); printf("x=%i, y=%i\n", x, y); return x*y; } void main() { fact(5); }
Эта функция рекурсивная, т. е. вызывает сама себя, она реализует факториал по его определению, т. е. факториал от 0 или 1 равен 1, а факториал от другого целого числа равен произведению этого числа на факториал от числа на единицу меньше. В рассматриваемой функции есть дополнительные строчки, которые печатают на каждом шаге само число, и факториал от числа на единицу меньше. Большинство циклов можно записать в рекуррентной или итеративной формах. Рекуррентная форма использует рекурсивные функции, а итеративная находит нужное значение пошагово. В рекуррентной форме удобно записывать большинство алгоритмов. Эта форма более соответствует человеческому мышлению, чем запись алгоритма в виде цикла. В результате возникает задача преобразования рекуррентной формы в итеративный цикл. Рассмотрим работу этой функции для случая вычисления факториала 5:
x=2, y=1 x=3, y=2 x=4, y=6 x=5, y=24
Заметим, что на каждом шаге цикла выполняются определенные условия, их можно записать следующим образом: y = (x – 1)!. Условие, которое выполняется на каждом шаге цикла, называется инвариантом. Данное условие выполняется в самом начале работы функции: x = 2, y = 1. Это называется начальным условием цикла или предусловием, т. е. в начале цикла необходимо обеспечить выполнение этого условия и задать переменным нужные значения. В последней строке напечатано: x = 5, y = 24. Для завершения работы нужно сделать еще один шаг, который в рекуррентной форме не показывается: x = 6, y = 120. Инвариант выполняется и в этом случае, в конце цикла он называется постусловием, т. е. условием, которое создастся после окончания цикла, или, другими словами, условием, которого имеют целью достигнуть с помощью цикла. По постусловию можно определить условие окончания цикла. Это часть постусловия, которая позволяет определить, что цикл нужно закончить. В нашем случае условие окончания будет x = 6, или, в общем случае, x = n + 1, где n – число, для которого определяется факториал. Во многих языках программирования высокого уровня в формах записи цикла требуется указать не условие окончания, а условие продолжения цикла. В нашем случае цикл должен продолжаться до тех пор, пока x < 6 или x < n + 1. Записав все условия (инвариант, предусловие, постусловие), можно сос-тавить тело цикла. Очевидно, что для того чтобы приблизить условия окончания цикла, нужно увеличить x, например, на единицу. Обозначим x` = x + 1, где x` – значение переменной x на новом шаге. Нужно найти y` = (x` – 1)!. Мы не можем использовать функцию факториала, поскольку мы ее реализуем, но, используя определения факториала, и то, что y = (x – 1)!, получаем: y` = (x `– 1)! = (x + 1 – – 1)! = (x – 1)! x = y * x. Таким образом, можно получить значение y на новом шаге, умножив x на y из предыдущего шага. Получаем следующее тело цикла:
y=y*x; x++;
Цикл разработан, осталось записать его на языке программирования. Запишем цикл с помощью изученного в первом семестре оператора for:
for(x=2, y=1; x<n+1; x++) y=y*x;
В поле инициализации оператора мы записали инициализацию цикла – задание начальных значений переменных. Для того чтобы задать сразу два значения, был применен оператор «запятая», который указывает на то, что нужно выполнить последовательно два действия. В операторе for во втором поле указывается условие выполнения цикла: цикл будет выполняться до тех пор, пока x < n, где n – число, факториал которого мы считаем. Третье поле указывает шаг цикла, который выполняется после тела. Оператор x++ по смыслу соответствует шагу цикла, т. е. приближает условие окончания цикла, поэтому он был перенесен сюда из тела цикла. Функция, вычисляющая факториал с помощью цикла, имеет вид:
int fact1(int n) { if(n==0) return 1; if(n==1) return 1; int x, y; for(x=2, y=1; x<n+1;x++) y=y*x; return y; }
|