九连环是中国民间玩具。以金属丝制成9个圆环，将圆环套装在横板或各式框架上，并贯以环柄。游九连环时，按照一定的程序反复操作，可使9个圆环分别解开，或合而为一。
九连环的形态多样，但其原理与结构其实大同小异，今天小城就给大家讲解最常见的九连环（图1）
图1仔细观察下面环与环的嵌套方式
这是其中一端（图2）
图2这是另一端（图3）
图3你会发现 图2 端最左边的环永远是自由的，而 图3 端最右边的环永远收到前一个环的牵制，所以根据环的特性为每个环命名（图4）
图4
要讲解九连环得讲一下一些简单的术语：
上第n个环（上）：（图5到图6的过程为上1环）
下第n个环（下）：（图6到图5的过程为下1环）
图5图6（必须以这 图6 状态在环上，否则没法玩）
规定环在叉上为1，否则为0
上n：小于等于n的环，从全为0到全为1的过程
下n：小于等于n的环，从全为1到全为0的过程下面先来研究上环吧：在玩九连环的过程中你会发现1环可以在任意时候上下；
可是从2环开始，如果想上2，1就得是1；
想上3，则2得是1，但是1要为0；
想要4为1，则3为1, 2环和1环为0；
如果要上5，则4为1, 3、2、1环为0；
不需要讲完九个环，就但从上边的这5个环中就可以发现一个规律，加入想上第n个环，则（n-1）环必须为1，名字小于（n-1）的环必须都为0。
这是个很重要的算法!在程序中可以用递归来解，鉴于这个，我想可以用程序来解九连环。
下面我列出等式分析九连环九个环上环的粗略步骤
（上n、下n如：上3表示1、2、3环开始为0，目的是1,2,3全为1，下5表示1、2、3、4、5环开始为1，要让1,2,3,4,5环都为0）
先从上环开始：
（1）上1=上1；
（2）上2=上1，上2；
（3）上3=上2，下1，上3，上1；
（4）上4=上3，下2，上4，上2；
（5）上5=上4，下3，上5，上3；
（6）上6=上5，下4，上6，上4；
（7）上7=上6，下5，上7，上5；
（8）上8=上7，下6，上8，上6；
（9）上9=上8，下7，上9，上7；
（n）上n=上（n-1），下（n-2），上n，上（n-2）；
(n)将会用到程序解九连环中，注意这里！！
为什么从第三项开始，粗略步骤只有4步呢？其实是因为它已经分解到的各个步骤在前面都有定义了
如：（4）中的上3前面有定义，上4是因为有了3为1,2和1环为0的条件，可以直接完成，而 下2（后面讲解），上2，可以用（2）代替，同理（2）中的上2可以一步完成，而上1由（1）定义过，而且1是永远自由的！
如果下环是什么样的呢？看看就知道了！
（1）下1=下1；
（2）下2=下2，下1；
（3）下3=下1，下3，上1，下2，
（4）下4=下2，下4，上2，下3
（5）下5=下3，下5，上3，下4
（6）下6=下4，下6，上4，下5
（7）下7=下5，下7，上5，下6
（8）下8=下6，下8，上6，下7
（9）下9=下7，下9，上7，下8
（n）下n=下（n-2），下n，上（n-2），下（n-1）；这个也会用到程序中
其实对照上边的可以看出，和上环的粗略步骤完全相反
上边两个（n）为标准步骤，当n>2时满足（n）式，当n为2时缺少包含（n-2)环的那一步，当n为1时缺少（n-1)和（n-2）的这两步，这是编程序必须清楚的一点！！
现在就可以解释详细步骤了！！！
如果要上第n个环，其实只需要不断代入已知公式即可，因为要不断地代入，递归的使用会使多一个环使得上环步骤成倍数增长，所以只举例 上3的具体步骤：（图7）
图7这个只是解九连环的原理，能帮助理解解九连环的思想，总不能用这种方法直接去解九连环吧！
所以小城要用C语言列出解九连环的详细步骤
以下为C语言列出具体步骤的代码及其详解：
外行看不懂的，可以跳过程序讲解，直接看后边解九连环的所有步骤
源代码：
#include
#include
#include/////////// 函数