|
Monday, Oct 30, 2000
Only three programs this week,
but they are good ones.
Graph Traverse begins
our exploration of search algorithms. Given an array of integers,
find the paths from one corner to the diagonally opposite corner with
the largest and smallest sums of integers on the path. This is an
"exhaustive" search since only by searching all paths can we
be sure we have found the extremes.
The Knight's Tour is
a classic chess problem which, in theory, is much more complex than the
Graph Traverse program. The problem is to make tour of a chess
board making standard "knightly" moves starting at an
arbitrary position and touching each square of the board exactly once.
Searching all possible paths is impossible in this case (unless we have
a very fast computer and a few million years to wait.)
Fortunately, as is often the case a mathematician, von Warnsdorf in
this case, developed a solution a couple of hundred years ago.
There were some pretty sharp guys back in those days.
Warnsdorf's heuristic (rule of thumb) makes solving the problem
almost trivial.
Finally a program demonstrating a
fast lookup method known as "Hashing" was
posted in the Math Topics section of the site.
Hey, we're up to a cumulative total of 1200 visitors!
I didn't know there were that many Delphi programmers out there.
Help spread the word - feel free to forward this to anyone who might be
interested.
Well, back to my annual "thought experiment"
trying to understand why, if I set my clock back and gained
an hour, it can be getting dark an hour earlier.
I've decided it's easiest just to think of it as moving the sun
forward.
To subscribe or unsubscribe, go to
the site and click on "Newsletters".
Gary
_____________________________
Gary Darby http://www.delphiforfun.org --------------------------------------------------
"One should guard against preaching to
young people success in the customary form as the main aim in life.
The most important motive for work in school and in life is pleasure in
work, pleasure in its result, and the knowledge of the value of the
result to the community." -- Albert Einstein
|
|
|