Solution to Code Kata Fifteen

5 11 2007

Just felt like doing some programming exercise. My bookmarks led me to the code kata 15. First, the problem:

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, 011, 100, 101, 110, 111. What is the number for sequences of length 4, 5, 10, n?

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

Now, the solution.

Let’s call the function that calculate the number of n-digit binary numbers without two adjacent 1 bits a(n).

Now let’s define two helper functions. a0(n) returns number of those binary numbers that end with zero, and a1(n) returns number of those ending with one. Thus, it’s obvious that:

a(n) = a0(n) + a1(n)

Now, suppose we already have a set of (n-1)-bit numbers generated and now, based on that, we want to generate a new set of n-bit numbers. We’ll do that by adding a single bit to the end of each (n-1)-bit number. Because we care only about adjacent 1s, we can add 0s to the end of every (n-1)-bit number. Thus:

a0(n) = a(n-1)

On the other hand we can’t add 1s to each (n-1)-bit number. We can only add 1 to numbers which had 0 at the end. Thus:

a1(n) = a0(n-1)

By simple substitution we can rewrite the last equation into the following one:

a1(n) = a(n-2)

Get back to the definition of a0(n) and a1(n) and make the final substitution:

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

Doesn’t it look familiar? Now you only have to say that a(1) = 2 and a(2) = 3 and you’re done.

Advertisements

Actions

Information

One response

14 03 2011
Vishal

That’s one interesting fix. Thanks for sharing. :)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: