У нас есть число с плавающей запятой r
от 0 до 1 и целое число p
.
Найти дробь целых чисел с наименьшим знаменателем, которая аппроксимируется r
с p
точностью не менее цифры.
- Входные данные:
r
(число с плавающей запятой) иp
(целое число). - Выходы:
a
иb
целые числа, гдеa/b
(как float) приблизительноr
доp
цифр.b
является возможным наименьшим таким положительным целым числом.
Например:
- если
r=0.14159265358979
иp=9
, - тогда результат
a=4687
иb=33102
, - потому что
4687/33102=0.1415926530119026
.
Любое решение должно теоретически работать с типами произвольной точности, но ограничения, вызванные типами с фиксированной точностью реализации, не имеют значения.
Точность означает количество цифр после " 0.
" в r
. Таким образом, если r=0.0123
и p=3
, то a/b
следует начать с 0.012
. Если первые p
цифры дробной части r
0, неопределенное поведение приемлемо.
Критерии выигрыша:
- Алгоритмически быстрый алгоритм выигрывает. Скорость измеряется в O (p).
- Если есть несколько самых быстрых алгоритмов, то самый короткий выигрывает.
- Мой собственный ответ исключен из множества возможных победителей.
Ps математическая часть на самом деле намного проще, как кажется, я предлагаю прочитать этот пост.
источник
padEnd
иmatch
? Разве вы не можете простоslice
каждую строку на правильную длину, а затем вычесть их?padEnd
используется для тестаf(0.001,2)
иf(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]}
(не полностью гольф).Haskell , O (10 p ) в худшем случае
121119 байтПопробуйте онлайн!
Сохранено 2 байта благодаря Laikoni
Я использовал алгоритм из /math/2432123/how-to-find-the-fraction-of-integers-with-the-smallest-denominator-matching-an-i .
На каждом шаге новый интервал составляет половину предыдущего интервала. Таким образом, интервал размер
2**-n
, гдеn
находится текущий шаг. Когда2**-n < 10**-p
мы обязательно получим правильное приближение. Еще еслиn > 4*p
потом2**-n < 2**-(4*p) == 16**-p < 10**-p
. Вывод таков, что алгоритм естьO(p)
.РЕДАКТИРОВАТЬ Как указал orlp в комментарии, утверждение выше ложно. В худшем случае
r = 1/10**p
(r= 1-1/10**p
аналогично), будет10**p
шаги:1/2, 1/3, 1/4, ...
. Есть лучшее решение, но сейчас у меня нет времени, чтобы это исправить.источник
f=
и сэкономить два байтаz<-floor.(*10^p),u<-a+c,v<-b+d
.f=
на TIO в коде на Haskell.-cpp
флаг компилятора и написатьf=\
в шапке: Попробуйте онлайн!C, 473 байта (без контекста), O (p), не конкурирует
Это решение использует математическую часть, подробно описанную в этом прекрасном посте. Я рассчитал только
calc()
на размер ответа.источник