Question 5475 – NIELIT Junior Teachnical Assistant_2016_march
November 15, 2023
UGC NET CS 2018-DEC Paper-2
November 15, 2023
Question 5475 – NIELIT Junior Teachnical Assistant_2016_march
November 15, 2023
UGC NET CS 2018-DEC Paper-2
November 15, 2023

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
= 22T(n – 2) + 3

2k T(n – k) + (2k – 1)
= 2n-1T(1) + (2n-1 – 1)
= 2n-1 + 2n-1 – 1
= 2n – 1
≅ O(2n)

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);
}
}

A
Theory Explanation is given below.
0 0 votes
Article Rating
Subscribe
Notify of
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x
error: Alert: Content selection is disabled!!