案例 2020-01-15 10:13:41
汉诺塔:汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。上帝创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上安大小顺序摞着64片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。
假设木柱上有1个圆盘,只需移动1次
假设木柱上有2个圆盘,需移动3次(甲-丙,甲-乙,丙-乙)
假设木柱上有3个圆盘,需移动7次
甲-乙
甲-丙
乙-丙
甲-乙
丙-甲
丙-乙
甲-乙
假设木柱上有n个圆盘
实际上是有规律的
由一根针上移到另一根针上,并且始终保持上小下大的顺序。需要递归的方法,移动次数是f(n).显然f(1)=1,f(2)=3,f(3)=7,且f(k+1)=2*f(k)+1。此后不难证明f(n)=2^n-1。
那么f(5)=2^5-1=32-1=31次
moxingzu
文章:57 问答:0
Copyright 模型组 2006-2024 All Rights Reserved ICP证:蜀ICP备2023015644号-7
四川鑫众焱信息技术服务有限公司| 地址:绵阳市涪城区瀚威城市中心1栋1单元42层2号