How to resolve the algorithm Greedy algorithm for Egyptian fractions step by step in the Racket programming language
How to resolve the algorithm Greedy algorithm for Egyptian fractions step by step in the Racket programming language
Table of Contents
Problem Statement
An Egyptian fraction is the sum of distinct unit fractions such as:
Each fraction in the expression has a numerator equal to 1 (unity) and a denominator that is a positive integer, and all the denominators are distinct (i.e., no repetitions).
Fibonacci's Greedy algorithm for Egyptian fractions expands the fraction
x y
{\displaystyle {\tfrac {x}{y}}}
to be represented by repeatedly performing the replacement
(simplifying the 2nd term in this replacement as necessary, and where
⌈ x ⌉
{\displaystyle \lceil x\rceil }
is the ceiling function).
For this task, Proper and improper fractions must be able to be expressed.
Proper fractions are of the form
a b
{\displaystyle {\tfrac {a}{b}}}
where
a
{\displaystyle a}
and
b
{\displaystyle b}
are positive integers, such that
a < b
{\displaystyle a<b}
, and improper fractions are of the form
a b
{\displaystyle {\tfrac {a}{b}}}
where
a
{\displaystyle a}
and
b
{\displaystyle b}
are positive integers, such that a ≥ b.
(See the REXX programming example to view one method of expressing the whole number part of an improper fraction.) For improper fractions, the integer part of any improper fraction should be first isolated and shown preceding the Egyptian unit fractions, and be surrounded by square brackets [n].
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Greedy algorithm for Egyptian fractions step by step in the Racket programming language
Source code in the racket programming language
#lang racket
(define (real->egyptian-list R)
(define (inr r rv)
(match* ((exact-floor r) (numerator r) (denominator r))
[(0 0 1) (reverse rv)]
[(0 1 d) (reverse (cons (/ d) rv))]
[(0 x y) (let ((^y/x (exact-ceiling (/ y x))))
(inr (/ (modulo (- y) x) (* y ^y/x)) (cons (/ ^y/x) rv)))]
[(flr _ _) (inr (- r flr) (cons flr rv))]))
(inr R null))
(define (real->egyptian-string f)
(define e.f.-list (real->egyptian-list f))
(define fmt-part
(match-lambda
[(? integer? (app number->string s)) s]
[(app (compose number->string /) s) (format "/~a"s)]))
(string-join (map fmt-part e.f.-list) " + "))
(define (stat-egyptian-fractions max-b+1)
(define-values (max-l max-l-f max-d max-d-f)
(for*/fold ((max-l 0) (max-l-f #f) (max-d 0) (max-d-f #f))
((b (in-range 1 max-b+1)) (a (in-range 1 b)) #:when (= 1 (gcd a b)))
(define f (/ a b))
(define e.f (real->egyptian-list (/ a b)))
(define l (length e.f))
(define d (denominator (last e.f)))
(values (max max-l l) (if (> l max-l) f max-l-f)
(max max-d d) (if (> d max-d) f max-d-f))))
(printf #<<EOS
max #terms: ~a has ~a
[~.a]
max denominator: ~a has ~a
[~.a]
EOS
max-l-f max-l (real->egyptian-string max-l-f)
max-d-f max-d (real->egyptian-string max-d-f)))
(displayln (real->egyptian-string 43/48))
(displayln (real->egyptian-string 5/121))
(displayln (real->egyptian-string 2014/59))
(newline)
(stat-egyptian-fractions 100)
(newline)
(stat-egyptian-fractions 1000)
(module+ test (require tests/eli-tester)
(test (real->egyptian-list 43/48) => '(1/2 1/3 1/16)))
You may also check:How to resolve the algorithm Zig-zag matrix step by step in the PureBasic programming language
You may also check:How to resolve the algorithm Find limit of recursion step by step in the DWScript programming language
You may also check:How to resolve the algorithm 15 puzzle game step by step in the 68000 Assembly programming language
You may also check:How to resolve the algorithm Playing cards step by step in the E programming language
You may also check:How to resolve the algorithm Calendar step by step in the Huginn programming language