51个经典算法荟萃-老奔整理【PDF清晰版】
本文档首要收录了一些著名的问题和经典算法1.河内之塔说明河内之塔(TowersofHanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的,河内为越战时北越的首都,即如今的胡志明;1883年法国数学家EdouardLucas曾提及这个故事,听说创世纪时Benares有一座波罗教塔,是由三支钻石棒(Pag)所支持,开始时神在第一根棒上放置64个由上至下依由小至大摆放的金盘(Disc),并命令僧侣将一切的金盘从第一根石棒移至第三根石棒,且转移过程中恪守大盘子在小盘子之下的准则,若每日仅搬一个盘子,则当盘子全数转移结束之时,此塔将毁损,而也即是S界末日来临之时。解法假如柱子标为ABC,要由A搬至C,在只要一个盘子时,就将它直接搬至C,当有两个盘子,就将B当作辅佐柱。假如盘数超过2个,将第三个以下的盘子遮起来,就很简单了,每次管理两个盘子,也即是:A-gt;B、A-gt;C、B-gt;C这三个步骤,而被遮住的部份,本来即是进入程式的递回管理。事实上,若有n个盘子,则移动结束所需之次数为2^n-1,所以当盘数为64时,则所需次数为:264-1=18446744073709551615为5.05390248594782e+16年,也即是约5000世纪,假如对这数字没什幺概念,就假定每秒钟搬一个盘子好了,也要约5850亿年左右。....经典算法大全.pdf
(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)
页:
[1]