Je prévois un programme C ++ qui prend 3 chaînes qui représentent un puzzle cryptarithmétrique. Par exemple, donné deux, deux et quatre, le programme trouverait des substitutions de chiffres pour chaque lettre de sorte que l'expression mathématique soit vraie, les intrants supposés être justifiés. Une façon d'aller à ce sujet, ce serait bien sûr de la force de brute, attribuant chaque substitution possible pour chaque lettre avec des boucles imbriquées, en essayant la somme de manière répétée, etc. jusqu'à ce que la réponse soit enfin trouvée. Ma pensée est que cependant inefficace terriblement inefficace, la boucle sous-jacente peut être une voie réalisable (ou même nécessaire) à utiliser - après une série de déductions étant effectuées pour limiter les domaines de chaque variable. Je trouve qu'il est un peu difficile de visualiser, mais il serait raisonnable d'assumer d'abord une structure générale / rembourrée comme celle-ci (chaque X représente un chiffre non nécessairement distinct, et chaque C est un chiffre de transport, qui, dans ce cas, sera soit 0 ou 1)? : avec cela à l'esprit, d'autres pensées de planification: - Les zéros de premier plan ne seront pas donnés dans le problème, je devrais probablement ajouter Assez d'entre eux, le cas échéant, les opérandes de l'extérieur / match. -Je pense à penser que je devrais commencer par un ensemble de valeurs possibles 0-9 pour chaque lettre, peut-être stocké comme des vecteurs dans une table «domaines» et éliminer les valeurs à partir de cela, car des déductions sont effectuées. Par exemple, si je vois des lettres alignées comme celle-ci , je peux dire que c est zéro et ceci élimine toutes les autres valeurs de son domaine. Je peux penser à de nombreuses déductions, mais les généraliser à toutes sortes de petites situations et la mettre en code semble un peu délicate à première vue. -assuming J'ai une bonne série de déductions qui traversent des objets et démarrent de nombreuses valeurs de la table des domaines, je suppose que je voudrais toujours tout simplement boucler sur tout et espère que l'espace d'état est suffisamment petit générer une solution dans une quantité de temps raisonnable. Mais on se sent comme il doit y avoir plus que ça! - Peut-être d'équations intelligentes pour mettre en place ou quelque chose le long de ces lignes. Les conseils sont appréciés!
3 Réponses :
Vous pouvez itérer ce problème de droit à gauche, c'est-à-dire la façon dont vous effectuez l'opération réelle. Commencez avec la colonne la plus à droite. Pour chaque chiffre que vous rencontrez, vous vérifiez s'il existe déjà une mission pour ce chiffre. S'il y a, vous utilisez sa valeur et continuez. S'il n'y en a pas, vous entrez une boucle sur tous les chiffres possibles (peut-être omettre déjà des utilisateurs déjà utilisés si vous souhaitez une carte bijective) et continuez de manière récursive avec chaque affectation possible. Lorsque vous atteignez la ligne Somme, vous vérifiez à nouveau si la variable du chiffre donné est déjà assignée. Si ce n'est pas le cas, vous attribuez le dernier chiffre de votre somme actuelle, puis continuez à la colonne de valorisation supérieure suivante, en prenant le transport avec vous. S'il y a déjà une mission, et cela accepte le dernier chiffre de votre résultat, vous continuez de la même manière. S'il y a une affectation et qu'il n'est pas d'accord, vous abandonnez la branche actuelle et revenez à la boucle la plus proche où vous avez eu d'autres chiffres à choisir.
Le bénéfice de cette approche devrait être que de nombreuses variables sont déterminées par une somme, au lieu de deviner à l'avance. En particulier pour les lettres qui ne se produisent que dans la gamme Somme, cela pourrait être une énorme victoire. En outre, vous pourrez peut-être repérer des erreurs plus tôt, évitant ainsi les choix de lettres dans certains cas où les choix que vous avez fabriqués jusqu'à présent sont déjà incohérents. Un inconvénient peut être la structure récursive légèrement plus compliquée de votre programme. Mais une fois que vous avez obtenu ce droit, vous avez également appris une bonne affaire de tournage de pensées en code.
J'ai résolu ce problème à mon blog en utilisant un algorithme d'escalade randomisé. L'idée de base est de choisir une affectation aléatoire de chiffres aux lettres, "Score" de l'affectation en calculant la différence entre les deux côtés de l'équation, puis modifiant l'affectation (échange de deux chiffres) et recomposer le score, en gardant ces changements qui améliorent le score et jeter ces changements qui ne le font pas. C'est la montée en colline, car vous n'acceptez que des changements dans une direction. Le problème avec l'escalade de la colline est que cela reste coincé dans un maximum local, donc chaque si souvent, vous jetez la tentative actuelle et recommencez; C'est la partie de randomisation de l'algorithme. L'algorithme est très rapide: il résout chaque cryptarithme que je l'ai donné dans des fractions d'une seconde.
L'escalade de la colline est un peu inutile pour la satisfaction de contraintes avec autant de contraintes qu'il y a ici.
Les problèmes cryptarithmétiques sont classiques Problèmes de satisfaction de contrainte . Fondamentalement, ce que vous devez faire, c'est que votre programme génère des contraintes basées sur les entrées telles que vous vous retrouvez avec quelque chose comme ce qui suit, à l'aide de votre exemple donné:
Range(O, W, T) == {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Range(Carry1, Carry2, F) == {0, 1}
Supposez-vous que la réponse est unique? Si quelqu'un vous a donné
aa + bb = cc par exemple essayer de trouver toutes les solutions ou une seule?La première réponse qui fonctionne sera suffisante.
Quelle est votre question sur c ++?
Pas tant de question à propos de C ++ comme un peu d'une étiquette d'information pour montrer ce qui est disponible conteneur-sage. Conceptualiser le problème avec les outils disponibles est l'une des parties les plus difficiles. De plus, la balise génère probablement beaucoup de hits. :-)
Je envisagerais que la planification de la programmation soit un sujet légitime et pertinent; Je suis sûr que de nombreuses erreurs publient des erreurs sur le résultat d'une planification médiocre. En tout cas, 7 personnes jusqu'à présent ne semblent pas mener la question du tout.