Here are a few more results: ghci> hanoiR 6 It's too late at night for me to verify more, without writing a simulator. I've verified the correctness of the answer for 4 disks and 4 pegs. I haven't tried to optimize k, though n/2 seemed like a good guess. But I may have silly mistakes so feedback is welcome.Īs you can see from the code, the heuristic for k is simply floor(n / 2). I'm pretty new to Haskell so I must admit I'm proud that this works. move the top disk from peg 1 to peg 2, then the top disk from peg 1 to peg 3, etc. You can name the 4 pegs whatever you want, e.g. run the Towers of Hanoi with 4 disks and 4 pegs. n disks and r > 3 pegs: use Frame-Stewart algorithm n disks and 3 pegs - unneeded covered by (null rest) below. HanoiR 1 (p1 : p2 : rest) = - only needed for smart-alecks? one disk: one move and two pegs needed. Here is an implementation in Haskell (update: took care of 3-peg case by making k = n-1 when r=3): - hanoi for n disks and r pegs Note that this does not handle degenerate cases for which there is no solution, such as HanoiK 2 > let k = if rest.IsEmpty then n - 1 else int(n / 2) Hanoi3(nDisks - 1, source, dest, intermed) Īnd without treating 3 pegs as an edge case: let rec HanoiK n pegs = ![]() Here's a recursive algorithm that solves the problem: void Hanoi3(int nDisks, char source, char intermed, char dest) You must also do this with the minimum number of moves. You are given 3 pegs with disks on one of them, and you must move all the disks from one peg to another, by following the given rules. The Towers of Hanoi problem is a classic problem for recursion.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |