一.起源:
漢諾塔(又稱河內塔)問題是源于印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子,在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規定,在小圓盤上不能放大圓盤,在三根柱子之間一次只能移動一個圓盤。
二.抽象為數學問題:
如下圖所示,從左到右有A、B、C三根柱子,其中A柱子上面有從小疊到大的n個圓盤,現要求將A柱子上的圓盤移到C柱子上去,期間只有一個原則:一次只能移到一個盤子且大盤子不能在小盤子上面,求移動的步驟和移動的次數
~~~
解:
(1)n == 1
第1次 1號盤 A---->C sum = 1 次
(2) n == 2
第1次 1號盤 A---->B
第2次 2號盤 A---->C
第3次 1號盤 B---->C sum = 3 次
(3)n == 3
第1次 1號盤 A---->C
第2次 2號盤 A---->B
第3次 1號盤 C---->B
第4次 3號盤 A---->C
第5次 1號盤 B---->A
第6次 2號盤 B---->C
第7次 1號盤 A---->C sum = 7 次
不難發現規律:1個圓盤的次數 2的1次方減1
2個圓盤的次數 2的2次方減1
3個圓盤的次數 2的3次方減1
。 。 。 。 。
n個圓盤的次數 2的n次方減1
故:移動次數為:2^n - 1
~~~
三.調用方法的棧機制:(特點:先進后出)
從主線程開始調用方法(函數)進行不停的壓棧和出棧操作,函數的調用就是將函數壓如棧中,函數的結束就是函數出棧的過程,這樣就保證了方法調用的順序流,即當函數出現多層嵌套時,需要從外到內一層層把函數壓入棧中,最后棧頂的函數先執行結束(最內層的函數先執行結束)后出棧,再倒數第二層的函數執行結束出棧,到最后,第一個進棧的函數調用結束后從棧中彈出回到主線程,并且結束。
四.算法分析(遞歸算法):
我們在利用計算機求漢諾塔問題時,必不可少的一步是對整個實現求解進行算法分析。到目前為止,求解漢諾塔問題最簡單的算法還是同過遞歸來求,至于是什么是遞歸,遞歸實現的機制是什么,我們說的簡單點就是自己是一個方法或者說是函數,但是在自己這個函數里有調用自己這個函數的語句,而這個調用怎么才能調用結束呢?,這里還必須有一個結束點,或者具體的說是在調用到某一次后函數能返回一個確定的值,接著倒數第二個就能返回一個確定的值,一直到第一次調用的這個函數能返回一個確定的值。
實現這個算法可以簡單分為三個步驟:
(1) 把n-1個盤子由A 移到 B;
(2) 把第n個盤子由 A移到 C;
(3) 把n-1個盤子由B 移到 C;
從這里入手,在加上上面數學問題解法的分析,我們不難發現,移到的步數必定為奇數步:
(1)中間的一步是把最大的一個盤子由A移到C上去;
(2)中間一步之上可以看成把A上n-1個盤子通過借助輔助塔(C塔)移到了B上,
(3)中間一步之下可以看成把B上n-1個盤子通過借助輔助塔(A塔)移到了C上;
~~~
package com.imooc;
import java.util.Scanner;
public class TowerOfHanoi {
static int m =0; //標記移動次數
//實現移動的函數
public static void move(int disks,char N,char M)
{
System.out.println("第" + (++m) +" 次移動 : " +" 把 "+ disks+" 號圓盤從 " + N +" ->移到-> " + M);
}
//遞歸實現漢諾塔的函數
public static void hanoi(int n,char A,char B,char C)
{
if(n == 1 ) //圓盤只有一個時,只需將其從A塔移到C塔
TowerOfHanoi.move(1, A, C); //將編b號為1的圓盤從A移到C
else
{
//否則
hanoi(n - 1, A, C, B); //遞歸,把A塔上編號1~n-1的圓盤移到B上,以C為輔助塔
TowerOfHanoi.move(n, A, C); //把A塔上編號為n的圓盤移到C上
hanoi(n - 1, B, A, C) ; //遞歸,把B塔上編號1~n-1的圓盤移到C上,以A為輔助塔
}
}
public static void main(String[] args) {
Scanner imput = new Scanner(System.in);
char A = 'A';
char B = 'B';
char C = 'C';
System.out.println("*************************************");
System.out.println("這是漢諾塔問題(把A塔上編號從小號到大號的圓盤從A塔通過B輔助塔移動到C塔上去");
System.out.println("***************************************");
System.out.print("請輸入圓盤的個數:");
int disks = imput.nextInt();
TowerOfHanoi.hanoi(disks, A, B, C);
System.out.println(">>移動了" + m + "次,把A上的圓盤都移動到了C上");
imput.close();
}
}
**********************************************************************
這是漢諾塔問題(把A塔上編號從小號到大號的圓盤從A塔通過B輔助塔移動到C塔上去
**********************************************************************
請輸入圓盤的個數:4
第1 次移動 : 把 1 號圓盤從 A ->移到-> B
第2 次移動 : 把 2 號圓盤從 A ->移到-> C
第3 次移動 : 把 1 號圓盤從 B ->移到-> C
第4 次移動 : 把 3 號圓盤從 A ->移到-> B
第5 次移動 : 把 1 號圓盤從 C ->移到-> A
第6 次移動 : 把 2 號圓盤從 C ->移到-> B
第7 次移動 : 把 1 號圓盤從 A ->移到-> B
第8 次移動 : 把 4 號圓盤從 A ->移到-> C
第9 次移動 : 把 1 號圓盤從 B ->移到-> C
第10 次移動 : 把 2 號圓盤從 B ->移到-> A
第11 次移動 : 把 1 號圓盤從 C ->移到-> A
第12 次移動 : 把 3 號圓盤從 B ->移到-> C
第13 次移動 : 把 1 號圓盤從 A ->移到-> B
第14 次移動 : 把 2 號圓盤從 A ->移到-> C
第15 次移動 : 把 1 號圓盤從 B ->移到-> C
>>移動了15次,把A上的圓盤都移動到了C上
~~~
- 說明
- 排序
- java實現
- 二分歸并排序
- 快速排序
- js實現
- 冒泡排序 (Bubble Sort)
- 快速排序-js
- ES6-rest參數
- 比較排序
- 堆排序
- 插入排序
- 歸并排序
- 選擇排序
- shellSort
- 排序基礎知識
- 其他
- Rabbit
- chickenProblem
- 漢諾塔
- 取出兩個字符串中開頭相同的部分
- 兩個七進制輸入,輸出七進制
- 二維數組(矩陣)對角線輸出
- 根據概率取值
- 最小編輯距離算法
- 列劃分算法
- 數組去重
- 數組去重1
- 在一天里,鐘表的時針和分針會重合多少次?
- 找第二大問題
- Raft算法
- B-tree
- Leetcode JAVA實現
- leetcode1. 2 Sum
- leetcode2. Add Two Numbers
- leetcode7. Reverse Integer
- leetcode8. String to Integer (atoi)
- leetcode12. Integer to Roman
- leetcode13. Roman to Integer
- leetcode15. 3Sum
- leetcode18. 4Sum
- leetcode20. Valid Parentheses
- leetcode26. Remove Duplicates from Sorted Array
- leetcode27. Remove Element
- leetcode58. Length of Last Word
- leetcode66. Plus One
- leetcode67. Add Binary
- leetcode80. Remove Duplicates from Sorted Array II
- leetcode 88. Merge Sorted Array
- leetcode101. Symmetric Tree
- leetcode104. Maximum Depth of Binary Tree
- leetcode110. Balanced Binary Tree
- leetcode118. Pascal's Triangle
- leetcode119. Pascal's Triangle II
- leetcode121. Best Time to Buy and Sell Stock
- leetcode125. Valid Palindrome
- leetcode136. Single Number
- leetcode144. Binary Tree Preorder Traversal
- leetcode145. Binary Tree Postorder Traversal
- leetcode155. Min Stack
- leetcode169. Majority Element
- leetcode171. Excel Sheet Column Number
- leetcode172. Factorial Trailing Zeroes
- leetcode189. Rotate Array
- leetcode191. Number of 1 Bits
- leetcode202. Happy Number
- leetcode203. Remove Linked List Elements
- leetcode204. Count Primes
- leetcode225. Implement Stack using Queues
- leetcode226. Invert Binary Tree
- leetcode231. Power of Two
- leetcode232. Implement Queue using Stacks
- leetcode234. Palindrome Linked List
- leetcode237. Delete Node in a Linked List
- leetcode242. Valid Anagram
- leetcode258. Add Digits
- leetcode263. Ugly Number
- leetcode283. Move Zeroes
- leetcode292. Nim Game
- leetcode344. Reverse String
- leetcode371. Sum of Two Integers
- leetcode804. Unique Morse Code Words
- Leetcode JS 實現
- Js-leetcode 1. Two Sum
- Js-leetcode 2. Add Two Numbers
- Js-leetcode 10. Regular Expression Matching
- Js-leetcode 14. Longest Common Prefix
- Js-leetcode 17.Letter Combinations of a Phone Number
- Js-leetcode 20. Valid Parentheses
- Js-leetcode 27. Remove Element
- Js-leetcode 30. Substring with Concatenation of All Words
- Js-leetcode 35. Search Insert Position
- Js-leetcode 41. First Missing Positive
- Js-leetcode 48. Rotate Image
- Js-leetcode 53. Maximum Subarray
- Js-leetcode 54. Spiral Matrix
- Js-leetcode 73. Set Matrix Zeroes
- Js-leetcode 75. Sort Colors
- Js-leetcode 85. Maximal Rectangle
- Js-leetcode 89. Gray Code
- Js-leetcode 93.Restore IP Addresses
- Js-leetcode 98. Validate Binary Search Tree
- Js-leetcode 104. Maximum Depth of Binary Tree
- Js-leetcode 118. Pascal's Triangle
- Js-leetcode 121. Best Time to Buy and Sell Stock
- Js-leetcode 136. Single Number
- Js-leetcode 164. Maximum Gap
- Js-leetcode 189. Rotate Array
- Js-leetcode 215. Kth Largest Element in an Array
- Js-leetcode 217. Contains Duplicate
- Js-leetcode 258. Add Digits
- Js-leetcode 263.Ugly Number
- Js-leetcode 283. Move Zeroes
- Js-leetcode 326. Power of Three
- Js-leetcode 434. Number of Segments in a String
- Js-leetcode 459. Repeated Substring Pattern
- Js-leetcode 507. Perfect Number
- Js-leetcode 537. Complex Number Multiplication
- Js-leetcode 541. Reverse String II
- Js-leetcode 551. Student Attendance Record I
- Js-leetcode 557. Reverse Words in a String III
- Js-leetcode 605. Can Place Flowers
- Js-leetcode 606. Construct String from Binary Tree
- Js-leetcode 621. Task Scheduler
- Js-leetcode 622. Design Circular Queue
- Js-leetcode 633. Sum of Square Numbers
- Js-leetcode 657. Robot Return to Origin
- Js-leetcode 682. Baseball Game
- Js-leetcode 686. Repeated String Match
- Js-leetcode 696. Count Binary Substrings
- Js-leetcode 709.To Lower Case.md
- Js-leetcode 771 Jewels and Stones
- Js-leetcode 804.Unique Morse Code Words
- Js-leetcode 867. Transpose Matrix
- Js-leetcode 905. Sort Array By Parity
- Js-leetcode 914. X of a Kind in a Deck of Cards
- Js-leetcode 922. Sort Array By Parity II
- Js-leetcode 1221. Split a String in Balanced Strings
- Js-leetcode 3. Longest substring without repeating characters
- document
- 劉宇波老師--基礎知識
- 算法與數據結構
- 數據機構與算法介紹
- 二叉樹
- 堆
- 鏈表
- 隊列
- 并查集
- 最小生成樹
- 圖論
- 最短路徑
- 總結
- 玩轉數據結構
- 介紹
- 數組
- 棧和隊列
- 玩轉鏈表
- 鏈表與遞歸
- 二分搜索樹
- 集合與映射
- 第8章 優先隊列和堆
- 第9章 線段樹
- 第10章 Trie
- 玩轉算法面試 leetcode題庫分門別類詳細解析
- 第一章 介紹
- 第二章 時間復雜度和空間復雜度
- 第三章
- 深度實戰玩轉算法
- JS數據結構與算法
- 第一章.介紹
- 第二章.字符串
- 第三章.數組
- 第四章
- 第五章.排序
- 第六章.遞歸
- 第七章.棧
- 第八章.隊列
- 第九章.鏈表
- 第十章.矩陣
- 第十一章.二叉樹
- 第十二章.堆
- 極客時間
- 第01課丨數據結構與算法總覽
- 第02課丨訓練準備和復雜度分析
- 第03課丨數組、鏈表、跳表
- 第04課丨棧、隊列、優先隊列、雙端隊列
- 算法基礎
- 哈希表(散列表)
- 異或運算
- leetcode
- KD樹(K-Dimension Tree)
- Rtree
- B站-左神
- 一周刷爆LeetCode,算法大神左神(左程云)耗時100天打造算法與數據結構基礎到高級全家桶教程,直擊BTAJ等一線大廠必問算法面試題真題詳解
- 簡單的排序算法
- 認識Nlog(N)的算法
- 第三節:桶排序及排序算法總結
- 左程云算法課程
- 1 認識復雜度、對數器、二分法與異或運算
- 2 鏈表結構、棧、隊列、遞歸行為、哈希表和有序表
- 10道BAT必問算法面試題
- 超級水王問題
- 78節
- 04鏈表