search
Log In
17 votes
1.4k views

Let $x_n$ denote the number of binary strings of length $n$ that contain no consecutive 0s.

The value of $x_5$ is 

  1. $5$
  2. $7$
  3. $8$
  4. $16$
in Algorithms
edited by
1.4k views
0

4 Answers

16 votes
Here X1 =0,1(2)

X2=01,10,11(total 3)

X3=010,011,101,110,111(total 5)

Here X3=X2+x1

X4=3+5=8

X5=5+8=13

No option matching here.
2 votes
x1=2

x2=3

x3=5

x4=8.................... so on

it seems fibbonacci form so x5=5+8=13

 so ans will be 13
1 vote
Though everyone has already given the correct answer but let me try an easier explanation.

You can do it by hit and trial method.

The smallest string you can think of in the first attempt is

Let's say x1, then it should contain either 0 or 1.

So, for x1 Answer = 2

for x2, it may contain, 11, 10 or 01 ----------> = 3

Similarly, for x3 it may contain, 111, 110, 101, 011, 010 ---------------> = 5

Now, you can see that it is forming a series like 2, 3, 5, ....and so on.

Recall, this popular series. It's nothing but the Fibonacci series.

So, here's your answer for.

since, f(n) = f(n-1) + f(n-2), (By fibonacci Series)

So, f(5) = f(4) + f(3), ...............(1)

f(4) = f(3) + f(2) = 5 + 3...........(2)

putting this value of equation 2 in equation 1.

f(5) = 8 + 5

So, answer = 13.
0 votes
x1 = 0, 1  [Total = 1 (since 0 is not considered)]

x2 = 10,11 [Total = 2]

x3 = 100,101,110,111 [Total = 3]

x4 = 1000,1001,1010,1011,1100,1101,1110,1111 [Total = 5]

Applying for x4 we get that [ Xn= X(n-1)+X(n-2) ] satisfies it -

x4 = x3+x2

     = 3+2 = 5

so, for x5

x5 = x4+x3 = 5+3 = 8

so option C is the correct answer
1 flag:
✌ Low quality (Chirag Shilwant “Wrong explanation”)
Answer:

Related questions

30 votes
6 answers
1
2.8k views
Let $x_n$ denote the number of binary strings of length $n$ that contain no consecutive 0s. Which of the following recurrences does $x_n$ satisfy? $x_n = 2x_{n-1}$ $x_n = x_{\lfloor n/2 \rfloor} + 1$ $x_n = x_{\lfloor n/2 \rfloor} + n$ $x_n = x_{n-1} + x_{n-2}$
asked Sep 12, 2014 in Algorithms Kathleen 2.8k views
17 votes
3 answers
2
2.4k views
Consider the following C program that attempts to locate an element $x$ in an array $Y[ \ ]$ using binary search. The program is erroneous. f (int Y[10] , int x) { int u, j, k; i= 0; j = 9; do { k = (i+ j) / 2; if( Y[k] < x) i = k;else j = k; } while (Y[k] != x) && (i < j)) ; if( ... $(Y[k] < x) i = k$; else $j = k$; Change line 7 to: } while $((Y[k] == x) \&\& (i < j))$ ;
asked Apr 23, 2016 in Algorithms jothee 2.4k views
23 votes
6 answers
3
2.5k views
Consider the following C functions: int f1 (int n) { if(n == 0 || n == 1) return n; else return (2 * f1(n-1) + 3 * f1(n-2)); } int f2(int n) { int i; int X[N], Y[N], Z[N]; X[0] = Y[0] = Z[0] = 0; X[1] = 1; Y[1] = 2; Z[1] = 3; for(i = 2; i <= n; i++){ ... X[i]; Z[i] = 3 * X[i]; } return X[n]; } $f1(8)$ and $f2(8)$ return the values $1661$ and $1640$ $59$ and $59$ $1640$ and $1640$ $1640$ and $1661$
asked Apr 23, 2016 in Algorithms jothee 2.5k views
24 votes
2 answers
4
3.6k views
The subset-sum problem is defined as follows. Given a set of $n$ positive integers, $S = \{ a_1, a_2, a_3, \dots , a_n \}$, and positive integer $W$, is there a subset of $S$ whose elements sum to $W$? A dynamic program for solving this problem uses a $\text{2-dimensional}$ Boolean array, $X$ ... , implies that there is a subset whose elements sum to $W$? $X[1, W]$ $X[n, 0]$ $X[n, W]$ $X[n-1, n]$
asked Apr 23, 2016 in Algorithms jothee 3.6k views
...