1. Review the following code from Lab-8.txt
;; Integer Integer
(define fib-r
(λ(n)
(if (<= n 2)
1
(+ (fib-r (- n 1))
(fib-r (- n 2))))))
(define fib-i
(λ(n)
(f-iter n 1 1)))
(define f-iter
(λ(n a b)
(cond( (= n 1) a)
( (= n 2) b)
(else (f-iter (- n 1) b (+ a b))))))
2. Draw a tree recursive trace diagram for (fib-r 6).
3. Draw a trace diagram for (fib-i 6).
4. Complete part III from Lab-8.
(Lab-8) III. Explicit Method
(a). Define phi to be (/ (+ 1 (sqrt 5)) 2).
(b). Add the distance method to your work space.
(define distance
(lambda (a b)
(abs (- a b))))
(c). Useful functions.
(ceiling x ) evaluates to the smallest integer greater than or equal x.
(floor x) evaluates to the largest integer greater than or equal to x.
(expt b n) evaluates to b raised to the nth power. This function is
fast.
Test:
(ceiling 2.3)
(floor 2.3)
(ceiling 12.8)
(floor 12.8)
(ceiling -3.1)
(floor -3.1)
Write the function (closest-integer x) that returns the closest integer
to x. Assume x is a real number.
Test cases:
(closestInteger 3.9) -> 4
(closestInteger 3.1) -> 3
(closestInteger 3.5) -> 4
(closestInteger 2.5) -> 3
(d). Note the closest integer to (phi^n)/(sqrt 5) is the nth term in the
Fibonacci sequence that begins with 1 and 1.
Write a function (fib n) to compute the nth term.
(f). Verify that it works.
(g). Can you compute the 100th term? Is it equal to (fib-i 100)?
(h). Write the function (find-largest n) that finds the largest integer
n such that (fib n) is equal to (fib-i n).
;; Integer -> Integer
;; Assumes n >= 100.
(define find-largest
(lambda(n)
(i). What is the result of (find-largest 100)?