九連環的數學分析
7 人贊了文章
九連環是中國著名的古典智力遊戲,距今至少已有800多年,在我國古籍中有關它的記載也很多見。對於解九連環,我想大多數玩過的人都對它的解環過程映像深刻,古人曾經總結出了三句口訣:
1.一二一三一二一
2.釵頭雙連下第二
3.獨環在釵上後環
本文將從九連環的基本操作規律中通過逆向歸納得到解法,並隨之導出解環所需步驟數的遞推關係式,得到了解下九連環的步數。在文末,舉例簡單地介紹了求解不同設定的九連環的步數問題。
九連環的基本操作規律
1.九個環中只有第一個環和第二個環既可單獨套上或取下,也可同時上下。
2.當前個環都解下而第
個環在環柄時,第$n$個環才能上下,此時第
個環不能上下(
)。
3.上環過程是下環的逆。
註:熟悉九連環的可跳過下面的解法分析。
解法分析
根據基本操作規律,要想解下全部的九個環,首先要做的要讓第九個環解下,然後再依次解下所有環。類似於河內塔問題,要把全部n個盤挪位置,一定要讓最後一個位於塔底的盤挪出來,在接著後續的步驟。
而要解第九個環,根據上述規律2,操作狀態為:解下前7個環,九號環解下,八號環在環柄。這時然後再解第八個環,即當前六個環都解下時,八號環解下;接著解第七個環……,直至1號環和2號環解下,完成九個環的環柄分離。
上述是一個解九連環的分段目標,具體每一段的操作又有很大的重複性,我們可以通過逆向歸納得到每一階段的操作過程。
比如,解下九號環,要先解前七個環,則必須先解七號環,依次往下推:解下前5個環先解5號環
解下前三個環
解三號環,最後回到了開始時第一步:解下一號環。然後逆此方向就可以完成九號環下柄。
同理,當完成九號環的下柄過程後,繼續解八號環分兩步:
1.當九號環解下時,一至七環都已被解下,要解下八號環,要達到的狀態是:七號環上,而前六個環解下。 這時,七號上需要六號上而一至五環都解下,依次往下推有,五號上 四號上
三號上
二號上(一號上);
2.接著此時狀態相當於九號環被解下,而一至八環在環柄上。所以需要先解下八號環,仍然可以通過逆推來完成八號環的下柄,不再多言。
依次類推,解下所有環。
從上述較為詳細而啰嗦的文字分析可以知道,粗略地說,在解九連環的過程中,每解下一個環,就得重複一遍之前所做的大部分工作。顯然,解環的過程是蘊含遞推關係的,下面來推導解環所需步驟數的遞推公式。
遞推公式和通項公式
令表示解下前n個環所需操作步驟數,將解下n個環的過程表述如下:
1. 解下前n-2個環
2. 解下第n號環
3. 前n-2個環重新上柄
4. 解下前n-1個環
所以,H(n)的遞推關係為:
可化為常係數齊次遞推公式:
利用初始條件:,易解得通項公式為:
(n為奇數)
(n為偶數)
這樣的話,解下九連環的步驟數為:H(9)=256
解特殊狀態的九連環
玩九連環時,一般是以九個環都在環柄上作為初始狀態開始解的,已經知道了這樣的情況需要256步。如果要求初始狀態是1至8號環都已經解下,只有九號環在環柄上,此時取下所有環需要多少步?
來解一下:
根據九連環的規律,必須先要九號環解下,所以讓已經解下的一至八環再套上去,這樣就回到了「正常」狀態的九連環。所以這樣的情況一共需要:H(8)+H(9)=383 步。
類似地,還可以隨便指定合理的初始狀態去求解。
本文屬於個人原創文章,歡迎各位讀者參閱、指正^_^
推薦閱讀:
※十條笑話:上數學課,男生接了一句:愛過!全班哄堂大笑
※Oracle優化
※五階立方體:初級降階法
※奇門遁甲代數學基本公式
TAG:數學 |