Thanks to the kind participants of Habr for being invited to write posts and receive feedback on them.
Today I would like to highlight the topic of representing numbers using the Fibonacci series and, of course, write a simple REST API using the Mongo DB algorithm using the Ruby language , which would return its representation for a given number N.
Part 1: the Zeckendorff representation
As the Wikipedia article states :
Zeckendorff's theorem states that any natural number can be uniquely represented as the sum of one or several different Fibonacci numbers so that this representation does not contain two adjacent numbers from the Fibonacci sequence.
100 = 89 + 8 + 3.
I think, understanding what Fibonacci numbers are, it will not be difficult to understand what this theorem is about.
Goals to be achieved:
work speed
maximum code simplicity
As a programming language I will use Ruby , why? Because Ruby is
The programmer's best friend.
First, theoretically, you need to find a pattern by which the algorithm will be written.
, (), , , .
:
N = 51
F = 1 , 1 , 2 , 3 , 5 , 8 , 13, 21, 34.
34, (21) , N, , :-).
, : .
- : .
: N , , <= 0.
:
N = 51
F = 1 , 1 , 2 , 3 , 5 , 8 , 13, 21, 34.
ans = [34]
N = 51 - 34 = 17
F = 1 , 1 , 2 , 3 , 5 , 8 , 13.
ans = [34 , 13]
N = 17 - 13 = 4
F = 1 , 1 , 2 , 3.
ans = [34 , 13 , 3]
N = 4 - 3 = 1
F = 1
ans = [34 , 13 , 3, 1]
:
def le_fib(limit, fib)
theoretical = fib[fib.count - 1] + fib[fib.count - 2]
return fib.last if theoretical > limit
fib << theoretical
le_fib(limit, fib)
end
def main(target,result)
temporary = le_fib(target, [1,1])
result << temporary
return result if target - temporary <= 0
main(target - temporary, result)
end
pp main(gets.to_i,[])
le_fib - , , target. , , .
main - c, , .
, , , , , .
20 1000
( )
As you can see, the operating time even on numbers up to 10 ^ 9 is very positive.
And the total amount of code in 17 lines indicates that both tasks were completed successfully.
An article about interest, you always need to have a couple of problems with Fibonache numbers up your sleeve, otherwise what kind of programmer are you :-)