História
Então, eu tenho um livro que quero separar da minha mesa com nada além de outros livros. Quero saber quantos livros eu preciso para conseguir isso com um comprimento de livros.
Aqui está uma visualização que meu amigo da Wolfram desenhou para mim:
Mais informações sobre o tópico em Wolfram e Wikipedia .
Desafio
Dada uma entrada inteira , imprima quantos livros são necessários para que o livro superior fique com comprimento de livro da tabela horizontalmente. ou
Encontre o menor valor inteiro de para a entrada na seguinte desigualdade.
n
n m ∑ i = 1 1
Editar: para frações, use pelo menos um ponto flutuante de precisão única IEEE. desculpe pelo desafio de edição após a postagem
( OEIS A014537 )
Casos de teste
1 4
2 31
3 227
5 12367
10 272400600
Respostas:
Oitava ,
414033 bytes1 byte salvo graças a @Dennis
Experimente online!
Explicação
Isso usa o fato de que os números harmônicos podem ser delimitados por uma função logarítmica.
Além disso, a
>=
comparação pode ser substituída por,>
porque os números harmônicos não podem ser inteiros (obrigado, @Dennis!).fonte
Python 3 , 35 bytes
Experimente online!
fonte
Casca , 8 bytes
Experimente online!
Como Husk usa números racionais quando pode, isso não tem problemas de ponto flutuante
Explicação
fonte
JavaScript, 30 bytes
Uma função recursiva, para que ela surja muito cedo.
Experimente online
fonte
Haskell, 38 bytes
fonte
Rápido , 65 bytes
Experimente online!
Ungolfed
fonte
R , 39 bytes
Experimente online!
Força Bruta!
fonte
Javascript (ES6), 34 bytes
Ungolfed
Casos de teste
Mostrar snippet de código
fonte
eval
declaração?eval
ai
variável terá de serreturn
ed no final, à custa de mais alguns bytes.Gelatina , 8 bytes
Isso é muito lento.
Experimente online!
fonte
Haskell,
714948 bytesA @BMO me salvou 22 bytes!
fonte
Julia 0.6 ,
3027 bytesExperimente online!
Só funciona
n = 6
, porque Julia não tem otimização de chamada de cauda.-3 bytes graças a Dennis .
fonte
TI-BASIC, 27 bytes
Solicita entrada ao usuário e exibe a saída na finalização. Nota:
⁻¹
é o token -1 (inverso).fonte
Ans
noN
imediato, em seguida,Input N
ouPrompt N
é um método de entrada que você economiza um byte maisAns→N
. EM
pode ser substituído porAns
, para que1→M
se torne1
eM+1→M
se torneAns+1
. (Mas eu sou cético sobre uma saída emAns
que não são exibidas - veja este - então talvez terminando com:Ans
é apropriado:., Em seguida, o valor será exibido no lugar de "Done")Ans→N
era engraçado. Otimizações agradáveis. Também tomou seu conselho sobre a saída apenas para ser seguro. Ainda sai com uma rede -3 bytes: D05AB1E , 11 bytes
Experimente online!
Explicação
fonte
Pitão , 10 bytes
Experimente online!
Extremamente lento.
Pitão , 10 bytes
Experimente online!
fonte
Japonês , 12 bytes
O mesmo comprimento, mas um pouco mais eficiente que, a opção recursiva.
Tente
Explicação
fonte
J, 22 bytes
-6 bytes graças ao frownyfrog
Experimente online!
resposta original
A resposta de Luis em J:
Ungolfed
Principalmente curioso para ver se ele pode ser melhorado drasticamente ( tosse paging miles)
Explicação
Experimente online!
fonte
1+]i.~[:<.
->1+]I.~
->I.~0,
I.~0+/\@,
PHP, 35 bytes
Execute-o usando a CLI:
fonte
Wolfram Language (Mathematica) , 40 bytes
Experimente online!
fonte
Java 8, 49 bytes
Explicação:
Experimente online. (Tempo limite para os casos de teste acima
n=7
.)fonte
tinylisp , 98 bytes
A última linha é uma função lambda sem nome que pega o número de comprimentos de livros e retorna o número de livros necessários. Experimente online!
Explicação
O único tipo de dado numérico tinylisp é o número inteiro; portanto, calculamos a série harmônica como uma fração, acompanhando o numerador e o denominador. Em cada etapa,
N
é o numerador,D
é o denominador ek
é o índice da soma. Queremos que a nova soma parcial sejaN/D + 1/k
, ou(N*k + D)/(D*k)
. Assim, recorremos a um novo numerador deN*K + D
, um novo denominador deD*k
e um novo índice dek+1
.A recursão deve parar quando a soma parcial for maior ou igual ao
#
número desejado de comprimentos de livros. Neste ponto, já fomos longe demais em um livro, então voltamosk-1
. A condição é1/2 * N/D < #
; multiplicando o denominador, obtemosN < D*#*2
, que é a maneira mais divertida de escrevê-lo.A função auxiliar recursiva
_
faz todos esses cálculos; a principal função é apenas um de um argumento invólucro que as chamadas_
com os valores iniciais corretos parak
,N
, eD
.fonte