Recíproco repetido

11

O que você precisa fazer é criar uma função / programa que use um decimal como entrada e produz o resultado de pegar repetidamente o inverso da parte fracionária do número, até que o número se torne um número inteiro.

Mais especificamente, o processo é o seguinte:

  1. Seja x a entrada

  2. Se x é um número inteiro, produza-o.

  3. Caso contrário: x1frac(x) . Volte para 2.

frac(x) é o componente fracionário dex e é igual axx . x é o piso de x, que é o maior número inteiro menor quex .

Casos de teste:

0 = 0
0.1 = 1/10 -> 10
0.2 = 1/5 -> 5
0.3 = 3/10 -> 10/3 -> 1/3 -> 3
0.4 = 2/5 -> 5/2 -> 1/2 -> 2
0.5 = 1/2 -> 2
0.6 = 3/5 -> 5/3 -> 2/3 -> 3/2 -> 1/2 -> 2
0.7 = 7/10 -> 10/7 -> 3/7 -> 7/3 -> 1/3 -> 3
0.8 = 4/5 -> 5/4 -> 1/4 -> 4
0.9 = 9/10 -> 10/9 -> 1/9 -> 9
1 = 1
3.14 = 157/50 -> 7/50 -> 50/7 -> 1/7 -> 7
6.28 = 157/25 -> 7/25 -> 25/7 -> 4/7 -> 7/4 -> 3/4 -> 4/3 -> 1/3 -> 3

Resumo de 0 a 1 em incrementos de 0,1: 0, 10, 5, 3, 2, 2, 2, 3, 4, 9, 1

Isso é , e o menor número de bytes vence.

Esclarecimentos:

  • "Pontos de bônus" para nenhum erro de arredondamento
  • Deve funcionar para qualquer número racional não negativo (ignorando o erro de arredondamento)
  • Você pode, mas não precisa executar as etapas executadas
  • Você pode considerar a entrada como decimal, fração ou par de números, que pode estar em uma sequência.

Desculpe por todos os problemas, esta é a minha primeira pergunta neste site.

Solomon Ucko
fonte
O fato de isso terminar está intimamente relacionado à possibilidade de expressar um decimal na fração continuada.
Leaky Nun
4
Esperamos produzir carros alegóricos? Eles causam algum problema de precisão.
Leaky Nun
7
Você poderia detalhar um pouco mais o processo? Estou inseguro quanto ao que "recíproca da parte fracionária do número" implica, e os casos de teste não ajuda muito
Ad Hoc Garf Hunter
4
Podemos usar dois números inteiros como entrada para representar um número racional?
Leaky Nun
1
Isso é igual ao elemento final da fração contínua simples da entrada.
Isaacg 02/07

Respostas:

5

J, 18 bytes

%@(-<.)^:(~:<.)^:_

Em J, o idioma u ^: v ^:_significa "Continue aplicando o verbo uenquanto a condição vretornar verdadeira.

No nosso caso, a condição final é definida pelo gancho ~:<., o que significa "o piso do número <.não é igual ~:ao número em si" - portanto, pararemos quando o verbo principal uretornar um int.

unesse caso, existe outro gancho -<.- o número menos seu piso - cujo valor de retorno é alimentado no @verbo recíproco %.

Experimente online!

Jonah
fonte
Também 18, mas tem algumas imprecisões de ponto flutuante por causa de tolerâncias presumivelmente: _2{(%@-<.) ::]^:a:.
cole
%@|~&1^:(~:<.)^:_
precisa saber é o seguinte
5

Python 3 , 101 bytes

lambda s:g(int(s.replace(".","")),10**s[::-1].index("."))
g=lambda a,b:a and(b%a and g(b%a,a)or b//a)

Experimente online!

Formato: a sequência deve conter um ponto decimal.

Freira Furada
fonte
.replace(".","")-> .replace(*"._")save 1 byte
tsh
5

Mathematica, 36 bytes

Last@*ContinuedFraction@*Rationalize

Demo

In[1]:= f = Last@*ContinuedFraction@*Rationalize

Out[1]= Last @* ContinuedFraction @* Rationalize

In[2]:= f[0]

Out[2]= 0

In[3]:= f[0.1]

Out[3]= 10

In[4]:= f[0.2]

Out[4]= 5

In[5]:= f[0.3]

Out[5]= 3

In[6]:= f[0.4]

Out[6]= 2

In[7]:= f[0.5]

Out[7]= 2

In[8]:= f[0.6]

Out[8]= 2

In[9]:= f[0.7]

Out[9]= 3

In[10]:= f[0.8]

Out[10]= 4

In[11]:= f[0.9]

Out[11]= 9

In[12]:= f[1]

Out[12]= 1
Anders Kaseorg
fonte
O que acontece sem Rationalize?
Greg Martin
1
@GregMartin Sem Rationalize, o Mathematica acha que não há precisão suficiente para gerar todos os termos da fração continuada. Por exemplo, ContinuedFraction[0.1]é justo {0}.
Anders Kaseorg
4

Perl 6 , 42 bytes

{($_,{1/($_-.floor)}...*.nude[1]==1)[*-1]}

Experimente online!

O nudemétodo regressa ao nu merator e de numerador de um número racional como uma lista de dois elementos. É mais curto obter o denominador dessa maneira do que chamar o denominatormétodo diretamente.

Sean
fonte
4

Haskell , 47 bytes

Isso supera a resposta do Assistente de Trigo, porque GHC.Realpermite padronizar a correspondência nos racionais usando :%, além de ter um nome mais curto

import GHC.Real
f(x:%1)=x
f x=f$1/(x-floor x%1)

Experimente online!

frecebe um Rationalnúmero como entrada, embora o ghc permita que eles sejam escritos em formato decimal, com certa precisão.

H.PWiz
fonte
4

Haskell , 40 34 bytes

Editar:

  • -6 bytes: @WheatWizard apontou que a fração provavelmente pode ser dada como dois argumentos separados.

(Não pude resistir a postar isso depois de ver as respostas Haskell com importações detalhadas - agora vejo que outras respostas em idiomas também estão essencialmente usando esse método.)

!pega dois argumentos inteiros (numerador e denominador da fração; eles não precisam estar nos menores termos, mas o denominador deve ser positivo) e retorna um número inteiro. Ligar como 314!100.

n!d|m<-mod n d,m>0=d!m|0<1=div n d

Experimente online!

  • Ignorando a incompatibilidade de tipos, a parte fracionária de n/d(assumindo dpositivo) é mod n d/d, portanto, a menos que mod n d==0, !retorne com uma representação de d/mod n d.
Ørjan Johansen
fonte
@WheatWizard Bem, eu interpretei "par" como tendo que ser um par, em vez de dois argumentos distintos. Suponho que seja uma interpretação excessivamente centrada em Haskell.
Ørjan Johansen
3

Python 3 + sympy , 67 bytes

from sympy import*
k=Rational(input())
while k%1:k=1/(k%1)
print(k)

Experimente online!

Sympy é um pacote simbólico de matemática para Python. Por ser simbólico e não binário, não há imprecisões de ponto flutuante.

HyperNeutrino
fonte
3

PHP , 69 bytes

for(;round(1e9*$a=&$argn)/1e9!=$o=round($a);)$a=1/($a-($a^0));echo$o;

Experimente online!

PHP , 146 bytes

for($f=.1;(0^$a=$argn*$f*=10)!=$a;);for(;1<$f;)($x=($m=max($a,$f))%$n=min($a,$f))?[$f=$n,$a=$x]:$f=!!$a=$m/$n;echo($o=max($a,$f))>1?$o:min($a,$f);

Experimente online!

Jörg Hülsermann
fonte
2

Geléia , 8 bytes

®İ$%1$©¿

Experimente online!

Imprecisões de ponto flutuante.

Erik, o Outgolfer
fonte
Boa sorte a fazê-lo para 0,7
Leaky Nun
@LeakyNun Essa sorte significa loops infinitos ou loops infinitos ...
Erik the Outgolfer
Use Mpara corrigir imprecisões de ponto flutuante: P . É Jelly, mas com precisão arbitrária em matemática. Porém, não corrige o loop 0,7.
HyperNeutrino
@HyperNeutrino M é uma versão desatualizada de Jelly.
Erik the Outgolfer
5 bytes
caird coinheringaahing
2

JavaScript ES6, 25 bytes

f=(a,b)=>a%b?f(b,a%b):a/b

Ligue f(a,b)paraa/b

l4m2
fonte
Se gcd(a,b)=1pode remover/b
l4m2
2

Haskell , 62 61 bytes

import Data.Ratio
f x|denominator x==1=x|u<-x-floor x%1=f$1/u

Experimente online!

Usa a Data.Ratiobiblioteca de Haskell para racionalidades de precisão arbitrárias. Se apenas os nomes incorporados não fossem tão longos.

Caçador Ad Hoc Garf
fonte
@ H.PWiz Nice! Eu estava tentando padronizar a correspondência Data.Ratio. Eu nunca ouvi falar disso GHC.Real. Sinta-se livre para postar isso como sua própria resposta.
Ad Hoc Garf Hunter
publicado
H.PWiz
1

APL (Dyalog Classic) , 18 bytes

{1e¯9>t1|⍵:⍵⋄∇÷t}

Experimente online!

APL NARS, 18 caracteres

-1 byte graças ao teste de Uriel

f←{1e¯9>t1|⍵:⍵⋄∇÷t}
v0 .1 .2 .3 .4 .5 .6 .7 .8 .9 1 3.14
⎕←vf¨v
  0 0  0.1 10  0.2 5  0.3 3  0.4 2  0.5 2  0.6 2  0.7 3  0.8 4  0.9 9  1 1  3.14 7 
RosLuP
fonte
⍵-⌊⍵1|⍵para um byte
Uriel
@Uriel obrigado ... Então, os bytes são como a solução J
RosLuP
1

Smalltalk, 33 bytes

[(y:=x\\1)>0]whileTrue:[x:=1/y].x
Leandro Caniglia
fonte
1

Stax , 8 bytes

ç▄é⌠á◙àù

Execute e depure

"Pontos de bônus" sem erros de precisão. Nenhuma aritmética de ponto flutuante usada. Isso (finalmente) faz uso do tipo racional embutido da stax.

recursivo
fonte
0

JavaScript, 70 bytes

x=>(y=(x+'').slice(2),p=(a,b)=>b?a%b?p(b,a%b):a/b:0,p(10**y.length,y))

Se pudermos alterar o tipo de entrada para uma string, ele poderá salvar 5 bytes.

tsh
fonte
Isso não funcionará para números> = 10. #
1100 Shaggy
@Shaggy Os números de suporte> 1 são necessários?
tsh
Sim, deve funcionar para qualquer número racional (ignorando o erro de arredondamento).
Solomon Ucko