Discussion :

[Malek mansour]

Salut
Svp comment résoudre algorithmiquement le problème suivant :
Chercher le nombre d'occurrences de chaque caractère dans une chaîne de caractères sans redondance.

[WhiteCrow]

Bonjour,
cela se résout exactement de la même manière algorithmiquement que manuellement 😀
Comment fais-tu à la main ? Tu me dis si tu fais autrement que :

1. je prends une feuille de papier vierge et un crayon de papier
2. je me positionne sur le premier caractère de la chaîne
3. si le caractère actuel est écrit sur ma feuille alors j'incrémente la valeur écrite à côté
   sinon j'écris ce caractère en notant 1 à côté
4. tant que je ne suis pas au bout de la chaîne j'avance de caractère et je recommence en 3
5. et voilà c'est fini

Prendre une feuille de papier vierge et un crayon de papier consiste à utiliser une structure de données permettant d'associer une clé (le caractère) et une donnée (son nombre d'occurrence). Tu as le choix, le simple tableau (ça fait très C) ou une liste (très lisp) ou un dictionnaire (très python) ou plus complexe (très nerd). En général ces sdd te permettent de savoir si un clé a déjà été aperçue ou non, si ce n'est pas le cas de la créer en lui associant une valeur 1 ou sinon de récupérer la valeur actuelle et de l'incrémenter.
Quant à parcourir une chaîne c'est un peu trivial …
Et ensuite ça va dépendre du dialecte que tu emploi pour l'algo et des contraintes que l'on te donne aussi. Ça peut aller du

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
algo occ
entrée : phrase une chaine de caractère
sortie : occ un dictionnaire associant un caractère à un nombre
 
début
    occ ← dictionnaire_vide()
    pour tous les caractères c de phrase faire
        si occ contient c alors
            occ[c] ← occ[c] + 1
        sinon
            occ[c] ← 1
        fin si
    fin pour
    retourner occ
fin.

au

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
function occ( string S ) : int[]
begin
    for c in 'a' .. 'z' do
        occ[c]=0
    for i=0 .. length(S) do
        occ[ lowercase(S[i]) ] ++
end.

Deux algos, deux dialectes, deux contraintes différentes, … mais un seul problème.