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

21 January, 2008 (21:29) | Решения упражнений

Это упражнение простое, но требует внимания. Девять случаев, о которых сказано в условии, получаются путем комбинации трех вариантов расположения первого интервала относительно нуля с тремя вариантами расположения второго интервала относительно нуля.

Три возможных варианта следующие:

  1. интервал лежит целиком справа от нуля (обе границы неотрицательны);
  2. интервал лежит целиком слева от нуля (обе границы неположительны);
  3. интервал содержит нуль (левая граница отрицательна, а правая - положительна).

Рассматривая каждый из этих случаев, легко увидеть, что во всех ситуациях, кроме единственной (когда оба интервала-сомножителя содержат нуль), мы сразу же можем сказать, какие границы исходных интервалов необходимо перемножить для получения границ интервала-произведения. Лишь в случае, когда оба перемножаемых интервала содержат нуль, нам требуется выбрать максимум и минимум из двух произведений для каждой границы (даже в этом случае есть экономия, так как в исходной версии произведения минимум и максимум выбирался из четырех вариантов, а не двух).

Вот код процедуры, реализующей оптимизационное предложение Бена:

(define (mul-interval x y)
    (let ((xl (lower-bound x))
          (xu (upper-bound x))
          (yl (lower-bound y))
          (yu (upper-bound y)))
      (cond ((>= xl 0)
             (cond ((>= yl 0)
                    (make-interval (* xl yl) (* xu yu)))
                   ((<= yu 0)
                    (make-interval (* xu yl) (* xl yu)))
                   (else
                    (make-interval (* xu yl) (* xu yu)))))
            ((<= xu 0)
             (cond ((>= yl 0)
                    (make-interval (* xl yu) (* xu yl)))
                   ((<= yu 0)
                    (make-interval (* xu yu) (* xl yl)))
                   (else
                    (make-interval (* xl yu) (* xl yl)))))
            (else
             (cond ((>= yl 0)
                    (make-interval (* xl yu) (* xu yu)))
                   ((<= yu 0)
                    (make-interval (* xu yl) (* xl yl)))
                   (else
                    (make-interval (min (* xl yu) (* xu yl))
                                   (max (* xl yl) (* xu yu)))))))))

Не исключаю, что его можно записать компактнее.

Comments

Comment from Dima
Date: June 22, 2008, 3:30 pm

Не знаю если это компактнее, но можно записать протседуру так, что “вручную” необходимо рассмотреть только 6 вариантов вместо 9ти. Это возможно благодаря коммутативности умножения.

(define (mul-interval x y)
    (let ((xl (lower-bound x))
          (xu (upper-bound x))
          (yl (lower-bound y))
          (yu (upper-bound y)))
      (cond ((>= xl 0)
             (cond ((>= yl 0)
                    (make-interval (* xl yl) (* xu yu)))
                   ((<= yu 0)
                    (make-interval (* xu yl) (* xl yu)))
                   (else
                    (make-interval (* xu yl) (* xu yu)))))
            ((and (<= xu 0) ( xu 0) (< xl 0))
             (cond (( yu 0) (< yl 0))
                    (make-interval (min (* xl yu) (* xu yl))
                                   (max (* xl yl) (* xu yu))))))
            (else (mul-interval y x)))))

Comment from Dima
Date: June 23, 2008, 11:19 am

Всё что было в угловых скобках, в (>= …) и так далее, было стёрто. Попробую ещё раз. Заменяю на less= и less.

(define (mul-interval x y)
    (let ((xl (lower-bound x))
          (xu (upper-bound x))
          (yl (lower-bound y))
          (yu (upper-bound y)))
      (cond ((>= xl 0)
             (cond ((>= yl 0)
                    (make-interval (* xl yl) (* xu yu)))
                   ((less= yu 0)
                    (make-interval (* xu yl) (* xl yu)))
                   (else
                    (make-interval (* xu yl) (* xu yu)))))
            ((and (less= xu 0) (less= yu 0))
             (make-interval (* xu yu) (* xl yl)))
            ((and (> xu 0) (less xl 0))
             (cond ((less= yu 0)
                    (make-interval (* xu yl) (* xl yl)))
                   ((and (> yu 0) (less yl 0))
                    (make-interval (min (* xl yu) (* xu yl))
                                   (max (* xl yl) (* xu yu))))))
            (else (mul-interval y x)))))

Write a comment