Итеративный процесс возведения в степень


Из SICP по 1.24: (возведение в степень)

(возможно, вам придется нажать и прочитать ~1 страницы, чтобы понять)

Упражнение 1.16. Разработать процедуру который развивается итерационный процесс возведения в степень, которая использует последовательные квадратуры и использует логарифмическое число шагов, как это делает быстро-только. (Подсказка: с помощью наблюдение, что (бн/2)2 = (Б2)п/2, сохранить, наряду с показателем ни базы б, дополнительная государства переменной а, и определяют состояние трансформация таким образом, что продукт бн остается неизменной от состояния для государства. В начале процесс также берется 1, а ответ дан по значению , апо в конце процесса. В общем, метод определения инвариантного количество, которое остается неизменным от государства-мощный способ подумать о дизайне итерационный алгоритмы.)

Я написал следующее решение:

(define (even n) (= (remainder n 2) 0))

(define (fast-expt b n)
  (fast-expt-iter b b n))

(define (fast-expt-iter a b n)
  (cond ((= n 1) a)
    ((even n) (fast-expt-iter (* a b) b (/ n 2)))
    (else (fast-expt-iter (* a b) b (- n 1)))))

Вы думаете, что мое решение является правильным? Кроме того, что вы думаете о моем коде?



1203
3
задан 25 марта 2011 в 06:03 Источник Поделиться
Комментарии
1 ответ

Ваша реализация не будет производить правильные результаты в целом за свои рекурсивные определения являются ошибочными.

Следует отметить, что в случае n = 0, результат 1. В случае четных N (или N = 2 я), можно написать б ^ п = (б * б) ^ я. В случае нечетного N (или N = 2 я + 1), можно написать б ^ п = б * (б * б) ^ я. Вот реализация (с помощью если вместо Конд и складывая два рекурсивных шагов в одну):

(define (fast-expt b n)
(if (= n 0) 1
(* (if (= (remainder n 2) 0) 1 b) (fast-expt (* b b) (quotient n 2)))))

Чтобы сделать это итерационного определения, использовать гидроаккумулятор, а, что изначально 1. Когда n четно (п = 2 я), квадрат Б, но сохранить неизменным. При этом сохраняется отеля B ^ N = А * (Б ^ 2) ^ я. Когда n нечетно (п = 2 я + 1), квадрат B и умножить a на B. При этом сохраняется свойство б ^ п = (А * Б) * (Б ^ 2) ^ я. Таким образом, мы имеем:

(define (fast-expt b n)
(fast-expt-iter 1 b n))

(define (fast-expt-iter a b n)
(if (= n 0) a
(fast-expt-iter (* a (if (= (remainder n 2) 0) 1 b)) (* b b) (quotient n 2))))

4
ответ дан 25 марта 2011 в 10:03 Источник Поделиться