Вычисление - факториал
Cтраница 4
В следующих разделах описываются методы для устранения рекурсии из любого алгоритма. Некоторые нерекурсивные алгоритмы понять всего лишь чуть-чуть труднее, чем рекурсивные. Нерекурсивные функции вычисления факториала, НОД, чисел Фибоначчи и BigAdd относительно просты. [46]
 |
Структура стека. [47] |
Однако остается нерешенной проблема, связанная с тем, что данная программа, по-видимому, была вызвана некоторой главной программой. Главная программа оставляет ее адрес возврата в определенной ячейке, известной подпрограмме. Когда программа вычисления факториала обращается к самой себе, она оставляет свой адрес возврата в том же самом месте, тем самым стирая адрес возврата в главную программу. Когда программа FACT вновь обращается к самой себе, предыдущий адрес возврата теряется и заменяется новым. Таким образом, когда происходит возврат, он осуществляется по адресу, который связан с последним обращением. [48]
Рассмотрим создание и использование программного модуля на следующем примере. Создадим модуль под названием mathem, выполняющий те математические операции, для которых в языке Паскаль не существует стандартных функций или процедур. К таким операциям относится вычисление факториала числа, нахождение среднего арифметического, среднего геометрического и среднего гармонического двух чисел, определение наибольшего общего делителя двух чисел, возведение числа в произвольную целую степень. Заготовки для выполнения почти всех этих операций у нас уже имеются в виде функций или процедур, которые мы уже разрабатывали в предыдущих программах. Описание этих функций и процедур можно скопировать из этих программ и вставить в создаваемый нами модуль. [49]
При сопоставлении этих двух алгоритмов видно, что предельным размером данных в нашем случае служит 1, и при таких данных никаких арифметических операций не выполняется. Во всех остальных случаях мы переходим к залогу else. Первым шагом в общем алгоритме служит разбиение ввода на более мелкие части; в алгоритме вычисления факториала этому шагу соответствует вычисление переменной smaller, которое требует одного вычитания. [50]
После умножения выполняется команда возврата RTS. В этот момент в стеке может быть либо адрес возврата в программу, вызвавшую FACTOR, либо очередная двухсловная запись, выполненная при рекурсивном вызове подпрограммы FACTOR. В последнем случае в R1 загружается новое значение N, которое будет умножено на промежуточный результат, хранимый в стеке, и процесс повторится. Если же вычисление факториала закончено, то управление передается в вызывающую программу, а результат остается в стеке. [51]
Программа выполняется следующим образом. После ввода исходных данных определяется отношение t / t, n задается равным единице и производится обращение к процедуре TANK. Поэтому содержание процедуры TANK представляет собой оператор цикла, и при каждом значении параметра цикла i вычисляется один член ряда. Поскольку каждый член ряда одним из сомножителей содержит факториал, то в цикле же производится обращение к процедуре вычисления факториала. [52]
Программа выполняется следующим образом. После ввода исходных данных определяется отношение tit, n задается равным единице и производится обращение к процедуре TANK. Поэтому содержание процедуры TANK представляет собой оператор цикла, и при каждом значении параметра цикла i вычисляется один член ряда. Поскольку каждый член ряда одним из сомножителей содержит факториал, то в цикле же производится обращение к процедуре вычисления факториала. [53]
Страницы: 1 2 3 4