Ensemble definis recursivement.
Soit S l'ensmble des chaines sur l'alphabet {0,1} qui ne contiennent pas deux 0 consecutifs.
Par Exemple, 10111011 e S et 10100011 n'appartient pas a S
Pouvez vous m'enumerer tous les elements de S de longueur 0,1,2,3,4
Merci de votre aide
2006-12-03 07:03:33 · 5 réponses · demandé par ostie127 2 dans Sciences et mathématiques ➔ Mathématiques
L=0 pour Vide
L=1 pour 0,1
L=2 pour 01,10,11
L=3 pour 010,011,101,110,111
On peut calculer recursivement le nombre S(n) d'éléments de longueur n et désignant par U(n) le nombre d'élements finissant par 0 et V(n) ceux finissant par 1. On a U(n+1)=V(n) et V(n+1)=U(n)+V(n)=S(n).
etc.. mais ce n'est pas l'objet du débat
2006-12-03 08:49:16 · answer #1 · answered by Anonymous · 0⤊ 0⤋
D'abord, écris toutes les chaînes possibles d'une longeur donnée.
(Un indice:
pour la longueur 0, tu dois écrire 0 chaine.
pour la longueur 1, tu dois écrire 2 chaines.
pour la longueur 2, tu dois écrire 4 chaines.
pour la longueur 3, tu dois écrire 8 chaines.
pour la longueur 4, tu dois écrire 16 chaines.
)
Ensuite, pour chaque longueur, tu élimines toutes celles qui ne contiennent pas deux 0 consécutifs.
Ca n'est pas bien dur, ça devrait te prendre 3 minutes.
2006-12-03 16:02:00 · answer #2 · answered by Matt 5 · 1⤊ 0⤋
Je ne peux pas répondre à ta question... désolée ! mais avoues que ça "a de a gueule" : on dirait des octets ;-))
Demande à Bill Gates !! Syllicon Valley pourra t'aider (le dimanche soir en france, c'est le milieu de la journée aux USA : tu as tes chances !).
2006-12-03 15:15:55 · answer #3 · answered by the unknown 1 · 0⤊ 0⤋
oui je peux !
2006-12-03 15:09:36 · answer #4 · answered by Anonymous · 0⤊ 2⤋
et c'est dimanche soir que tu fais tes devoirs!!
2006-12-03 15:08:52 · answer #5 · answered by steph 5 · 0⤊ 2⤋