Решение упражнения 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 работает! Интересно, а насчёт этих чисел что, целая математическая теория есть?

Pingback from Упражнение 1.19 | SICP по-русски 2
Date: May 8, 2011, 12:12 am

[…] мучений подсмотрел как считать возведение в квадрат тут. Дальше все просто. В заключение хочу добавить что я […]

Comment from Yaga
Date: February 25, 2012, 2:17 pm

Почему тут речь о квадрате функции Т? Что она выдает? Идем дальше – суть упражнения в логарифмической сложности – если Т(а,б) выдает следующий член и уже известный, то Т(Т(а,б)) дает два следующих члена после “а” и “б”. Как этим достигается логарифмическое число шагов вычислений, указанное в книге? Сложность остается ~n (/2). Неужели весь смысл упражнения в прыжке через шаг? а как же обещанная log(n)? 8((( одно расстройство…

Comment from Yaga
Date: February 25, 2012, 2:39 pm

Мне кажется это упражнение правильно было бы решать через матрицы. Написанное Eugene Kirpichov больше похоже на решение с логарифмической сложностью, но понять не могу – читаю только первую главу. А на http://stackoverflow.com/questions/1896974/sicp-exercise-1-19 указывают на некую Q-матрицу Фибоначи, вот ее уже можно в степень возводить и добиваться тем самым логарифмической сложности… А вообще спасибо, за Sicp на русском – он нам строить и жить помогает! )))

Comment from Mike
Date: June 12, 2013, 12:02 pm

Все отлично, но предлагаю автору (правда уже не актуально) решения уравнений или каких-либо других математичкеских задач для наглядности иллюстрировать ссылкой на Wolfram Alpha. Например для этого упражнения исчерпывающая информация выглядела бы так: http://www.wolframalpha.com/input/?i=%28bp%2Baq%29q%2B%28bq%2Baq%2Bap%29q%2B%28bq%2Baq%2Bap%29p%3Dby%2Bay%2Bax%2C+%28bp%2Baq%29p%2B%28bq%2Baq%2Bap%29q%3Dbx%2Bay+for+x+and+yhttp://www.wolframalpha.com/input/?i=%28bp%2Baq%29q%2B%28bq%2Baq%2Bap%29q%2B%28bq%2Baq%2Bap%29p%3Dby%2Bay%2Bax%2C+%28bp%2Baq%29p%2B%28bq%2Baq%2Bap%29q%3Dbx%2Bay+for+x+and+y

Comment from Alexey
Date: November 5, 2015, 9:50 am

Я гораздо проще рассуждал, но почему-то неправильно. А почему?
a1 = b0*q + a0*q + a0*p
b1 = b0*p + a0*q

По определению чисел: a2 = a1+b1; b2 = a1, тогда

a2 = b0*(q+p) + a0*(p+q) + a0*p
b2 = b0*q + a0*(q+p)

Тут я сравнил с
a2 = b0*q’ + a0*q’ + a0*p’
b2 = b0*p’ + a0*q’

Тогда получаются q’ = p+q; p’ = q. Почему такие рассуждения неправильны?

Comment from Den
Date: April 26, 2016, 1:46 pm

Объясните, как происходит переход от удвоения трансформации, к возведению в квадрат. Как нужно рассуждать, чтобы самому догадаться, что в четной степени нужно “накапливать изменения” в (p и q), а не в (a и b).

Write a comment