SICP по-русски

Comment from лина
Date: May 23, 2008, 7:31 am

можно ли опубликовать подробно с примерами. Я блондинка и начинающий программист:)

Comment from Piter
Date: June 19, 2008, 12:16 pm

спасибо, долго ломал голову, над этой задачкой. теперь стало понятно, где я ошибся.

Comment from гена
Date: June 26, 2008, 9:42 am

хороший пример. как говориться все гениальное-просто.

Comment from meduza
Date: October 19, 2008, 11:17 am

на 1 проверять желательно, но не обязательно.

Comment from vovka
Date: March 10, 2010, 12:49 pm

если b меньше 0, не работает

Comment from Ayrat
Date: April 1, 2010, 11:41 am

У меня попроще:
(define (** a b)
(cond ((= b 0) 0)
((even? b) (** (double a) (halve b)))
(else (+ a (** a (- b 1))))))

Comment from Dmitri
Date: July 25, 2010, 5:58 pm

В вашем примере это: ((= b 1) a)
лишнее. Можно без него

Comment from aeracode
Date: February 2, 2011, 6:40 pm

Итеративный процесс:

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


Можно еще дополнительно оптимизировать проверкой:
(if (> x y)
(iter 0 x y)
(iter 0 y x))

Comment from aeracode
Date: February 2, 2011, 6:53 pm

Ой, кажись я поспешил. Считайте это ответом на 1.18.

Comment from zap
Date: May 4, 2011, 6:43 pm

интересно что будет возвращать функция если “((= b 1) a)” лишнее

Comment from Broh
Date: August 14, 2012, 10:31 pm


(define (product-by-sum a b)
(define (even? n)
(= (remainder n 2) 0))

(cond ((= b 1) a)
((= b (- 1)) (- a))
((even? b) (product-by-sum (double a) (halve b)))
(else (+ a (product-by-sum a (- b 1))))))


В этом примере использовано условие ((= b 1) a), вместо ((= b 0) 0), так как и в том и в другом случае результат будет одинаковый, но при втором условии произойдет лишний вызов функции.


Вот с такими параметрами будет вызываться функция product-by-sum:

Если же условие будет ((= b 0) 0) то произойдет еще один вызов:
5. (3 + 12 + product-by-sum 12 0) Вызов функции произошол, но он сразу же вернет 0.
6. (3 + 12 + 0)
7. (3 + 12)


Условие ((= b (- 1)) (- a)) нужно для правильного умножения на отрицательное b.

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

получил практически аналогичное решение


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

Comment from Серёнька Всёдофени
Date: August 5, 2013, 1:49 pm

Для работы с отрицательными числами (на 1 вызов больше =)):

(define (fast-mult a b)
  (cond ((= b 0) 0)
        ((= b 1) a)
        ((< b 0) (fast-mult (- a) (- b)))
        ((even? b)(double (fast-mult a (halve b))))
        (else (+ a (fast-mult a (- b 1))))))

Comment from uitczilopochtli
Date: January 22, 2014, 11:28 pm

2 Серёнька, надо проверять оба числа на “отрицательность”, иначе -3 * -5 = -15

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

Comment from Arsen
Date: May 29, 2016, 9:46 am

Поправьте, если ошибаюсь, но в оригинальном решении не итеративный процесс. Это можно проверить, взглянув на стек выполнения процедуры, при вызове, например, (fast-* 3 16). На четвертой итерации, когда b будет равен 1 стек будет выглядеть так:

(cond ...)
(fast-* ...)
(fast-* ...)
(fast-* ...)
(fast-* ...)
??

Вот пример, в котором работает хвостовая оптимизация:

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

Comment from Arsen
Date: May 29, 2016, 9:49 am

Прошу прощения, в упражнении ничего не было сказано про итеративность. В комментариях выше уже привели итеративное решение.

комментарии не читай@сразу отвечай