有三根桿(編號A侠草、B辱挥、C)，在A桿自下而上边涕、由大到小按順序放置64個金盤晤碘。
目標(biāo)：把A桿上的金盤全部移到C桿上，并仍保持原有順序疊好功蜓。
操作規(guī)則：每次只能移動一個盤子园爷，并且在移動過程中三根桿上都始終保持大盤在下，小盤在上式撼，操作過程中盤子可以置于A腮介、B、C任一桿上端衰。
1叠洗、物理世界中的解答
2、抽象為數(shù)學(xué)的問題
對于復(fù)雜的問題旅东，我們需要簡化的去想灭抑，比如上面物理模型，我們是先從2個盤開始的思考的抵代，如果一開始就從64個盤開始思考腾节，太過復(fù)雜，我們可能在思考的過程中出錯荤牍。
就是說 n 個盤的問題案腺，我們就需要把它想成 n-1 個盤的問題，最終將其想成 2 個盤康吵，1 個盤的問題劈榨。
所以這個移動的問題，可以歸納為：
(1)以C盤為中介晦嵌，從A桿將1至n-1號盤移至B桿同辣；
(2)將A桿中剩下的第n號盤移至C桿；
(3)以A桿為中介惭载；從B桿將1至n-1號盤移至C桿旱函。
這樣問題就解決了，但是實(shí)際操作中描滔，第一步和第三步 會成為新的移動問題棒妨，但是我們觀察，會發(fā)現(xiàn)第一步和第三步 的移動問題含长，是最開始移動問題的簡化版本 （從移動 n 個盤 到移動 n-1 個盤子）券腔，但是解決方式是一樣的伏穆。同樣的 n-1 個盤子的問題同樣可以簡化 為 移動 n-2 個盤子的問題，這樣一直簡化下去颅眶，最后就是移動 2 個盤蜈出，1 個盤的問題，而移動 1 個 盤的問題是可以解決的涛酗，這樣反推回去铡原，就可以解決 移動 n 個盤子的問題。
就是說商叹，我們知道怎么移動 1 個盤子燕刻，就可以知道怎么移動 2 個盤子的問題，然后 3個剖笙、4個 .... 直到 n 個
這種由繁化簡卵洗，用簡單的問題和已知的操作運(yùn)算來解決復(fù)雜問題的方法，就是遞歸法
我們利用數(shù)學(xué)函數(shù)來解決這個問題弥咪，比如我們用 H(n) 來表示移動 n 個圓盤需要的步數(shù)过蹂，則：
H(1)=1;
H(n)=2*H(n-1)+1;（n>1）
第二個等式，是從上面的歸納來的，(1)和(3) 需要移動 H(n-1) 步，即新的移動問題切平，(2) 需要移動 1 步
來推導(dǎo)一下
H(n) = 2*(2*H(n-2)+1)+1
H(n) = 22*H(n-2) + 2 + 1
...
H(n) = 2^(n-1)*H(n-(n-1)) + 2^(n-2) + ... + 2^1 + 1
H(n) = 2^(n-1)*H(1) + 2^(n-2) + ... + 2^1 + 1
H(n) = 2^(n-1) + 2^(n-2) + ... + 2^1 + 1
兩邊同時乘以2
2*H(n) = 2^(n) +2^(n-1) + 2^(n-2) + ... + 2^2 + 2^1
2*H(n) - H(n) = 2^(n) - 1
H(n) = 2^(n) - 1 ;(n>0)
3、編碼模擬移動過程
num脆诉，表示需要移動的盤子個數(shù)；使用遞歸調(diào)用來模擬移動贷币；遞歸到 n = 1 時停止
private List<String> arrayⅠ;
private List<String> arrayⅡ;
private List<String> arrayⅢ;
//移動的步數(shù)
private double moveAmount = 0;
private void startHanoi(int num) {
moveAmount = 0;
arrayⅠ = new ArrayList<>();
arrayⅡ = new ArrayList<>();
arrayⅢ = new ArrayList<>();
for (int i = 1; i <= num; i++) {
arrayⅠ.add(i + "");
}
Log.i("move", "arrayⅠ-" + toStringByArray(arrayⅠ));
hanoi(num, 'Ⅰ', 'Ⅱ', 'Ⅲ');
}
/**
* @param n 盤子的數(shù)目
* @param origin 源座
* @param assist 輔助座
* @param destination 目的座
*/
private void hanoi(int n, char origin, char assist, char destination) {
if (n == 1) {
move(origin, destination);
} else {
hanoi(n - 1, origin, destination, assist);
move(origin, destination);
hanoi(n - 1, assist, origin, destination);
}
}
private void move(char origin, char destination) {
moveAmount++;
Log.i("move", origin + "--->" + destination);
//移動的盤子編號
String moveNum = null;
switch (origin) {
case 'Ⅰ':
moveNum = arrayⅠ.get(0);
arrayⅠ.remove(0);
break;
case 'Ⅱ':
moveNum = arrayⅡ.get(0);
arrayⅡ.remove(0);
break;
case 'Ⅲ':
moveNum = arrayⅢ.get(0);
arrayⅢ.remove(0);
break;
default:
break;
}
switch (destination) {
case 'Ⅰ':
arrayⅠ.add(0, moveNum);
break;
case 'Ⅱ':
arrayⅡ.add(0, moveNum);
break;
case 'Ⅲ':
arrayⅢ.add(0, moveNum);
break;
default:
break;
}
Log.i("move", "arrayⅠ-" + toStringByArray(arrayⅠ));
Log.i("move", "arrayⅡ-" + toStringByArray(arrayⅡ));
Log.i("move", "arrayⅢ-" + toStringByArray(arrayⅢ));
Log.i("move", "移動" + moveAmount + "步");
Log.i("move", "---------------------");
}
private String toStringByArray(@NonNull List<String> array) {
StringBuilder sb = new StringBuilder();
for (String s : array) {
sb.append(s);
}
return sb.toString();
}
- 盤數(shù)為3時的移動過程
開始：柱Ⅰ上是123击胜，三個盤，數(shù)字越大表示盤越大役纹，左到右相當(dāng)于上到下
