Desafio
Dado um número inteiro positivo N
, produza a soma dos primeiros N
recíprocos como uma fração exata, que é representada como um par de números inteiros em uma ordem consistente, representando numerador e denominador.
Regras
A saída deve ser exata.
A saída deve ser como um par de números inteiros em uma ordem consistente, representando numerador e denominador.
É proibido o uso de tipos numéricos não inteiros (integrados ou biblioteca).
- Esclarecimento / exceção: tipos numéricos não inteiros são válidos se, e somente se, todos os valores usados, computados e retornados forem números inteiros (por exemplo, seu idioma usa números racionais por padrão, mas você só usa aritmética inteira em sua resposta)
A saída deve ser o mais reduzida possível. (
3/2
está tudo bem,6/4
não está)As brechas padrão são proibidas.
Os envios devem funcionar para entradas de no mínimo 20, ou essa meta , o que for maior.
Casos de teste
1: 1/1
2: 3/2 (1/1 + 1/2)
3: 11/6 (1/1 + 1/2 + 1/3)
4: 25/12 etc.
5: 137/60
6: 49/20
20: 55835135/15519504
56: 252476961434436524654789/54749786241679275146400
226: 31741146384418617995319820836410246588253008380307063166243468230254437801429301078323028997161/5290225078451893176693594241665890914638817631063334447389979640757204083936351078274058192000
Geração de casos de teste (Python 3)
import fractions
def f(x):
return sum(fractions.Fraction(1,i) for i in range(1,x+1))
Semelhante a este desafio e este desafio .
Os numeradores são OEIS A001008 e os denominadores são OEIS A002805 .
code-golf
math
rational-numbers
pizzapants184
fonte
fonte
gcd
uma "função interna" se o seu idioma fornecer?gcd
e outras funções internas estão bem. Tipos racionais / fracionários não são permitidos.Respostas:
Python 2 ,
8079 bytesExperimente online!
Imprime o numerador e o denominador.
Yay! Suporte MathJax !!!! Observa-se:
Então, pensando em recursão, para positivo, no umerador:n
N
e não se pode deixar de pensar non!
D
enominador recursivamente também; assim o .exec
Devemos pagar o Piper de frações reduzidas com um cálculo de GCD no
while
loop; e então terminamos.fonte
Gelatina , 10 bytes
Experimente online!
Como funciona
fonte
J , 16 bytes
Experimente online!
Executar exemplos
Como funciona
J , 9 bytes, usando o tipo de fração
Experimente online!
J fornece frações para a divisão int-int, se não divisível.
fonte
2 x:1#.1%1+i.
como uma resposta válida ou é um uso inválido de um tipo racional?05AB1E , 10 bytes
Experimente online!
Usa o mesmo método que todas as outras entradas. A saída está no formulário
[denominator, numerator]
.fonte
Wolfram Language (Mathematica) , 30 bytes
Experimente online!
14 bytes se tipos fracionários internos forem permitidos
Experimente online!
fonte
InputForm@HarmonicNumber
(24 bytes) fornece saída no formato fornecido pelo OP.JavaScript (ES6), 60 bytes
Retorna
[numerator, denominator]
.Experimente online!
Quão?
O método é semelhante à resposta Python do @ ChasBrown .
atén = 0 .
Nós economizamos( a , b ) para dentro ( p , q) e depois calcular a ← gcd ( a , b ) com:
atéb = 0 .
Finalmente retornamos o numerador reduzidop / a e denominador reduzido q/ a .
fonte
Perl 6 ,
5753 bytesExperimente online!
Um bloco de código anônimo que pega um número inteiro e retorna uma tupla de
denominator, numerator
.Se nos fosse permitido usar tipos fracionários, seria o 32 byter muito mais simples:
Experimente online!
fonte
Oitava , 29 bytes
Experimente online!
fonte
C ++ 17 (gcc) , 108 bytes
Use apenas aritmética inteira:
Experimente online!
C ++ 17 (gcc) , 108 bytes
Experimente online!
O mesmo que abaixo, mas use C ++ 17's
std::gcd
.C ++ (gcc) , 109 bytes
Experimente online!
Como o C ++ não possui suporte nativo ao bigint, isso definitivamente excederá
n>20
.Exigir:
import
declaração obsoleta do gcc .std::__gcd
.-O0
(Acho que sim) caso contrário, o compilador será otimizadod/=a
.long
.Explicação:
a*d
para número inteiro mais próximo, lançandoa*d+.5
paralong
, e atribuir an
. Agoran/d
é a saída.std::__gcd
.fonte
auto a=0.
vez dedouble a=0
(1 char a menos)?Pari / GP , 34 bytes
Experimente online!
17 bytes se tipos fracionais internos forem permitidos
Experimente online!
fonte
MATL, 13 bytes
Experimente no MATL Online
O mesmo método usado na resposta do @Dennis 'Jelly .
(Saída implícita, imprime o denominador primeiro e depois o numerador.)
Imprecisões de ponto flutuante significam que isso não funciona para n = 20, porque os valores intermediários são muito grandes.Parece que a saída do caso de teste foi um erro de digitação, isso retorna a mesma resposta que as outras respostas para n = 20.Aqui está uma versão de preservação de tipo inteiro (25 bytes) que tentei enquanto isso, antes de descobrir isso:
25 bytes, entrada até 43
Experimente online!
Faz a conversão dos números
uint64
antes de operá-los, faz a aritmética explicitamente em um loop (sem usarprod
ousum
). Mais importante, divide os numeradores e denominadores parciais pelo seu CDG a cada passo ao longo do caminho, no final de cada iteração. Isso aumenta a faixa de entrada para permitirn
até 43. Parte do código é baseada na resposta Python do @Chas Brown.Método alternativo (original) usando LCM em vez de fatorial:
1615 bytesExperimente no MATL Online
fonte
Excel VBA, 141 bytes
Leva entradas
[A1]
e saídas para o console.Sem Golfe e Comentado
fonte
dc , 87 bytes
Experimente online!
Isso deixa o numerador e o denominador no topo da pilha nessa ordem, conforme permitido por esse padrão de saída. Como
dc
não possui umgcd
built-in, isso utiliza o algoritmo euclidiano para calcular ogcd
.fonte
Stax , 11 bytes
Execute e depure
Explicação:
Queremos calcular:
Agora precisamos de um denominadorb e uma lista de numeradores umaEu :
Podemos fazerb = n ! , então nós temos:
Então nós temos:
fonte
APL (NARS), 56 caracteres, 112 bytes
teste:
Em poucas palavras, reduza "a função soma em 2 números de fração" (um número de fração é uma lista de 2 números inteiros) no conjunto:
isso abaixo parece errado:
mas se eu alterar o tipo de entrada do que:
fonte
APL (Dyalog Unicode) ,
1512 bytesExperimente online!
Função tácita, usando um único argumento
⍵
. Salva um byte removendo o⌽
se for permitido imprimir o denominador primeiro.Obrigado @dzaima por 3 bytes.
Quão:
fonte