Решение упражнения 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))

Comment from Александр
Date: July 27, 2012, 2:28 pm

фак-е, кажется теперь я понял прием с инвариантам цикла, спасибо!

Comment from povloid
Date: December 15, 2012, 9:27 am

(define (*-fast-log a b)
  (*-fast-log-iter 0 a b))

(define (*-fast-log-iter r a b)
  (if (or (= b 0) (= a 0))
      r
      (if (even? b)
          (*-fast-log-iter r (double a) (halve b))
          (*-fast-log-iter (+ r a) a (- b 1)))))

Comment from zMol
Date: November 4, 2013, 8:55 pm

(define (* a b)
  (cond ((= a 0) 0)
        ((< a 0) (*-iter (- 0 a) (- 0 b) 0))
        (else (*-iter a b 0))))
(define (*-iter a b add)
  (cond ((= a 1) (+ b add))
        ((= (remainder a 2) 0) (*-iter (/ a 2) (+ b b) add))
        (else (*-iter (- a 1) b (+ add b)))))

Comment from Evgeniy
Date: December 5, 2013, 1:41 pm

Тьфу чёрт, а я в 1.17 неправильно задание понял, и сразу итеративное сделал.

Comment from Irv
Date: December 30, 2015, 11:51 am

(define (M a b)
  (define (double x)
    (+ x x))
  (define (iter value param)
    (if (= b param)
        value
        (if (> b (double param))
            (iter (double value) (double param))
            (iter (+ a value) (+ 1 param)))))
  (iter a 1))

Comment from Irv
Date: January 5, 2016, 8:48 pm

ошибся. сложность алгоритма выше O(n)

правильнее как у автора

(define (double x)
  (* x 2))

(define (halve x)
  (/ x 2))

(define (M x y)
  (define (iter a b c)
    (if (= b 1)
        (+ a c)
        (if (even? b)
            (iter (double a) (halve b) c)
            (iter a (- b 1) (+ a c)))))
  (iter x y 0))

(M 6 7)

Write a comment