4. (14 points) Consider the following problem. Suppose you have n blocks of distinct sizes, stacked in a tower in order of size so that the largest block is at the bottom, followed by the second-largest immediately above it, and so on up to the smallest block at the top. The tower is on table A and there are two other tables, B and C, which are initially empty. The goal is to move the tower to table C while obeying the following rules: 1. You can only move one block at a time. 2. For each move, you must take the top block from a tower on one of the three tables and move it to the top of a tower on a different table, or place it on an empty table. 3. You cannot place a block on top of a smaller block. B A do . A B Figure 1: Two valid moves A B B A B (a) Violates rule 1 (b) Violates rule 3 Figure 2: Two invalid moves Consider the following simple recursive function move: def move (numBlocks, from, extra, to): 1: if numBlocks > 0 then 2: move (numBlocks-1, from, to, extra) //move numBlocks-1 blocks from table from to table extra Move one block from table from to table to //an actual, physical move move (numBlocks-1, extra, from, to) //move numBlocks-1 blocks from table extra to table to 5: end if 3: 4: Show by establishing partial correctness and termination that if table from contains at least numBlocks blocks stacked in decreasing order of size, all of which are smaller than any blocks on tables to and extra, then move moves the top numBlocks blocks from from to the top of to without making any invalid moves. Use this to conclude that calling move(n,A,B,C) correctly solves the above problem. 4. (14 points) Consider the following problem. Suppose you have n blocks of distinct sizes, stacked in a tower in order of size so that the largest block is at the bottom, followed by the second-largest immediately above it, and so on up to the smallest block at the top. The tower is on table A and there are two other tables, B and C, which are initially empty. The goal is to move the tower to table C while obeying the following rules: 1. You can only move one block at a time. 2. For each move, you must take the top block from a tower on one of the three tables and move it to the top of a tower on a different table, or place it on an empty table. 3. You cannot place a block on top of a smaller block. B A do . A B Figure 1: Two valid moves A B B A B (a) Violates rule 1 (b) Violates rule 3 Figure 2: Two invalid moves Consider the following simple recursive function move: def move (numBlocks, from, extra, to): 1: if numBlocks > 0 then 2: move (numBlocks-1, from, to, extra) //move numBlocks-1 blocks from table from to table extra Move one block from table from to table to //an actual, physical move move (numBlocks-1, extra, from, to) //move numBlocks-1 blocks from table extra to table to 5: end if 3: 4: Show by establishing partial correctness and termination that if table from contains at least numBlocks blocks stacked in decreasing order of size, all of which are smaller than any blocks on tables to and extra, then move moves the top numBlocks blocks from from to the top of to without making any invalid moves. Use this to conclude that calling move(n,A,B,C) correctly solves the above
