flexser at fiu.edu
Mon Feb 6 19:23:35 EST 2006
On Mon, 6 Feb 2006, Robert Gault wrote:
> 4) In theory, the assignment of mines could be improved. The current
> method is analogous to throwing darts at a map divided into 338 squares.
> Darts are thrown until there are 45 darts on the map, each in a
> different square. This could take a very long time if the darts keep
> hitting the same squares, which is possible.
> Another analogy is a bag of 338 marbles each labeled with a different
> number. Pull out 45 marbles and the mines go on the squares
> corresponding to the marbles. There can't be any multiple hits of the
> same squares.
> The question is can the second routine be programmed in as simple a
> fashion as the first. I have not been able to write a Basic program
> using method 2 that is even close to method 1 in speed, even though
> method 2 is the better method. It is a good example of complexity
> overwhelming speed.
> Care to guess how the speed of method 1 will be affected by increasing
> the percentage of the mined area?
An interesting mathematical problem, more or less equivalent to finding a
formula for the expected number of dart throws when there are N squares and i
darts, and a dart must be rethrown if it hits a square already occupied by
another dart. Any takers?
More information about the Coco