If you need help reviewing Scheme, take a look at these resources:
Each question has a "Toggle Solution" button -- click it to reveal that question's solution.
What would Scheme print
For the following questions, write the value that the expression
evaluates to if you type it into
scm. If the expression contains a
function (or multiple), write "FUNCTION" in place of that function. If
the expression causes an error, write "ERROR".
scm> (cons 1 (cons 2 (cons 3 (cons 4 nil)))) ______(1 2 3 4) scm> (cons (cons (cons 3 2) 1) (cons 4 nil)) ______(((3 . 2) . 1) 4) scm> (cdr (cons (cdr (list 1 2)) (cons 3 (cons 4 nil)))) ______(3 4) scm> (define lst (cons (lambda (x) (cons x x)) nil)) scm> ((car lst) lst) ______((FUNCTION) FUNCTION) scm> (define (x) (lambda (x) (list x x))) scm> (((car ((x) x))) 4) ______(4 4)
Implement a function
count-stairways, which takes a number
n as an
argument. Assuming you can only take 2 or 3 steps at a time, return the
number of ways you can reach the top of a staircase with
This is different than the usual
count-stairways — notice that this
time, we can only take 2 or 3 steps, rather than 1 or 2.
(define (count-stairways n) ; YOUR CODE HERE ) ; Tests scm> (count-stairways 1) 0 scm> (count-stairways 4) 1 scm> (count-stairways 5) 2 scm> (count-stairways 8) 4
(define (count-stairways n) (cond ((= n 1) 0) ((or (= n 2) (= n 3)) 1) (else (+ (count-stairways (- n 2)) (count-stairways (- n 3))))))
Implement a function
count-serpinski, which takes a numbero
as an argument. The function calculates how many triangles are
contained in a Serpinski's triangle with the given depth. See the tests
How can you use recursive calls on n-1 to build your answer for n?
(define (count-serpinski depth) ; YOUR CODE HERE ) ; Tests scm> (count-serpinski 1) 1 scm> (count-serpinski 2) 5 scm> (count-stairways 3) 17 scm> (count-stairways 4) 53
(define (count-serpinski n) (if (= n 1) 1 (+ 2 (* 3 (count-serpinski (- n 1))))))
The recursive call can be derived as follows:
- There are three smaller n-1 serpinski triangles at each of the corners
- There are two additional triangles drawn — the triangle in the center, and the overall triangle.
Fill-in the blank questions
Fill in the blanks for the
construct function. It takes a value and a
list of lists as arguments. It returns a new list of lists, where each
element is a list from the old list, but with the value added to the
(define (construct value lists) (if ______ ______ (cons _____________ _____________))) ) ; Tests scm> (define lists '((10) () (4 3) (2 5 3))) lists scm> (construct 6 lists) ((6 1) (6) (6 4 3) (6 2 5 3)) scm> (construct 6 '()) ()
(define (construct value lists) (if (null? lists) nil (cons (cons value (car lists)) (construct value (cdr lists)))))