Develop a program that will read a value of k from the keyboard and then display C(k) and D(k). (D(k) is interesting because it turns out to be the number of ways that we can parenthesize an arithmetic expression that has k binary operators.)

Question

Imagine a candy bar that has k places where it can be cut. You would like to know how many different sequences of 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, and finally at location 3. We indicate this sequence of cuts by 123. So if k is 3, we have six ways to divide the bar: 123, 132, 213, 231, 312, or 321. Notice that we have k possibilities for making the first cut. Once we make the first cut we have k - 1 places where a cut must be made. Recursively, this can be expressed as
C(k) = k C(k - 1)
Lets 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 would not be 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


The recursive algorithm for C(k) is easy to implement and should be familiar. The recursive algorithm for D(k) is slightly more complicated, but can be based on C(k). Instead of making a single recursive call, loop and make the recursive calls. As with previous projects, this one can experience overflow if the input value k is too large.

Answer 1

See the code in Cuts.java.