Kiedy konwertujesz ułamek na liczbę dziesiętną i chcesz zapisać tę liczbę, często musisz ją zaokrąglić, ponieważ chcesz użyć tylko określonej ilości pamięci. Załóżmy, że możesz zapisać tylko 5 cyfr dziesiętnych, a następnie 5/3 staje się 1,6667. Jeśli możesz zapisać tylko 2 cyfry dziesiętne, będzie to 1,7 (teraz zakładając, że zawsze zawiera się między 0 a 9,99 ...).

Jeśli teraz spróbujesz odwrócić ten proces za pomocą 1.7 i chcesz odzyskać swoją frakcję, może to być trudne, ponieważ wiesz, że 1.7 to tylko zaokrąglona liczba. Oczywiście możesz wypróbować 17/10, ale jest to raczej „brzydka” frakcja w porównaniu do „eleganckiej” 5/3.

Zatem celem jest teraz znalezienie ułamka a / b o najmniejszym mianowniku b, który po zaokrągleniu powoduje zaokrąglenie liczby dziesiętnej.

Detale

Dane wejściowe zawierają ciąg o liczbie od 1 do 5 cyfr, który zawiera się w przedziale od 0 (włącznie) do 10 (nie wliczając) ze znakiem „.” po pierwszej cyfrze. Powiedzmy, że noznacza liczbę cyfr. Dane wyjściowe muszą być listą / tablicą dwóch liczb całkowitych [numerator, denominator]lub racjonalnym typem danych (możesz utworzyć własny lub użyć wbudowanego), gdzie licznik jest nieujemny, a mianownik jest dodatni. Licznik ułamkowy / mianownik musi być równy wartości wejściowej, jeśli jest prawidłowo zaokrąglony do ncyfr (co oznacza n-1cyfry po przecinku dziesiętnym).

Ograniczenie: dozwolona jest tylko jedna instrukcja pętli. Oznacza to, że możesz użyć tylko jednej instrukcji pętli (jak forlub whilelub gotoitp.), A także pętli funkcjonalnych, takich jak maplub, foldktóre stosują kod do każdego elementu listy / tablicy) w całym kodzie, ale możesz go „nadużyć” lub użyj rekurencji itp.

Powinieneś napisać funkcję. Jeśli twój język nie ma funkcji (a nawet jeśli tak jest), możesz alternatywnie założyć, że dane wejściowe są przechowywane w zmiennej (lub dane wejściowe przez stdin) i wydrukować wynik lub zapisać go w pliku. Najmniejsza liczba bajtów wygrywa.

Zaokrąglanie

Zaokrąglanie powinno odbywać się zgodnie z „konwencjonalnymi” regułami zaokrąglania, tj. Jeśli ostatnia cyfra, która zostanie odcięta, to 5 lub więcej, zaokrąglisz w górę i zaokrąglisz w dół dla innych przypadków, np .:

Podczas zaokrąglania do wyniku będzie 4.5494

• 1 cyfra: 5
• 2 cyfry: 4.5
• 3 cyfry: 4,55
• 4 cyfry: 4.549

Przykłady

Podaj następujące przypadki testowe i inne „interesujące”:

Input 1.7     Output 5/3
Input 0.      Output 0/1
Input 0.001   Output 1/667
Input 3.1416  Output 355/113

CJam, 41 40 36 bajtów

Q'./1=,:L0\{;)_Qd*mo_d2$/LmOQd-}g'/@

Zakłada, że ​​ciąg wejściowy jest przechowywany w Q, co jest wyraźnie dozwolone w pytaniu. Wypróbuj online.

Przypadki testowe

$ for d in 1.7 0. 0.001 3.1416; do cjam <(echo "\"$d\":Q;
> Q'./1=,:L0\{;)_Qd*mo_d2$/LmOQd-}g'/@
> "); echo; done
5/3
0/1
1/667
355/113

Jak to działa

Q'./1=,:L  " Count the number of characters after the dot and store it in L.     ";
0\         " Push 0 (denominator) and swap it with L (dummy value).              ";
{          "                                                                     ";
  ;        " Discard the topmost item from the stack (numerator or dummy value). ";
  )        " Increment the denominator.                                          ";
  _Qd*mo   " Multiply a copy by Double(Q) and round.                             ";
  _d2$/    " Cast a copy to Double and it divide it by the denominator.          ";
  LmO      " Round to L digits.                                                  ";
  Qd       " If the result is not Double(Q),                                     ";
}g         " repeat the loop.                                                    ";
./@        " Push a slash and rotate the denominator on top of it.               ";

T-SQL 254

Chociaż T-SQL tak naprawdę nie nadaje się do tego typu rzeczy, fajnie jest spróbować. Wydajność staje się naprawdę zła, im wyższy mianownik. Jest ograniczony do mianownika 1000.

Dane wejściowe to zmienna zmiennoprzecinkowa @

WITH e AS(SELECT *FROM(VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9),(0))n(n)),t AS(SELECT ROW_NUMBER()OVER(ORDER BY(SELECT \))N FROM e a,e b,e c,e d)SELECT TOP 1concat(n.n,'/',d.n)FROM t d,t n WHERE round(n.n/(d.n+.0),len(parsename(@,1)))=@ ORDER BY d.n,n.n

Podział zapytania

WITH                                      -- Start CTE(Common Table Expression)
 e AS(                                    --Create a set of 10 rows
   SELECT *
   FROM(VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9),(0))n(n)
 ),
 t AS(                                    
   SELECT ROW_NUMBER()OVER(ORDER BY(SELECT \))N 
   FROM e a,e b,e c,e d                   --Cross join e to produce 1000 numbered rows
 )
SELECT 
  TOP 1                                   --Grab first result
  concat(n.n,'/',d.n)                     --Build output
FROM t d,t n                              --Cross join t against itself for denominator and numerator
WHERE round(
  n.n/(d.n+.0),                           --Force float division with +.0
  len(parsename(@,1))                     --Get rounding length
  )=@                                     --Filter where the rounded result = input
ORDER BY d.n,n.n                          --Order by denominator then numerator

Haskell, 62 59

gdyby tylko imiona nie były tak długie ...

import Data.Ratio
f s=approxRational(read s)$50/10^length s

jest to funkcja zwracająca Rationalwartość.

wyjaśnienie: funkcja approxRationaljest funkcją, która pobiera liczbę zmiennoprzecinkową i zmiennoprzecinkową epsilon i zwraca najprostszą wartość racjonalną, która znajduje się w odległości epsilon odległości wejściowej. w zasadzie zwraca najprostsze przybliżenie liczby zmiennoprzecinkowej do wartości wymiernej w odległości „wybaczalnego błędu”.

wykorzystajmy tę funkcję do naszego użytku. w tym celu musimy dowiedzieć się, jaka jest powierzchnia pływaków, które zaokrąglają w górę do podanej liczby. to włączenie tej approxRationalfunkcji da nam odpowiedź.

spróbujmy na przykład 1.7. najniższy float, który zaokrągla do 1,7, wynosi 1,65. dowolna niższa nie zaokrągli się do 1,7. podobnie, górna granica pływaków zaokrąglających do 1,7 wynosi 1,75.
oba granice są granicami są liczbą wejściową +/- 0,05. łatwo można wykazać, że odległość ta jest zawsze 5 * 10 ^ -(the length of the input - 1)(-1 oznacza, że ​​na wejściu zawsze jest „.”). stąd kod jest dość prosty.

przypadki testowe:

*Main> map f ["1.7", "0.001", "3.1416"]
[5 % 3,1 % 667,355 % 113]

niestety nie działa na „0” ponieważ funkcja parsera Haskella nie rozpoznaje .znaku końca pływaka. można to naprawić dla 5 bajtów, zastępując read sprzez read$s++"0".

Rubin, 127 125 bajtów

f=->n{b=q=r=(m=n.sub(?.,'').to_r)/d=10**p=n.count('0-9')-1
b=r if(r=(q*d-=1).round.to_r/d).round(p).to_f.to_s==n while d>1
b}

Definiuje funkcję, fktóra zwraca wynik jako Rational. Np. Jeśli dodasz ten kod

p f["1.7"]
p f["0."]
p f["0.001"]
p f["3.1416"]

Dostajesz

(5/3)
(0/1)
(1/667)
(355/113)

Pętla jest ponad mianownikami. Zaczynam od pełnego ułamka, np. 31416/10000Dla ostatniego przykładu. Następnie zmniejszam mianownik, proporcjonalnie zmniejszam licznik (i zaokrąglam go). Jeśli powstałe racjonalne zaokrąglenie do tego samego, co liczba wejściowa, pamiętam nową najlepszą frakcję.

Mathematica, 49 53 znaków

Rationalize[ToExpression@#,5 10^(1-StringLength@#)]&@

Stosowanie:

Rationalize[ToExpression@#,5 10^(1-StringLength@#)]&@"1.7"

Wydajność:

5/3

Przypadki testowe:

input: 1.7     output: 5/3
input: 0.      output: 0
input: 0.001   output: 1/999
input: 3.1416  output: 355/113

Przypadek 0,001 wydaje mi się dziwny; ponieważ funkcja racjonalizacji nie działała zgodnie z jej opisem, gdy nie znalazła przypadku 1/667. Powinien generować liczbę o najmniejszym mianowniku, który mieści się w określonych granicach.

Python 2.7+, 111 znaków

Dowód, że możesz napisać okropny kod w dowolnym języku:

def f(s):
 t,e,y=float(s),50*10**-len(s),1;n=d=x=0
 while x|y:n,d=n+x,d+y;a=1.*n/d;x,y=a<t-e,a>t+e
 return n,d

Wydajność

>>> [f(s) for s in ("1.7", "0.", "0.001", "3.1416")]
[(5, 3), (0, 1), (1, 667), (355, 113)]

APL, 50

2↑⍎⍕(⍎x←⍞){50>|(10*⍴x)×⍺-⍵÷⍨n←⌊.5+⍺×⍵:n ⍵⋄''}¨⍳1e5

Tak długo jak się nie liczysz evali toStringjako pętle

Wyjaśnienie

Podejście polega na iteracji powyżej 1 do 10000 jako mianownika i obliczeniu licznika, który najbardziej pasuje do liczby zmiennoprzecinkowej, a następnie sprawdź, czy błąd mieści się w granicach. Na koniec wybierz najmniejszą parę ze wszystkich znalezionych frakcji.

(⍎x←⍞)Pobierz ciąg znaków z ekranu, przypisz do xi ewaluuj
⍳1e5Generuj tablicę od 1 do 10000
{...}¨Dla każdego elementu tablicy wywołaj z nią funkcję (⍎x←⍞)i argumenty (pętla)

⍺×⍵Pomnóż argumenty
⌊.5+Zaokrąglij (dodając 0,5, a następnie zaokrąglając w dół)
n←Przypisz do n
⍺-⍵÷⍨Podziel przez prawy argument, a następnie odejmij od lewego argumentu
(10*⍴x)×Pomnóż przez 10 do potęgi „długości x”
|Weź wartość bezwzględną
50>Sprawdź, czy mniej niż 50 (długość xwynosi 2 więcej niż liczba dp, więc użyj tutaj 50 zamiast 0,5)
:n ⍵⋄''Jeśli poprzednie sprawdzenie zwraca true, to zwróć tablicę ni odpowiedni argument, w przeciwnym razie zwróć pusty ciąg.

⍎⍕ toStringa następnie, evalaby uzyskać tablicę wszystkich liczb w tablicy
2↑Wybierz tylko pierwsze 2 elementy, czyli pierwszą znalezioną parę licznik-mianownik

GNU dc, 72 bajty

Bez pętli - dc nawet ich nie ma. Zamiast tego kontrola pochodzi z jednego makro rekurencyjnego ogona - idiomatycznego dla dc.

?dXAr^d2*sf*sq1sd0[ld1+sd]sD[r1+r]sN[dlf*ld/1+2/dlq>Ndlq<Dlq!=m]dsmxpldp

Wydajność:

$ for n in 1.7 0. 0.001 3.1416; do echo "    n = $n:"; dc unround.dc <<< $n; done
    n = 1.7:
5
3
    n = 0.:
0
1
    n = 0.001:
1
667
    n = 3.1416:
355
113
$ 

Uff Częściowe wyjaśnienie w tej odpowiedzi .

Mathematica, 111 znaków

f=Module[{a=0,b=1,k},While[Round[a/b,10^-(StringLength[#]-2)]!=(k=ToExpression)@#,If[N[a/b]>k@#,b++,a++]];a/b]&

Naprawdę proste, i nie sądzę, że nigdzie zbiega się tak szybko jak inne rozwiązania, ponieważ licznik i mianownik zwiększają się tylko o jeden. Głównie chciałem znaleźć proste rozwiązanie tego problemu. Będę musiał zobaczyć inne odpowiedzi i zobaczyć, jakie mądre rzeczy się tam zdarzają.

Wydajność

f/@{"1.7","0.0","0.001","3.1416","3.14"}
{5/3, 0, 1/667, 355/113, 22/7}

Czy ktoś tutaj obchodzi Dzień Zbliżenia Pi ?

Jabłkowy,> 300 bajtów

Chciałem to zrobić w języku, który natywnie wykonuje wymagane zaokrąglanie. Okazuje się, że Applescript pasuje do rachunku. Potem zobaczyłem wyliczenie rounding as taught in schooli nie mogłem się oprzeć jego użyciu, pomimo rażącej niekonkurencyjności Applescript do gry w golfa:

on u(q)
    set n to 0
    set d to 1
    set x to 0
    set AppleScript's text item delimiters to "."
    set f to 10 ^ (q's text item 2's length)
    repeat until x = q as real
        set x to (round n * f / d rounding as taught in school) / f
        if x < q then set n to n + 1
        if x > q then set d to d + 1
    end repeat
    return {n, d}
end u

log my u("1.7")
log my u("0.")
log my u("0.001")
log my u("3.1416")

Można to trochę pograć w golfa, ale prawdopodobnie nie warto.

Wydajność:

(*5, 3*)
(*0, 1*)
(*1, 667*)
(*355, 113*)

BC, 151 148 bajtów

Edycja - szybsza i krótsza wersja

define f(v){s=scale(x=v);for(i=r=1;i<=10^s;i+=1){t=v*i+1/2;scale=0;p=t/=1;scale=s+1;t=t/i+10^-s/2;scale=s;t=t/1-v;if((t*=-1^(t<0))<r){r=t;n=p;d=i}}}

ten sam przypadek testowy.

Wiele jest podobnych do poprzedniej wersji, ale zamiast wypróbować wszystkie możliwe kombinacje n / d, wspinamy się po resztkach v i ilorazach wstecznych wielokrotności m == v * d i mianownikach d. Znów precyzja obliczeń jest taka sama.

Oto nieplątane:

define f(v)
{
    s= scale(x=v)
    for( i=r=1; i <= 10^s; i+=1 ){
        t= v * i +1/2
        scale=0
        m=t/=1 # this rounded multiple becomes nominator if
               # backward quotient is first closest to an integer
        scale=s+1
        t= t / i +10^-s/2 # divide multiple back by denominator, start rounding again...
        scale=s
        t= t/1 - v # ...rounding done. Signed residue of backward quotient
        if( (t*= -1^(t < 0)) < r ){
            r=t
            n=m
            d=i
        }
    }
}

Ta wersja naprawdę ma tylko jedną pętlę i wykonuje tylko operacje arytmetyczne $ \ Theta \ left (\ operatorname {fractional_decimals} (v) \ right) $.

Oryginał - wersja wolna

Ta funkcja oblicza najmniejszy mianownik n i mianownik d tak, że ułamek n / d zaokrąglony do cyfr ułamkowych (v) jest równy danej wartości dziesiętnej v.

define f(v){s=scale(v);j=0;for(i=r=1;j<=v*10^s;){scale=s+1;t=j/i+10^-s/2;scale=s;t=t/1-v;if((t*=-1^(t<0))<r){r=t;n=j;d=i};if((i+=1)>10^s){i=1;j+=1}};v}

walizka testowa:

define o(){ print "Input ",x,"\tOutput ",n,"/",d,"\n" }
f(1.7); o()
> 0
> Input 1.7       Output 5/3
> 0
f(0.); o()
> 0
> Input 0 Output 0/1
> 0
f(0.001); o()
> 0
> Input .001      Output 1/667
> 0
f(3.1416); o()
> 0
> Input 3.1416    Output 355/113
> 0

A oto nie splątane:

define f(v)
{
    s=scale(x=v) # save in global for later print
    j=0
    # do a full sequential hill-climb over the residues r of v and all possible
    # fractions n / d with fractional_decimals(v) == s precision.
    for( i=r=1; j <= v * 10^s; ){
        scale=s+1
        t= j / i +10^-s/2 # start rounding...
        scale=s
        t= t/1 - v # ...rounding done. New residue, but still signed
        if( (t*= -1^(t < 0)) < r ){ # absolute residue better?
            # climb hill
            r=t
            n=j
            d=i
        }
        if( (i+=1) > 10^s ){ # next inner step. End?
            # next outer step
            i=1
            j+=1
        }
    }
    v
}

Przyznaję, trochę oszukiwałem, emulując drugą wewnętrzną pętlę wewnątrz pojedynczej zewnętrznej pętli, ale bez użycia dalszych instrukcji pętli. I właśnie dlatego faktycznie wykonuje operacje arytmetyczne $ \ Theta \ left (v \ nazwa operatora {ułamkowe_decymale} (v) ^ 2 \ right) $.

C 233

Działa to poprzez wywołanie funkcji racjonalizacji r () z początkowym mianownikiem 1. Funkcja zaczyna zwiększać licznik i sprawdzać przy każdym kroku, czy wynikowa liczba, po zaokrągleniu do tej samej liczby cyfr co oryginał, ma ten sam ciąg przedstawienie jako oryginał. Po zwiększeniu licznika tak bardzo, że wynik jest większy niż oryginał, funkcja zwiększa mianownik i wywołuje samą siebie.

To oczywiście wymaga znacznie więcej kodu, ale myślę, że duch problemu uwalnia od tego podejścia; z tego co wiemy, wewnętrzne funkcje racjonalizacji () współczesnych języków mają wiele wewnętrznych pętli.

Zauważ, że to nie działa dla wejścia „0”. ponieważ nie jest to standardowy sposób na pisanie liczb zmiennoprzecinkowych, więc kiedy ponownie zapisuje zmiennoprzecinkowe na łańcuch, wynikiem nigdy nie będzie „0”.

Specyfikacje chcą funkcji, która zwraca wartości zamiast po prostu wypisuje na ekran, stąd przekazywanie argumentów.

Kod (bez golfa):

void r(char* x, int* a, int* b) {
    int i = -1;
    char z[32];
    double v =atof(x);
    while(1) {
        i++;
        double y = ((double)i)/((double)(*b));
        double w;
        sprintf(z, "%.*f", strlen(strchr(x,'.'))-1, y);
        if(strcmp(x, z)==0) {
            *a = i;
            return;
        }
        w = atof(z);
        if(w > v) {
            (*b)++;
            r(x, a, b);
            return;
        }
    }
}

Stosowanie:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char* argv[]) {
    int num;
    int denom = 1; // start with a denominator of 1
    r(argv[1], &num, &denom);
    printf("%d/%d\n", num, denom);
    return 0;
}

Kod do gry w golfa:

typedef double D;
void r(char*x,int*a,int*b){int i=-1;char z[32];D v=atof(x);while(1){i++;D y=((D)i)/((D)(*b));D w;sprintf(z,"%.*f",strlen(strchr(x,'.'))-1,y);if(!strcmp(x,z)){*a=i;return;}w=atof(z);if(w>v){(*b)++;r(x,a,b);return;}}}

Pure Bash, 92 bajty

Jako częściowe wyjaśnienie tej odpowiedzi , tutaj jest przeniesiony do bash:

f=${1#*.}
q=${1//.}
for((n=0,d=1;x-q;x=2*10**${#f}*n/d+1>>1,n+=x<q,d+=x>q));{ :;}
echo $n/$d

Szczególnie:

• bash ma arytmetykę tylko liczb całkowitych. Więc odpowiednio skalujemy wszystko o 2 * 10 ^ (liczba cyfr ułamkowych).
• bash zaokrągla w dół do najbliższej liczby całkowitej; 2 w powyższym wyrażeniu oznacza, że ​​zamiast tego możemy zaokrąglić do najbliższej liczby całkowitej (w górę lub w dół ).
• Tylko jedna pętla
• sprawdzamy, czy racjonalne przekroczenie lub niedopasowanie dziesiętne i odpowiednio zwiększamy mianownik lub licznik.

Wydajność:

$ for n in 1.7 0. 0.001 3.1416; do echo "    n = $n:"; ./unround.sh $n; done
    n = 1.7:
5/3
    n = 0.:
0/1
    n = 0.001:
1/667
    n = 3.1416:
355/113
$ 

JavaScript (E6) 85

F=r=>(l=>{for(n=r,d=1;l&&r!=((n=r*d+1/2|0)/d).toFixed(l);d++);})(r.length-2)||[n|0,d]

Nie golfił

F=r=>{
  l = r.length-2; // decimal digits
  if (l==0) return [r|0, 1] // if no decimal return the same (conv to number) with denominator 1

  // loop for increasing denominator 
  for(d = 2; 
      r != ( // loop until find an equal result
      // given R=N/D ==> N=R*D
      (n=r*d+1/2|0) // find possible numerator, rounding (+0.5 and trunc)
      /d).toFixed(l); // calc result to given decimals
      d++);
  return [n,d]
}

Testuj w konsoli FireFox / FireBug

;["1.7","0.","0.001","3.1416","9.9999"].forEach(v => console.log(v,F(v)))

Wydajność

1.7 [5, 3]
0. [0, 1]
0.001 [1, 667]
3.1416 [355, 113]
9.9999 [66669, 6667]