Exercises

3.1. (Towers of Hanoi). Given are three rods and x disks of different sizes. The

disks can be stacked up on the rods, thereby forming “towers.” Let the n disks initially be placed on rod A in the order of decreasing size, as shown in Fig. 3.10 for n = 3. The task is to move the n disks from rod A to rod C

such that they are ordered in the original way. This has to be achieved under the constraints that

Find an algorithm which performs this task. Note that a tower may conveniently be considered as consisting of the single disk at the top and the tower consisting of the remaining disks. Describe the algorithm as a recursive program.

3.2. Write a procedure that generates all 1! permutations of n elements a;,...,

a, in situ, i.e., without the aid of another array. Upon generating the next permutation, a parametric procedure Q is to be called which may, for instance, output the generated permutation.

Q;,...+ 54m as consisting of the m subtasks of generating all permutations of Q1,..+54m-1 followed by a,,, where in the ith subtask the two elements a; and a,, had initially been interchanged.

3.3. Deduce the recursion scheme of Fig. 3.11 which is a superposition of the

four curves W,, W,, W;, W,. The structure is similar to that of the Sierpinski curves (3.21) and (3.22). From the recursion pattern, derive a recursive program that plots these curves.

3.4. Only 12 of the 92 solutions computed by the Eight Queens Program 3.5

3.5. Change the Stable Marriage Program so that it determines the optimal solu-

3.6. Acertain railway company serves 7 stations S,,..., S,. Itintends to improve

3.7. The Ackermann Function 4A is defined for all non-negative integer arguments

m and nas follows: