123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081 |
- #!/usr/bin/ruby
- # Daniel "Trizen" Șuteu
- # Date: 24 April 2019
- # https://github.com/trizen
- # Encode positive integers in binary format, using the Fibonacci numbers.
- # Example:
- # 30 = "10100010" = 1×21 + 0×13 + 1×8 + 0×5 + 0×3 + 0×2 + 1×1 + 0×1
- # See also:
- # https://projecteuler.net/problem=473
- # https://en.wikipedia.org/wiki/Fibonacci_coding
- # https://en.wikipedia.org/wiki/Zeckendorf%27s_theorem
- # https://en.wikipedia.org/wiki/Golden_ratio_base
- func fibonacci_encoding(n) {
- return '0' if (n == 0)
- var phi = (sqrt(1.25) + 0.5)
- var idx = int((log(n) + log(5)/2) / log(phi))
- var (f1, f2) = (fib(idx), fib(idx-1))
- if (f1+f2 <= n) {
- (f1, f2) = (f1+f2, f1)
- }
- var enc = ''
- while (f1 > 0) {
- if (n >= f1) {
- n -= f1
- enc += '1'
- }
- else {
- enc += '0'
- }
- (f1, f2) = (f2, f1-f2)
- }
- return enc
- }
- func fibonacci_decoding(enc) {
- var len = enc.len
- var (f1, f2) = (fib(len), fib(len - 1))
- var dec = 0
- enc.each {|bit|
- dec += f1 if bit
- (f1, f2) = (f2, f1-f2)
- }
- return dec
- }
- say fibonacci_encoding(30) #=> 10100010
- say fibonacci_decoding('10100010') #=> 30
- say fibonacci_decoding(fibonacci_encoding(144)) #=> 144
- say fibonacci_decoding(fibonacci_encoding(144 - 1)) #=> 143
- say fibonacci_decoding(fibonacci_encoding(144 + 1)) #=> 145
- # Verify the encoding/decoding algorithm
- for n in (0..100) {
- if (fibonacci_decoding(fibonacci_encoding(n)) != n) {
- die "Error for #{n}";
- }
- }
- with (81923489126412312421758612841248123) {|n|
- assert_eq(fibonacci_decoding(fibonacci_encoding(n)), n)
- }
|