how come class assignment question is similar to fobonaccai??
could you please explain the logic behind the question and using fibonaccai using it
Class assignment
Hello @Vibhuti0206,
It can be solved in a manner similar to computing Fibonacci sequence.
For n=1 i.e. string of length 1
{a,b}=2
(First base case)
For n=2 i.e. string of length 2
{aa,ab,ba}=3 //b cannot be together
(second base case)
For n=3
{aaa,aba,baa,aab,bab}=5
fib[3]=fib[2]+fib[1]=3+2=5
For n=4
{aaaa,abaa,baaa,aaba,baba,aaab,abab,baab}=8
fib[4]=fib[3]+fiib[2]=5+3=8
so on…
Concluding: fib[n]=fib[n-1]+fib[n-1]
Hope, this would help.
Give a like if you are satisfied.
is there some other solution using recursion?
Hello @tusharnitharwal,
Yes, you can solve this question recursively also.
HINT:
you can refer to this video Count Binary Strings Hint from your course as it is a similar question but still different.