Решение упражнения 1.16 из SICP

29 August, 2007 (20:01) | Решения упражнений

Как и указано в условии упражнения, инвариантом будет abn = const.

В начале процесса a полагаем равным 1 и как следствие результат будет равен bn. Условием выхода из процесса является n=0, а стало быть abn = a.

Код процедуры приведен ниже:

(define (fast-expt b n)
  (fast-expt-iter 1 b n))
(define (fast-expt-iter a b n)
  (if (= n 0)
      a
      (if (even? n)
          (fast-expt-iter a (square b) (/ n 2))
          (fast-expt-iter (* a b) b (- n 1)))))

Comments

Comment from Dmitry Matveev
Date: September 25, 2008, 9:17 pm

Спасибо!!!! А то я с этим инвариантом голову сломал

Comment from serg
Date: March 30, 2009, 1:40 am

Да уж… Что-то они напарили там в “подсказке”, я-то подумал что что-то сложное, сказали бы сразу, смотреть как факториал сделан с итерацией и возведение в степень, и также делать.

Comment from adaptun
Date: March 10, 2010, 7:37 pm

Я перед тем как написать такой вариант, два часа возводил в квадрат а, а не b (в случае с чётным n).

Write a comment