Najbliższa frakcja

24

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

użytkownik2428118
źródło
1
Twój pierwszy przykład nie jest zgodny ze specyfikacją: obie frakcje muszą mieć niższy mianownik niż dane wejściowe.
Howard,
1
Pierwszym przykładem powinno być wyjście 1/3 1/2.
Heiko Oberdiek,
@HeikoOberdiek Masz rację. Naprawiony.
user2428118,
1
Zdefiniuj „komputer przeciętnego użytkownika domowego”. Czy 90 sekund na komputerze z procesorem Intel Atom 1,6 GHz jest dopuszczalne?
John Dvorak
2
Twój ostatni przykład jest niepoprawny. Frakcja wejściowa jest równa pierwszej frakcji wyjściowej.
DavidC

Odpowiedzi:

3

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
Wrzlprmft
źródło
Bałem się już, że nie dostanę żadnych nowych zgłoszeń do tej nagrody. Świetna robota.
user2428118
Niezła sztuczka z exec!
xnor
Jako jedyna odpowiedź przesłana w okresie nagrody, niniejszym przyznam nagrodę. Gratulacje.
user2428118,
Po prostu stała się błąd w jednym z przykładów. Możesz poprawić swoje zgłoszenie (mimo że minęło pół roku od jego przesłania).
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)

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.

isaacg
źródło
To k=1jest czysta niegodziwość.
Evpok
1
@Evpok: Próbowałem zmusić k = y = n do pracy, ale najwyraźniej jeśli zmodyfikujesz zmienną wewnątrz funkcji, python chce, aby była lokalna. To był jedyny sposób na uzyskanie zmiennej lokalnej składającej się z 4 znaków. Ponadto, ponieważ ułamek jest dodatni i właściwy, mianownik nie może wynosić 1.
isaacg
Argumenty wiersza poleceń są łatwe w Pythonie, więc powinny być użyte do wprowadzania danych zgodnie z instrukcją.
Alex Thornton,
1
Możesz wybrać, czy chcesz otrzymywać frakcję jako argument wiersza polecenia (np. Yourprogram.exe 2/5), czy monit o podanie danych przez użytkownika .”
isaacg
Zaoszczędź 6 znaków:print`(a*n+p)/d`+('/'+`a`)*(a>1),
mbomb007
5

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}}
Martin Ender
źródło
3

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

Glen O
źródło
Testowanie za pomocą 55552/999999daje mi -396/920632 486/936509.
user2428118
@ user2428118 - Czy korzystasz z 32-bitowego systemu (lub używasz 32-bitowej Julii)? Użyłem „int”, co oznacza, że ​​w systemie 32-bitowym użyje Int32 zamiast Int64. int32(55552*999999)daje -282630400. Dla mnie z tym testem otrzymuję 51143/920632 52025/936509- zauważ, że mianowniki są takie same i że 52025-51143 = 486 - (- 396). Dodam notatkę, aby wspomnieć o tym problemie.
Glen O
Jeśli chcesz mieć pewność, że kod będzie działał dla wszystkich danych wejściowych o rozmiarze Int64, możesz zamienić „int” na „int128”. Przy tej zmianie wprowadzanie 1234567891234567/2145768375829475878wyników w 869253326028691/1510825213275018197 365314565205876/634943162554457681. Ta zmiana dodaje tylko 3 dodatkowe postacie.
Glen O
Tak, używam komputera 32-bitowego. Wypróbuję go na komputerze 64-bitowym, kiedy będę miał na to czas.
user2428118
Testowanie na komputerze 64-bitowym daje poprawny wynik, więc akceptuję tę odpowiedź.
user2428118
2

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
Michael M.
źródło
... zbyt wiele ... eval. EEK
John Dvorak
3
Testowanie za pomocą 2/6daje 1/3 2/5jednak 1/3nie mniej niż, ale równe 2/6 .
user2428118,
@ user2428118 naprawiono
Michael M.
Dlaczego ta odpowiedź została zaakceptowana tak wcześnie?
Evpok
1
@ user2428118: Wiesz, możesz odczekać kilka dni zanim zaakceptujesz rozwiązania. To rozwiązanie nie jest już najkrótsze.
isaacg
2

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";
skibrianski
źródło