The Question:

Think of binary numbers: sequences of 0's and 1's. How many n-digit binary numbers are there that don't have two adjacent 1 bits? For example, for three-digit numbers, five of the possible eight combinations meet the criteria: 000, 001, 010,

Having worked out the pattern, there's a second part to the question: can you prove why that relationship exists?

The answer is in the replied comments, it is a fibonacci series:

f(1) = 2 => 0,1

f(2) = 3 => 00, 01, 10

f(n) = f(n-1) + f(n-2)

Now I will try to explain why it is like this using my own thoughts:

f(3) can be thought of 2 groups, one is begin with 0, and the other is begin with 1

begin with 0 group: 0 + xx, => f(2)

begin with 1 group: since it begins with 1, it must be followed by 0, so it becomes 10 + x , =>f(1)

so f(3) = f(2) + f(1)

same thing with f(n)

begins with 0: 0 + xxx...x ( n-1 digit) => f(n-1)

begins with 1: 10 + xxx..x ( n-2 digit) => f(n-2)

so f(n) = f(n-1) + f(n-2)

Now I will give the solution in Ruby:

def non_adjacent_one_array(n)

if(n == 1)

["0", "1"]

elsif (n== 2)

["00", "01", "10"]

else

array1 = non_adjacent_one_array(n-1).collect { |i| "0"+i}

array2 = non_adjacent_one_array(n-2).collect { |i| "10"+i}

array1+array2

end

end

s=non_adjacent_one_array(5)

puts "n=5, number is #{s.length}\n"

puts s

puts "\n"

1.upto(10) do |i|

s = non_adjacent_one_array(i)

puts "n=#{i} number=#{s.length}\n"

end

And the results are:

n=5, number is 13

00000

00001

00010

00100

00101

01000

01001

01010

10000

10001

10010

10100

10101

n=1 number=2

n=2 number=3

n=3 number=5

n=4 number=8

n=5 number=13

n=6 number=21

n=7 number=34

n=8 number=55

n=9 number=89

n=10 number=144

## No comments:

## Post a Comment