Tâche:

Votre programme reçoit une fraction simple appropriée et positive dans le format .<numerator>/<denominator>

Pour cette entrée, il doit trouver deux fractions.

1. Une fraction inférieure à l'entrée.
2. Une fraction supérieure à l'entrée.

Les deux fractions doivent avoir un dénominateur inférieur à l'entrée. De toutes les fractions possibles, elles devraient avoir la plus faible différence avec l'entrée.

Sortie:

La sortie de votre programme doit être:

• Une fraction plus petite que l'entrée, au format <numerator>/<denominator>.
• Suivi d'un caractère espace (code ASCII 32).
• Suivi d'une fraction supérieure à l'entrée, au format <numerator>/<denominator>.

Comme suit:

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

Règles:

• Toutes les fractions produites doivent être en termes les plus bas .
• Toutes les fractions produites doivent être des fractions appropriées.
• S'il n'y a pas de fractions appropriées possibles autorisées par les règles, vous devez générer 0une entrée au lieu d'une fraction <entrée et 1au lieu d'une fraction> entrée.
• Vous pouvez choisir si vous souhaitez recevoir la fraction sous forme d'argument de ligne de commande (par exemple yourprogram.exe 2/5) ou inviter l'utilisateur à entrer.
• Vous pouvez supposer que votre programme ne recevra aucune entrée invalide.
• Le code le plus court (en octets, dans n'importe quelle langue) gagne.

• Tous les arguments de ligne de commande non standard (arguments qui ne sont normalement pas requis pour exécuter un script) comptent pour le nombre total de caractères.

• Ce que votre programme ne doit pas faire:

  • Dépendez de toutes les ressources externes.
  • Dépendre d'avoir un nom de fichier spécifique.
  • Sortie autre chose que la sortie requise.
  • Prenez exceptionnellement longtemps à courir. Si votre programme dure plus d'une minute pour les fractions avec un numérateur et un dénominateur à 6 chiffres (par exemple 179565/987657) sur l'ordinateur d'un utilisateur à domicile moyen, il n'est pas valide.
  • Fractions de sortie avec 0comme dénominateur. Vous ne pouvez pas diviser par zéro.
  • Fractions de sortie avec 0comme numérateur. Votre programme doit sortir 0au lieu d'une fraction.
  • Réduisez une fraction saisie. Si la fraction donnée en entrée est réductible, vous devez utiliser la fraction telle qu'elle est entrée.
• Votre programme ne doit pas être écrit dans un langage de programmation pour lequel il n'existait pas de compilateur / interprète accessible au public avant la publication de ce défi.

Exemples:

Entrée: 2/5
Sortie: 1/3 1/2

Entrée: 1/2
Sortie: 0 1

Entrée: 5/9
Sortie: 1/2 4/7

Entrée: 1/3
Sortie: 0 1/2

Entrée: 2/4
Sortie: 1/3 2/3

Entrée: 179565/987657
Sortie: 170496/937775 128779/708320

Sauge - 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

Sage n'est nécessaire que dans la dernière ligne, qui s'occupe de la sortie. Tout le reste fonctionne également en Python.

Remplacez raw_input()par sys.argv[1]pour que l'entrée soit lue à partir d'un argument de ligne de commande au lieu d'une invite. Cela ne change pas le nombre de caractères. (Ne fonctionne pas en Python sans importersys préalable.)

Cela construit essentiellement récursivement les séquence de Farey utilisant des médiants des éléments existants, mais se limite aux éléments les plus proches de l'entrée. D'un autre point de vue, il exécute une recherche à intervalles imbriqués sur les séquences de Farey respectives.

Il traite correctement tous les exemples en moins d'une seconde sur ma machine.

Voici une version non golfée:

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

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)

J'ai commencé avec la solution évidente de force brute, mais je me suis rendu compte que puisque l'OP voulait être capable de résoudre des instances avec des numérateurs et des dénominateurs à six chiffres en moins d'une minute, j'ai besoin d'une meilleure solution que d'essayer un billion de possibilités. J'ai trouvé une formule pratique sur la page Wikipedia pour la séquence de Farey: si a / b, c / d sont voisins dans l'une des séquences de Farey, avec a/b<c/d, alorsb*c-a*b=1 . La boucle while à l'intérieur de f dans mon programme étend ce fait aux nombres non réduits, en utilisant le gcd, que l'autre boucle while calcule.

J'ai déjà joué au golf assez dur, mais j'aimerais entendre des suggestions.

Modifications:

166-> 162: Supprimé aet bdu programme externe. Ils n'étaient pas nécessaires.
162-> 155:str() -> ``
155-> 154: ajouté k.
154-> 152: supprimé xde l'intérieur de la fonction, passé à la place comme argument.
152-> 150: a donné aune valeur par défaut au lieu de la passer en argument.
150-> 146: modification de l'initialisation de xet y.
146-> 145: supprimé k.
145-> 144: Changé ... et ... ou ... en (..., ...) [...], économisant ainsi un espace.
144-> 138: changé (..., ...) [...] en ... + ... * (...). Merci à @ mbomb007.

Cas de test:

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

L'avant-dernier test a pris moins d'une seconde sur mon ordinateur, tandis que le dernier a pris environ 5 à 10 secondes.

Mathematica, 163 octets

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

Ceci est sévèrement limité par l'exigence d'entrée / sortie en tant qu'entrée utilisateur et chaînes. Le traitement des cordes est vraiment compliqué dans Mathematica (au moins lorsque vous voulez jouer au golf). En faisant cela de façon naturelle dans Mathematica, (en utilisant uniquement des entiers et des rationnels), je pourrais probablement réduire cela à 50% de la taille.

Il peut faire des nombres à 6 chiffres en quelques secondes sur ma machine.

Légèrement plus lisible (mais pas vraiment non golfé):

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

Pour le plaisir, faire ceci "de façon naturelle", c'est-à-dire en tant que fonction prenant le numérateur et le dénominateur et retournant deux rationnels, cela ne fait que 84 caractères (donc mon estimation de 50% était en fait assez proche):

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

Julia - 127 125 octets

Je l'ai abordé d'un point de vue mathématique pour éviter d'avoir besoin de boucles, donc ce code s'exécute assez rapidement pour les grandes entrées (remarque: si a / b est l'entrée, alors a * b doit tenir dans Int64 (Int32 sur les systèmes 32 bits) , sinon des réponses absurdes sont générées - si a et b sont tous deux exprimables en Int32 (Int16 sur les systèmes 32 bits), aucun problème ne se produit).

MISE À JOUR: Il n'est plus nécessaire de surcharger la barre oblique inverse pour div, en utilisant ÷, une économie nette de 2 octets.

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))

Non golfé:

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

Idée de base: trouver le plus grand d et f inférieur à b qui satisfait ad-bc = gcd (a, b) (suivant le plus petit) et be-af = gcd (a, b) (suivant le plus grand), puis calculer c et e à partir de Là. La sortie résultante est c / de / f, sauf si d ou f vaut 1, auquel cas le / d ou / f est omis.

Fait intéressant, cela signifie que le code fonctionne également pour les fractions impropres positives, tant que l'entrée n'est pas un entier (c'est-à-dire, gcd (a, b) = a).

Sur mon système, la saisie 194857602/34512958303ne prend pas de temps perceptible pour la sortie171085289/30302433084 23772313/4210525219

JavaScript, 131

Avec notation fléchée et evalappels:

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}

Le 179565/987657test de résistance est exécuté en environ 35 secondes sur Firefox, beaucoup plus sur Chrome (~ 6 minutes)

Méthode plus rapide et evalnotation sans et grosse flèche

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)

Le 179565/987657test de résistance est exécuté en environ 5 secondes.

Non golfé:

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

perl, 142 octets (155 sans 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"

Ou si les modules CPAN sont interdits / un code 3-4 fois plus rapide est nécessaire:

$/="/";$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"

L'ancienne version prend 9,55 secondes sur ma machine, la dernière version 2,44 secondes.

Moins illisible:

($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";