Умножение в плане того


Поставлены следующие задачи:

Упражнение 1.17

Возведения алгоритмы в этом разделе основаны на выполнение возведения в степень путем многократного умножения. В аналогичным образом можно проанализировать целое умножение путем многократного дополнение. Следующее умножение процедура (в которой предполагается, что наш язык можно только добавить, не умножьте) аналогичен только процедура:

(define (* a b)
  (if (= b 0)
      0
      (+ a (* a (- b 1)))))

Этот алгоритм принимает ряд шагов что является линейной в б. Теперь предположим, что мы включают, вместе с добавлением, операции двойник, который удваивает целое число, и вдвое, что разделяет (даже) целое число на 2. Используя эти, разработать процедуру умножения аналогично быстро-только что использует логарифмическое число шагов.

Я написал это решение:

(define (double a) (* a 2))
(define (halve a) (/ a 2))
(define (even n) (= (remainder n 2) 0))

(define (times a b)
  (cond ((= 1 b) a)
        ((even b) (times (double a) (halve b)))
        (else (times (+ a a) (- b 1)))))

Что вы думаете?



968
1
задан 25 марта 2011 в 06:03 Источник Поделиться
Комментарии
1 ответ

Ваша реализация не будет производить правильные результаты в целом.

В базовом случае b = 0, результат должен быть 0. В случае даже б, итог-два раза половину Б (где вы сделали правильно). В случае нечетного Б, результат должен быть + (два раза полтора (Б - 1)).

(define (times a b)
(cond ((= 0 b) 0)
((even b) (times (double a) (halve b)))
(else (+ a (times (double a) (halve (- b 1)))))))

Чтобы сделать этот итеративный определению, добавьте гидроаккумулятор, вот так:

(define (times a b)
(times-iter 0 a b))

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

2
ответ дан 25 марта 2011 в 10:03 Источник Поделиться