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 n
oznacza 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 n
cyfr (co oznacza n-1
cyfry 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 for
lub while
lub goto
itp.), A także pętli funkcjonalnych, takich jak map
lub, fold
któ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
repeat
tworzy 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.for n in numbers: f(g(n))
jest równoważne zmap(f, map(g, numbers))
. Wersja funkcjonalna używamap
dwa razy, czy naprawdę należy to zabronić?Odpowiedzi:
CJam,
414036 bajtówZakłada, że ciąg wejściowy jest przechowywany w Q, co jest wyraźnie dozwolone w pytaniu. Wypróbuj online.
Przypadki testowe
Jak to działa
źródło
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 @
Podział zapytania
źródło
3.14159
i to dało mi właściwie355/113
Haskell,
6259gdyby tylko imiona nie były tak długie ...
jest to funkcja zwracająca
Rational
wartość.wyjaśnienie: funkcja
approxRational
jest 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
approxRational
funkcji 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:
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ącread s
przezread$s++"0"
.źródło
Rubin,
127125 bajtówDefiniuje funkcję,
f
która zwraca wynik jakoRational
. Np. Jeśli dodasz ten kodDostajesz
Pętla jest ponad mianownikami. Zaczynam od pełnego ułamka, np.
31416/10000
Dla 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ę.źródło
Mathematica,
4953 znakówStosowanie:
Wydajność:
Przypadki testowe:
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.
źródło
0.001
nie pasuje do OP, ponieważRationalize
nie 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.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ą. : PPython 2.7+, 111 znaków
Dowód, że możesz napisać okropny kod w dowolnym języku:
Wydajność
źródło
APL, 50
Tak długo jak się nie liczysz
eval
itoString
jako pętleWyjaś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 dox
i ewaluuj⍳1e5
Generuj 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 don
⍺-⍵÷⍨
Podziel przez prawy argument, a następnie odejmij od lewego argumentu(10*⍴x)×
Pomnóż przez 10 do potęgi „długościx
”|
Weź wartość bezwzględną50>
Sprawdź, czy mniej niż 50 (długośćx
wynosi 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ęn
i odpowiedni argument, w przeciwnym razie zwróć pusty ciąg.⍎⍕
toString
a następnie,eval
aby uzyskać tablicę wszystkich liczb w tablicy2↑
Wybierz tylko pierwsze 2 elementy, czyli pierwszą znalezioną parę licznik-mianownikźródło
GNU dc, 72 bajty
Bez pętli - dc nawet ich nie ma. Zamiast tego kontrola pochodzi z jednego makro rekurencyjnego ogona - idiomatycznego dla dc.
Wydajność:
Uff Częściowe wyjaśnienie w tej odpowiedzi .
źródło
Mathematica, 111 znaków
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ść
Czy ktoś tutaj obchodzi Dzień Zbliżenia Pi ?
źródło
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 school
i nie mogłem się oprzeć jego użyciu, pomimo rażącej niekonkurencyjności Applescript do gry w golfa:Można to trochę pograć w golfa, ale prawdopodobnie nie warto.
Wydajność:
źródło
BC,
151148 bajtówEdycja - szybsza i krótsza wersja
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:
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.
walizka testowa:
A oto nie splątane:
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) $.
źródło
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):
Stosowanie:
Kod do gry w golfa:
źródło
approxRational
ma tylko jedną rekurencyjną funkcję pomocniczą i nie więcej zapętla.Pure Bash, 92 bajty
Jako częściowe wyjaśnienie tej odpowiedzi , tutaj jest przeniesiony do bash:
Szczególnie:
Wydajność:
źródło
int
tylko port do cJavaScript (E6) 85
Nie golfił
Testuj w konsoli FireFox / FireBug
Wydajność
źródło