OI WIKI:写递归的要点
明白一个函数的作用并相信它能完成这个任务,千万不要跳进这个函数里面企图探究更多细节, 否则就会陷入无穷的细节无法自拔,人脑能压几个栈啊。
问题
将a柱上的n个盘子挪到b柱上,同时可以借助c柱来操作。
限制:圆盘从大到小,从下往上放置,大的必须在小的下面。
定义
发现不管有几个盘子都要上面n-1个圆盘先放到c柱上,第n个放到b柱上,再把n-1个放回来。
定义
$f(n,a,b,c)$为将n个盘子从a柱挪到b柱。
$move(a,c)$为将a柱的盘子挪到c柱。
递归
$f(n-1,a,c,b)$
将n-1个柱子从a柱挪到c柱
$move(a,c)$
将第n个盘子挪到b柱
$f(n-1,c,b,a)$
将n-1个柱子从c柱挪到b柱