Homework 01

Cutting a Candy Bar

Imagine a candy bar that has $k$ places where it can be cut. You would like to know how many how many different cuts are possible to divide the bar into pieces. For example, if $k$ is 3, you could cut the bar at location 1, then location 2, then finally at location 3. We indicate this sequence by '123'. So, if $k$ is 3, we have six ways to divide the bar: 123, 132, 213, 231. Recursively, this can be expressed as:

$C(k) = kC(k-1)$

Let's make this a bit more interesting by adding a restriction. You must always cut the leftmost pieces that can be cut. Now if $k$ is 3, we can cut the bar at locations 123, 132, 213, 312, or 321. A cutting sequence of 231 is not allowed, because after the cut at 2 we would have to make the cut at location 1, since it is the leftmost piece. We still have $k$ possibilities for making the first cut, but now we have to count the number of ways to cut two pieces and multiply. Recursively, this can be expressed as:

$D(k) = \sum\limits_{i=1}^{k} D(i - 1)D(k - i)$

For example, when k is 3 we would compute

$D(3) = \sum\limits_{i=1}^{3} D(i - 1)D(3 - i) = D(0)D(2) + D(1)D(1) + D(2)D(0)$
$D(2) = \sum\limits_{i=1}^{2} D(i - 1)D(2 - i) = D(0)D(1) + D(1)D(0)$
$D(1) = \sum\limits_{i=1}^{1} D(i - 1)D(1 - i) = D(0)D(0)$

In both cases, when $k=0$ there is exactly one way to divide the bar.

Write a java class CandyBar that will read a value $k$ from the keyboard and then display $C(k)$ and $D(k)$.

In addition to a main method, you should have two recursive methods (one each for $C(k)$ and $D(k)$).
Summations can easily be transformed into for loops.


    Enter a value of k: 3
    C(k) = 6
    D(k) = 5

Upload the .java file(s) to the dropbox

Make sure it conforms to the style guidelines