Anonymous user
Greedy algorithm for Egyptian fractions: Difference between revisions
Greedy algorithm for Egyptian fractions (view source)
Revision as of 00:15, 15 November 2018
, 5 years agore-introduced original whitespace, and used a bigger font for most formulas.
m (re-introduced original whitespace, used bigger font for the formulas.) |
m (re-introduced original whitespace, and used a bigger font for most formulas.) |
||
Line 1:
{{task}}
An [[wp:Egyptian fraction|<u>Egyptian fraction</u>]] is the sum of distinct unit fractions such as:
:::: <big><big> <math> \tfrac{1}{2} + \tfrac{1}{3} + \tfrac{1}{16} \,(= \tfrac{43}{48})</math> </big></big>
Each fraction in the expression has a numerator equal to
Fibonacci's [[wp:Greedy algorithm for Egyptian fractions|<u>Greedy algorithm for Egyptian fractions</u>]] expands the fraction <big> <math> \tfrac{x}{y} </math> </big> to be represented by repeatedly performing the replacement
:::: <big> <math> \frac{x}{y} = \frac{1}{\lceil y/x\rceil} + \frac{(-y)\!\!\!\!\mod x}{y\lceil y/x\rceil} </math> </big>
(simplifying the 2<sup>nd</sup> term in this replacement as necessary, and where <big> <math> \lceil x \rceil </math> </big> is the ''ceiling'' function).
<!--
This Rosetta Code task will be using the Fibonacci greedy algorithm for computing Egyptian fractions; however, if different method is used instead, please note which method is being employed. Having all the programming examples use the Fibonacci greedy algorithm will make for easier comparison and compatible results.
-->
For this task, [[wp:Fraction (mathematics)#Simple.2C_common.2C_or_vulgar_fractions|<u>Proper and improper fractions</u>]] must be able to be expressed.
Proper fractions are of the form <big> <math>\tfrac{a}{b}</math> </big> where <big> <math>a</math> </big> and <big> <math>b</math> </big> are positive integers, such that <big> <math>a < b</math></big>, and ▼
▲Proper fractions are of the form <math>\tfrac{a}{b}</math> where <math>a</math> and <math>b</math> are positive integers, such that <math>a < b</math>, and
▲<br>improper fractions are of the form <math>\tfrac{a}{b}</math> where <math>a</math> and <math>b</math> are positive integers, such that <span style="font-family:times">''a'' ≥ ''b''</span>.
(See the [[#REXX|REXX programming example]] to view one method of expressing the whole number part of an improper fraction.)
Line 29 ⟶ 33:
;Task requirements:
* show the Egyptian fractions for: <math> \tfrac{43}{48} </math> and <math> \tfrac{5}{121} </math> and <math> \tfrac{2014}{59} </math>
* for all proper fractions, <big> <math>\tfrac{a}{b}</math> </big> where <big> <math>a</math> </big> and <big> <math>b</math> </big> are positive one-or two-digit (decimal) integers, find and show an Egyptian fraction that has:
::* the largest number of terms,
::* the largest denominator.
* for all one-, two-, and three-digit integers
| |||