TIFR CSE 2021 | Part B | Question: 6

Question

Consider the following pseudocode:

procedure HowManyDash(n)
 if n=0 then
  print '-'
 else if n=1 then
  print '-'
 else
  HowManyDash(n-1)
  HowManyDash(n-2)
 end if
end procedure

How many ‘-’ does HowManyDash$(10)$ print?

• A. $9$
• B. $10$
• C. $55$
• D. $89$
• E. $1024$

Answer 1

Answer $(D)$

Array index starts from $0$ and $A[i]$ stores the value of the function for index $i$ – 

1

1

2

3

5

8

13

21

34

55

89

$A[0] = A[1] = 1$

for rest of the table use, $A[i] = A[i-1] + A[i-2]$

Answer $= 89$

Answer 2

\[
    T(n)=
\begin{cases}
    1& \text{if } n= 0\\1& \text{if } n= 1\\
    T(n-1)+T(n-2),              & n\geq2, \text{otherwise}
\end{cases}
\]

$T(2)=T(1)+T(0)=1+1=2$

$T(3)=T(2)+T(1)=2+1=3$

$T(4)=T(3)+T(2)=3+2=5$

$T(5)=T(4)+T(3)=5+3=8$

$T(6)=T(5)+T(4)=8+5=13$

$T(7)=T(6)+T(5)=13+8=21$

$T(8)=T(7)+T(6)=21+13=34$

$T(9)=T(8)+T(7)=34+21=55$

$T(10)=T(9)+T(8)=55+34=89$

Option $(D)$ is correct.