2014-02-24
1576
Приемы программирования циклов
Итерация как базисная вычислительная схема (рекуррентные вычисления). Рекуррентные вычисления с целочисленными типами. Рекуррентные вычисления с вещественными типами. Программирование циклов в языке С++. Вложенные циклы. Циклы со сложным условием продолжения (выхода). Пред- и постутверждения, инвариант цикла. Примеры.
Циклические алгоритмы, соответствующие многократному повторению одного и того же алгоритма и реализующиеся с помощью циклических инструкций, в том или ином виде присутствуют в подавляющем большинстве практически значимых программ. С алгоритмической точки зрения все циклы можно разделить на две группы: циклы с заранее определенным числом повторений тела цикла и циклы, в которых количество итераций (под итерацией понимается однократное выполнение тела цикла) заранее не известно. Вторую разновидность циклов иногда называют итерационными циклами.
Существует много различных типовых схем вычислений, основанных на использовании циклов. Одной из них является схема рекуррентных вычислений.
|
|
|
Рекуррентные схемы используются при вычислении значений некоторой последовательности, в которой значение каждого очередного элемента определяется на основе значений одного или нескольких предыдущих элементов.
В общем случае схему рекуррентных вычислений можно представить следующим образом.
Пусть в некоторой последовательности известны первые n значений:
Тогда элемент 
при
определяется так:
Или, иными словами:
Простейшим примером рекуррентного соотношения является вычисление факториала числа:
Программная реализация вычисления факториала:
