上海交通大学：《程序设计基础》课程教学讲义（密西根学院）Lecture Notes_20 Looking Ahead

◆交大密西根学院◆一 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)

◆交大密西根学院一 宫8 1817 UM-SJTU Joint Institute University of Michigan Shanghai Jiao Tong University Write the Solution Void MoveTower (int n,char start,char finish,char tmp) { if (n ==1) { MoveSingleDisk(start,finish); else MoveTower(n-1,start,tmp,finish); MoveSingleDisk(start,finish); MoveTower(n-1,tmp,finish,start); 3 Done !!

Write the Solution Write the Solution Void MoveTower (int n, char start, char finish, char tmp) { if (n == 1) { MoveSingleDisk(start, finish); } else { MoveTower(n-1, start, tmp, finish); MoveSingleDisk(start, finish); MoveTower(n-1, tmp, finish, start); } } Done !!!

◆交大密西根学院◆ 宫8 1817 UM-SJTU Joint Institute University of Michigan Shanghai Jiao Tong University Seems Like Magic？ Trust the recursive leap of faith: -All you need to do is: breaking a problem down into smaller subproblems of the same form and then providing solutions for the simple cases Trust the recursive process without going into the details how it works

Seems Like Magic ? Seems Like Magic ? • Trust the recursive leap of faith: – All you need to do is: • breaking a problem down into smaller subproblems of the same form and • then providing solutions for the simple cases – Trust the recursive process without going into the details how it works

Towers of Hanoi Case:n-4 (at the beginning)

Towers of Hanoi Case:n=4 (when finished)

Lets Us Trace the Solution Step 1 Move from Sre to Aux ■工>