A árvore Stern-Brocot é uma árvore binária de frações, onde cada fração é adquirida adicionando os numeradores e denominadores das duas frações vizinhas nos níveis acima.
É gerado iniciando com 0/1
e 1/0
como "frações de ponto final" e, a partir daí, iterando colocando uma fração entre cada par consecutivo de frações adicionando os numeradores e denominadores dessas frações, da seguinte forma:
0. 0/1 1/0
1. 0/1 1/1 1/0
2. 0/1 1/2 1/1 2/1 1/0
3. 0/1 1/3 1/2 2/3 1/1 3/2 2/1 3/1 1/0
4. 0/1 1/4 1/3 2/5 1/2 3/5 2/3 3/4 1/1 4/3 3/2 5/3 2/1 5/2 3/1 4/1 1/0
Em cada iteração da árvore Stern-Brocot (a n
iteração), existem 2^n + 1
elementos na sequência aos quais podemos atribuir uma fração de 0/2^n
para 2^n/2^n
. Cada nova iteração simplesmente insere uma fração "na metade" entre cada par de frações consecutivas.
Isso faz da árvore de Stern-Brocot um mapeamento individual entre os números racionais positivos e as frações binárias entre 0 e 1, servindo também como prova de que os dois conjuntos têm a mesma cardinalidade.
Sua tarefa é escrever um programa ou função que, dado o numerador e o denominador de um número racional positivo em termos mais baixos, determine a fração binária que corresponde à posição dessa fração na árvore Stern-Brocot.
Exemplos de entradas e saídas são fornecidos abaixo:
2/3 -> 3/8 (4th number in iteration 3)
4/7 -> 9/32 (between 1/2 and 3/5 in the chart above)
1/1 -> 1/2 (middle number in the first iteration)
Entradas que você não precisa oferecer suporte, mas estão incluídas para referência:
0/1 -> 0/1 (0/1 is considered the left number)
1/0 -> 1/1 (1/0 is considered the rightmost number)
O programa mais curto em qualquer idioma para atingir esse objetivo vence.
1/1 => 1
,1/2 => 2
,2/1 => 3
,1/3 => 4
, etc.). Se o número assim gerado para um nó forn
, então2^lg n
(log binário) será o bit mais alto configuradon
e a fração binária desejada será(2*(n - 2^lg n) + 1) / 2^(lg n + 1)
. (Qualquer pessoa que tente uma solução de assembler em um conjunto de instruções com um bit de maior valor definido provavelmente desejará usar essa abordagem).Respostas:
GolfScript (
49 4846 caracteres)ou
Ambas são funções que pegam o numerador e o denominador na pilha e deixam o numerador e o denominador na pilha. Demonstração online .
A idéia central é expressa em pseudocódigo na seção Concrete Mathematics 4.5 (p122 em minha edição):
Se a sequência de Ls e Rs é interpretada como um valor binário com L = 0 e R = 1, o dobro desse valor mais um é o numerador e o denominador é um pouco mais longo.
Como um ponto de interesse para os Golfscripters, essa é uma daquelas raras ocasiões em que considero útil o desdobramento. (Ok, eu apenas o uso como contador de loop, mas é melhor que nada).
fonte
Mathematica,
130 114111 caracteresExemplo:
fonte
Ruby,
132125Rubied & golfed a solução de referência da @JoeZ.
Exemplos de uso:
fonte
Ruby (69 caracteres)CoffeeScript (59 caracteres)Esta é uma função que recebe numerador e denominador como argumentos e retorna uma matriz que contém o numerador e o denominador após a bijeção.
Demonstração online
Ele usa a mesma abordagem da minha solução GolfScript acima, mas é muito mais legível, porque eu posso usar 4 variáveis sem ter que me preocupar com boxe e unboxing em uma matriz. Eu escolhi o CoffeeScript porque ele não prefixa variáveis com
$
(20 caracteres salvos, por exemplo, PHP), possui uma sintaxe curta de definição de função que permite valores de parâmetro padrão (portanto, não há necessidade de agruparf(a,b,x,y)
uma funçãog(a,b) = f(a,b,0,1)
) e me permite usar Booleans como números inteiros em expressões com valores úteis. Para quem não conhece, o CoffeeScript não possui o operador ternário padrão do estilo C (C?P:Q
), mas posso substituí-loC&&P||Q
aqui, porqueP
nunca será falso.Uma alternativa sem dúvida mais elegante, mas indiscutivelmente menos curta, é substituir a subtração repetida por divisão e módulo:
(65 caracteres; demonstração online ). Escrever dessa maneira expõe o relacionamento com o algoritmo de Euclides.
fonte
a<b
quais economiza um caractere. Inliningc
dá outros dois. Você também pode considerar a sintaxef=->a,b,x=0,y=1{...}
para uma definição ainda mais curta.c=a<b ?
com um espaço extra depoisb
. Caso contrário, o ponto de interrogação é tratado como parte dob
.Python - 531
Uma solução não destruída em Python, para servir como uma solução de referência de último lugar:
Ele simplesmente faz uma pesquisa binária entre frações, aproveitando o fato de que a mediana de quaisquer duas frações sempre estará entre os valores dessas duas frações.
fonte
GolfScript, 54 caracteres
A entrada deve ser fornecida no STDIN no formato especificado na tarefa. Você pode tentar o código online .
fonte
Mathematica 138
Não é tão simples quanto o procedimento de alefalpha, mas foi o melhor que pude produzir até agora.
Teste
fonte
JavaScript 186
poderia ser menor, mas eu gosto de golfe legível
fonte
Haskell , 125 bytes
Experimente online!
Entrada e saída na forma de um par
(n,d)
.Breve explicação:
n
constrói a próxima linha da anterior, olhando para cada par de frações e inserindo a nova entre a primeira e a recursão (que colocará a segunda fração ali). O caso base é muito simples, pois é basicamente apenas a função de identidade. At
função itera essa função indefinidamente com base no estado inicial com apenas as duas frações de limite.t
depois indexa cada linha (i
) e cada item da linha (j
) e procura a primeira fração que corresponde ao que estamos procurando. Quando encontra, cedej
como numerador e2^i
como denominador.fonte