If only three pegs are allowed, we know that the best (minimum) number of moves is T3(n) =2 n−1, and a straight forward divide-and-conquer algorithm solves the 3-peg puzzle using exactly these many moves. Each move transfers a single disk d from Peg p to Peg q (p <= q),such that the following two conditions hold just before the movement: (i) Disk d must be sitting at the top of Peg p, and (ii) Disk d is not allowed to be larger than the disk (if any) sitting on the top of Peg q. Your task is to transfer the n disks from Peg A to Peg B taking help from the other two pegs, using a sequence of moves. The three other pegs are initially empty. Initially, n disks of diameters 1,2,3.,n are stacked on Peg A in the sorted order (the smallest disk at the top, and the largest disk at the bottom). There are four pegs A,B,C,D(numbered as 0,1,2,3). Very recently, Roberto Demontis (December 2018) proved that the Frame–Stewart algorithm is indeed optimal. In 1994, Paul Stockmeyer calculated an approximate closed-formexpression for the optimal number of moves made by the Frame–Stewart algorithm. Stewart independently proposed a particular way of solving the 4-peg puzzle, which is popularly known as the Frame–Stewart algorithm (see below). The 4-peg version eluded mathematicians for over a century. The 3-peg version is well understood, and its time complexity is easily provable.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |