Sale!

CSC148 Assignment #1

$30.00

Category:

CSC148, Assignment #1

From an early draft of his Canterbury tales, Chaucer removed an account of the pilgrims staying at Anne
Hoy’s1
inn, an establishment that served bad ale, but good cheese. The missing account explained how Anne
kept her high-quality cheese stacked on stools, the largest rounds underneath the smaller rounds, to stop
rats and mice from getting at them.
Occasionally the stool holding the cheese would need some maintenance (for example, the legs would
start to buckle under the weight), and Anne would shift the entire stack from one stool to another. Since
she could only move a single (hundred-pound plus) round of cheese at one time, and she refused to stack
a larger-diameter cheese round on a smaller one (the outer part of the larger cheese would droop) she used
three stools: one was her destination for her entire stack of cheese, one was the source (which likely needed
its legs reinforced), and the third was for intermediate stacking. Chaucer immortalized the complicated
routine Anne endured, lugging rounds of cheese from stool to stool as \The tour of Anne Hoy ” (TOAH).2
One of Chaucer’s pilgrims had a mathematical bent. She had seen a miraculous early draft of the
Wikipedia article on the Tower of Hanoi in a vision, and noticed that Anne’s routine for moving cheeses
was identical to the problem of moving rings between three posts. Using this similarity she calculated that
to move n cheeses in this way required 2n 1 moves. This disheartened Anne, who had plans to increase
her stack of cheese beyond the 8 she currently had. She decided to invest some of her pro ts in a fourth
stool.
Anne gured that she could do substantially better than 2n 1 moves using the following strategy:
 For a stack of 1 cheese round, her four-stool con guration allowed her to move the stack in 1 move,
using her previous three-stool TOAH method.
 To move a stack of n > 1 cheese rounds from some origin stool to some destination stool, she reasoned
that she could think of some number i between 1 and n 1, and then:
1. Move n i cheese rounds to an intermediate stool using all four stools.
2. Move i cheese rounds from the origin stool to the destination stool, using the (now) only three
available stools and her TOAH method.
3. Move the n i smallest cheese rounds from the intermediate stool to the destination stool, using
all four stools
Notice that steps 1 and 3 require Anne to know how to move n i cheese rounds using four stools. Anne
gured this wasn’t a problem, since she could apply her recursive strategy to this smaller problem. She
presented her plan to the above-mentioned mathematically-inclined pilgrim who said that if she called the
minimum number of moves that her strategy needed to move n rounds of cheese M(n), and if some i between
1 and n 1 were chosen, then (reasoning recursively):
M(n) = (
1 n == 1
2 M(n i) + 2i 1 otherwise:
(1)
1
In Middle English her name would have been spelled Auyne H’Oeuil
2Chaucer conjectured Anne’s muttered \cheeses crust!” and \gentle jumping cheeses!” were veiled religious oaths, not
mundane references to cheese mainte

Reviews

There are no reviews yet.

Be the first to review “CSC148 Assignment #1”

Your email address will not be published.