龙空技术网

好玩的九连环

满分思维 71

前言:

而今兄弟们对“九连环解法与递归算法”可能比较注重,各位老铁们都需要分析一些“九连环解法与递归算法”的相关内容。那么小编同时在网摘上汇集了一些对于“九连环解法与递归算法””的相关文章,希望姐妹们能喜欢,姐妹们一起来了解一下吧!

九连环是中国最杰出的益智游戏。九连环作为我国民间玩具,以金属丝制成9个圆环,将圆环套装在横板或各式框架上,并贯以环柄。游戏时,按照一定的程序反复操作,可使9个圆环分别解开,或合而为一。

“九连环”现已成为一种国际性的益智游戏,国内外都有学者在研究,拆解九连环的过程中也蕴含着一些数学原理。

九连环的迷人之处

一是挑战性。任何一种连环的解法都具有较高的难度,有的难度极高,甚至令人觉得根本不可能解开。因此解连环就具有强大的挑战性,强烈地吸引着人们的好奇心和征服欲。

二是规律性。智力玩具都有其内在的规律,连环类玩具的规律性则特别强,必须按照特定的程序,有条不紊地操作,才能最终解开。

三是趣味性。伴随着挑战性和规律性而来的是趣味性。苏霍姆林斯基说:“在人的心灵深处,都有一种根深蒂固的需要,这就是希望感到自己是一个发现者、研究者、探索者。而在儿童的精神世界中,这种需要则特别强烈。”因此,人们对智力玩具具有天生的爱好,都想探索它、研究它、发现其中的奥妙,儿童更是如此。挑战性越强就越能吸引人,发现规律的过程往往令人心醉神迷。

九连环上下原则

改变某一环状态(上方和下方)必须要满足以下三条规则:

1、 九连环中的第一个环,在任何情况下都可上可下;

2、如果某一个环在上面的环杆上,而它前面所有的环都在下面的环杆上,那么这个环的后一个就可上也可下。这也就是说,如果我们想把第n个环卸下,那么第n-1个环要留在上面的环杆上,而第n-1个环前面的所有环都要在下面的环杆上。

3、每次只能解下或装上一个环。

数学证明

在数学证明中,九连环的拆解方法就涉及到了“数列”这一数学原理。

我们假设环的数量为n,记解开n连环所需的总步数是Sn, 解下每个环的步数为an;根据第二个原理我们可以推出,如若要卸下第n个环,就需要先卸下前n-2个环,其总步数就为Sn-2,这时再需要一步就可以把第n个环解下;而为了解下第n-1个环,还需要把前面的n-2个环套上,装上前n-2个环就需要Sn-2步(因为装上和卸下的步骤正好相反,所以步数相同),所以卸下第n个环需要an=2Sn-2+1步。因此,解开九连环所需要的步数就是一道数列题:“已知S1=1,S2=2,an=2Sn-2+1,求Sn(n≥3)。”

由上图可知,S9=341,即拆解一个九连环需要341步。

编程验证

用计算机编程来解九连环,通常将其视为二进制系统。因为其九个环有固定的顺序,且每个环都有位于上方和下方两种状态,因此若将环的两种状态分别给予代号1和0,则每种状态可以用9位二进制代表,解法用到了递归思想。

定义解开n连环的操作为solve(n),它的逆过程为rsovle(n),即把n连环套上去的过程。因为后者只是前者的逆过程,以下只讨论solve(n)。

n=1和n=2的情形很显然能得出:

1						0-> 12           00 -> 01 -> 11

n>2的过程如下:

1		solve(n - 2);2		flip(n - 1);3		rsolve(n - 2);
solve(n - 2);flip(n - 1);rsolve(n - 2);

熟悉九连环的人解开处于原始状态下的九连环所需的时间大概是6分钟左右,解开11连环则需24分钟左右,以此类推,如要解开17连环就要一昼夜以上,这不仅仅是在解环,也是在挑战自身的极限。这也就是九连环自诞生之后,虽然步骤简单却可以在民间广为流传,盛行不衰的原因吧。

相关拆解与组装视频请移步龙叔思维抖音号“牟爸牛娃养成记”(longshusiwei)

想跟踪牛娃成长足迹的家长请关注微博牟爸牛娃养成记()

标签: #九连环解法与递归算法 #九连环解法与递归算法的关系