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
Question 1
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)
Code-Writing questions
Question 2
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 n
stairs.
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))))))
Question 3
Implement a function count-serpinski
, which takes a numbero depth
as an argument. The function calculates how many triangles are
contained in a Serpinski's triangle with the given depth. See the tests
for examples.
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
front.
(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)))))