Решение упражнения 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, ваше решение неверно.

Comment from Lonli-Lokli
Date: February 25, 2011, 12:34 am

(define (fast-product a b)
(define (iter append a b)
(if (= b 1)
(+ a append)
(if (even? b)
(iter append (double a) (half b))
(iter (+ append a) a (- b 1)))))
(define (even? a)
(= (remainder a 2) 0))
(define (half a)
(/ a 2))
(define (double a)
(* a 2))
(iter 0 a b))

Write a comment