(This document mainly includes some well-known problems and classical algorithms , which is now Ho Chi Minh; in 1883, the French mathematician Edouard Lucas mentioned this story. He heard that there was a Polo tower in Benares at the time of Genesis, which was supported by three diamond rods (Pag). At the beginning, God was in the first rod. Place 64 gold discs (Discs) from top to bottom, from small to large, and order the monks to move all the gold discs from the first stone rod to the third stone rod. The rule under the small plate, if only one plate is moved a day, when all the plates are transferred, the tower will be destroyed, which is when the end of the S world comes. Solution If the column is marked as ABC, it needs to be moved from A to C. When there is only one plate, it is directly moved to C. When there are two plates, B is used as an auxiliary column. If the number of plates exceeds 2, it is very simple to cover the plate below the third, and manage two plates at a time, that is: A-gt; B, A-gt; C, B-gt; C These three steps, and the covered part, are the recursive management of entering the program. In fact, if there are n disks, the number of times required for the end of the move is 2^n-1, so when the number of disks is 64, the required number of times is: 264-1=18446744073709551615 is 5.05390248594782e+16 years, also Even if it is about 5,000 centuries, if you have no idea about this number, assuming that one plate is moved every second, it will take about 585 billion years. ....
Classic Algorithms.pdf)
收藏
