UVa 10450

From Algorithmist
Jump to navigation Jump to search

Description:[edit]

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


Data type:[edit]

need a array which double. a[51].
you can use long long to print your output.

Explanation:[edit]

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)?:[edit]

  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


To calculate Fibonacci almost everyone write a function which is started by the number is either 0 and 1. So if the function is 'Fibo' than Fibo(0) = 0 and Fibo(1) = 1. But in this problem you need to count Fibo(0) = 1 and Fibo(1) = 2. That's it.....

Fibonacci sequence is found:[edit]

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 Fibonacci

Implementations[edit]

Example:[edit]

2

50

51

Output[edit]

Scenario #1:

32951280099


Scenario #2:

53316291173