| Les deux révisions précédentesRévision précédenteProchaine révision | Révision précédente |
| nsi:terminales:boyer_moore [2022/04/02 17:00] – goupillwiki | nsi:terminales:boyer_moore [2023/05/08 21:26] (Version actuelle) – [Fonctions intermédiaires] goupillwiki |
|---|
| |
| <WRAP box>**À faire :** | <WRAP box>**À faire :** |
| - Écrivez une fonction ''bons(foin:str; aiguille:str, shift:int) -> int'' qui pour un décalage (//shift//) donné, renvoie le nombre de caractères corrects comptés à partir de la droite.<code python> | - Écrivez une fonction ''bons(foin:str, aiguille:str, shift:int) -> int'' qui pour un décalage (//shift//) donné, renvoie le nombre de caractères corrects comptés à partir de la droite.<code python> |
| >>> bons("ACTGCGTACGCCATAA", "GAGTAC", 3) | >>> bons("ACTGCGTACGCCATAA", "GAGTAC", 3) |
| 4 | 4 |
| 0 | 0 |
| >>> bons("ACTGCGTACGCCATAA", "GCGTAC", 6) | >>> bons("ACTGCGTACGCCATAA", "GCGTAC", 6) |
| 0 | 1 |
| </code> | </code> |
| - Faites l'implémentation en Python d'une fonction ''rangs(aiguille:str)'' et renvoyant un résultat indiquant la première position en partant de la droite pour chaque lettre de ''aiguille'' sous forme d'un dictionnaire.<code python> | - Faites l'implémentation en Python d'une fonction ''rangs(aiguille:str)'' et renvoyant un résultat indiquant la première position en partant de la droite pour chaque lettre de ''aiguille'' sous forme d'un dictionnaire.<code python> |
| |
| <code lang-none> | <code lang-none> |
| soit L la longueur de l'aiguille | Soit L la longueur de l'aiguille |
| Analyser aiguille selon fonction précédente -> rangs | Analyser aiguille selon fonction précédente -> rangs |
| régler le décalage à 0 | régler le décalage à 0 |
| <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> |
| === 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''. |
| 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 |
| </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> |
| |
| |
