Esta tarea consiste en escribir código para calcular exactamente una probabilidad. El resultado debe ser una probabilidad precisa escrita como una fracción en su forma más reducida. Es decir, nunca debería salir, 4/8
sino más bien 1/2
.
Para un número entero positivo n
, considere una cadena uniformemente aleatoria de 1s y -1s de longitud n
y llámela A. Ahora concatene a A
su primer valor. Es decir, A[1] = A[n+1]
si la indexación desde 1. A
ahora tiene longitud n+1
. Ahora también considere una segunda cadena aleatoria de longitud n
cuyos primeros n
valores son -1, 0 o 1 con probabilidad 1 / 4,1 / 2, 1/4 cada uno y llámelo B.
Por ejemplo, considere n=3
. Los posibles valores de A
y B
podrían ser A = [-1,1,1,-1]
y B=[0,1,-1]
. En este caso, los dos productos internos son 0
y 2
.
Ahora considere el producto interno de A[1,...,n]
y B
y el producto interno de A[2,...,n+1]
y B
.
Su código debe generar la probabilidad de que ambos productos internos sean cero.
Por n=1
esta probabilidad es clara 1/2
.
No me importa cómo n
se especifica en el código, pero debería ser muy simple y obvio cómo cambiarlo.
Idiomas y bibliotecas
Puede usar cualquier idioma y bibliotecas que desee. Me gustaría ejecutar su código, así que incluya una explicación completa sobre cómo ejecutar / compilar su código en Linux si es posible.
n
serían útiles. También puede ser útil un ejemplo explícito de A, B y los dos productos internos.n=4
cuenta como cero, dos o tres bytes? ¿La salida tiene que ser exactamentea/b
o[a b]
, por ejemplo, estar permitida?n
? De lo contrario, creo que eso no está permitido.Respuestas:
Pyth,
48474644 bytesPruébelo en línea: demostración
La versión en línea probablemente no computa
n=6
. En mi computadora portátil (versión fuera de línea) toma alrededor de 45 segundos.Enfoque de fuerza bruta.
Explicación:
fuente
+0r1_2
es más corto que/R2r2_2
.Mathematica,
159100878685 bytesPara cambiar,
n
simplemente cambie la definición de la variable al principio.Como es la fuerza bruta, es bastante lenta, pero aquí están los primeros ocho resultados:
El último ya tomó 231 segundos y el tiempo de ejecución es terriblemente exponencial.
Explicación
Como dije, es fuerza bruta. Esencialmente, solo enumero todos los posibles
A
yB
, calculo los dos productos de puntos para cada par posible y luego encuentro la fracción de pares que produjo{0, 0}
. Las funciones de combinatoria y álgebra lineal de Mathematica fueron bastante útiles para jugar golf:Esto genera todas las n-tuplas que contienen
1
o-1
, es decir, todas las posiblesA
. Porn = 3
eso es:Para calcular
B
hacemos casi lo mismo:Repitiendo
0
, duplicamos cada tupla para cada uno0
que contiene, con lo que0
el doble de probabilidades1
o-1
. Nuevamente usandon = 3
como ejemplo:Ahora, para cada posible
A
, queremos el producto escalar de cada uno de esos posiblesB
, conA[1 .. n]
yA[2 .. n+1]
. Por ejemplo, si nuestro actualA
es{1, 1, -1}
, queremos el producto de punto con ambos{1, 1, -1}
y con{1, -1, 1}
. Como todos nuestrosB
ya son convenientemente las filas de una matriz, queremos que las dos sublistas seanA
como columnas de otra matriz, para que podamos calcular un simple producto de puntos entre ellas. Pero la transposición{{1, 1, -1}, {1, -1, 1}}
simplemente da{{1, 1}, {1, -1}, {-1, 1}}
cuál es solo una lista de todas las sublistas cíclicas de 2 elementosA
. Eso es lo que hace esto:Entonces calculamos eso y tomamos el producto punto con nuestra lista de
B
. Como ahora obtenemos una lista anidada (dado que cada posibleA
produce un vector separado), los aplanamos con##&@@
.Para averiguar si un par
{x, y}
es{0, 0}
, calculamosSign[Norm[{x,y}]]
dóndeNorm
da√(x²+y²)
. Esto da0
o1
.Por último, ya que ahora sólo queremos saber las fracciones de
1
s en una lista de0
s y1
S Todo lo que necesitamos es la media aritmética de la lista. Sin embargo, esto produce la probabilidad de que al menos un producto de punto sea distinto de cero, por lo que lo restamos1
para obtener el resultado deseado.fuente
Pyth -
6555 bytesError solucionado con reducción de fracción al costo de un byte.
Utiliza un enfoque de fuerza bruta, y se puede jugar mucho al golf, pero solo quería obtener algo. Muy lento
Utiliza productos cartesianos para generar ambos
A
yB
, haciendo las probabilidades variables haciendo0
aparecer dos veces en la lista fuente y luego cuenta las que ese producto interno a cero. El producto interno se hace fácil por elV
azúcar sintáctico de ectorización. Simplificar la fracción me estaba asustando inicialmente, pero fue bastante fácil con laP
función de Factorización de tiempo y la comprensión de que solo tenemos que reducir en potencias de 2.Pruébelo en línea aquí .
fuente
n
?CJam,
5857545146 bytesPara ejecutarlo, inserte el número entero deseado entre
WX]
ym*
.¡Gracias a @ jimmy23013 por la poca magia y por jugar golf en 5 bytes!
Pruébelo en línea en el intérprete de CJam .
Idea
La mayoría de las partes de estas respuestas son sencillas, pero utiliza dos trucos geniales:
En lugar de emparejar todos los vectores de {-1, 1} n con todos los vectores de {-1, 0, 1} n con las probabilidades deseadas, considera el número de tripletas de vectores en {-1, 1} n que satisfacen Una cierta condición.
Si sumamos los dos últimos vectores de un triplete, el resultado será un vector de {-2, 0, 2} n .
Como (-1) + 1 = 0 = 1 + (-1) , 0 s ocurrirá el doble de veces que -2 sy 2 s.
Dividir cada componente por 2 produciría un vector de {-1, 0, 1} n con las probabilidades deseadas.
Como solo estamos interesados si el producto escalar es 0 o no, podemos omitir la división por 2 .
Después de contar todos los trillizos que satisfacen la condición de la pregunta y el número total de trillizos, tenemos que reducir la fracción resultante.
En lugar de calcular el MCD de ambos números, dado que el denominador siempre será una potencia de 2, es suficiente dividir ambos números por la potencia más alta de 2 que divide el numerador.
Para obtener la mayor potencia de 2 que divide x , podemos tomar el AND bit a bit de x y ~ x + 1 .
~ x invierte todos los bits de x , por lo que todos los 0 s finales se convierten en 1 s. Al agregar 1 a ~ x , esos 1 s volverán a ser 0 sy el último 1 en ~ x + 1 coincidirá con el último 1 en x .
Todos los demás bits son 0 o distintos, por lo que el bit a bit Y devuelve el entero que consiste en el último 1 de x y todos los 0 s que le siguen. Esta es la potencia más alta de 2 que divide x .
Código
fuente
WX]m*Zm*_{~.+2,@fm<\f.*::+0-!},,__W*&:T/'/@,T/
.