Ułamki okrągłe

22

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
wada
źródło
1
Ale w językach funkcjonalnych nie ma czegoś takiego jak pętla. Przykład wroga w haskell repeattworzy nieskończoną listę argumentów. Wydaje się, że zapętla się, ale faktycznie ma złożoność czasową O (1). Ale myślę, że sortowanie każdego przypadku z osobna jest lepsze niż niedozwolone języki funkcjonalne.
dumny haskeller
3
Nie podoba mi się obecna definicja „pętli”. Na przykład w Pythonie for n in numbers: f(g(n))jest równoważne z map(f, map(g, numbers)). Wersja funkcjonalna używa mapdwa razy, czy naprawdę należy to zabronić?
trzęsienie ziemi
1
@ MartinBüttner Mówiłem o sprawie, w której języki funkcjonalne zostałyby niedozwolone z powodu niejasności
dumny haskeller
1
Przykro mi, że tak naprawdę nie mogę przyczynić się do tej dyskusji, ponieważ moja wiedza na temat programowania funkcjonalnego jest w zasadzie zerowa. Jeśli masz rozwiązanie, którego nie jesteś pewien, czy jest ono zgodne z „zasadami”, prześlij je mimo to! W końcu ma to być zabawne i edukacyjne wyzwanie!
flawr
2
@Dennis Nie, to było niefortunne sformułowanie, możesz przesłać je w dowolnej formie, a główną ideą tego paragrafu było to, że nie powinieneś mieć wady, jeśli twój język zajmuje więcej bajtów na „odczytanie” liczby wejściowej.
flawr

Odpowiedzi:

4

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

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
MickyT
źródło
+1. Kocham to. Włożyłem 3.14159i to dało mi właściwie355/113
Tom Chantler
1
+1 Nigdy nie spodziewałem się, że zobaczę tutaj język SQL !!!
flawr
@TomChantler Podejrzewam, że masz na myśli w końcu :)
MickyT
@ flawr Szczerze mówiąc, nie myślałem, że to zadziała ... jednak metoda bardzo brutalnej siły.
MickyT
12

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".

dumny haskeller
źródło
Jest to interesująca funkcja. Zwykle takie funkcje istnieją w celu znalezienia najlepszego racjonalnego przybliżenia liczby w jak najmniejszej liczbie kroków, co jest możliwe do udowodnienia przy użyciu obciętych ciągłych reprezentacji ułamkowych. Alternatywnie, znalezienie frakcji o najniższym mianowniku jest bardziej akademicką ciekawostką. Zazwyczaj nikt nie spodziewałby się, że znajdzie ją jako standardową funkcję biblioteki.
COTO,
4
@ COTO To jest Haskell, jest pełen badań akademickich.
dumny haskeller
7

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ę.

Martin Ender
źródło
4

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.

Zestawienie
źródło
2
haha Użyłem dokładnie tego samego rozwiązania. szkoda, że ​​w Haskell jest dłużej. btw, nie wygląda na to, żeby twoje rozwiązanie pobierało ciąg znaków jako dane wymagane przez spec.
dumny haskeller
Czekaj, wejście było ciągiem? Cholera, to znaczy, że mogę wyciągnąć kilka rzeczy z kodu.
Tally
Twoje wyjście dla 0.001nie pasuje do OP, ponieważ Rationalizenie jest ograniczone, aby zminimalizować mianownik. Jak wspomniałem dumnemu Haskellerowi, racjonalna funkcja aproksymacji polegająca na zminimalizowaniu mianownika jest wysoce ezoteryczna (krótko mówiąc, jest to kiepski i nieefektywny sposób przybliżania liczb). Zwykle nie spodziewałbym się, że będzie to standardowa funkcja biblioteki.
COTO,
@COTO Zgodnie z docs to ma zminimalizować mianownik chociaż.
Martin Ender
@ MartinBüttner: Wydaje się to interesujące 1/999. 999 staje się (akceptowalnym) najniższym mianownikiem tylko dla błędu między z grubsza 1e-6 a 2e-6. Granica błędu to wyraźnie 5e-4. Więc cokolwiek Mathematica robi w tym przypadku, zdecydowanie nie działa zgodnie ze specyfikacją. : P
COTO,
4

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)]
Steve
źródło
3

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

TwiNight
źródło
2

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 .

Cyfrowa trauma
źródło
2

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 ?

krs013
źródło
Nie, obchodzę tylko dzień zbliżenia tau. = P Ale właśnie zauważyłem, że | 355/113 - pi | <10 ^ -6 =)
błąd
2

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*)
Cyfrowa trauma
źródło
2

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

Franki
źródło
1
prawdopodobnie powinieneś przenieść nową wersję na przód posta
dumny haskeller
@proudhaskeller zrobione
Franki
1

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;}}}
RT
źródło
w rzeczywistości w implementacji biblioteki Haskell ( hackage.haskell.org/package/base-4.7.0.1/docs/src/… ), definicja approxRationalma tylko jedną rekurencyjną funkcję pomocniczą i nie więcej zapętla.
dumny haskeller
cóż, myliłem się, faktycznie ma dwie rekurencyjne funkcje pomocnicze, ale według specyfikacji jest w porządku
dumny haskeller
Nie próbowałem powiedzieć, że czyjeś rozwiązania były nieprawidłowe, chciałem tylko opublikować takie bez wbudowanej racjonalizacji :)
RT
oczywiście, ale fakt, że sama definicja nie ma pętli, jest przyjemny i tak naprawdę, napisałeś w swoim poście „o ile wiemy, wewnętrzne funkcje racjonalizacji () współczesnych języków mają wiele wewnętrznych pętli”. więc to sprawdziłem.
dumny haskeller
w każdym razie, jak działa rozwiązanie?
dumny haskeller
1

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
$ 
Cyfrowa trauma
źródło
Powinien być dość prosty - inttylko port do c
Digital Trauma
1

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]
edc65
źródło