I\'m not really sure what to do here-looking for some help Suppose we have a 4 p

Question

I'm not really sure what to do here-looking for some help

Suppose we have a 4 peg Towers of Hanoi problem. We have a functionf(n) that allows us to formulate the following recursivealgorithm:

void Hanoi4(peg A, peg B, peg C, peg D, int n)
{ if (n<3) {
       Hanoi3(A,B,C,n);
       return;
    }
    Hanoi4(A,D,B,C,n-f(n));
    Hanoi3(A,B,C, f(n));
    Hanoi4(D,B,A,C,n-f(n));

a) Show that for every n>2 we have 0<f(n)<n then this is acorrect algorithm.
b) For 2<n<=20, find values for f(n) that result in theminimum number of moves by Hanoi4.


Hanoi3 was defined earlier as:

void Hanoi3 (peg A, peg B, peg C, int n)
{ if (n==0)
    return;
    Hanoi3(A,C,B,n-1);
    move a disk from A to B;
    Hanoi3(C,B,A,n-1);
}

Appreciate any help on this one

Explanation / Answer

a)

If we have n < 3 discs, we use Hanoi3, so we can rely on thecorrectness of Hanoi3. For a larger n we will perform the reasoningof the inductive step.

Let N denote the top n f (n) discs and F denote thebottom f (n) discs.

We start with configuration A(NF), B(), C(), D(), meaning, N andF on peg A, nothing

on other pegs.

Hanoi4(A,D,B,C,n-f(n)) changes the configuration to A(F), B(),C(), D(N),

Hanoi3(A,B,C,f(n)) changes the configuration to A(), B(F), C(),D(N).

Note that pegs B and C were empty, so Hanoi3 can operate withoutobstruction.

Hanoi4(D,B,A,C,n-f(n)) changes the configuration to A(), B(NF),C(), D().

Note that discs of F that were initially on B are larger thanthe discs of N, so they do not

obstruct the movement of N when we executeHanoi4(D,B,A,C,n-f(n)).This is desired configuration.

b)

We fill a table that gives the number of moves that result fromdifferent choices

of f , the best choices will be possible values forf (n)

n                              3    4     5    6      7     8      9    10     11    12

2T4(n - 1) + T3(1)      7    11  19  27    35   51    67    83

2T4(n - 2) + T3(2)      5     9   13  21    29   37    53    69

2T4(n - 3) +T3(3)   NA   9   13   17    25   33    41    57    73     89

2T4(n - 4) +T3(4)   NA   NA 17   21   25    33    41  49      65    81

2T4(n - 5) + T3(5)   NA   NA NA 33    37   41   49   57     65     81

best f (n)                 2      2,3 2,3   3   3,4   3,4  3,4   4      4,5    4,5

Such calculations give the best values for f(n):

n                           13      14 15   16  17     18    19  20      21

f (n)                      4,5      4,5   5  5,6 5,6    5,6   5,6 5,6      6

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.