Esta tarefa é sobre escrever código para calcular exatamente uma probabilidade. A saída deve ser uma probabilidade precisa escrita como uma fração em sua forma mais reduzida. Ou seja, nunca deve produzir, 4/8
mas sim 1/2
.
Para um número inteiro positivo n
, considere uma sequência uniformemente aleatória de 1s e -1s de comprimento n
e chame-a de A. Agora concatene A
seu primeiro valor. Ou seja, A[1] = A[n+1]
se a indexação de 1. A
agora tiver comprimento n+1
. Agora considere também uma segunda sequência aleatória de comprimento n
cujos primeiros n
valores sejam -1, 0 ou 1 com probabilidade 1 / 4,1 / 2, 1/4 cada e chame-a de B.
Por exemplo, considere n=3
. Valores possíveis para A
e B
poderiam ser A = [-1,1,1,-1]
e B=[0,1,-1]
. Nesse caso, os dois produtos internos são 0
e 2
.
Agora considere o produto interno de A[1,...,n]
e B
e o produto interno de A[2,...,n+1]
e B
.
Seu código deve gerar a probabilidade de que ambos os produtos internos sejam zero.
Pois n=1
essa probabilidade é clara 1/2
.
Não me importo como n
é especificado no código, mas deve ser muito simples e óbvio como alterá-lo.
Línguas e bibliotecas
Você pode usar qualquer idioma e bibliotecas que desejar. Gostaria de executar o seu código, portanto, inclua uma explicação completa de como executar / compilar seu código no linux, se possível.
n
seriam úteis. Talvez também um exemplo explícito de A, B e dos dois produtos internos possa ajudar.n=4
conta como zero, dois ou três bytes? A saída precisa ser exatamentea/b
ou seria[a b]
, por exemplo, permitida?n
? Caso contrário, acho que isso não é permitido.Respostas:
Pitão,
48474644 bytesExperimente online: Demonstração
A versão online provavelmente não computa
n=6
. No meu laptop (versão offline), leva cerca de 45 segundos.Abordagem de força bruta.
Explicação:
fonte
+0r1_2
é mais curto que/R2r2_2
.Mathematica,
159100878685 bytesPara mudar
n
basta alterar a definição da variável no início.Como a força bruta é bastante lenta, mas aqui estão os oito primeiros resultados:
O último já levou 231 segundos e o tempo de execução é terrivelmente exponencial.
Explicação
Como eu disse, é força bruta. Basicamente, estou apenas enumerando tudo possível
A
eB
calcule os dois produtos de ponto para cada par possível e, em seguida, encontre a fração de pares que produziu{0, 0}
. As funções combinatória e de álgebra linear do Mathematica foram bastante úteis no golfe:Isso gera todas as n-tuplas que contêm
1
ou-1
, ou seja, tudo possívelA
. Poisn = 3
isso é:Para calcular
B
, fazemos quase o mesmo:Repetindo
0
, duplicamos cada tupla para cada um0
que contém, aumentando assim a0
probabilidade de duas vezes1
ou-1
. Novamente usandon = 3
como exemplo:Agora, para cada possível
A
, queremos o produto escalar de cada uma delas possívelB
, comA[1 .. n]
eA[2 .. n+1]
. Por exemplo, se nossa atualA
é{1, 1, -1}
, queremos o produto escalar com ambos{1, 1, -1}
e com{1, -1, 1}
. Como todas as nossasB
já são convenientemente as linhas de uma matriz, queremos as duas sublistasA
como colunas de outra matriz, para que possamos calcular um simples produto de ponto entre elas. Mas a transposição{{1, 1, -1}, {1, -1, 1}}
simplesmente fornece{{1, 1}, {1, -1}, {-1, 1}}
qual é apenas uma lista de todas as sublistas cíclicas de 2 elementosA
. É o que isso faz:Então calculamos isso e pegamos o produto escalar com nossa lista de
B
. Como agora obtemos uma lista aninhada (uma vez que cada possívelA
gera um vetor separado), as aplainamos##&@@
.Para saber se um par
{x, y}
é{0, 0}
calculamosSign[Norm[{x,y}]]
ondeNorm
dá√(x²+y²)
. Isso dá0
ou1
.Finalmente, uma vez que agora só quero saber as frações de
1
s em uma lista de0
s e1
s toda necessidade que é a média aritmética da lista. No entanto, isso gera a probabilidade de que pelo menos um produto de ponto seja diferente de zero, então subtraímos1
para obter o resultado desejado.fonte
Pitão -
6555 bytesCorrigido o erro com redução de fração ao custo de um byte.
Usa a abordagem de força bruta e pode jogar muito golfe, mas só queria obter algo por aí. Muito devagar
Ele usa produtos cartesianos para gerar ambos
A
eB
, fazendo as probabilidades variáveis, fazendo0
aparecer duas vezes na lista de fontes e, em seguida, conta como zero o produto interno. O produto interno é facilitado peloV
açúcar sintático da ectorização. Simplificar a fração estava me assustando inicialmente, mas era bastante fácil com aP
função de fatoração de rime e a percepção de que só precisamos reduzir por potências de 2.Experimente online aqui .
fonte
n
?CJam,
5857545146 bytesPara executá-lo, insira o número inteiro desejado entre
WX]
em*
.Obrigado a @ jimmy23013 pela mágica dos bits e por jogar fora 5 bytes!
Experimente on-line no intérprete CJam .
Idéia
A maioria das partes dessas respostas é direta, mas usa dois truques:
Em vez de emparelhar todos os vetores de {-1, 1} n com todos os vetores de {-1, 0, 1} n com as probabilidades desejadas, considera-se contar o número de trigêmeos de vetores em {-1, 1} n que satisfazem uma certa condição.
Se adicionarmos os dois últimos vetores de um trigêmeo, o resultado será um vetor de {-2, 0, 2} n .
Desde (-1) + 1 = 0 = 1 + (-1) , 0 s ocorrerá duas vezes tão frequentemente quanto -2 s e 2 s.
Dividir cada componente por 2 produziria um vetor de {-1, 0, 1} n com as probabilidades desejadas.
Como estamos interessados apenas se o produto escalar for 0 ou não, podemos pular a divisão por 2 .
Depois de contar todos os trigêmeos que satisfazem a condição da pergunta e o número total de trigêmeos, temos que reduzir a fração resultante.
Em vez de calcular o MDC de ambos os números, como o denominador sempre terá uma potência de 2, basta dividir os dois números pela potência mais alta de 2 que divide o numerador.
Para obter a potência mais alta de 2 que divide x , podemos tomar o AND bit a bit de x e ~ x + 1 .
~ x inverte todos os bits de X , então todos os arrasto 0 s tornam-se 1 s. Ao adicionar 1 a ~ x , esses 1 s voltarão a 0 se o último 1 em ~ x + 1 corresponderá ao último 1 em x .
Todos os outros bits são 0 de distintos, portanto, AND bit a bit retorna o número inteiro que consiste no último 1 de x e em todos os 0 s que o seguem. Esta é a potência mais alta de 2 que divide x .
Código
fonte
WX]m*Zm*_{~.+2,@fm<\f.*::+0-!},,__W*&:T/'/@,T/
.