相关文章推荐
绅士的灭火器  ·  Oracle 与 TiDB ...·  1 年前    · 
爱跑步的钥匙  ·  sql server ...·  1 年前    · 

九连环的递归算法

一、九连环简介

九连环游戏是中国人自己发明的,它的历史非常悠久,据说是起源于战国时期。九连环主要是由一个框架和九个圆环组成:每个圆环上连有一个直杆,而这个直杆则在后面一个圆环内穿过,九个直杆的另一端用一块木板或圆环相对固定。

二、九连环的规律

通过玩九连环你就会发现存在这样一个规律:

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);         /* 函数声明 */

void DownRing(int n)     /* 下环逻辑 */
{
if(n>2) DownRing(n-2);
printf("
下第 %d
\n",n);
if(n>2) UpRing(n-2);
if(n>1) DownRing(n-1);
}

void UpRing(int n)         /* 上环逻辑 */
{
if(n>1) UpRing(n-1);
if(n>2) DownRing(n-2);
printf("
上第 %d
\n",n);
if(n>2) UpRing(n-2);
}

void main()

printf(" 拆解 \n");
DownRing(9);
printf("
安装
\n");
UpRing(9);
printf("
结束
\n");
}

The C++ Code Here:
/****************************/
           任意 N连环均适用
           日期:2012/8/12
           程序设计:YCY
           电邮:ycy360@163.com
/****************************/
#include<iostream> 
using namespace std; 
class Ring
public:
       Ring(int n):nRingNum(n){}
       void UpRing(int n);
       void DownRing(int n);
       void startDownRing(); 
       void startUpRing();
       void totalCnt();
       void setUpZero();
private:
       int nRingNum;
       static int s_nCnt;
int Ring::s_nCnt = 0;    //计数
void Ring::UpRing(int n)  //Upring是DownRing的逆过程.
       ++s_nCnt;
       if(n>1) UpRing(n-1);
       if(n>2) DownRing(n-2);
       cout << "上第" << n << "环" << endl;
       if(n>2) UpRing(n-2);
void Ring::DownRing(int n)
       ++s_nCnt;
       if(n>2) DownRing(n-2);
       cout <<"下第" << n << "环" << endl;
       if(n>2) UpRing(n-2);
       if(n>1) DownRing(n-1);
void Ring::startDownRing()
       cout << "拆解" << nRingNum << "连环操作!" << endl;
       DownRing(nRingNum);
       cout << "拆解完毕" << endl;
void Ring::startUpRing()
       cout << "安装" << nRingNum << "连环操作!" << endl;
       UpRing(nRingNum);
       cout << "安装完毕" << endl;
void Ring::totalCnt()
       cout << "共累计上、下环" << s_nCnt << "次!" << endl << endl;
void Ring::setUpZero()
       Ring::s_nCnt = 0;
int main()                  
       Ring ring(3);
       ring.startDownRing();
       ring.totalCnt();
       ring.setUpZero();      //置为0
       ring.startUpRing();
       ring.totalCnt();
       ring.setUpZero();
       return 0;

存在以下序列即:

 N(numOfRing)

1

2

3

4

5

6

7

8

9

10

11

 Cnts

1

2

5

10

21

42

85

170

341

682

1365

….

呈现阶层递增的趋势。

不知道大家有没有玩过一个叫做 九连环 的玩具,如下图所示。 如果你不了解九连环,那玄黄就带你领略九连环的奥妙: 九连环是我国传统的民间智力玩具,玩具上面有九个连环套在杆上,目标就是通过一定的方式将九个连环从杆上全部取下来。 玩法是...   九连环的递回算法   1、九连环简介   九连周游戏是止您妊旁己创造的,它的汗青十分悠暂,听说是来源于战国期间。九连环次要是由一个框架战九个悦挥蟹组成:每一个悦挥蟹上连有一个曲杆,而那个曲杆则正在前面一个悦挥蟹内脱过,九个曲杆的另外一端用一块木板或悦挥行肃对固定。   2九连环的纪律   经由过程玩九连环您便会发明存正在如许一个纪律:
做题做到TOJ 3318 Chinese Rings 故此借鉴 Mohrie 的C++递归实现九连环http://download.csdn.net/source/770975 仍可计算步数、每步操作 可循环输入 以输入0结束 运行环境:Dev-C++
九连环是一种流传于山西省的传统民间的智力玩具,由九个圆环相连成串,以解开为胜。 九连环的九个环,一环扣一环地套在钗上。除了第 1 号环可以随时装上或卸下以外,其它环装上或卸下的条件是:在它的前面仅有紧靠它那一个环在钗上。即:当第 1 ~ i−2 号环都不在钗上,第 i−1 号环在钗上,这时可以装上或卸下第 i 号环。 环数 操作(U表示装上, D表示卸下) 装上或卸下九连环的操作步骤 每行显示一步操作,具体格式为: 环号: U或D (U表示装上,D表示卸下) #include<s
//求取下n环放上n环的步数int ans; //规则一:第一环可以在任何时候放上或取下环柄。 //规则二:只有紧跟在领头环后的环可以放上或取下环柄。(领头环是套在柄上的最前面的环 int DownRing(int); int UpRing(int); int DownRing(int n) int res = 0; if(n == 1)