Recursion - Data Structures and Problem Solving Using Java - page 348

figure 7.31
The first three
iterations of a Koch
star.

Use dynamic programming to solve the longest increasing sequence
problem in Exercise 7.51 (a). Hint : Find the best sequence emanat-
ing from each grid element, and to do so, consider the grid elements
in decreasing sorted order (so that the grid element containing 98 is
considered first).

7.52

Consider the following two-player game: N coins c 1 , c 2 , ... c N (you
may assume that N is even) are placed in a line on a table. Players
alternate turns and at each turn a player selects either the first or last
coin in the row, removing the coin and keeping it. Devise an algo-
rithm that, given the array of coins, determines the maximum amount
of money that player #1 can definitely win.

7.53

A Koch star is formed starting with an equilateral triangle and then
recursively altering each line segment as follows:

7. 5 4

1. divide the line segment into three segments of equal length.
2. draw an equilateral triangle that has the middle segment from step 1
as its base and points outward.
3. remove the line segment that is the base of the triangle from step 2.

The first three iterations of this procedure are shown in Figure 7.31.
Write a Java program to draw a Koch star.

references

Much of this chapter is based on the discussion in [3]. A description of the
RSA algorithm, with proof of correctness, is presented in [1], which also
devotes a chapter to dynamic programming. The shape-drawing examples are
adapted from [2].