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

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

Процедура, порождающая итеративный процесс для умножения, приведена ниже:

(define (fast-* a b)
  (fast-*-iter a b 0))
(define (fast-*-iter a b c)
  (cond ((= b 0) c)
        ((even? b) (fast-*-iter (double a) (halve b) c))
        (else (fast-*-iter a (- b 1) (+ c a)))))
 

Инвариант здесь ab+c=const. В начале вычислений c=0 и следовательно вычисляется произведение ab. Условием выхода является b=0 а тогда ab+c=c, который и возвращается как результат.

Comments

Comment from JessicaFletcher
Date: January 6, 2010, 7:06 am

(define (* a b)
  (cond (= b 0) a
        (even? b) (* (+ a b) (- b 1))
        (else (* (double a) (half b)))))

(define (even? b)
  (if (= b 1) true
      false))

Comment from Dmitri
Date: July 25, 2010, 6:16 pm

JessicaFletcher, ваше решение неверно.

Write a comment