Temos um número de ponto flutuante r
entre 0 e 1 e um número inteiro p
.
Encontre a fração de números inteiros com o menor denominador, que se aproxima r
com pelo menos p
precisão de dois dígitos.
- Entradas:
r
(um número de ponto flutuante) ep
(inteiro). - Saídas:
a
eb
inteiros, em quea/b
(flutuante) aproxima-ser
até osp
dígitos.b
é o menor número inteiro positivo possível.
Por exemplo:
- se
r=0.14159265358979
ep=9
, - então o resultado é
a=4687
eb=33102
, - porque
4687/33102=0.1415926530119026
.
Qualquer solução precisa funcionar em teoria com tipos de precisão arbitrária, mas as limitações causadas pelos tipos de precisão fixa das implementações não importam.
Precisão significa o número de dígitos após " 0.
" dentro r
. Assim, se r=0.0123
e p=3
, então, a/b
deve começar com 0.012
. Se os primeiros p
dígitos da parte fracionária de r
forem 0, o comportamento indefinido será aceitável.
Critérios de vitória:
- O algoritmo algoritmicamente mais rápido vence. A velocidade é medida em O (p).
- Se houver vários algoritmos mais rápidos, os ganhos mais curtos.
- Minha própria resposta está excluída do conjunto dos possíveis vencedores.
Ps a parte de matemática é realmente muito mais fácil, ao que parece, sugiro ler este post.
fonte
padEnd
ematch
? Você não pode apenasslice
cada corda no comprimento correto e depois subtraí-las?padEnd
é usado para testcasef(0.001,2)
ef(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]}
(não totalmente jogado).Haskell , O (10 p ) na pior das hipóteses
121119 bytesExperimente online!
Economizou 2 bytes graças a Laikoni
Eu usei o algoritmo de /math/2432123/how-to-find-the-fraction-of-integers-with-the-smallest-denominator-matching-an-i .
A cada etapa, o novo intervalo é metade do intervalo anterior. Assim, o tamanho do intervalo é
2**-n
onden
está a etapa atual. Quando2**-n < 10**-p
, temos a certeza de ter a aproximação correta. No entanto, sen > 4*p
então2**-n < 2**-(4*p) == 16**-p < 10**-p
. A conclusão é que o algoritmo éO(p)
.EDIT Como apontado pelo orlp em um comentário, a reivindicação acima é falsa. No pior dos casos,
r = 1/10**p
(r= 1-1/10**p
é similar), haverá10**p
etapas:1/2, 1/3, 1/4, ...
. Existe uma solução melhor, mas não tenho tempo agora para corrigir isso.fonte
f=
e salvar dois bytes comz<-floor.(*10^p),u<-a+c,v<-b+d
.f=
no TIO no código Haskell.-cpp
sinalizador do compilador e escreverf=\
no cabeçalho: Experimente online!C, 473 bytes (sem contexto), O (p), não concorrente
Esta solução usa a parte matemática detalhada neste excelente post. Eu calculei apenas
calc()
no tamanho da resposta.fonte