Je cherche à créer un programme qui identifierait certains modèles en chiffres. Je ne suis pas sûr que cela nécessite un algorithme ou simplement une programmation soigneusement pensée. Je ne cherche pas quelqu'un pour fournir un code source, juste une pensée qui consiste à provoquer des idées pour me commencer dans la bonne direction.
Les numéros seront fixés de 6 chiffres de 000000 à 999999. Je suppose que chaque numéro serait stocké dans le cadre de un tableau. Je voudrais ensuite tester le numéro contre un motif. p>
Par exemple permet de dire que les 3 motifs que j'utilisés sont p> Je suppose que la partie que je suis bloquée est de savoir comment allouer chaque partie de la Tableau entier à une valeur telle que A ou B P> Mes pensées initiales seraient simplement d'allouer chaque partie comme lettre individuelle. Donc, si le tableau consistait en 1 3 5 4 6 8 8, je créerais une carte comme p> puis certains comment prennent le premier modèle, P> package com.doyleisgod.number.pattern.finder;
public class PatternFoundException extends Exception {
private static final long serialVersionUID = 1L;
private final String pattern;
public PatternFoundException(String pattern) {
this.pattern = pattern;
}
public String getPattern() {
return pattern;
}
}
5 Réponses :
Vous pouvez casser vos chiffres dans un tableau d'octets (ou INTS si vous préférez), un pour chaque caractère. Chaque motif pourrait être défini en termes de comparaison directe entre les éléments appropriés de la matrice.
ababab=a[0]==a[2] && a[2]==a[4] && a[1]==a[3] && a[3]==a[5] && a[0]!=a[1] aaabbb=a[0]==a[1] && a[1]==a[2] && a[3]==a[4] && a[4]==a[5] && a[0]!=a[3] fedcba=(a[0]-a[1])==1 && (a[1]-a[2])==1 && (a[2]-a[3])==1 && (a[3]-a[4])==1 && (a[4]-a[5]==1)
Je suggérerais de construire une machine à états:
a. Initialisation avec motifs:
b. Exécuter la machine à états
a.1. Normalisation des motifs.
AAAAAA => A0 A0 A0 A0 A0 A0 A0
CACACA => A0 B0 A0 A0 A0 A0 B0 (Commencez toujours avec A, puis B, C, D, etc. .)
B B + 1 B + 2 A A + 1 A + 2 => A0 A1 A2 B0 B1 B2
Ainsi, vous avez toujours un démarrage de modèle normalisé avec A0. < /p >p>a.2. Construisez un arbre b. Exécuter la machine à états Utilisez Algorithme de recherche de profondeur-premier à l'aide de la récursivité à Trouvez un motif assorti. a-t-il de sens?
Merci Yuri, cela semble avoir commencé dans la bonne direction. La méthode que j'ai prise est de créer une structure d'arborescence de motifs. De sorte que tous les modèles seraient contenus dans l'arbre et avec la technique DFS pour éliminer les branches au plus haut niveau éliminant ainsi plusieurs modèles.
Ceci est facile avec la fonction de match très rapide suivante.
Étant donné que les modèles sont des matrices de motifs, où le modèle est constitué d'une lettre et d'un entier.
étant donné que les numéros sont des matrices de chiffres.
Appelez maintenant une fonction de match () avec chaque combinaison de chiffres et de chiffres (emboutite imbriquée).
La fonction de correspondance iTère sur le motif et le nombre de gauche à droite et fait un remplacement des nombres pour correspondre aux lettres du motif. Si un chiffre est remplacé, remplacez tous les mêmes chiffres à son droit également. Si vous atteignez un index qui n'est pas un chiffre, car il est déjà remplacé, vérifiez si cet élément correspond au motif. pour le (n + 2) que vous pourriez Faites de même, en faisant des mathématiques supplémentaires lors du remplacement ou de la correspondance. Remarque: le nombre n'a pas besoin de consister simplement de chiffrer. Si vous souhaitez remplacer un caractère, vous pouvez même faire correspondre des modèles similaires! Donc, un B C A B C correspond également à D F G D F G sur la forme générique.
Vous pouvez déduire Par exemple, indiquons chacun des 6 chiffres D1, D2, D3, D4, D5 et D6 respectivement. Ensuite, le motif Dans vos exemples, je ne peux voir que 2 types de règles inférées - une pour l'égalité des chiffres (D1 = D2 si leurs positions de motif ont le même caractère) et une autre pour les opérations arithmétiques (je n'ai pas t savoir si A et B devraient être des nombres différents et si vous aurez ainsi besoin de règles supplémentaires pour les inégalités). Toutes les types peuvent être trivialement traduits en contraintes. L'arborescence des solutions possibles peut être compilée à partir de ces contraintes. Il peut commencer par quelque chose comme: puis contiennent des contraintes sur d'autres nœuds. Il peut être difficile d'appliquer correctement l'algorithme de retrait de vous-même, donc Il est logique de trouver une implémentation de prologs pour votre plate-forme (voir Cette question pour Java ) puis traduisez simplement des contraintes sur les règles de prolog. A (A + 1) (A + 2) B (B + 1) (B + 2) peut être réécrit à l'ensemble de règles / contraintes suivant: < Pré> xxx
Pour les modèles spécifiques que vous avez mentionnés comme exemples, des programmes simples peuvent être écrits pour vérifier si la correspondance des chaînes d'entrée.
Si les motifs sont plus compliqués que ceux que vous mentionnez, vous pouvez utiliser grammaire sans contexte < / a> et des expressions régulières pour spécifier vos règles. Et il existe des outils tels que Lex et YACC qui traiteront les chaînes d'entrée en fonction des règles spécifiées et de retourner s'ils correspondaient ou non.
Eh bien, je n'aurais pas du cap de correspondre à une correspondance exacte (c'est-à-dire des situations de type = 1). Vous voudrez probablement envisager chaque personnage différent rencontré pour être un chiffre différent. Les séparations spatiales doivent probablement être des nombres différents (pas des chiffres).
Ceci est un trucs. Douglas Hofstadter a rendu son opérateur sur une telle découverte de modèle.
Hé, voulez-vous avoir plusieurs modèles prédéfinis et juste les vérifier? Et existe-t-il déjà une sémantique comment vos motifs seront stockés ou n'y a-t-il pas de format correct?
J'ai construit un petit modèle, c'est qu'il vaut la peine de la publier ici de sorte que d'autres personnes qui puissent vouloir résoudre un problème similaire peut le regarder. Si oui, où di poster-le? dans un nouveau fil? Ou modifiez mon message d'origine dans ce fil?