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