1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889 |
- #!/usr/bin/ruby
- # Daniel "Trizen" Șuteu
- # Date: 10 February 2018
- # https://github.com/trizen
- # Encode a given fraction into a string of L's and R's,
- # indicating the turning points in the Stern-Brocot tree.
- # The decoding function takes a string of L's and R's and
- # constructs the fraction by navigating the Stern-Brocot tree.
- # See also:
- # https://www.youtube.com/watch?v=qPeD87HJ0UA
- # https://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree
- func stern_brocot_encode (Number r) {
- var (m, n) = r.abs.nude
- var e = ''
- while (m != n) {
- if (m < n) {
- e += 'L'
- n -= m
- }
- else {
- e += 'R'
- m -= n
- }
- }
- return e
- }
- func stern_brocot_decode (String e) {
- var (a, b, c, d) = (1, 0, 0, 1)
- e.each { |t|
- if (t == 'L') {
- a += b
- c += d
- }
- else {
- b += a
- d += c
- }
- }
- return [[a,b],[c,d]]
- }
- func matrix2rat (Array A) {
- (A[0][0] + A[0][1]) / (A[1][0] + A[1][1])
- }
- say stern_brocot_decode(stern_brocot_encode(5/7)) # [[3, 2], [4, 3]]
- say stern_brocot_decode(stern_brocot_encode(43/97)) # [[4, 39], [9, 88]]
- say stern_brocot_decode(stern_brocot_encode(97/43)) # [[88, 9], [39, 4]]
- say ''
- say stern_brocot_encode(3/11) # LLLRL
- say stern_brocot_encode(19/8) # RRLLRL
- say ''
- say stern_brocot_decode('LLLRL') # [[2, 1], [7, 4]]
- say stern_brocot_decode('RRLLRL') # [[12, 7], [5, 3]]
- say ''
- say stern_brocot_decode('LRLRLRLRLRLRLRLRLRLRLRLRLRLRLR') # [[514229, 832040], [832040, 1346269]]
- say stern_brocot_decode('RLRLRLRLRLRLRLRLRLRLRLRLRLRLRL') # [[1346269, 832040], [832040, 514229]]
- say ''
- say stern_brocot_decode('RLLRR') # [[3, 7], [2, 5]]
- say stern_brocot_decode('RLLRRLL') # [[17, 7], [12, 5]]
- say stern_brocot_decode('RLLRRLLRR') # [[17, 41], [12, 29]]
- say stern_brocot_decode('RLLRRLLRRLL') # [[99, 41], [70, 29]]
- say stern_brocot_decode('RLLRRLLRRLLRR') # [[99, 239], [70, 169]]
- say stern_brocot_decode('RLLRRLLRRLLRRLL') # [[577, 239], [408, 169]]
- say stern_brocot_decode('RLLRRLLRRLLRRLLRR') # [[577, 1393], [408, 985]]
- say ''
- say matrix2rat(stern_brocot_decode('RLLRRLLRRLLRRLLRRLL')) # 1.414213...
|