◆交大密西根学院◆一 1817 UM-SITU Joint Institute University of Michigan Shanghai Jiao Tong University Vg101 Introduction to Computer and Programming Looking Forward in MATLAB
Vg101 Introduction to Computer and Introduction to Computer and Programming Programming Looking Forward in MATLAB
Tower of Hanoi Initial State A B Goal MoveTower A B Rules Can only move one disk at a time Not allowed to move a larger disk on top of a smaller one
Tower of Hanoi Tower of Hanoi A B C A B C Rules – Can only move one disk at a time – Not allowed to move a larger disk on top of a smaller one Initial State Goal MoveTower
Thinking Recursively MoveTower A B MoveTower MoveSingleDisk A B
Thinking Recursively Thinking Recursively A B C A B C MoveTower MoveSingleDisk MoveTower
◆交大密西根学院 1817 UM-SJTU Joint Institute University of Michigan Shanghai Jiao Tong University Thinking Recursively (cont.) A B This way,we have decomposed the problem of n disks into three simpler subproblems: 1. Move the top N-I disks (a sub-tower)from A to C 2.Move a single remaining disk from A to B 3.Move the N-I disks (a sub-tower)from C to B
Thinking Recursively (cont.) Thinking Recursively (cont.) • This way, we have decomposed the problem of n disks into three simpler subproblems: 1. Move the top N-1 disks (a sub-tower) from A to C 2. Move a single remaining disk from A to B 3. Move the N-1 disks (a sub-tower) from C to B A B C
◆交大密西根学院◆- 1817 UM-SJTU Joint Institute University of Michigan Shanghai Jiao Tong University Analyze the Recursion Condition Simple Cases: MoveSingleDisk(start spire,finish spire) Recursive Decomposition -Simpler subproblems:Tower with N-1 disks Same Form: MoveTower number of disks,start spire,finish spire,temporary spire)
Analyze the Recursion Condition Analyze the Recursion Condition • Simple Cases: – MoveSingleDisk(start spire, finish spire) • Recursive Decomposition – Simpler subproblems: Tower with N-1 disks – Same Form: • MoveTower ( number of disks, start spire, finish spire, temporary spire)