6.001 Recitation #7

          5 minute Problem #2 (posed Wed, 9/10/97)

Ben Bitdiddle has defined a procedure, p, which takes a number argument
and returns a truth value.  Your job is to define a procedure find-min
with the property that, for any integer n, the value of 
                (find-min n)
is the SMALLEST INTEGER, k, such that
        (i)  k >= n, and
        (ii) the value of (p k) is true.

For example, if Ben had written
        (define (p k) (<= 100 k))            ;<= is the `less-than-or-equal-to' test
then you could do your job by writing
        (define (find-min n)
          (if (<= n 100) 100 n))

(1) Suppose Ben had written
        (define (p k) (even? k))
Complete the following:
        (define (find-min n) <??>)

   SOLN (1):  if n is even, (p n) is #t, so (findmin n) is simply n.
              if n is odd, then (p n) is #f, but p applied to n+1 is #t, so
              (findmin) is n+1.  Here's a Scheme definition which behaves
              this way:
   (define (findmin n)
      (if (even? n) n (+ n 1)))


(2) The real problem is that you don't know Ben's definition of p.  But
(find-min n) can be computed ANYWAY: by starting with n and then trying
n+1, n+2, ... until a k is found at which (p k) is true.  Give a Scheme
definition of find-min using this idea.

How does your procedure behave when Ben has defined p never to be true?:
        (define (p n) #f)



                                 SOLN (2) (presented Fri, 9/12)

(define (find-min n)
 (if (p n) n (find-min (inc n))))