Binary Search Trees_lab 10 Solution

Lab 10
Objectives
• Workwithtrees
• UseBinarySearchTrees
Activities
1. Define a SCHEME function named num-list which converts any integer to a list of single-digit integers (use division by 10 and the floor function). For instance, the expression (num-list 12345) would return ’(1 2 3 4 5). 2. Define a SCHEME function named (list-num l) which takes a list of digits in base 10 and converts them to aninteger(thereverseof num-list). 3. "Don’ttheyteachrecreationalmathematicsanymore"? Enjoy this clip of the BBC television show Doctor Who: http://www.youtube.com/watch?v=ee2If8jSxUo. Ok,nowgettowork. Yourjob,shouldyouchoosetoacceptit,istowriteafunction(andanyhelperfunctions necessary)tofindthenexthappyprimeinthesequence...,313,331,367,379,....
Now,whatdidhesay? “Anynumberthatreducestoonewhenyoutakethesumofthesquareofit’sdigitsandcontinue iterating until it yields 1 is a happy number. Any number that doesn’t, isn’t. A happy prime is a numberthat’sbothhappyandprime,nowTYPEITIN.”
(a) Wealreadyhaveafunctionfromquestion1thatexplodesanintegerintoalistofdigits. (b) Tocomputethesumofthesquaresofthedigits,defineaSCHEME functionwhichtakesalistofintegersas aparameterandreturnsthesumofthesquaresoftheintegersinthelist. (c) Ifweeversumthesquaresofthedigitsofanumberanditproducesanumberwe’vealreadycomputed,we will always loop through the numbers we’ve already tried. We’ll need to keep track of the numbers we’ve tried so that we can stop if we come to a number we’ve already seen before. Define SCHEME functions insert and element? whichimplementasetADTwithabinarysearchtree. (d) Use all of these helper functions to define a SCHEME function named is-happy? which, given a positive integerasaparameter,returnstrueifthenumberisahappynumberandfalseotherwise. Itmightbeuseful to define a helper function that also takes the set, S, as a parameter and adds the sum of the squares of the digitsofanumbertothatsetifitisn’ttherealready. (e) Use your new is-happy? function and a function that tests for primality to define a SCHEME function namedhappy-prime? which,givenapositiveintegerasaparameter,returnstrueifthenumberisaprime numberthatisalsoahappynumberandfalseotherwise. Recall, (define (prime n) (define (divides a b) (= (modulo b a) 0)) (define (smooth k) (and (= k 2)
1
(or (divides k n) (smooth (- k 1))))) (not (smooth (floor (sqrt n))))) (f) DefineaSCHEME functionnamedhappy-primeswhichtakesanintegern asaparameterandreturnsalist of the first n happy primes. See the following code for a filter function. You should see that the happy primesmentionedinthecliparethe18th,19th and20th. Whatisthe21st?
(define (find sequence test n) (define (find-aux x found) (let* ((fx ( sequence x)) (satisfies-test (test fx))) (cond ((and satisfies-test (= (+ found 1) n)) fx) (satisfies-test (find-aux (+ x 1) (+ found 1))) (else (find-aux (+ x 1) found))))) (find-aux 1 0))