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

17 January, 2008 (22:54) | Решения упражнений

Еще одно интересное упражнение. Сразу вспоминается Пифагор со знаменитым высказыванием “всё есть число”. В данном случае пару неотрицательных целых чисел можно представить как единственное число. Для этого cons будет вычислять произведение 2a3b, как и предложено в условии (на самом деле вместо 2 и 3 можно использовать любые два взаимно простых числа). Процедуры car и cdr будут просто вычислять кратность двойки и тройки соответственно в разложении своего аргумента на простые сомножители (я обзову это вычисление факторизацией).

(define (cons a b) 
  (* (power 2 a) (power 3 b)))
(define (car pair) 
  (factor 2 pair))
(define (cdr pair) 
  (factor 3 pair))

Для реализации возведения в степень и факторизации я выбрал простые алгоритмы, порождающие, однако, итеративные процессы. Можно также построить и более эффективные по сложности вычислений алгоритмы, что для возведения в степень уже обсуждалось в разделе 1.2.4.

(define (factor base value) 
  (define (factor-iter value counter) 
    (if (= (remainder value base) 0) 
        (factor-iter (/ value base) (+ counter 1)) 
        counter)) 
  (factor-iter value 0))
(define (power base exponent) 
  (define (power-iter base counter product) 
    (if (= counter 0) 
        product 
        (power-iter base (- counter 1) (* base product)))) 
  (power-iter base exponent 1))

Это упражнение позволяет взглянуть на данные сложной структуры под еще одним интересным углом. Если в предыдущем упражнении мы сводили составные данные к процедурам, то в этом идет сведение к простейшим данным – числам.

Write a comment