九连环的递归算法(C和C++)
九连环的递归算法
一、九连环简介
九连环游戏是中国人自己发明的,它的历史非常悠久,据说是起源于战国时期。九连环主要是由一个框架和九个圆环组成:每个圆环上连有一个直杆,而这个直杆则在后面一个圆环内穿过,九个直杆的另一端用一块木板或圆环相对固定。
二、九连环的规律
通过玩九连环你就会发现存在这样一个规律:
(1)第 1环可以自由上下 (2)而上/下第 n环时(n>1),则必须满足: (a)第 n-1个环在架上 (b)前 n-2个环全部在架下
三、拆解/安装的过程
正确的拆解是先以第 9环为目标,先拆下它,简化为拆一个 8连环。接着再也第 8 环为目标,拆下它,简化为拆一个 7连环。以此类推,直至全部拆解。
其实安装和拆解是一个道理,因为他们均是使用上面说的规律来完成的。
正确是安装也是先以第 9环为目标,先装上它,简化为装一个 8连环。接着再也第 8 环为目标,装上它,简化为装一个 7连环。以此类推,直至全部安装。
当然,现在这么说是便于理解,当你深刻的理解了上面所说的规律后,就会发现,安装上第 9环后,问题可以被简化为装一个 7连环,而当装上第 7 环后,问题就被简化为装一个 5连环了,呵呵,就是这样的,不知道你现在是否明白我的意思……
四、一个猜想
仔细观察九连环的结构、思考九连环的规律及拆解/安装的过程,你是不是有一种感觉:九连环跟递归一定有联系。你看,递归的基本思想是把一个大的问题分解为一个规模较小的问题,从这些较小问题的解,构造出大问题的解,而这些规模较小的问题,用同样的方法分解成更小的问题,从更小问题的解,构造出较小的问题,一层层下去,一般最后总是可以分解到可以直接求解的小问题。嘿嘿,九连环的拆解/安装多么的符合这个规律啊……^_^
五、算法实现
以下是算法实现,程序写的很简洁,省略了很多功能的实现,比如计数等,如果你觉得有必要的话,可以自行添加上去,我相信很容易,并不要很多的改动。
The C Code Here:
/****************************/ 任意 N连环均适用 日期:2002/11/6 程序设计:道可道 腾讯QQ:3908000 电邮:Havelife@mail.csdn.net /****************************/
void UpRing(int n); /*函数