UVa 10450

From Algorithmist
Revision as of 16:42, 17 December 2009 by 119.30.36.52 (Talk) (Output)

Jump to: navigation, search

Description:

From the problem description, we must find the number of all binary-strings of length n that don't have consecutive ones.


Data type:

 need a array which double. a[51].


Explanation:

f(1) =number of strings that start with '0'.+ number of strings that start with '1' = f0(1)+f1(1)= 2 that is ’1’ &’0’ . Similarly f(2) = 3 , because ‘00’,’01’,’10

How can calculate f(3)?:

  1. If the string starts with '1', clearly the next digit has to be '0', so, the strings are fixed to "100 0r 101". So f1(3) = 2 which is unchanged with f(1). That means it is the same as calculating f(3-2).
  2. f0(n) starts with '0', the next digit can be either '0' or '1' ... The strings are only fixed to pattern "000 or 001 or 010..." and the rest should be chosen in such a way so that no consecutive ones are found. It's the same as recursively calculating f(3-1) = f(2) = 3.

So f(3) = f0(3)+f1(3) = f(3-2)+f(3-1) = f(1)+f(2) = 2+3 = 5


Fibonacci sequence is found:

Let's consider f1(n)

  1. If the string starts with '1', clearly the next digit has to be '0', so, the strings are fixed to "10????...". Starting from s[2] until s[n-1], the values are chosen so there is no consecutive ones. That means it is the same as calculating f(n-2).
  2. f0(n) starts with '0', the next digit can be either '0' or '1' ... The strings are only fixed to pattern "0????..." and the rest should be chosen in such a way so that no consecutive ones are found. It's the same as recursively calculating f(n-1).
  3. We can see that f(n) = f(n-2) + f(n-1) ... which is Fibonacc


Example:

2

50

51

Output

Scenario #1:

32951280099


Scenario #2:

53316291173