什么是漢諾塔？

漢諾塔（Tower of Hanoi），又稱河內塔，是一個源于印度古老傳說的益智玩具，大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤，大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上，并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤，

一. 求解漢諾塔問題的思路

假設有三個柱子，一共有四個圓盤，如圖所示：

要想把A柱上的四個圓片按相同的順序放在C柱上，必須要借助B柱，并且一次只能拿一個圓片，因此在移動的程序中會出現兩種情況，也就是從下往上看會有由大到小和由小到大的情況，
第一步：要把A柱上除了最大的圓片之外的三個放到B柱上，然后把A柱上的最大的圓片放到C柱上，

第二步：完成第一步之后，A柱就空出來了，再借助A柱，將B柱上的除了最下面的圓片之外的兩個放到A柱上，將B柱的最下面的圓片放到C柱上，

第三步：完成第二步之后就把B柱空出來了，借助B柱，將A柱除了最下面的圓片的另一個圓片放在B柱上，將A柱的最下面的圓片放在C柱上，

第四步：將B柱上的最后一個圓片放在A柱上，

這樣就完成了將A柱上的圓片按相同的順序放在C柱上，

二. 漢諾塔問題的代碼實作

要想將漢諾塔的問題求解，就要從其中找到規律，找到解出問題的思路，
我們可以把三個柱子想象成三個陣列，分別是arr1、arr2、arr3

整個程序中，只借助A柱和B柱，來進行移動，不涉及C柱，C柱只是依次放圓片，
按照上面的步驟，如下圖

第一次：
對于arr1和arr2：
arr1[3] ===> arr2[0]
arr1[2] ===> arr2[1]
arr1[1] ===> arr2[2]
對于arr3：
arr1[0] ===> arr3[0]

第二次：
對于arr1和arr2：
arr2[1] ===> arr1[0]
arr2[0] ===> arr1[1]
對于arr3:
arr2[2] ===> arr3[1]

第三次：
對于arr1和arr2：
arr1[1] ===> arr2[0]
對于arr3:
arr1[0] ===> arr3[2]

arr2[0] ===> arr3[3]

最后一次只剩下了一個圓片，直接放在C柱即arr3上即可，

總結規律

1.在移動中只借助arr1和arr2，因此移動得部分只需要設計arr1和arr2陣列即可，并且每移動一次，arr1和arr2中就會有一個變成空的，
2.C柱也就是arr3放置的位置就會加一，
3.移動的程序中，會出現兩種不同的情況，因此需要在移動的函式中設計不同的放置方法，

三. 代碼實作

根據上面的思路和總結的規律，由于每一次移動的流程幾乎是相同的，我覺得可以用遞回來實作漢諾塔的流程，并且遞回中最重要的兩個條件：
1.限制條件是能夠移動的圓片的數量，當圓片為0時表示移動完成
2.每呼叫一次函式，圓片數量減少一個，以此來不斷逼近限制條件，

代碼實作如下：

1.主函式代碼

#include "hanoi.h"
int main()
{
	int i = 0;
	int arr1[SIZE] = {4, 3, 2, 1 };
	int arr2[SIZE] = { 0 };
	int arr3[SIZE] = { 0 };
	Hanoi(arr1, arr2, arr3,SIZE);
	print(arr1);
	print(arr2);
	print(arr3);
	return 0;
}

我在主函式中定義了3個陣列，arr1代表A柱，arr2代表B柱，arr3代表C柱
arr1中，用4代表最大的圓片，1代表最小的圓片，也就是從下到上依次減小，
SIZE定義的是圓片的數量，

2.Hanoi函式

Hanoi函式是用來實作整個漢諾塔流程的，

void Hanoi(int* arr1, int* arr2, int* arr3, int sum)
{
	if (sum > 1)
	{

		if (*arr2 == 0)
		{
			move2(arr1, arr2, arr3, sum);
			clear(arr1);
			Hanoi(arr1, arr2, arr3 + 1, sum - 1);
		}
		else if (*arr1 == 0)
		{
			move1(arr1, arr2, arr3, sum);
			clear(arr2);
			Hanoi(arr1, arr2, arr3 + 1, sum - 1);
		}
	}
	else
	{
		if (*arr1 != 0)
		{
			*arr3 = *arr1;
			clear(arr1);
		}
		else if (*arr2 != 0)
		{
			*arr3 = *arr2;
			clear(arr2);
		}
	}
}

限制條件是可移動的圓片數量，在Hanoi函式中用sum表示，
這里的if條件設為大于1是因為，當圓片數量只剩一個的時候，可以直接放到arr3中，屬于特殊情況，而數量大于1時，在不斷進行遞回，
判斷為真之后，要判斷哪一個陣列為空，來借助這個陣列進行移動，這也是為什么在主函式中將空陣列初始化為0的原因，就是為了在這里方便判斷，因為傳引數過去傳的是陣列的首元素地址，但是因為整個陣列都初始化為0，因此判斷首元素是否為0就可以知道哪個陣列是空的，

注：每次遞回的函式有兩個地方是變化的：
1.arr3的位置每次加一，因為每一次移動之后，arr3都會放置一個，所以要將其位置每次呼叫時進行更新，
2.sum的值每次減一，因為每次移動之后，可移動圓片的數量都會減少一個，不斷地接近限制條件，

3.move1和move2函式

void move2(int* arr1, int* arr2, int* arr3, int sum)
{
	int i = 0;
	if (*arr1 > *(arr1 + 1))
	{
		for (i = sum - 1; i >= 1; i--)
		{
			*(arr2 + sum - i - 1) = *(arr1 + i);
		}
		*arr3 = *arr1;

	}
	else if (*arr1 < *(arr1 + 1))
	{
		for (i = sum - 1; i >= 1; i--)
		{
			*(arr2 + sum - i - 1) = *(arr1 + i-1);
		}
		*arr3 = *(arr1 + sum - 1);
	}
}

void move1(int* arr1, int* arr2, int* arr3, int sum)
{

	int i = 0;
	if (*arr2 > *(arr2 + 1))
	{
		for (i = sum - 1; i >= 1; i--)
		{
			*(arr1 + sum - i - 1) = *(arr2 + i);
		}
		*arr3 = *arr2;

	}
	else if (*arr2 < *(arr2 + 1))
	{
		for (i = sum - 1; i >= 1; i--)
		{
			*(arr1 + sum - i - 1) = *(arr2 + i-1);
		}
		*arr3 = *(arr2 + sum - 1);
	}
}

move1函式是當arr1陣列為空時，借助arr1移動，
move2函式時當arr2陣列為空時，借助arr2移動，
根據上面總結的規律，每次移動之前判斷圓片的放置情況，從小到大是一種規律，從大到小是另一種規律；在移動之前先進行判斷，

4.clear函式

void clear(int* arr)
{
	int i = 0;
	for (i = 0; i < SIZE; i++)
	{
		*(arr + i) = 0;
	}
}

這部分放在move1和move2函式之后，這個函式的目的是為了將移動之后的空的陣列進行清零，方便下一次進行判斷，

我在總結規律中發現，如果開始移動的時候是借助arr1陣列，那么移動完之后arr2陣列就是空的；如果開始移動的時候是借助arr2陣列，那么移動完之后arr1陣列就是空的，根據這個規律，我在move1函式后面將arr2清零；在move2函式后面將arr1清零，這樣在下次判斷時就會很方便，

5.print函式

void print(int* arr)
{
	int i = 0;
	for (i = 0; i < SIZE; i++)
	{
		printf("%d ", *(arr + i));
	}
	printf("\n");
}

這個函式是為了在最后列印三個陣列來看看是否完成整個問題的求解，

運行結果：

四. 總結

根據這次完成漢諾塔問題的代碼，使我對遞回這部分有了更深刻的認識，遞回在寫的時候一定要注意兩個必要條件，并且能用遞回解決的問題一定是有規律可循的，如果遞回越寫越麻煩，肯定是不對的，寫代碼更多的是思想，先要在腦子里構思，再動手去寫，這次的程式實作讓我有了很大的識訓，