recategorized by
512 views
2 votes
2 votes

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?

  1. $9$
  2. $10$
  3. $55$
  4. $89$
  5. $1024$
recategorized by

2 Answers

1 votes
1 votes

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$

0 votes
0 votes
\[
    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.
Answer:

Related questions