Nächste Fraktion

24

Aufgabe:

Ihr Programm erhält einen korrekten , positiven einfachen Bruch im Format <numerator>/<denominator>.

Für diese Eingabe müssen zwei Brüche gefunden werden.

  1. Ein Bruchteil, der kleiner als die Eingabe ist.
  2. Ein Bruchteil, der größer als die Eingabe ist.

Beide Brüche müssen einen niedrigeren Nenner als die Eingabe haben. Von allen möglichen Brüchen sollten sie den geringsten Unterschied zur Eingabe aufweisen.

Ausgabe:

Die Ausgabe Ihres Programms muss sein:

  • Ein Bruch, der im Format kleiner als die Eingabe ist <numerator>/<denominator> .
  • Gefolgt von einem Leerzeichen (ASCII-Code 32).
  • Gefolgt von einem Bruch, der größer als die Eingabe ist, im Format <numerator>/<denominator>.

Wie folgt:

«fraction that is < input» «fraction that is > input»

Regeln:

  • Alle ausgegebenen Brüche müssen in niedrigsten Ausdrücken angegeben werden .
  • Alle ausgegebenen Brüche müssen richtige Brüche sein.
  • Wenn keine korrekten Brüche möglich sind, die nach den Regeln zulässig sind, müssen Sie 0anstelle eines Bruches <input und ausgeben1 > anstelle eines Bruchs> eine Eingabe vornehmen.
  • Sie können wählen, ob Sie den Bruch als Befehlszeilenargument erhalten möchten (z. B. yourprogram.exe 2/5 ) oder zur Eingabe durch den Benutzer .
  • Sie können davon ausgehen, dass Ihr Programm keine ungültigen Eingaben erhält.
  • Der kürzeste Code (in Bytes, in jeder Sprache) gewinnt.
  • Alle nicht standardmäßigen Befehlszeilenargumente (Argumente, die normalerweise nicht zum Ausführen eines Skripts erforderlich sind) werden auf die Gesamtzahl der Zeichen angerechnet.

  • Was Ihr Programm nicht tun darf :

    • Abhängig von externen Ressourcen.
    • Hängen Sie davon ab, einen bestimmten Dateinamen zu haben.
    • Geben Sie etwas anderes als die erforderliche Ausgabe aus.
    • Es dauert außergewöhnlich lange zu laufen. Wenn Ihr Programm für Brüche mit einem 6-stelligen Zähler und Nenner länger als eine Minute läuft (z. B.179565/987657 ) auf dem Computer eines durchschnittlichen Heimanwenders ausgeführt wird, ist es ungültig.
    • Ausgabefraktionen mit 0als Nenner. Sie können nicht durch Null teilen.
    • Brüche mit 0als Zähler ausgeben. Ihr Programm muss 0anstelle eines Bruchs ausgegeben werden.
    • Reduzieren Sie einen eingegebenen Bruch. Wenn der als Eingabe angegebene Bruch reduzierbar ist, müssen Sie den als Eingabe angegebenen Bruch verwenden.
  • Ihr Programm darf nicht in einer Programmiersprache geschrieben sein, für die es vor Veröffentlichung dieser Herausforderung keinen öffentlich verfügbaren Compiler / Interpreter gab.

Beispiele:

Eingabe: 2/5
Ausgabe: 1/3 1/2

Eingabe: 1/2
Ausgabe: 0 1

Eingabe: 5/9
Ausgabe: 1/2 4/7

Eingabe: 1/3
Ausgabe: 0 1/2

Eingabe: 2/4
Ausgabe: 1/3 2/3

Eingabe: 179565/987657
Ausgabe: 170496/937775 128779/708320

user2428118
quelle
1
Ihr erstes Beispiel entspricht nicht der Spezifikation: Beide Brüche müssen einen niedrigeren Nenner als die Eingabe haben.
Howard
1
Erstes Beispiel sollte Ausgabe sein 1/3 1/2.
Heiko Oberdiek
@HeikoOberdiek Du hast recht. Fest.
user2428118
1
Definieren Sie "durchschnittlicher Heimcomputer". Sind 90 Sekunden auf einem 1,6 GHz Intel Atom-Computer akzeptabel?
John Dvorak
2
Ihr letztes Beispiel ist falsch. Der Eingabeanteil entspricht dem ersten der Ausgabeanteile.
DavidC

Antworten:

3

Salbei - 119 117

x,X=map(int,raw_input().split('/'))
a=0
A=c=C=1
while C<X:exec("ab,,AB"[c*X>C*x::2]+"=c,C");c=a+b;C=A+B
print a/A,b/B

Salbei wird nur in der letzten Zeile benötigt, die sich um die Ausgabe kümmert. Alles andere funktioniert auch in Python.

Ersetzen Sie raw_input()durch sys.argv[1], um die Eingabe von einem Befehlszeilenargument anstelle einer Eingabeaufforderung lesen zu lassen. Die Zeichenanzahl wird dadurch nicht geändert. (Funktioniert nicht in Python, ohne sysvorher importiert zu haben .)

Dies konstruiert im wesentlichen rekursiv das jeweilige Farey-Sequenz Verwendung von Medianten der vorhandenen Elemente, beschränkt sich jedoch auf diejenigen Elemente, die der Eingabe am nächsten liegen. Aus einer anderen Sicht führt es eine Suche nach verschachtelten Intervallen für die jeweiligen Farey-Sequenzen durch.

Auf meinem Computer werden alle Beispiele in weniger als einer Sekunde korrekt verarbeitet.

Hier ist eine ungolfed Version:

x,X = map(Integer,sys.argv[1].split('/'))
x = x/X
a = 0
c = b = 1
while c.denominator() < X:
    if c > x:
        b = c
    else:
        a = c
    c = ( a.numerator() + b.numerator() ) / ( a.denominator() + b.denominator() )
print a,b
Wrzlprmft
quelle
Ich hatte schon Angst, dass ich für diese Prämie keine neuen Einreichungen bekommen würde. Gute Arbeit.
user2428118
Netter Trick mit dem exec!
Xnor
Als einzige Antwort innerhalb der Kopfgeldfrist erteile ich Ihnen hiermit das Kopfgeld. Herzliche Glückwünsche.
user2428118
Ich habe gerade einen Fehler in einem der Beispiele behoben . Möglicherweise möchten Sie Ihre Übermittlung korrigieren (obwohl seit der Übermittlung bereits ein halbes Jahr vergangen ist).
user2428118
12

Python 2.7 - 138

x,y=n,d=map(int,raw_input().split('/'))
while y:x,y=y,x%y
def f(p,a=d):
 while(a*n+p)%d:a-=1
 print`(a*n+p)/d`+('/'+`a`)*(a>1),
f(-x);f(x)

Ich habe mit der offensichtlichen Brute-Force-Lösung begonnen, aber mir wurde klar, dass ich, da das OP Instanzen mit sechsstelligen Zählern und Nennern in weniger als einer Minute lösen wollte, eine bessere Lösung brauche, als Billionen von Möglichkeiten auszuprobieren. Ich habe auf der Wikipedia-Seite eine nützliche Formel für die Farey-Sequenz gefunden: Wenn a / b, c / d Nachbarn in einer der Farey-Sequenzen sind, mita/b<c/d , dannb*c-a*b=1 . Die while-Schleife in f in meinem Programm erweitert diese Tatsache auf nicht reduzierte Zahlen, wobei die gcd verwendet wird, die die andere while-Schleife berechnet.

Ich habe das schon ziemlich hart gespielt, aber ich würde gerne Vorschläge hören.

Bearbeitungen:

166-> 162: Entfernt aund baus dem äußeren Programm. Sie waren unnötig.
162-> 155: str()-> ``
155-> 154: Hinzugefügt k.
154-> 152: Wurde xaus der Funktion entfernt und stattdessen als Argument übergeben.
152-> 150: Hat aeinen Standardwert angegeben, anstatt ihn als Argument zu übergeben.
150-> 146: Die Initialisierung von xund wurde geändert y.
146-> 145: entfernt k.
145-> 144: Geändert ... und ... oder ... zu (..., ...) [...], wodurch Platz gespart wird.
144-> 138: Geändert (..., ...) [...] zu ... + ... * (...). Vielen Dank an @ mbomb007.

Testfälle:

2/5
1/3 1/2

1/2
0 1

2/4
1/3 2/3

179565/987657
170496/937775 128779/708320

12345678/87654321
12174209/86436891 11145405/79132382

Der vorletzte Test dauerte auf meinem Computer weniger als eine Sekunde, während der letzte etwa 5-10 Sekunden dauerte.

isaacg
quelle
Das k=1ist reine Bosheit.
Evpok
1
@ Evpok: Ich habe versucht, k = y = n zum Laufen zu bringen, aber anscheinend möchte Python, dass es lokal ist, wenn Sie eine Variable innerhalb einer Funktion ändern. Dies war die einzige Möglichkeit, eine lokale Variable mit 4 Zeichen zu erhalten. Da der Bruch positiv und korrekt ist, kann der Nenner auch nicht 1 sein.
isaacg
Befehlszeilenargumente sind mit Python einfach, daher sollten sie wie hier beschrieben für die Eingabe verwendet werden.
Alex Thornton
1
" Sie können wählen, ob Sie den Bruch als Befehlszeilenargument (z. B. yourprogram.exe 2/5) oder als Eingabeaufforderung erhalten möchten ."
Isaacg
Speichern Sie 6 Zeichen:print`(a*n+p)/d`+('/'+`a`)*(a>1),
mbomb007
5

Mathematica, 163 Bytes

{a,b}=FromDigits/@InputString[]~StringSplit~"/";r=Range[b-1];""<>Riffle[#~ToString~InputForm&/@(#@DeleteCases[#2[a/b*r]/r,a/b]&@@@{{Max,Floor},{Min,Ceiling}})," "]

Dies wird durch die Eingabe- / Ausgabeanforderung als Benutzereingabe und Zeichenfolgen stark eingeschränkt. Der Umgang mit Streichern ist in Mathematica sehr umständlich (zumindest, wenn Sie Golf spielen möchten). Wenn ich das in Mathematica auf natürliche Weise mache (nur mit ganzen Zahlen und Rationen), würde ich das wahrscheinlich auf 50% der Größe reduzieren.

Es kann 6-stellige Zahlen in ein paar Sekunden auf meinem Computer machen.

Etwas besser lesbar (allerdings nicht wirklich ungolfed):

{a, b} = FromDigits /@ InputString[]~StringSplit~"/";
r = Range[b - 1];
"" <> Riffle[#~ToString~
     InputForm & /@ (#[DeleteCases[#2[a/b*r]/r, a/b]] & @@@ {{Max, 
       Floor}, {Min, Ceiling}}), " "]

Zum Spaß, wenn man dies "auf natürliche Weise" macht, dh als Funktion, die Zähler und Nenner nimmt und zwei Rationen zurückgibt, sind dies nur 84 Zeichen (meine 50% -Schätzung war also eigentlich ziemlich nahe):

f[a_,b_]:=#@DeleteCases[#2[a/b*(r=Range[b-1])]/r,a/b]&@@@{{Max,Floor},{Min,Ceiling}}
Martin Ender
quelle
3

Julia - 127 125 Bytes

Ich habe dies aus mathematischer Sicht angegangen, um die Notwendigkeit von Schleifen zu vermeiden, sodass dieser Code für große Eingaben recht schnell ausgeführt wird (Hinweis: Wenn a / b die Eingabe ist, muss a * b in Int64 passen (Int32 auf 32-Bit-Systemen). , andernfalls werden unsinnige Antworten generiert - wenn a und b in Int32 (Int16 auf 32-Bit-Systemen) beide ausgedrückt werden können, treten keine Probleme auf.

UPDATE: Es besteht keine Notwendigkeit mehr, einen Backslash für div zu überladen, indem ÷ verwendet wird, was 2 Bytes einspart.

a,b=int(split(readline(),"/"));k=gcd(a,b);f=b-invmod(a÷k,b÷k);d=2b-f-b÷k;print(a*d÷b,d<2?" ":"/$d ",a*f÷b+1,"/$f"^(f>1))

Ungolfed:

a,b=int(split(readline(),"/")) # Read in STDIN in form a/b, convert to int
k=gcd(a,b)           # Get the greatest common denominator
f=b-invmod(a÷k,b÷k)  # Calculate the denominator of the next biggest fraction
d=2b-f-b÷k           # Calculate the denominator of the next smallest fraction
print(a*d÷b,d<2?" ":"/$d ",a*f÷b+1,"/$f"^(f>1)) # Calculate numerators and print

Grundidee: Finde das größte d und f kleiner als b, das ad-bc = gcd (a, b) (das nächstkleinere) und be-af = gcd (a, b) (das nächstgrößere) erfüllt, und berechne dann c und e aus Dort. Die resultierende Ausgabe ist c / de / f, es sei denn, d oder f sind 1. In diesem Fall wird / d oder / f weggelassen.

Interessanterweise bedeutet dies, dass der Code auch für positive nicht ordnungsgemäße Brüche funktioniert, solange die Eingabe keine ganze Zahl ist (d. H. Gcd (a, b) = a).

Auf meinem System nimmt die Eingabe 194857602/34512958303keine wahrnehmbare Zeit in Anspruch171085289/30302433084 23772313/4210525219

Glen O
quelle
Testen mit 55552/999999gibt mir -396/920632 486/936509.
user2428118
@ user2428118 - Verwenden Sie ein 32-Bit-System (oder eine 32-Bit-Julia)? Ich habe "int" verwendet, was bedeutet, dass auf einem 32-Bit-System Int32 anstelle von Int64 verwendet wird. int32(55552*999999)gibt -282630400. Bei diesem Test 51143/920632 52025/936509stelle ich fest, dass die Nenner gleich sind und 52025-51143 = 486 - (- 396). Ich werde eine Notiz hinzufügen, um dieses Problem zu erwähnen.
Glen O
Wenn Sie sicherstellen möchten, dass der Code für alle Int64-Größeneingaben funktioniert, können Sie "int" durch "int128" ersetzen. Mit dieser Änderung führt die Eingabe 1234567891234567/2145768375829475878zu 869253326028691/1510825213275018197 365314565205876/634943162554457681. Diese Änderung fügt nur 3 zusätzliche Zeichen hinzu.
Glen O
Ja, ich verwende einen 32-Bit-Computer. Ich werde es irgendwann auf einem 64-Bit-Computer versuchen, wenn ich die Zeit dafür habe.
user2428118
Das Testen auf einem 64-Bit-Computer liefert das richtige Ergebnis, daher akzeptiere ich diese Antwort.
user2428118
2

JavaScript, 131

Mit fetter Pfeilnotation und evalAufrufen:

m=>{for(e=eval,n=e(m),i=p=0,q=1;++i</\d+$/.exec(m);)if(n*i>(f=n*i|0))g=f+1,p=f/i>e(p)?f+'/'+i:p,q=g/i<e(q)?g+'/'+i:q;return p+' '+q}

Der 179565/987657Stresstest dauert ca. 35 Sekunden Firefox , unter Chrome noch viel mehr (~ 6 Minuten)

Schnellere Methode und ohne evalund fette Pfeilnotation

for(n=eval(m=prompt(a=i=p=0,b=c=d=q=1));++i<m.match(/\d+$/);)if(n*i>(f=n*i|0))g=f+1,p=f*c>i*a?(a=f)+'/'+(c=i):p,q=g*d<i*b?(b=g)+'/'+(d=i):q;alert(p+' '+q)

Der 179565/987657Stresstest dauert ca. 5 Sekunden.

Nicht golfen:

m=prompt(); //get input
a=0; c=1; //first fraction
b=1; d=1; //second fraction
n=eval(m); //evaluate input
for (i=1; i<m.match(/\d+$/); i++) { //loop from 1 to input denominator
  f=Math.floor(n*i);
  if (n*i > f) { //if fraction not equal to simplification of input
    g=f+1; // f/i and g/i are fractions closer to input
    if (f/i>a/c) a=f, c=i;
    if (g/i<b/d) b=g; d=i; 
  }
}
alert(a+'/'+c+' '+b+'/'+d); //output values handling 0 and 1 correctly
Michael M.
quelle
Auch ... viel ... eval. EEK
John Dvorak
3
Testen mit 2/6gibt 1/3 2/5jedoch 1/3nicht weniger als aber gleich 2/6 .
user2428118
@ user2428118 behoben
Michael M.
Warum wurde diese Antwort so früh angenommen?
Evpok
1
@ user2428118: Es kann einige Tage dauern, bis Lösungen akzeptiert werden. Auch diese Lösung ist nicht mehr die kürzeste.
Isaacg
2

Perl, 142 Bytes (155 ohne CPAN)

use bare A..Z;$/="/";N=<>;D=<>;F=N/D;K=G=1;for$H(1..D){J<F&&J>E?(E,I):J>F&&J<G?(G,K):()=(J=$_/H,"$_/$H")for(Z=int F*H)..Z+1}print I||0," $K\n"

Oder wenn CPAN-Module nicht erlaubt sind / 3-4 mal schnellerer Code benötigt wird:

$/="/";$N=<>;$D=<>;$F=$N/$D;$g=$G=1;for$d(1..$D){$f<$F&&$f>$E?($E,$e):$f>$F&&$f<$G?($G,$g):()=($f=$_/$d,"$_/$d")for($z=int$F*$d)..$z+1}print$e||0," $g\n"

Die erste Version dauert auf meinem Computer 9,55 Sekunden, die zweite Version 2,44 Sekunden.

Weniger unleserlich:

($N, $D) = split(m[/], <>);
$F = $N / $D;
$G = 1;
foreach $d (1 .. $D) {
    $z = int $F * $d;
    foreach $_ ($z .. $z + 1) {
        $f = $_ / $d;
        ($f < $F && $f > $E ? ($E, $e) :
        ($f > $F && $f < $G ? ($G, $g) : ())) = ($f, "$_/$d");
    }
}
print $e || 0, ' ', $g || 1, "\n";
Skibrianski
quelle