九连环游戏与递归算法.ppt

1、,九连环游戏与递归算法,2011-12,九连环是中国民间玩具。这种古老玩具包含着九个相同的圆环及一把“剑”，目的是把九个圆环全套上或卸下。解九连环可以训练脑筋，甚至代表聪明的象征。 西方被称为一“中国环 (Chinese Ring)”。被认为是全世界发明的最奥妙三大智力玩具之一。,思维游戏,九连环是一种流传于山西民间的智力玩具。它用九个圆环相连成串，以解开为胜。据明代杨慎丹铅总录记载，曾以玉石为材料制成两个互贯的圆环，“两环互相贯为一，得其关捩，解之为二，又合而为一”。后来，以铜或铁代替玉石，成为妇女儿童的玩具。它在中国差不多有二千年的历史，卓文君在给司马相如的信中有“九连环从中折断”的句子。

2、清代，红楼梦中也有林黛玉巧解九连环的记载。周邦彦也留下关于九连环的名句“纵妙手、能解连环。”,思维故事,九连环是中国传统的有代表性的智力玩具，凝结着中国传统文化，具有极强的趣味性。九连环能既练脑又练手，对于开发人的逻辑思维能力及活动手指筋骨大有好处。同时它还可以培养学习工作的专注精神和耐心，实为老少咸宜。 九连环历史非常悠久，据说发明于战国时代。它是人类所发明的最奥妙的玩具之一。宋朝以后，九连环开始广为流传。在明清时期，上至士大夫，下至贩夫走卒，大家都很喜欢它。很多著名文学作品都提到过九连环，红楼梦中就有林黛玉巧解九连环的记载。在国外，数学家卡尔达诺在公元1550年已经提到了九连环。后来，数学

3、家华利斯对九连环做了精辟的分析。 格罗斯也深入研究了九连环，用二进制数给了它一个十分完美的答案。 九连环主要由九个圆环及框架组成。每一个圆环上都连有一个直杆，各直杆在后一个圆环内穿过，九个直杆的另一端用板或圆环相对固定住。圆环在框架上可以解下或套上。玩九连环 就是要把这九个圆环全部从框架解下或套上。九连环的玩法比较复杂，无论解下还是套上，都要遵循一定的规则。 19世纪的格罗斯经过运算，证明共需要三百四十一步，到目前为止还没有其它更为便捷的答案。1975年国外出了一本关于离散数学的书，其中收录了这样一个数列： 1,2,5,10,21,42,85,170,341 这就是“九连环”的数列。 实际上，

4、解下或套上n连环所需步数可用CM公式算出： f(n)=2(n+1)-0.5*(-1)n-1.5/3。 九连环的确环环相扣，趣味无穷。在第一次玩时，需要分析与综合相结合，不断进行思考和推理。复杂的玩法需要耐心和在困难面前不急躁的作风，切不可心浮气躁，使用暴力。玩九连环的次数多了，就会越来越熟练，也会对玩法有更加深刻的理解，能更好地体会其中的内在 思想。,网络探索,九连环的玩法 1. 将第一环从手柄的前端绕出，它就可以从手柄的中缝中掉落下来，从而解下第一环。,2. 我们可以将九连环的前两个环一起从手柄的前端绕出，从手柄的中缝里放下，从而解下第一环和第二环。,3. 九连环的每个环互相制约，只有第一环

5、能够自由上下。要想下/上第n个环，就必须满足两个条件（第一个环除外）： 一、第n-1个环在架上； 二、第n-1个环前面的环全部不在架上。,下面是解下九连环前五个环的具体步骤： 步骤： 1 2 3 4-5 操作： 下一 下三 上一 下一二 步骤： 6 7-8 9 10 操作： 下五 上一二 下一 上三 步骤： 11 12-13 14 15-16 操作： 上一 下一二 下四 上一二 步骤： 17 18 19 20-21 操作： 下一 下三 上一 下一二 【探索】依照上述步骤你一定能解下了前五个环，那么请你依照上述步骤从最后一步逆行操作至第一步，不过要将操作中的所有的“下” 改变为“上”，所有的“上

6、”改为“下”。是否也能成功地将前五个环套上去呢？,卸九连环的时候要记住，必须要卸下第九环，要卸下第九环，你必须先把前七环全部卸下，留下第八环，才可以卸下第九环，然后再卸第八环；要卸下第八环，你必须先把前六环全部卸下才可以卸下第八环；要卸下第七环，你必须先把前五环全部卸下才可以卸下第七环； 这样讲似乎是在讲绕口令，啊哈！这就是一种用不同的数字去反复调用同一规则的方法，在计算机中就称作为递归算法。,void DownRing(int n) /*下环的递归就体现在这里*/ if(n2) DownRing(n-2); printf(DW:%dt,n); +downstep; if(n2) UpRing

7、(n-2); if(n1) DownRing(n-1); void UpRing(int n) /*上环的递归则体现在这里*/ if(n1) UpRing(n-1); if(n2) DownRing(n-2); printf(UP:%dt,n);+upstep; if(n2) UpRing(n-2); ,#include int upstep = 0，downstep = 0; void DownRing(int n) if(n2) DownRing(n-2); printf(DW:%dt,n);+downstep; /* getch();*/ if(n2) UpRing(n-2); if(n1) DownRing(n-1); void UpRing(int n) if(n1) UpRing(n-1); if(n2) DownRing(n-2); printf(UP:%dt,n);+upstep; if(n2) UpRing(n-2); main() int rings=9;