Question 9727 – Data-Structures

The following recursive function in C is a solution to the Towers of Hanoi problem.

 Void move (int n, char A, char B, char C)
 {
     if (…………………………………) {
         move (…………………………………);
         printf(“Move disk %d from pole %c to pole %c\n”, n,A,C);
         move (………………………………….);

Fill in the dotted parts of the solution.

Correct Answer: A

Question 47 Explanation:

move (disk-1, source, aux, dest) //Step-1
move disk from source to dest //Step-2
move (disk-1, aux, dest, source) //Step-3
Recurrence: 2T(n – 1) + 1
T(n) = 2T (n – 1) + 1
= 2[2T(n – 2) + 1] + 1
= 2²T(n – 2) + 3
⁞
2^k T(n – k) + (2^k – 1)
= 2^n-1T(1) + (2^n-1 – 1)
= 2^n-1 + 2^n-1 – 1
= 2ⁿ – 1
≅ O(2ⁿ)

void move (int n, char A, char B, char C) {
if (n>0)
move(n-1, A, C, B);
printf(“Move disk%d from pole%c to pole%c\n”, n,A,C);
move(n-1, B, A, C);
}
}

Theory Explanation is given below.

0 0 votes

Article Rating

0 Comments

Inline Feedbacks

View all comments