九連環是中國著名的古典智力遊戲，距今至少已有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 步。類似地，還可以隨便指定合理的初始狀態去求解。本文屬於個人原創文章，歡迎各位讀者參閱、指正^_^
九連環是中國著名的古典智力遊戲，距今至少已有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 步。類似地，還可以隨便指定合理的初始狀態去求解。本文屬於個人原創文章，歡迎各位讀者參閱、指正^_^