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

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

Как и указано в условии упражнения, инвариантом будет abn = const.

В начале процесса a полагаем равным 1 и как следствие результат будет равен bn. Условием выхода из процесса является n=0, а стало быть abn = a.

Код процедуры приведен ниже:

(define (fast-expt b n) 
  (fast-expt-iter 1 b n))
(define (fast-expt-iter a b n) 
  (if (= n 0) 
      a 
      (if (even? n) 
          (fast-expt-iter a (square b) (/ n 2)) 
          (fast-expt-iter (* a b) b (- n 1)))))

Comments

Comment from Dmitry Matveev
Date: September 25, 2008, 9:17 pm

Спасибо!!!! А то я с этим инвариантом голову сломал

Comment from serg
Date: March 30, 2009, 1:40 am

Да уж… Что-то они напарили там в “подсказке”, я-то подумал что что-то сложное, сказали бы сразу, смотреть как факториал сделан с итерацией и возведение в степень, и также делать.

Comment from adaptun
Date: March 10, 2010, 7:37 pm

Я перед тем как написать такой вариант, два часа возводил в квадрат а, а не b (в случае с чётным n).

Comment from Эребус
Date: February 6, 2011, 4:43 pm

Я думаю, тут было бы более уместо cond, а не if

Comment from vladimir
Date: October 19, 2011, 7:20 am

там можно cond’ом обойтись?

Comment from Arkady
Date: January 19, 2012, 10:53 am

Разумеется.

(define (fast-expt-iter a b n)
  (cond ((= n 0) a)
           ((even? n) (fast-expt-iter a (square b) (halve n)))
           (else (fast-expt-iter (* a b) b (- n 1)))))

Comment from Александр
Date: July 27, 2012, 1:29 pm

подсказка отличная, мне правда не помогла. спасибо за ответ

Comment from povloid
Date: December 14, 2012, 8:45 pm

Задание через чур замороченное. В итоге написал так:

(define (even1? n)
  (= (remainder n 2) 0))

(define (square x)
  (* x x))

(define (fast-expt b n)
  (fast-expt-iter 1 b (+ n 1)))

(define (fast-expt-iter a b n)
  (if (= n 1) a
      (if (even1? n)
         (fast-expt-iter (* a b)(square  b) (/ n 2)) 
         (fast-expt-iter (* a b) b (- n 1)))))
                 
(fast-expt 4 1)
(fast-expt 4 2)
(fast-expt 4 3)
(fast-expt 4 4)
(fast-expt 4 5)
(fast-expt 4 6)
(fast-expt 4 7)
(fast-expt 4 8)

выдает:

4
16
64
256
1024
4096
16384
65536

Comment from Irv
Date: December 29, 2015, 4:40 pm

#lang racket
(define (square x) (* x x))

(define (expr b n)
   (cond ((= n 0) 1)
        ((= (remainder n 2) 0) (square (expr b (/ n 2))))
        (else (* b (expr b (- n 1))))))

(define (expi b n)
  (define (iter value degree)
    (if (= n degree)
        value
        (if (> n (* 2 degree))
            (iter (square value) (* 2 degree))
            (iter (* b value) (+ 1 degree)))))
  (iter b 1))


(= (expr 2 64) (expi 2 64))

Comment from Irv
Date: January 7, 2016, 10:44 pm

правильнее так:

(define (square x) (* x x))

; O(log(n)) / O(log(n))
(define (exp-recursive base exp)
  (cond [(= exp 0) 1]
        [(even? exp) (square (exp-recursive base (/ exp 2)))]
        [else (* base (exp-recursive base (- exp 1)))]))

; O(n) / O(1)
(define (exp-iterative-bad base exp)
  (define (iter b i)
    (if (= exp i)
        b
        (if (> exp (* 2 i))
            (iter (square b) (* 2 i))
            (iter (* base b) (+ 1 i)))))
  (iter base 1))

; O(log(n)) / O(1)
(define (exp-iterative-good base exp)
  (define (iter a b n)
    (if (= 1 n)
        (* a b)
        (if (even? n)
            (iter a (square b) (/ n 2))
            (iter (* a b) b (- n 1)))))
  (iter 1 base exp))

(exp-recursive 2 64)
(exp-iterative-bad 2 64)
(exp-iterative-good 2 64)

Comment from Jellyfish
Date: February 2, 2016, 5:02 am

Подскажите, является ли процедура такого типа итеративной со сложностью О(log n)?

(define (pow-it b n)
  (pow-iter b n 1))

(define (pow-iter b n a)
  (cond ((= n 0) a)
        ((even? n) (pow-iter b (halve n) (* a (pow-it b (halve n)))))
        (else (pow-iter b (- n 1) (* a b)))))

Comment from Arsen
Date: May 29, 2016, 9:20 am

Jellyfish, по-моему это все-таки рекурсивный процесс, так как при успешной проверке на четность неявно вызовется сама функция pow-iter через pow-it и придется придется использовать стек, чтобы подставить значение в вызов pow-iter. Выразился сумбурно, поправьте, если не прав.

(define (pow-it b n)
  (pow-iter b n 1))

(define (pow-iter b n a)
  (cond ((= n 0) a)
        ((even? n) (pow-iter b (halve n) (* a (pow-it b (halve n)))))  ;; <- вот тут будет формироваться рекурсивный процесс.
        (else (pow-iter b (- n 1) (* a b)))))

Comment from Ilyas
Date: January 23, 2017, 12:12 am

Ну на тебе, я же правильно делал, и все просто было, но потом в такие дебри мыслительные ушёл из-за этой “подсказски” с инвариантом.

Comment from bis
Date: March 22, 2017, 6:30 pm

Посоветуйте, пожалуйста, где можно посмотреть про итерацию, никак этот слэнг не словлю. Кроме Кнута)))

Write a comment