The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+14 votes
1.3k views

Consider the following C program:

void abc(char*s)
{
    if(s[0]=='\0')return;
    abc(s+1);
    abc(s+1);
    printf("%c",s[0]);
}

main()
{ 
    abc("123");
}
  1. What will be the output of the program?
  2. If $abc(s)$ is called with a null-terminated string $s$ of length $n$ characters (not counting the null ('\0') character), how many characters will be printed by $abc(s)$?
asked in Programming by Veteran (59.5k points)
edited by | 1.3k views

2 Answers

+25 votes
Best answer

Answer is a) $332 \ 332 \ 1$
Answer b) $2^n-1$

Q. a) $O/p$ :

3 3 2 3 3 2 1

b) : $T(n) = 2T(n-1) +1 ; n>0 $

      $=  0 ; n=0$ [Since for length zero string no character will be printed]

After solving it by substitution,

$T(n) = 2T(n-1) +1$

      $= 2(2T(n-2)  + 1 )  +1$

      $= 2^2T(n-2)  +  2 +1$

     $=  2^2(2T(n-3) +1 )  + 2 + 1$

     $= 2^3T(n-3) + 2^2  + 2 + 1$

Finally, it will expand like

    $= 2^nT(n-n) + 2^{n-1} + 2^{n-2} + \ldots + 2^2 + 2 + 1 $

    $= 2^nT(0) + 2^{n-1} + 2^{n-2} + \ldots+ 2^2 + 2 + 1$

    $= \frac{1.(2^n -1)}{(2 - 1)}$

   $= 2^n -1$

answered by Loyal (8.2k points)
edited by
0
can you plz explain more clearly ... as i am not getting the meaning of the code line ...??
0
How did u get the recurrence relation ? I am confused .It should be T(n) = 2* T(n+1) +1. Plz help.
+1
we are decreasing length of input by 1 so that's why n-1 in recurrence relation.
+3 votes
ans for B is: 2^n -1

for length 2 -> 3 characters

for length 3-> 7 characters

for length 4-> 15 characters

hence for n-> 2^n - 1 characters
answered by Loyal (8.2k points)
+4

a) 3323321

b) we can also get the answer of b by solving recurrence relation 

T(n) = 2 * T(n-1) +1 ; n>0 

      =  0 ; n=0 [Since for length zero string no character will be printed]

After solving it by substitution,

T(n) = 2 * T(n-1) +1

      = 2  x  (2  x  T(n-2)  + 1 )  +1

      = 2x T(n-2)  +  2 +1

     =  22 x (2*T(n-3) +1 )  + 2 + 1

     = 2x T(n-3) + 22  + 2 + 1

Finally it will expand like

    = 2x T(n-n) + 2n-1 + 2n-2 + - - - -  - - - + 2+ 2 + 1 

    = 2x T(0) + 2n-1 + 2n-2 + - - - - - - - - - - + 2+ 2 + 1

   = 1x (2-1) / (2 - 1 )

   = 2-1

  

0
But how do we come to this recurrence  relation first....i mean it works for all questions like this....do we have to learn this...please reply?
+3

 Supreet Kaur 1  

lets assume to solve length n input it takes T(n) times

now in ques they have two abc(s+1) and one printf

abc(s+1) reduces the length of input by 1 so now it have length (n-1)

now to solve length (n-1) input it takes T(n-1) times and printf take 1 unit of time

hence reccurence relation is :

T(n)=2.T(n-1)+1

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,713 questions
46,750 answers
140,552 comments
58,380 users