Give an optimal algorithm to break an mxn Hershey bar into 1x1 pieces. At each step, you can choose a single rectangle of chocolate and crack it along one of its vertical or horizontal lines. A single crack counts one step. You are to make the fewest number of cracks.
David Gries's coffee can problem:
Given a can of black and white coffee beans, do the following: Pull out two beans: if both are the same color, replace them with a white bean. If the two are different, replace them with a black bean. What color is the last bean?
http://www.cs.cmu.edu/~mblum/research/pdf/grad.html
ReplyDelete