Modify the Towers of Hanoi program to help identify its algorithm efficiency. Declare a static variable named moveCount that keeps track of the total number of moves. Remove (or comment out) all the print statements that document a move, and replace them with statements that increment the moveCount variable. In the main method, prompt the user for the number of disks and assign the user input to a local variable named disks. Next, call the move method, but pass disks as an argument instead of the original program’s hardcoded 4 argument. After main calls the move method, add a statement that prints the value of disks and the final value of moveCount. Compare those output values with the values in Table 11.1 and identify the Big O growth rate for the Towers of Hanoi problem.

Table 11.1

Transcribed Image Text:

n 4 16 64 256 1,024 0(1) 1 1 1 1 1 O(log n) 2 4 6 8 10 O(n) 4 16 64 256 1,024 O(n log n) 8 64 384 2,048 10,240 0(n) 16 256 4,096 65,536 1.1 E6 0(n) 64 4,096 2.6 E5 1.7 E7 1.1 E9 0(2") 16 65,536 1.8 E19 1.2 E77 #NUM! 0(n") 256 1.8 E19 3.9 E115 #NUM! #NUM!