Fraction Frenzy!

9

BEARBEITEN: Ich bekomme viele Kommentare dazu, dass dies nicht beendet wird. Ich werde entweder der ersten Person, die mich gibt FF(3)(wie in der Antwort angegeben), FF(3)das Tag "Richtige Antwort" geben oder beweisen, dass dies tatsächlich auf unbestimmte Zeit explodiert.

Aufgabe:

Ihre Aufgabe ist es, das kleinstmögliche Programm zu erstellen, das die Liste der Kehrwerte der Fraction Frenzy-Funktion ( FF(n)) bei einer positiven Ganzzahl generiert n.

Einführung:

Bevor ich die FF-Funktion einführen kann, muss ich zuerst ägyptische Brüche erklären.

Ägyptische Fraktionen:

Ägyptische Brüche sind eine Möglichkeit, Brüche als Summe verschiedener Einheitsbrüche auszudrücken . Eine Möglichkeit, den Bruch auszudrücken, 5/8ist also 1/2 + 1/8. Es sind keine anderen Bruchbeträge wie

1/4 + 1/4 + 1/8
1/2 + 1/16 + 1/16

weil nicht alle ihre Brüche verschieden sind ( 1/4wird im ersten Beispiel und 1/16im zweiten wiederholt ).

In unserer Definition der ägyptischen Brüche berücksichtigen wir auch die Verwendung negativer Nenner in den Einheitsbrüchen.

FF-Funktion:

Die FF-Funktion (Fraction Frenzy) wird folgendermaßen beschrieben:

FF(1)ist die ägyptische Fraktion 1/2 + 1/3 + 1/5 + 1/-30.

FF(2)ist gleich FF(1)"multipliziert" mit sich selbst ( FF(1)"quadratisch"):

  (1/2 + 1/3 + 1/5 + 1/-30)(1/2 + 1/3 + 1/5 + 1/-30)
= 1/4 + 1/6 + 1/10 + 1/-60 + 1/6 + 1/9 + 1/15 + 1/-90 +
  1/10 + 1/15 + 1/25 + 1/-150 + 1/-60 + 1/-90 + 1/-150 + 1/900

Dies ist noch keine vollständig reduzierte ägyptische Fraktion, da es in Fraktionen "Wiederholungen" gibt. Um sie zu reduzieren, wird das folgende Verfahren durchgeführt:

  1. Summiere alle "Like" -Einheitsfraktionen zusammen.
  2. Reduzieren Sie die Summen auf ihre einfachsten Formen. Wenn also beispielsweise eine Summe aus Schritt 1vorliegt 2/6, kann diese auf reduziert werden 1/3.
  3. Wiederholen Sie 1 und 2, bis alle Nenner verschieden sind: Zum Beispiel 1/2 + 2/3 + 1/5im Gegensatz zu 1/2 + 1/3 + 1/3, die einen sich wiederholenden Nenner haben 3.
  4. Wenn es ein Paar aus einem positiven und einem negativen Bruch gibt, die den gleichen absoluten Wert haben, entfernen Sie beide (z. B. 1/-5und 1/5müssen beide entfernt werden).
  5. Wenn Brüche keine Einheit sind und nicht weiter reduziert werden können, teilen Sie sie in Einheitsfraktionen mit gleichem Nenner auf und behalten Sie eine Fraktion bei. Multiplizieren Sie sie mit den anderen mit FF(1): (1/2 + 1/3 + 1/5 + 1/-30).
  6. Wiederholen Sie die Schritte 1 bis 5, bis die endgültige Fraktionssumme eine gültige ägyptische Fraktion ist - dh alle Fraktionen unterscheiden sich voneinander und sind alle Einheitsfraktionen.

Dies ist die Reduzierung von FF(2):

  1/4 + 1/6 + 1/10 + 1/-60 + 1/6 + 1/9 + 1/15 + 1/-90 +
  1/10 + 1/15 + 1/25 + 1/-150 + 1/-60 + 1/-90 + 1/-150 + 1/900
= 1/4 + 2/6 + 1/9 + 2/10 + 2/15 + 1/25 + 2/-60 + 2/-90 + 2/-150 + 1/900 (step 1)
= 1/4 + 1/3 + 1/9 + 1/5 + 2/15 + 1/25 + 1/-30 + 1/-45 + 1/-75 + 1/900   (step 2)
= 1/3 + 1/4 + 1/5 + 1/9 + 1/15 + 1/15(1/2 + 1/3 + 1/5 + 1/-30) +        (step 5)
  1/25 + 1/-30 + 1/-45 + 1/-75 + 1/900
= 1/3 + 1/4 + 1/5 + 1/9 + 1/15 + 1/30 + 1/45 + 1/75 + 1/-450 +
  1/25 + 1/-30 + 1/-45 + 1/-75 + 1/900
= 1/3 + 1/4 + 1/5 + 1/9 + 1/15 + 1/25 + 1/-450 + 1/900                  (step 4)

Für alle n(außer für 1) FF(n)wird durch "Quadrieren" definiert FF(n-1).

Ein- und Ausgabe:

Bei einer gegebenen Ganzzahl nmüssen Sie eine Liste aller Kehrwerte von ausgeben FF(n), sortiert in aufsteigender Reihenfolge ihrer absoluten Werte:

1 -> [2, 3, 5, -30]
# 1/2 + 1/3 + 1/5 + 1/-30 = FF(1), reciprocals = [2, 3, 5, -30]

2 -> [3, 4, 5, 9, 15, 25, -450, 900]

Sie dürfen eine Zeichenfolge mit einem beliebigen Trennzeichen oder die Interpretation einer Liste durch Ihre Sprache verwenden, sodass diese Ausgaben für die Eingabe alle akzeptabel sind 1:

2 3 5 -30   (Space-delimited)
2,3,5,-30   (Comma-delimited)
[2 3 5 -30] (Lisp-like lists)
etc. etc.

Technische Daten:

  • Sie müssen die Ergebnisse der FF(n)Funktion genau wie oben angegeben ausgeben .
  • Sie können sicher sein, dass die Eingabe eine positive Ganzzahl ist - sie wird niemals unter Null liegen und niemals eine Dezimalzahl (oder ein Bruch).

Dies ist , also gewinnt der kürzeste Code in Bytes!

Clismique
quelle
4
Wird dies aus Neugier garantiert beendet?
Martin Ender
Lassen Sie uns diese Diskussion im Chat fortsetzen .
Clismique
Ich bestätige, dass FF (3) zu explodieren scheint. Haben Sie dies nicht bis zu ungefähr FF (10) getestet, bevor Sie es in die Sandbox gepostet haben?
Peter Taylor
Lassen Sie uns diese Diskussion im Chat fortsetzen .
Clismique
2
Ägyptische Fraktionen hatten keine negativen Werte, es handelt sich also nicht wirklich um eine ägyptische Fraktion.
mbomb007

Antworten:

1

Haskell , 365 Bytes

import Data.Function;import Data.List;import Data.Ratio;n=numerator;d=denominator
r=until=<<((==)=<<)$filter(/=0).map(sum).groupBy((==)`on`d).sortBy(compare`on`d)
p s=let(o,q)=span((<2).abs.n)s in case q of []->o;(a:b)->let j=a-1%d a*signum a in p.r$o++[a-j]++map(*j)e++b
s s=(*)<$>s<*>s;e=(1%)<$>[2,3,5,-30];f=iterate(p.r.s)e;o i=[abs(d q)*signum(n q)|q<-f!!(i-1)]

Probieren Sie es online aus!

Roman Czyborra
quelle
Hmm… ich stoße auf eine scheinbar unendliche Schleife, wenn ich die größte Nichteinheit aufteile und zu einem Zeitpunkt, wie dargestellt, erneut überprüfe, und hatte dies bereits getan, als ich die kleinste Nichteinheit vor dem erneuten Überprüfen in links rückwärts oder global alle Nichteinheiten aufteilte, aber vielleicht sollte ich es tun nicht versäumen, nicht-deterministisch Nicht-Einheiten dazwischen auszuwählen, ob man genug andere annulliert, um einen endlichen FF zu erreichen (3)?
Roman Czyborra
Die Verwendung (1%)<$>[2,4,6,12]als 1 verschiebt lediglich die Nichtbeendigung von FF (3) zu FF (4) Roman
Roman Czyborra
(1%)<$>[2,3,10,15]oder überhaupt (1%)<$>[3,4,6,8,12,24]keine Verbesserung ergeben 🤔
Roman Czyborra