Greedy algorithm for Egyptian fractions: Difference between revisions
Content added Content deleted
No edit summary |
|||
Line 35: | Line 35: | ||
* Wolfram MathWorld™ entry: [http://mathworld.wolfram.com/EgyptianFraction.html Egyptian fraction] |
* Wolfram MathWorld™ entry: [http://mathworld.wolfram.com/EgyptianFraction.html Egyptian fraction] |
||
<br><br> |
<br><br> |
||
=={{header|Common Lisp}}== |
|||
<lang common lisp>(defun egyption-fractions (x y &optional acc) |
|||
(let* ((a (/ x y))) |
|||
(cond |
|||
((> (numerator a) (denominator a)) |
|||
(multiple-value-bind (q r) (floor x y) |
|||
(if (zerop r) |
|||
(cons q acc) |
|||
(egyption-fractions r y (cons q acc))))) |
|||
((= (numerator a) 1) (reverse (cons a acc))) |
|||
(t (let ((b (1+ (floor y x)))) |
|||
(egyption-fractions (mod (- y) x) (* y b) (cons (/ b) acc))))))) |
|||
(defun test (n fn) |
|||
(car (sort (loop for i from 1 to n append |
|||
(loop for j from 2 to n collect |
|||
(cons (/ i j) (funcall fn (egyption-fractions i j))))) |
|||
#'> |
|||
:key #'cdr))) |
|||
</lang> |
|||
{{out}} |
|||
<pre>(egyption-fractions 43 48) |
|||
(egyption-fractions 5 121) |
|||
(egyption-fractions 2014 59) |
|||
(egyption-fractions 8 97) |
|||
</pre> |
|||
Basic tests: |
|||
<pre>(1/2 1/3 1/16) |
|||
(1/25 1/757 1/763309 1/873960180913 1/1527612795642093418846225) |
|||
(34 1/8 1/95 1/14947 1/670223480) |
|||
(1/13 1/181 1/38041 1/1736503177 1/3769304102927363485 |
|||
1/18943537893793408504192074528154430149 |
|||
1/538286441900380211365817285104907086347439746130226973253778132494225813153 |
|||
1/579504587067542801713103191859918608251030291952195423583529357653899418686342360361798689053273749372615043661810228371898539583862011424993909789665) |
|||
</pre> |
|||
Other tests: |
|||
<pre>(test 999 #'length) |
|||
(test 999 (lambda (xs) (loop for x in xs maximizing (denominator x)))) |
|||
</pre> |
|||
<pre>(493/457 . 13) |
|||
(36/457 |
|||
. 839018826833450186636781520007011999269820404906753180244759299287837378895397605613261469995626498719289835112392530430840514102146998625666594756995273418015600023494049208108894185781774002683063204252356172520941088783702738286944210460710059319691268110283467445381026653628599765684739105388642310044785844902157076919003735231543781785073393176144167688252446541416466418608465458502997971425428342769433127784560570193376772878336217849260872114137931351960543608384244009505664253173875705234889570853924105640193619301332776989688248555027054395237907581951261868280899150574360164800187964167274323078311078867593844043149124596271281252530924719121766925749760855109100066731841478262812686642693395896229983745226277793055820609058348269152190083695704685769622011655159174272326647342695589818127126303038171968768650476413027459205291075571637957597356820188031655122749743652301268394542123970892422944335857917641636041892192547135178153602038877677614358281581103685526041329841496863410305888255234495015115912388514981113593387572720476744188169200130515719608747338810136728267784013352396910979904545913458536243327311977805126410065576961237640824852114328884086581542091492600312838425666927627674227053793897767395465326589843035773944346372949759909905561209334216847158156644884281300512699910530092870919061876615770708519243818676366245477462042294267674677954783726990349386117468071932874021023714524610740225814235147693954027910741673103980749749728106483987721602738673173009362802337092908847797499475895347112889339502928407808058670297722175686638678788738689803945574002805677250463286479363670076942509109589495377221095405979217163821481666646160815221224686562530536116613645305335922819524037829878961518170177968768364853399057357772141655622381280196908637031556436461404285930426436983658106288733881761514992109680298995922754466040011586713812553117621857109517258943846004179432521131844156242428351270188803919554398620084668514054504414062276012292497375238210886595006249453460414790147611422121782194848803348777061816460876697945418158442269512987729152441940326466631610424906158237288218706447963113019239557885486647314085357651895226117364760315394354624547919209138539180807829672545924239541758108877100331729470119526373928796447673951888289511964811633025369821156695934557103429921063387965046715070102916811976552584464153981214277622597308113449320462341683055200576571910241686615924531368198770946893858410058348221985603151428153382461711196734214085852523778422630907646235900752317571022131569421231196329080023952364788544301495422061066036911772385739659997665503832444529713544286955548310166168837889046149061296461059432238621602179724809510024772127497080258401694929973105184832214622785679651550368465524821062859837409907538269572622296774545103747438431266995525592705) |
|||
</pre> |
|||
=={{header|D}}== |
=={{header|D}}== |