Four-Tower Towers of Hanoi
For this problem, we extend the Towers of Hanoi to have four towers and ask the question “What are the fewest number of moves to solve the Towers of Hanoi problem for a given n if we allow four towers instead of the usual three?” We keep the rules of trying to move n disks from one specified post to another and do not allow a bigger disk to be put on top of a smaller one. What is new for this problem is to have two spare posts instead of just one.
For example, to move 3 disks from post A to post D, we can move disk 1 from A to B, disk 2 from A to C, disk 3 from A to D, disk 2 from C to D, and disk 1 from B to D, making a total of 5 moves.
Input will be positive integers (n), one per line, none being larger than 1 000. For each value of n, compute the fewest number of moves for the four-tower problem. Stop processing at the end of the file. (There is no end-of-data flag.)
Output the fewest number of moves. Follow this format exactly:
Output for Sample Input
|University of Debrecen; Faculty of Informatics; v. 03/01/2019|