Cette tâche consiste à écrire du code pour calculer exactement une probabilité. La sortie doit être une probabilité précise écrite sous forme de fraction dans sa forme la plus réduite. C'est-à-dire qu'il ne devrait jamais sortir 4/8mais plutôt 1/2.

Pour un entier positif n, considérez une chaîne uniformément aléatoire de 1 et -1 de longueur net appelez-la A. Maintenant, concaténez à Asa première valeur. C'est A[1] = A[n+1]si l'indexation à partir de 1. a Amaintenant une longueur n+1. Considérons maintenant également une deuxième chaîne aléatoire de longueur ndont les premières nvaleurs sont -1, 0 ou 1 avec probabilité 1 / 4,1 / 2, 1/4 chacune et appelons-la B.

Par exemple, réfléchissez n=3. Les valeurs possibles pour Aet Bpourraient être A = [-1,1,1,-1]et B=[0,1,-1]. Dans ce cas, les deux produits intérieurs sont 0et 2.

Considérons maintenant le produit intérieur de A[1,...,n]et Bet le produit intérieur de A[2,...,n+1]et B.

Votre code doit générer la probabilité que les deux produits internes soient nuls.

Car n=1cette probabilité est clairement 1/2.

Cela ne me dérange pas comment nest spécifié dans le code, mais il devrait être très simple et évident comment le changer.

Langues et bibliothèques

Vous pouvez utiliser n'importe quelle langue et bibliothèque de votre choix. Je voudrais exécuter votre code, veuillez donc inclure une explication complète sur la façon d'exécuter / compiler votre code sous Linux si possible.

Pyth, 48 47 46 44 octets

K,smlf!|Fms*Vd.>Tk2^,1_1Q^+0tM3Q^8Qj\//RiFKK

Essayez-le en ligne: Démonstration

La version en ligne ne calcule probablement pas n=6. Sur mon ordinateur portable (version hors ligne), cela prend environ 45 secondes.

Approche par force brute.

Explication:

smlf!|Fms*Vd.>Tk2^,1_1Q^+0tM3Q   implicit: Q = input number
                          tM3    the list [-1, 0, 1]
                        +0       add zero, results in [0, -1, 0, 1]
                       ^     Q   all possible lists of length Q using these elements
 m                               map each list d (B in Lembik's notation) to:
                  ,1_1              the list [1, -1]
                 ^    Q             all possible lists of length Q
   f                                filter for lists T (A in Lembik's notation),
                                    which satisfy:
       m        2                      map each k in [0, 1] to:
        s*Vd.>Tk                          scalar-product d*(shifted T by k)
    !|F                                not or (True if both scalar-products are 0)      
  l                                 determine the length                
s                                add all possibilities at the end

K,...^8QQj\//RiFKK   
 ,...^8Q             the list [result of above, 8^Q]
K                    store it in K
              iFK    determine the gcd of the numbers in K
            /R   K   divide the numbers in K by the gcd
         j\/         join the two numbers by "/" and print

Mathematica, 159 100 87 86 85 octets

n=3;1-Mean@Sign[##&@@Norm/@({1,0,0,-1}~t~n.Partition[#,2,1,1])&/@{1,-1}~(t=Tuples)~n]

Pour changer, changez nsimplement la définition de la variable au début.

Comme c'est la force brute, c'est assez lent, mais voici les huit premiers résultats:

n   P(n)
1   1/2
2   3/8
3   7/32
4   89/512
5   269/2048
6   903/8192
7   3035/32768
8   169801/2097152

Le dernier a déjà pris 231 secondes et le temps d'exécution est horriblement exponentiel.

Explication

Comme je l'ai dit, c'est de la force brute. Essentiellement, j'énumère tout ce qui est possible Aet Bcalcule les deux produits scalaires pour chaque paire possible, puis trouve la fraction de paires qui a donné {0, 0}. La combinatoire et les fonctions d'algèbre linéaire de Mathematica ont été très utiles pour jouer au golf:

{1,-1}~(t=Tuples)~n

Cela génère tous les n-tuples contenant 1ou -1, c'est-à-dire tous les possibles A. Car n = 3c'est:

{{1, 1, 1}, 
 {1, 1, -1}, 
 {1, -1, 1}, 
 {1, -1, -1}, 
 {-1, 1, 1}, 
 {-1, 1, -1}, 
 {-1, -1, 1}, 
 {-1, -1, -1}}

Pour calculer, Bnous faisons presque la même chose:

{1,0,0,-1}~t~n

En répétant 0, nous dupliquons chaque tuple pour chacun 0qu'il contient, ce qui rend 0deux fois plus probable que 1or -1. En utilisant à nouveau n = 3comme exemple:

{{-1, -1, -1},
 {-1, -1, 0}, {-1, -1, 0},
 {-1, -1, 1},
 {-1, 0, -1}, {-1, 0, -1},
 {-1, 0, 0}, {-1, 0, 0}, {-1, 0, 0}, {-1, 0, 0},
 {-1, 0, 1}, {-1, 0, 1},
 {-1, 1, -1},
 {-1, 1, 0}, {-1, 1, 0},
 {-1, 1, 1},
 {0, -1, -1}, {0, -1, -1},
 {0, -1, 0}, {0, -1, 0}, {0, -1, 0}, {0, -1, 0},
 {0, -1, 1}, {0, -1, 1},
 {0, 0, -1}, {0, 0, -1}, {0, 0, -1}, {0, 0, -1},
 {0, 0, 0}, {0, 0, 0}, {0, 0, 0}, {0, 0, 0}, {0, 0, 0}, {0, 0, 0}, {0, 0, 0}, {0, 0, 0},
 {0, 0, 1}, {0, 0, 1}, {0, 0, 1}, {0, 0, 1},
 {0, 1, -1}, {0, 1, -1},
 {0, 1, 0}, {0, 1, 0}, {0, 1, 0}, {0, 1, 0},
 {0, 1, 1}, {0, 1, 1},
 {1, -1, -1},
 {1, -1, 0}, {1, -1, 0},
 {1, -1, 1},
 {1, 0, -1}, {1, 0, -1},
 {1, 0, 0}, {1, 0, 0}, {1, 0, 0}, {1, 0, 0},
 {1, 0, 1}, {1, 0, 1},
 {1, 1, -1},
 {1, 1, 0}, {1, 1, 0},
 {1, 1, 1}}

Maintenant, pour chaque possible A, nous voulons le produit scalaire de chacun de ces possibles B, à la fois avec A[1 .. n]et A[2 .. n+1]. Par exemple, si notre courant Aest {1, 1, -1}, nous voulons le produit scalaire avec {1, 1, -1}et avec {1, -1, 1}. Puisque tous nos Bsont déjà commodément les lignes d'une matrice, nous voulons que les deux sous-listes soient des Acolonnes d'une autre matrice, afin de pouvoir calculer un simple produit scalaire entre elles. Mais la transposition {{1, 1, -1}, {1, -1, 1}}donne simplement {{1, 1}, {1, -1}, {-1, 1}}ce qui n'est qu'une liste de toutes les sous-listes cycliques à 2 éléments de A. Voilà ce que cela fait:

Partition[#,2,1,1]

Nous calculons donc cela et prenons le produit scalaire avec notre liste de B. Puisque nous obtenons maintenant une liste imbriquée (puisque chaque possible Adonne un vecteur séparé), nous aplatissons ceux avec ##&@@.

Pour savoir si une paire {x, y}est, {0, 0}nous calculons Sign[Norm[{x,y}]] où Normdonne √(x²+y²). Cela donne 0ou 1.

Enfin, puisque nous voulons maintenant simplement connaître les fractions de 1s dans une liste de 0s et 1s, tout ce dont nous avons besoin est la moyenne arithmétique de la liste. Cependant, cela donne la probabilité qu'au moins un produit scalaire soit différent de zéro, nous le soustrayons donc 1pour obtenir le résultat souhaité.

Pyth - 65 55 octets

Correction d'un bug avec une réduction de fraction au prix d'un octet.

Utilise une approche par force brute et peut être joué au golf énormément, mais je voulais juste obtenir quelque chose. Très lent

*F-KP/Jmms*Vked,thdPhd*makhk^,1_1Q^[1ZZ_1)Q,ZZ2/lJ^2/K2

Il utilise des produits cartésiens pour générer les deux Aet B, faisant les probabilités variables en faisant 0apparaître deux fois dans la liste source, puis compte ceux qui produisent le produit à zéro. Le produit intérieur est facilité par le Vsucre syntaxique d'ectorisation. Simplifier la fraction me faisait peur au départ, mais c'était assez facile avec la Pfonction de factorisation du givre et la prise de conscience que nous n'avons qu'à réduire par des puissances de 2.

Essayez-le en ligne ici .

CJam, 58 57 54 51 46 octets

WX]m*Zm*_{~.+2,@fm<\f.*::+0-!},,__~)&:T/'/@,T/

Pour l'exécuter, insérez l'entier souhaité entre WX]et m*.

Merci à @ jimmy23013 pour le peu de magie et pour avoir joué 5 octets!

Essayez-le en ligne dans l' interpréteur CJam .

Idée

La plupart des parties de ces réponses sont simples, mais elles utilisent deux astuces intéressantes:

• Au lieu d'appairer tous les vecteurs de {-1, 1} ⁿ avec tous les vecteurs de {-1, 0, 1} ⁿ avec les probabilités souhaitées, il considère le nombre de triplets de vecteurs dans {-1, 1} ⁿ qui satisfont une certaine condition.

  Si nous ajoutons les deux derniers vecteurs d'un triplet, le résultat sera un vecteur de {-2, 0, 2} ⁿ .

  Puisque (-1) + 1 = 0 = 1 + (-1) , 0 s se produira deux fois plus souvent que -2 s et 2 s.

  La division de chaque composante par 2 donnerait un vecteur de {-1, 0, 1} ⁿ avec les probabilités souhaitées.

  Puisque nous ne sommes intéressés que si le produit scalaire est 0 ou non, nous pouvons sauter la division par 2 .

• Après avoir compté tous les triplets satisfaisant la condition de la question et le nombre total de triplets, nous devons réduire la fraction résultante.

  Au lieu de calculer le GCD des deux nombres, puisque le dénominateur sera toujours une puissance de 2, il suffit de diviser les deux nombres par la puissance la plus élevée de 2 qui divise le numérateur.

  Pour obtenir la puissance la plus élevée de 2 qui divise x , nous pouvons prendre le ET au niveau du bit de x et ~ x + 1 .

  ~ x inverse tous les bits de x , donc tous les 0 de fin deviennent 1 s. En ajoutant 1 à ~ x , ces 1 s redeviendront 0 s et le dernier 1 dans ~ x + 1 correspondra au dernier 1 dans x .

  Tous les autres bits sont tous les deux 0 de différents, donc le ET au niveau du bit renvoie l'entier composé du dernier 1 de x et de tous les 0 qui le suivent. Il s'agit de la puissance la plus élevée de 2 qui divise x .

Code

WX]    e# Push the array [-1 1].
       e# Insert N here.
m*     e# Cartesian product: Push the array of all vectors of {-1,1}^N.
Zm*    e# Cartesian product: Push the array of all triplets of these vectors.
_      e# Copy the array.
{      e# Filter; for each triplet of vectors U, V and W in {-1,1}^N:
  ~    e#   Dump U, V and W on the stack.
  .+   e#   Compute X := V + W, a vector of {-2,0,2}^N, where each component is
       e#   zero with probability 1/2.
  2,@  e#   Push [0 1]. Rotate U on top of it.
  fm<  e#   Push [U U'], where U' is U rotated one dimension to the left.
  \f.* e#   Push [U*X and U'*X], where * denotes the vectorized product.
  ::+  e#   Add the components of both products.
  0-   e#   Remove zeroes.
       e#   Push the logical NOT of the array.
},     e#   If the array was empty, keep the triplet.
,      e# Push X, the length of the filtered array.
__~)&  e# Push X & ~X + 1.
:T     e# Save the result in T and divide X by T.
'/     e# Push a slash.
@,T/   e# Dividet he length of the unfiltered array by T.