Discussion :

[Kopp92i]

Bonjour à tous,

Etant nouveau dans le beau monde qu'est la programmation, quelques difficultés font surface.

Dernièrement, j'ai été confronté à un exercice dont je n'ai pas pu trouvé la résolution, malgré avoir très bien compris l'énoncé. Le voici :

Pouvez-vous m'aider à résoudre cet exercice svp? Merci beaucoup!

[tyrtamos]

Bonjour,

L'exemple situé à la suite de l'énoncé est assez facile à comprendre. Mais je ne sais pas à quoi tu as droit comme instructions. Voilà comment je ferais à travers un exemple:

Soit le nombre n = 123456789

En chaine binaire, cela donne: b = bin(n) => "0b111010110111100110100010101"

On retire les "0b" du début avec: b = b[2:] => "111010110111100110100010101"

Prenons maintenant une chaine de 2 bits. Combien y a-t-il de façons de placer des "0" et des "1" dans une séquence de 2 bits: il y en a 2**2=4, soit "00", "01", "10", "11". Voilà comment on peut les trouver:

Code :

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

1
2
3
4
nb = 2
for x in range(0, 2**nb):
    s = bin(x)[2:].zfill(nb)
    print(s)

Ce qui affiche bien les 4 chaines demandées:

Code :

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

1
2
3
4
00
01
10
11

La méthode .zfill permet d'ajouter à gauche le "0" qui manque quand on trouve seulement "0" (=> "00") ou "1" (=>"01").

Il ne reste plus qu'à compter le nombre de fois où chaque séquence de 2 bits est trouvée dans la chaine binaire de début. On peut le faire avec la méthode .count:

Code :

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

1
2
3
4
5
b = "111010110111100110100010101"
nb = 2
for x in range(0, 2**nb):
    s = bin(x)[2:].zfill(nb)
    print(s, b.count(s))

Ce qui donne ici:

Code :

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

1
2
3
4
00 2
01 8
10 8
11 5

Ce qui veut dire qu'on a trouvé 2 fois la séquence "00", 8 fois la séquence "01", etc...

Pour trouver la même chose avec 3 bits, on applique le même code avec nb=3, ce qui donne:

Code :

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

1
2
3
4
5
6
7
8
000 1
001 2
010 3
011 3
100 2
101 4
110 4
111 2

etc...

Il ne reste plus qu'à stocker ces résultats, les trier et les présenter comme le demande l'exo.

Bon courage pour la suite!

[tyrtamos]

Juste un petit complément.

Il n'est pas précisé dans l'énoncé si la recherche doit être faite avec ou sans recouvrement. Or, on ne trouve bien sûr pas le même résultat dans les 2 cas.

Par exemple, imaginons "10001" et comptons les "00". la méthode count trouvera 1 seul motif parce que le 2e zéro ayant été pris dans le 1er comptage ne sera pas pris pour un second.

Si on veut compter avec recouvrement, il faut tester chaque caractère séparément avec une boucle. Par exemple:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
b="01010010010001000111101100001010011001111000010010011110010000000"
seq = "00"
 
# comptage sans recouvrement
print(seq, b.count("00"))
 
# comptage avec recouvrement
c = 0
for i in range(0, len(b)-1):
    if b[i:i+2]==seq:
        c += 1
print(seq, c)

Ce qui affiche:

Code :

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

1
2
"00" 16
"00" 23

[Kopp92i]

Merci beaucoup pour votre réponse, ça m'a beaucoup aidé!