Mamy liczbę zmiennoprzecinkową z zakresu r
od 0 do 1 oraz liczbę całkowitą p
.
Znajdź ułamek liczb całkowitych o najmniejszym mianowniku, który aproksymuje r
z przynajmniej p
cyfrową precyzją.
- Dane wejściowe:
r
(liczba zmiennoprzecinkowa) ip
(liczba całkowita). - Wyjścia:
a
ib
liczby całkowite, gdziea/b
(jako liczba zmiennoprzecinkowa) jest przybliżanar
dop
cyfr.b
jest możliwą najmniejszą taką dodatnią liczbą całkowitą.
Na przykład:
- jeśli
r=0.14159265358979
ap=9
, - Następnie wynik jest
a=4687
ib=33102
, - dlatego
4687/33102=0.1415926530119026
.
Każde rozwiązanie musi działać teoretycznie z typami o dowolnej precyzji, ale ograniczenia wynikające z typów o stałej precyzji implementacji nie mają znaczenia.
Precyzja oznacza liczbę cyfr po „ 0.
” w r
. Tak więc, jeśli r=0.0123
i p=3
, to a/b
należy zacząć od 0.012
. Jeśli pierwsze p
cyfry części ułamkowej r
są równe 0, nieokreślone zachowanie jest dopuszczalne.
Kryteria wygranej:
- Algorytm najszybszy algorytm wygrywa. Prędkość jest mierzona w O (p).
- Jeśli istnieje wiele najszybszych algorytmów, wygrywa najkrótszy.
- Moja własna odpowiedź jest wykluczona z listy możliwych zwycięzców.
Ps część matematyczna jest w rzeczywistości o wiele łatwiejsza, jak się wydaje, proponuję przeczytać ten post.
źródło
padEnd
imatch
? Czy nie możesz po prostuslice
każdego łańcucha do odpowiedniej długości, a następnie odjąć je?padEnd
służy do testcasef(0.001,2)
if(0.3,2)
.(r,p)=>{for(a=0,b=1;`${a/b}`.slice(0,p+2)-`${r}`.slice(0,p+2);a/b<r?a++:b++);return[a,b]}
(nie w pełni golfa).Haskell , O (10 p ) w najgorszym przypadku
121119 bajtówWypróbuj online!
Zaoszczędzono 2 bajty dzięki Laikoni
Użyłem algorytmu z /math/2432123/how-to-find-the-fraction-of-integers-w--the-smallest-denominator-matching-an-i .
Na każdym kroku nowy interwał stanowi połowę poprzedniego interwału. Zatem rozmiar interwału to
2**-n
, gdzien
jest bieżący krok. Kiedy z2**-n < 10**-p
pewnością będziemy mieć odpowiednie przybliżenie. Ale jeślin > 4*p
to2**-n < 2**-(4*p) == 16**-p < 10**-p
. Wniosek jest taki, że algorytm jestO(p)
.EDYCJA Jak wskazał orlp w komentarzu, powyższe twierdzenie jest fałszywe. W najgorszym przypadku
r = 1/10**p
(r= 1-1/10**p
podobnie), nie będzie10**p
etapy:1/2, 1/3, 1/4, ...
. Jest lepsze rozwiązanie, ale nie mam teraz czasu, aby to naprawić.źródło
f=
i zaoszczędzić dwa bajtyz<-floor.(*10^p),u<-a+c,v<-b+d
.f=
z TIO w kodzie Haskell.-cpp
flagę kompilatora i napisaćf=\
w nagłówku: Wypróbuj online!C, 473 bajtów (bez kontekstu), O (p), niekonkurujące
To rozwiązanie wykorzystuje część matematyczną opisaną w tym znakomitym poście. Przeliczyłem tylko
calc()
na rozmiar odpowiedzi.źródło