clarification to all
n=1
0,1 no of sequence =2
n=2
00,01,10 no of sequence =3
n=3
000,100,010,001,101 no of sequence =5
n=4
,1000,0100,0010,0001,1010,0101,1001 no of sequence
=8
n=5
@Rohit Saraf
i understood the question.
Superb solution by u.
On Thu, Jun 10, 2010 at 8:59 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote:
write an efficient algo to compute no. of sequences of n binary digits
that do not contain 2 1's in a row. eg 111 is invalid whereas
1001001 is
A more theoretical answer to the question can be the following:
Let's try to construct a tree for all such possible sequences.
Level 0 = 0 or 1
Level 1 = 01 0
Level 2 =0 1 0 01
Level 3 = 0 1 0 0 1 0 10
Oh! Forgot to mention that the count of the leaves of the tree, gives the
number of possible sequences (as required to be determined by the question)
On Fri, Jun 11, 2010 at 10:02 PM, Mayur mayurhem...@gmail.com wrote:
A more theoretical answer to the question can be the following:
Let's try
@Rohit:
Junta is looking forward for explanation about how one resorted to
Fibonacci for such solution ? Or was it some 'gyaan' like sun rise in east
direction.
Would be real glad if we can know methods to find such fits.
On Wed, Jun 9, 2010 at 9:16 PM, Rohit Saraf
@rohit: fibonacci sequence may be the answer to the prob, but I am curious
why? I haven't come across any such fib sequence property...
On Wed, Jun 9, 2010 at 9:16 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote:
@junta : are fibonacci sequence is the answer of the prob, it is not used
:D
write an efficient algo to compute no. of sequences of n binary digits
that do not contain 2 1's in a row. eg 111 is invalid whereas
1001001 is valid.
HERE the number of sequences comes to be a fibonacci number , precisely
fib(n+2).
So this prob is equivalent to finding fibonacci numbers
hmmm ... Atleast I was of the opinion that such nos. were required and hence
was thinking fib is not the thing. Thanks for clarifying.
On Wed, Jun 9, 2010 at 8:02 AM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote:
Fib comes because she wants the number of such sequences
--
Whats the logic behind using Fibonacci in determining the number of such
sequences?
-Sundeep.
On Wed, Jun 9, 2010 at 8:02 AM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote:
Fib comes because she wants the number of such sequences
--
--
Rohit
First 20 fibo no as follows with binary form
0 = 0
1 = 1
1 = 1
2 = 10
3 = 11
5 = 101
8 = 1000
13 = 1101
21 = 10101
34 = 100010
55 = 110111
89 = 1011001
144 = 1001
233 = 11101001
377 = 10001
610 = 1001100010
987 = 011011
1597 = 1100001
2584 = 10111000
4181 =
@debajyoti: read the prob before posting
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
On Wed, Jun 9, 2010 at 2:37 PM, Debajyoti Sarma
@junta : are fibonacci sequence is the answer of the prob, it is not used :D
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
On Wed, Jun 9, 2010 at 9:13 PM, Rohit
@Divya: That was the question i previously asked. If n=3 000,001,010,100,101
are valid. So the solution for this is fib(n+2).
If n=4 no. of sequences will be fib(6) i.e 8
On Tue, Jun 8, 2010 at 9:31 AM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote:
getting fibonacci nos is trivial using matrix
Yeah, I didn't get the question either. Do you want to generate these
numbers or do you want to be able to tell if
the number input is valid or not? And how does Fibo. fit in the
picture either way?
On Jun 7, 8:13 pm, Dave dave_and_da...@juno.com wrote:
Hmmm. The first few Fibonacci numbers
Fib comes because she wants the number of such sequences
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received this message because you are
Hmmm. The first few Fibonacci numbers are 1, 1, 2, 3, 5, 8, 13, 21,
34, 55, ...
Of these, 3, 13, and 55 have binary representations with two 1-bits in
a row.
And 9, 10, 17, 18, etc are not included. So what was your question?
Dave
On Jun 7, 9:28 pm, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:
getting fibonacci nos is trivial using matrix multiplication in almost
constant time.
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received this message
17 matches
Mail list logo
