The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+13 votes
930 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 (68.9k points)
edited by | 930 views

2 Answers

+23 votes
Best answer

answer a) $332 332 1$

answer b) $2^n-1$

 

Q. a) O/p :

3 3 2 3 3 2 1

b) 

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

     =  2x (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

answered by Boss (8.5k points)
selected by
can you plz explain more clearly ... as i am not getting the meaning of the code line ...??
+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 Boss (8.5k points)

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

 

  

 

 

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?

 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

32,693 questions
39,293 answers
110,107 comments
36,701 users