GoupillWiki

Outils pour utilisateurs

Outils du site

Piste :
nsi:terminales:boyer_moore

Différences

Ci-dessous, les différences entre deux révisions de la page.

Lien vers cette vue comparative

Les deux révisions précédentesRévision précédente
Prochaine révision		Révision précédente
nsi:terminales:boyer_moore [2023/05/08 21:12] – [Amélioration 1] goupillwikinsi:terminales:boyer_moore [2023/05/08 21:26] (Version actuelle) – [Fonctions intermédiaires] goupillwiki
Ligne 166: Ligne 166:
 <code python> <code python>
 rangs.get(B, L) rangs.get(B, L)
 +</code>
 +
 +<code python>
 +>>> r = {"A":1, "T": 2, "G":0}
 +>>> r["A"]
 +1
 +>>> r["C"]
 +KeyError 'C'
 +>>> r.get("A", 6)
 +1
 +>>> r.get("C", 6)
 +6
 </code> </code>
 </WRAP> </WRAP>
Ligne 246: Ligne 258:
 === Calcul de décalage === === Calcul de décalage ===
  
-On souhaite implémenter une fonction ''k_to_shift(aiguille:str, k:int) -> int'' qui renvoie le décalage possible, selon la règle précédente, quand on a trouvé ''k'' caractères coïncidents.+On souhaite implémenter une fonction ''%%k_to_shift(aiguille:str, k:int) -> int%%'' qui renvoie le décalage possible, selon la règle précédente, quand on a trouvé ''k'' caractères coïncidents.
  
-Considérant un mot ''aiguille'', et ''1 <= k < len(aiguille)''+Considérant un mot ''aiguille'', et ''%%1 <= k < len(aiguille)%%''
  
 Soit ''suffixe'' représentant les ''k'' derniers caractères de ''aiguille'' et ''c'' le caractère juste avant ''suffixe'' dans ''aiguille''. Nous souhaitons trouver la première apparition (partant de la fin) de ''suffixe'' dans ''aiguille'', **non précédée** de ''c''. Soit ''suffixe'' représentant les ''k'' derniers caractères de ''aiguille'' et ''c'' le caractère juste avant ''suffixe'' dans ''aiguille''. Nous souhaitons trouver la première apparition (partant de la fin) de ''suffixe'' dans ''aiguille'', **non précédée** de ''c''.
Ligne 277: Ligne 289:
 TANT QUE d < L FAIRE TANT QUE d < L FAIRE
     m = rang du caractère face au début du suffixe     m = rang du caractère face au début du suffixe
 +        en tenant compte du décalage d vers la gauche
     SI m > 0 ALORS     SI m > 0 ALORS
         caractère en vis à vis de c = caractère aiguille en m - 1         caractère en vis à vis de c = caractère aiguille en m - 1
Ligne 292: Ligne 305:
 </code> </code>
  
-<WRAP box>**À faire :** Faites l'implémentation de cette fonction ''k_to_shift(aiguille:str, k:iny)->int''</WRAP>+<WRAP box>**À faire :** Faites l'implémentation de cette fonction ''%%k_to_shift(aiguille:str, k:int)->int%%''</WRAP>
  
 === Constitution d'un tableau === === Constitution d'un tableau ===
  
-Le plus difficile est fait. On veut maintenant une fonction ''get_shifts_list(aiguille:str) -> list'' qui produit le tableau mentionné précédemment. Notons ''shifts'' ce tableau.+Le plus difficile est fait. On veut maintenant une fonction ''%%get_shifts_list(aiguille:str) -> list%%'' qui produit le tableau mentionné précédemment. Notons ''shifts'' ce tableau.
  
   * ''len(shifts) == len(aiguille)''   * ''len(shifts) == len(aiguille)''
   * ''shifts[0] = 0''   * ''shifts[0] = 0''
-  * ''shifts[k] = k_to_shift(aiguille, k)'' pour ''1 <= k < len(aiguille)''+  * ''%%shifts[k] = k_to_shift(aiguille, k)%%'' pour ''%%1 <= k < len(aiguille)%%''
  
-<WRAP box>**À faire :** Faites l'implémentation de cette fonction ''get_shifts_list(aiguille:str) -> list''</WRAP>+<WRAP box>**À faire :** Faites l'implémentation de cette fonction ''%%get_shifts_list(aiguille:str) -> list%%''</WRAP>
  
  
nsi/terminales/boyer_moore.1683573163.txt.gz · Dernière modification : de goupillwiki