Existe-t-il un formulaire fermé disponible pour le tableau suivant?

Question

Ci-dessous est une table qui a une relation récursive que la valeur actuelle de la cellule est la somme de la cellule supérieure et gauche.

je souhaite trouver des positions impaires pour toute ligne donnée désignée par v(x) comme représenté dans la première colonne.

Actuellement, je maintiens deux tableaux que je mets à jour avec de nouvelles valeurs de somme et en vérifiant littéralement si chaque valeur de position est impaire ou paire. Y a-t-il une forme fermée qui permette de dire directement quelles sont les positions impaires disponibles (disons, pour la 4e rangée, auquel cas il faut me dire que p1 et p4 sont les endroits impairs). Puisqu'il suit un modèle particulier, je suis certain qu'il doit exister une forme fermée qui me dirait mathématiquement les positions plutôt que de calculer chaque valeur et de la vérifier.

Toute aide est appréciée. Merci.

Answer 1

Les nombres que vous regardez sont les nombres dans le triangle de Pascal, juste rotation quatre-vingt dix degrés. Vous plus généralement le voir écrit comme ceci:

   1 
      1 1 
      1 2 1 
     1 3 3 1 
     1 4 6 4 1 
    1 5 10 10 5 1 
    1 6 15 20 15 6 1 
1 7 21 35 35 21 7 1 
      ... 

Vous réduisons le triangle de Pascal le long des bandes rayures diagonales allant sur la gauche (ou droite, selon votre point de vue), et la question que vous posez est de savoir comment pour trouver les positions des nombres impairs dans chaque bande.

Il existe un résultat mathématique appelé Lucas's theorem qui est utile pour déterminer si une entrée donnée dans le triangle de Pascal est paire ou impaire. L'entrée dans la rangée m, colonne n du triangle de Pascal est donnée par (m choisi n), et le théorème de Lucas dit que (m choisir n) mod 2 (1 si le nombre est impair, 0 sinon) peut être trouvé en comparant les bits de m et n. Si n a un bit défini dans une position où m n'a pas ce bit défini, alors (m choose n) est pair. Sinon, (m choisir n) est impair. Par exemple, essayons (5 choisissez 3). Les bits de 5 sont 101. Les bits de 3 sont 011. Comme le bit 2 de 3 est activé et que le bit 2 de 5 n'est pas défini, la quantité (5, choisissez 3) doit être paire. Et puisque (5 choisir 3) = 10, on voit que c'est bien le cas!

En utilisant les opérateurs relationnels pseudocode, vous voulez essentiellement les éléments suivants:

if ((~m & n) != 0) { 
    // Row m, entry n is even 
} else { 
    // Row m, entry n is odd. 
}