阅读与思考九连环 (3).ppt

九连环游戏与递归算法 2018 6 九连环是中国民间玩具 这种古老玩具包含着九个相同的圆环及一把 剑 目的是把九个圆环全套上或卸下 解九连环可以训练脑筋 甚至代表聪明的象征 西方被称为一 中国环 ChineseRing 被认为是全世界发明的最奥妙三大智力玩具之一 思维游戏 九连环是一种流传于山西民间的智力玩具 它用九个圆环相连成串 以解开为胜 据明代杨慎 丹铅总录 记载 曾以玉石为材料制成两个互贯的圆环 两环互相贯为一 得其关捩 解之为二 又合而为一 后来 以铜或铁代替玉石 成为妇女儿童的玩具 它在中国差不多有二千年的历史 卓文君在给司马相如的信中有 九连环从中折断 的句子 清代 红楼梦 中也有林黛玉巧解九连环的记载 周邦彦也留下关于九连环的名句 纵妙手 能解连环 思维故事 九连环是中国传统的有代表性的智力玩具 凝结着中国传统文化 具有极强的趣味性 九连环能既练脑又练手 对于开发人的逻辑思维能力及活动手指筋骨大有好处 同时它还可以培养学习工作的专注精神和耐心 实为老少咸宜 九连环历史非常悠久 据说发明于战国时代 它是人类所发明的最奥妙的玩具之一 宋朝以后 九连环开始广为流传 在明清时期 上至士大夫 下至贩夫走卒 大家都很喜欢它 很多著名文学作品都提到过九连环 红楼梦 中就有林黛玉巧解九连环的记载 在国外 数学家卡尔达诺在公元1550年已经提到了九连环 后来 数学家华利斯对九连环做了精辟的分析 格罗斯也深入研究了九连环 用二进制数给了它一个十分完美的答案 九连环主要由九个圆环及框架组成 每一个圆环上都连有一个直杆 各直杆在后一个圆环内穿过 九个直杆的另一端用板或圆环相对固定住 圆环在框架上可以解下或套上 玩九连环就是要把这九个圆环全部从框架解下或套上 九连环的玩法比较复杂 无论解下还是套上 都要遵循一定的规则 19世纪的格罗斯经过运算 证明共需要三百四十一步 到目前为止还没有其它更为便捷的答案 1975年国外出了一本关于离散数学的书 其中收录了这样一个数列 1 2 5 10 21 42 85 170 341 这就是 九连环 的数列 实际上 解下或套上n连环所需步数可用CM公式算出 f n 2 n 1 0 5 1 n 1 5 3 九连环的确环环相扣 趣味无穷 在第一次玩时 需要分析与综合相结合 不断进行思考和推理 复杂的玩法需要耐心和在困难面前不急躁的作风 切不可心浮气躁 使用暴力 玩九连环的次数多了 就会越来越熟练 也会对玩法有更加深刻的理解 能更好地体会其中的内在思想 网络探索 九连环的玩法1 将第一环从手柄的前端绕出 它就可以从手柄的中缝中掉落下来 从而解下第一环 2 我们可以将九连环的前两个环一起从手柄的前端绕出 从手柄的中缝里放下 从而解下第一环和第二环 3 九连环的每个环互相制约 只有第一环能够自由上下 要想下 上第n个环 就必须满足两个条件 第一个环除外 一 第n 1个环在架上 二 第n 1个环前面的环全部不在架上 下面是解下九连环前五个环的具体步骤 步骤 1234 5操作 下一下三上一下一二步骤 67 8910操作 下五上一二下一上三步骤 1112 131415 16操作 上一下一二下四上一二步骤 17181920 21操作 下一下三上一下一二 探索 依照上述步骤你一定能解下了前五个环 那么请你依照上述步骤从最后一步逆行操作至第一步 不过要将操作中的所有的 下 改变为 上 所有的 上 改为 下 是否也能成功地将前五个环套上去呢 卸九连环的时候要记住 必须要卸下第九环 要卸下第九环 你必须先把前七环全部卸下 留下第八环 才可以卸下第九环 然后再卸第八环 要卸下第八环 你必须先把前六环全部卸下才可以卸下第八环 要卸下第七环 你必须先把前五环全部卸下才可以卸下第七环 这样讲似乎是在讲绕口令 啊哈 这就是一种用不同的数字去反复调用同一规则的方法 在计算机中就称作为递归算法 voidDownRing intn 下环的递归就体现在这里 if n 2 DownRing n 2 printf DW d t n downstep if n 2 UpRing n 2 if n 1 DownRing n 1 voidUpRing intn 上环的递归则体现在这里 if n 1 UpRing n 1 if n 2 DownRing n 2 printf UP d t n upstep if n 2 UpRing n 2 includeintupstep 0 downstep 0 voidDownRing intn if n 2 DownRing n 2 printf DW d t n downstep getch if n 2 UpRing n 2 if n 1 DownRing n 1 voidUpRing intn if n 1 UpRing n 1 if n 2 DownRing n 2 printf UP d t n upstep if n 2 UpRing n 2 ma