Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

SICP halp for Nubi

Name: Anonymous 2009-06-01 20:26

Oh wise Lispers and Conjurers of /prog/, I, humble Nubi, seek your enlightenment.  I have started reading SICP, but I'm stuck on an exercise.  I have figured out how to make fast-mult into a logarithmic process, but how do I make it into a tail recursion as well as a logarithmic process?  Here is my code:

; SICP exercise 1-13
; Peasant's algorithm for multiplication
; write a logarithmic iterative process for mult

(define (fast-mult a b)
  (cond ((= b 0) 0)
        ((even? b) (double (fast-mult a (halve b))))
        (else (+ a (fast-mult a (- b 1))))))

(define (double a) (+ a a))
(define (halve a) (/ a 2))

(define (fast-mult2 a b)
  (fast-mult-iter a a b))

(define (fast-mult-iter a n b)
  (cond ((= b 1) n)
        ((and (even? b) (> b 2))
          (fast-mult-iter a (double n) (halve b)))
        (else (fast-mult-iter a (+ a n) (- b 1)))))

(fast-mult 3 2)
(fast-mult2 3 2)
(fast-mult 3 3)
(fast-mult2 3 3)
(fast-mult 3 4)
(fast-mult2 3 4)
(fast-mult 3 5)
(fast-mult2 3 5)
(fast-mult 3 6)
(fast-mult2 3 6)

Name: Anonymous 2009-06-02 13:30

Here's another one.  How do I make count-change, which calculates the number of different ways you can make change out a given amount, an iterative process instead of a tree-recursive one?

(define (count-change amount)
  (cc amount 5))
(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount
                     (- kinds-of-coins 1))
                 (cc (- amount
                        (first-denomination kinds-of-coins))
                     kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List