Question 5475 – NIELIT Junior Teachnical Assistant_2016_march
November 15, 2023Question 4846 – UGC NET CS 2018-DEC Paper-2
November 15, 2023Question 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)
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);
}
}
Theory Explanation is given below.
Subscribe
Login
0 Comments