SICP Exercise 1.13

Exercise 1.13.  Prove that Fib(n) is the closest integer to n/5, where  = (1 + 5)/2. Hint: Let = (1 - 5)/2. Use induction and the definition of the Fibonacci numbers (see section 1.2.2) to prove that Fib(n) = (n - n)/5.

SOLUTION




Comments

Post a Comment

Popular posts from this blog

SICP Exercise 1.22 search-for-primes

Image
Exercise 1.22.    Most Lisp implementations include a primitive called  runtime  that returns an integer that specifies the amount of time the system has been running (measured, for example, in microseconds). The following  timed-prime-test  procedure, when called with an integer  n , prints  n  and checks to see if  n  is prime. If  n  is prime, the procedure prints three asterisks followed by the amount of time used in performing the test. (define (timed-prime-test n)   (newline)   (display n)   (start-prime-test n (runtime))) (define (start-prime-test n start-time)   (if (prime? n)       (report-prime (- (runtime) start-time)))) (define (report-prime elapsed-time)   (display " *** ")   (display elapsed-time)) Using this procedure, ...
Read more

SICP Exercise 3.45 deadlock

Exercise 3.45.   Louis Reasoner thinks our bank-account system is unnecessarily complex and error-prone now that deposits and withdrawals aren't automatically serialized. He suggests that  make-account-and-serializer  should have exported the serializer (for use by such procedures as  serialized-exchange ) in addition to (rather than instead of) using it to serialize accounts and deposits as  make-account  did. He proposes to redefine accounts as follows: (define (make-account-and-serializer balance)   (define (withdraw amount)     (if (>= balance amount)         (begin (set! balance (- balance amount))                balance)         "Insufficient funds"))   (define (deposit amoun...
Read more

SICP Exercise 4.2 Louis Reasoner eval

Exercise 4.2.    Louis Reasoner plans to reorder the  cond  clauses in  eval  so that the clause for procedure applications appears before the clause for assignments. He argues that this will make the interpreter more efficient: Since programs usually contain more applications than assignments, definitions, and so on, his modified  eval  will usually check fewer clauses than the original  eval  before identifying the type of an expression. a. What is wrong with Louis's plan? (Hint: What will Louis's evaluator do with the expression  (define x 3) ?) b. Louis is upset that his plan didn't work. He is willing to go to any lengths to make his evaluator recognize procedure applications before it checks for most other kinds of expressions. Help him by changing the syntax of the evaluated language so that procedure applications start with  call . For example, instead of  (factorial 3)  we will now have to write  (c...
Read more