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

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

В этом упражнении мы отвлечемся от программирования и опять займемся математикой.

Итак, трансформация Tpq переводит пару (a, b) в пару (bq+aq+ap, bp+aq), что можно записать как

Tpq: (a, b) <- (bq+aq+ap, bp+aq) или Tpq(a, b) = (bq+aq+ap, bp+aq).

Вычислим Tpq²:


Tpq²(a, b) = Tpq(Tpq(a, b)) = Tpq(bq+aq+ap, bp+aq) =

= ([bp+aq]q+[bq+aq+ap]q+[bq+aq+ap]p, [bp+aq]p+[bq+aq+ap]q) =

= (b[2pq+q²]+a[2pq+q²]+a[p²+q²], b[p²+q²]+a[2pq+q²]) =

= (bq’+aq’+ap’, bp’+aq’) = Tp’q’(a, b),

где p’ = p²+q², q’ = 2pq+q².

Первая часть упражнения сделана.

Основываясь на результатах первой части и проанализировав код процедуры fib, приходим к выводу, что в пропущенных строках происходит скачок через шаг за счет использования факта, что Tpq²=Tp’q’. Пропущенные строки, таким образом, должны обеспечивать трансформацию (p,  q) <- (p’, q’)  и имеют вид:

(+ (square p) (square q))

(+ (* 2 p q) (square q))

Comments

Comment from thror
Date: February 15, 2008, 12:04 am

Автоматически строить дерево вычисления числа Fib(n) можно таким образом

(define (mknode n left right)
  (list n left right))

(define (mkleaf n)
  (list n))

(define (fib-tree n)
  (cond ((= n 0) (mkleaf 0))
	((= n 1) (mkleaf 1))
	(else (mknode n (fib-tree (- n 1)) (fib-tree (- n 2))))))

–thror

Comment from Eugene Kirpichov
Date: February 24, 2008, 11:04 am

Я решил это упражнение в чуть более общем виде, реализовав матричное умножение и итеративное логарифмическое возведение матрицы в степень - и заодно выпендрившись с в каком-то смысле continuation-passing style, поскольку cons’ов в этой главе еще не было :) 

(define (matrix a b c d)
  (lambda (p) (p a b c d)))

(define (mmul x y)
  (x (lambda (xa xb xc xd)
       (y (lambda (ya yb yc yd)
            (matrix (+ (* xa ya) (* xb yc))
                    (+ (* xa yb) (* xb yd))
                    (+ (* xc ya) (* xd yc))
                    (+ (* xc yb) (* xd yd))))))))

(define (mpow m n p)
    (define (iter a q n)
      (cond ((= n 0) (a p))
            ((= 0 (modulo n 2))
             (iter a
                   (mmul q q)
                   (/ n 2)))
            (else
             (iter (mmul a q)
                   (mmul q q)
                   (/ (- n 1) 2)))))
    (iter (matrix 1 0 0 1) m n))

(define (fib n)
    (define (p a b c d) a)
    (mpow (matrix 0 1 1 1) n p))

Comment from Dmitry Matveev
Date: November 7, 2008, 7:19 pm

Странно, но я получил те же формулы для p’ и q’, но в результате fib выдавала ложные значения))) приду домой - ещё проверю

Comment from serg
Date: March 30, 2009, 3:55 am

Я тоже сначала подумал, что ложные, а потом вспомнил, что они с нулевого начинаются, а не с первого:
fib 0 = 0; fib 1 = 1; ……..
Таким образом, fib 3 =2 и т. д. Так что формула с p и q работает! Интересно, а насчёт этих чисел что, целая математическая теория есть?

Write a comment