Zadanie:

Twój program ma odpowiednią , pozytywną, prostą część w formacie <numerator>/<denominator>.

Dla tego wejścia musi znaleźć dwie frakcje.

1. Ułamek, który jest mniejszy niż wkład.
2. Ułamek większy niż wkład.

Obie frakcje muszą mieć niższy mianownik niż wkład. Ze wszystkich możliwych ułamków powinny mieć najniższą różnicę w stosunku do danych wejściowych.

Wydajność:

Wyjście twojego programu musi być:

• Ułamek mniejszy niż dane wejściowe w formacie <numerator>/<denominator>.
• Po nim następuje spacja (kod ASCII 32).
• Po nim ułamek większy niż wejście, w formacie <numerator>/<denominator>.

Następująco:

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

Zasady:

• Wszystkie wyprowadzane ułamki muszą być najniższe .
• Wszystkie wyprowadzane ułamki muszą być ułamkami właściwymi.
• Jeśli nie są możliwe żadne właściwe ułamki, które są dozwolone przez reguły, musisz podać dane wyjściowe 0zamiast ułamka <wejście i 1zamiast ułamka> wejście.
• Możesz wybrać, czy chcesz otrzymać ułamek jako argument wiersza poleceń (np yourprogram.exe 2/5 ), Czy monit o podanie danych przez użytkownika.
• Możesz założyć, że twój program nie otrzyma nieprawidłowych danych wejściowych.
• Najkrótszy kod (w bajtach, w dowolnym języku) wygrywa.

• Wszelkie niestandardowe argumenty wiersza polecenia (argumenty, które zwykle nie są wymagane do uruchomienia skryptu) są liczone do całkowitej liczby znaków.

• Czego Twój program nie może robić:

  • Zależy od wszelkich zasobów zewnętrznych.
  • Zależy od posiadania określonej nazwy pliku.
  • Wyprowadzaj cokolwiek innego niż wymagane wyjście.
  • Uruchomienie zajmuje wyjątkowo długo. Jeśli program działa przez ponad minutę dla ułamków z 6-cyfrowym licznikiem i mianownikiem (np. 179565/987657) Na komputerze przeciętnego użytkownika domowego, jest nieprawidłowy.
  • Frakcje wyjściowe z 0 jako mianownik. Nie możesz podzielić przez zero.
  • Wyprowadzaj ułamki 0jako licznik. Twój program musi generować wyjście 0zamiast ułamka.
  • Zmniejsz ułamek wprowadzony. Jeśli ułamek podany jako dane wejściowe jest redukowalny, musisz użyć ułamka podczas wprowadzania.
• Twój program nie może być napisany w języku programowania, dla którego nie istniał publicznie dostępny kompilator / tłumacz przed opublikowaniem tego wyzwania.

Przykłady:

Wejście: 2/5
Wyjście: 1/3 1/2

Wejście: 1/2
Wyjście: 0 1

Wejście: 5/9
Wyjście: 1/2 4/7

Wejście: 1/3
Wyjście: 0 1/2

Wejście: 2/4
Wyjście: 1/3 2/3

Wejście: 179565/987657
Wyjście: 170496/937775 128779/708320

Szałwia - 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

Szałwia jest potrzebna tylko w ostatnim wierszu, który dba o wynik. Wszystko inne działa również w Pythonie.

Wymień raw_input()się sys.argv[1], że wejście odczytać z argumentem wiersza poleceń zamiast monitu. Nie zmienia to liczby postaci. (Nie działa w Pythonie bez wcześniejszego importowania sys).

To zasadniczo rekurencyjnie konstruuje odpowiednią sekwencję Farey przy użyciu mediantów istniejących elementów, ale ogranicza się do tych elementów najbliższych wejściu. Z innego punktu widzenia uruchamia wyszukiwanie zagnieżdżone w odpowiednich sekwencjach Farey.

Prawidłowo przetwarza wszystkie przykłady w mniej niż sekundę na moim komputerze.

Oto wersja bez golfa:

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)

Zacząłem od oczywistego rozwiązania brutalnej siły, ale zdałem sobie sprawę, że ponieważ OP chciał być w stanie rozwiązać instancje za pomocą sześciocyfrowych liczników i mianowników w niecałą minutę, potrzebuję lepszego rozwiązania niż próbowanie trylionów możliwości. I znaleziono przydatny wzór na stronie Wikipedia na ciąg fareya: Jeżeli a / b, c / d, sąsiadują w jednej sekwencji Farey z a/b<c/d, a następnieb*c-a*b=1 . Pętla while wewnątrz mojego programu rozszerza ten fakt na liczby nieskrócone, używając gcd, którą oblicza druga pętla while.

Grałem już w tę grę dość ciężko, ale bardzo chciałbym usłyszeć wszelkie sugestie.

Edycje:

166-> 162: Usunięto ai bz programu zewnętrznego. Były niepotrzebne.
162-> 155: str()-> ``
155-> 154: Dodano k.
154-> 152: Usunięto xz wnętrza funkcji, zamiast tego przekazano ją jako argument.
152-> 150: Podał awartość domyślną zamiast przekazać ją jako argument.
150-> 146: Zmieniono inicjalizację xi y.
146–> 145: usunięto k.
145-> 144: Zmieniono ... i ... lub ... na (..., ...) [...], oszczędzając w ten sposób miejsce.
144-> 138: Zmieniono (..., ...) [...] na ... + ... * (...). Dzięki @ mbomb007.

Przypadki testowe:

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

Przedostatni test trwał mniej niż sekundę na moim komputerze, a ostatni trwał około 5-10 sekund.

Mathematica, 163 bajty

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

Jest to poważnie ograniczone wymaganiem wejścia / wyjścia jako danych wejściowych i ciągów użytkownika. Radzenie sobie ze strunami jest naprawdę niewygodne w Mathematica (przynajmniej jeśli chcesz grać w golfa). Robiąc to w naturalny sposób w Mathematica (używając tylko liczb całkowitych i racjonalnych) prawdopodobnie zmniejszyłbym to do 50% wielkości.

Może wykonać 6-cyfrowe liczby w ciągu kilku sekund na moim komputerze.

Nieco bardziej czytelny (choć nie tak naprawdę niezamierzony):

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

Dla zabawy, robienie tego w „naturalny sposób”, tj. Jako funkcja przyjmująca licznik i mianownik i zwracająca dwie racjonalne wartości, to tylko 84 znaki (więc moje 50% oszacowanie było w rzeczywistości całkiem blisko):

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

Julia - 127 125 bajtów

Podszedłem do tego z matematycznego punktu widzenia, aby uniknąć potrzeby pętli, więc ten kod działa dość szybko dla dużych danych wejściowych (uwaga: jeśli a / b jest wejściem, to a * b musi mieścić się w Int64 (Int32 w systemach 32-bitowych) , w przeciwnym razie generowane są nonsensowne odpowiedzi - jeśli oba a i b są wyrażalne w Int32 (Int16 w systemach 32-bitowych), nie występują żadne problemy).

AKTUALIZACJA: Nie trzeba już przeciążać odwrotnego ukośnika dla div, używając ÷, oszczędzając 2 bajty netto.

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

Nie golfowany:

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

Podstawowa idea: znajdź największe d i f mniejsze niż b, które spełnia ad-bc = gcd (a, b) (następny najmniejszy) i be-af = gcd (a, b) (następny największy), a następnie oblicz c i e na podstawie tam. Wynikowe wyjście to c / de / f, chyba że albo d albo f wynosi 1, w którym to przypadku pominięto / d lub / f.

Co ciekawe, oznacza to, że kod działa również dla dodatnich niepoprawnych ułamków, o ile dane wejściowe nie są liczbami całkowitymi (to znaczy gcd (a, b) = a).

W moim systemie wprowadzanie danych 194857602/34512958303nie zajmuje zauważalnego czasu171085289/30302433084 23772313/4210525219

JavaScript, 131

Z grubą notacją strzałek i evalpołączeniami:

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}

Test 179565/987657warunków skrajnych jest wykonywany w około 35 sekund przeglądarce Firefox , a dużo więcej w Chrome (~ 6 minut)

Szybsza metoda bez evaloznaczenia grubej strzały

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)

Test 179565/987657warunków skrajnych jest wykonywany w około 5 sekund.

Nie grał w golfa:

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 bajty (155 bez 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"

Lub jeśli moduły CPAN są niedozwolone / potrzebny jest 3-4 razy szybszy kod:

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

Pierwsza wersja zajmuje 9,55 sekundy na moim komputerze, druga wersja 2,44 sekundy.

Mniej nieczytelne:

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