Week 10: Exercises

1. Stair Climbing

A staircase has n steps from bottom to top. A person walks up the staircase, and can take up to m steps at a time. Write a function

int stairs(int n, int m)

that returns the number of different ways in which the person may climb the stairs.

2. Carrots and Parsley

A garden contains N plant beds, all in a row. Each bed will contain either carrots or parsley, but no two neighboring beds may both contain parsley.

a) Write a function void garden(int n) that takes N, the size of the garden, and prints out all possible ways that exist to plant these vegetables in the garden. For example, garden(5) might print

C C C
P C C
C P C
C C P
P C P

b) Write a function int ways(int n) that takes N, the size of the garden, and returns the number of possible ways that exist to plant these vegetables in the garden. For example, ways(5) will print 5.

3. Box Stacking

A Box represents a box with a given width, height, and depth:

class Box {
    public int width, height, depth;

    public Box(int width, int height, int depth) {
        this.width = width; this.height = height; this.depth = depth;
    }
}

Write a method

int max_height(Box[] boxes)

that takes a set of boxes and determines the maximum possible height of a stack that can be formed from these boxes, assuming that you can place box b on box c only if b.width < c.width and b.depth < c.depth. You may not rotate the boxes in any way.

4. Tokenizer

The W programming language has the following features:

• integer constants

• variables

• the integer operators +, -, *, /, %

• the boolean operators ==, !=, >, >=, <, <=

• assignment statements

• if/else statements

• while statements

• a function print()

Here is a W program that prints the maximum of two values:

x = 1022
y = 1020

if (x > y) {
    print(x)
} else {
    print(y)
}

Here is a program that computes the sum of integers from 1 to 100:

x = 100
s = 0

while (x > 0) {
    s = s + x
    x = x - 1
}

print(s)

Here is a program that uses Euclid's algorithm to compute the GCD of two integers:

x = 1056
y = 668

while (y > 0) {
    t = x % y
    x = y
    y = t
}

print(t)

Variables can hold only integers, so boolean operators can be used only inside a 'while' condition. For example, 'x = y < z' is illegal. Arithmetic expressions may contain parentheses and may be nested. For example, 'x = (a + b) * (c + d)' is legal.

Write a class Lexer that can read the source code of a W program and produce a series of tokens. Each token is a string, and holds either

• an integer constant, e.g. "1056"

• an identifier, e.g. "x" or "y"

• a keyword, e.g. "if" or "while"

• a symbol, e.g. "(" or "<="

The tokenizer should ignore whitespace. It should have these members:

• Lexer(string filename) - create a Lexer that will read from the given file

• string? read() - read and return a token; return null at end of input

• string? peek() - return the next token without reading it; return null at end of input