Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
#1 13-12-2023 15:04:38
- pentium mix
- Membre
- Inscription : 27-10-2020
- Messages : 159
Afficher le debut de la plus longue suite consecutive de zeros
bonjour tout le monde. j'aimerai écrire l’algorithme qui retourne la position i dans le tableau T telle que T (i) est le début de la plus longue suite consécutive de zéros.
malheureusement je ne sais quel fonction écrire au préalable pour aboutir. J'ai penser a la fonction qui retourne la position du premier zeros mais cela ne m'aide pas
Merci
Hors ligne
#2 13-12-2023 17:00:53
- Fred
- Administrateur
- Inscription : 26-09-2005
- Messages : 7 227
Re : Afficher le debut de la plus longue suite consecutive de zeros
Bonjour,
Je ne suis pas sûr qu'il faille écrire une fonction au préalable. Je pense qu'on doit pouvoir s'en sortir en parcourant le tableau une seule fois, en gardant assez d'informations sur la position du début et la longueur de la suite de zéros la plus longue trouvée jusqu'à présent et en comparant avec la suite de zéros que l'on est en train d'analyser lors du parcours.
Je n'ai pas le temps d'écrire une fonction tout de suite mais je peux y revenir.
F.
Hors ligne
#3 13-12-2023 18:30:29
- Wiwaxia
- Membre
- Lieu : Paris 75013
- Inscription : 21-12-2017
- Messages : 427
Re : Afficher le debut de la plus longue suite consecutive de zeros
Bonjour,
Il faudra convenir de plusieurs choses:
a) la nature des éléments du tableau: il pourra s'agir d'entiers non signés au format Byte (par ex. {0. 1. 2}, ou éventuellement de booléens si l'on tient à allouer au tableau le minimum d'espace mémoire; les instructions dépendront du choix fait à ce niveau;
b) l'emplacement du premier zéro envisageable, par ex. la position (1); on aura par conséquent T(0) > 0 ;
c) l'origine ou la génération du tableau étudié, afin que cet objet soit directement observable : s'agit-il des décimales d'un nombre irrationnel, ou d'une séquence d'une suite modulaire arbitrairement choisie ? Mais peut-être as-tu une idée précise sur ce dernier point ...
Il faudra aussi deux variables de type entier pour mémoriser la plus grande longueur observée (Lmax) et la position du premier terme (Kini); toutes deux initialisées à zéro.
Hors ligne
#4 13-12-2023 18:42:03
- Fred
- Administrateur
- Inscription : 26-09-2005
- Messages : 7 227
Re : Afficher le debut de la plus longue suite consecutive de zeros
Re-
Une fonction comme la suivante devrait fonctionner :
def suite_tableau(T):
index=-1
longueur=-1
i=0
indexencours=0
lencours=0
l=0
while (i<len(T)):
if (T[i]==0):
if (lencours==0): # il y avait un 1 avant
indexencours=i
lencours+=1
if (lencours>longueur):
longueur=lencours
index=indexencours
else:
lencours=0
i+=1
return (index,longueur)
Hors ligne
#5 13-12-2023 19:27:01
- pentium mix
- Membre
- Inscription : 27-10-2020
- Messages : 159
Re : Afficher le debut de la plus longue suite consecutive de zeros
mince je suis un peu perdu
je ne comprend pas comment vous proceder
Re-
Une fonction comme la suivante devrait fonctionner :
def suite_tableau(T):
index=-1
longueur=-1
i=0
indexencours=0
lencours=0
l=0
while (i<len(T)):
if (T[i]==0):
if (lencours==0): # il y avait un 1 avant
indexencours=i
lencours+=1
if (lencours>longueur):
longueur=lencours
index=indexencours
else:
lencours=0
i+=1
return (index,longueur)
Hors ligne
#6 13-12-2023 19:28:13
- pentium mix
- Membre
- Inscription : 27-10-2020
- Messages : 159
Re : Afficher le debut de la plus longue suite consecutive de zeros
oh la j'ai carement oublié de preciser que le tableau n'est constitué que de 0 et 1
Bonjour,
Il faudra convenir de plusieurs choses:
a) la nature des éléments du tableau: il pourra s'agir d'entiers non signés au format Byte (par ex. {0. 1. 2}, ou éventuellement de booléens si l'on tient à allouer au tableau le minimum d'espace mémoire; les instructions dépendront du choix fait à ce niveau;
b) l'emplacement du premier zéro envisageable, par ex. la position (1); on aura par conséquent T(0) > 0 ;
c) l'origine ou la génération du tableau étudié, afin que cet objet soit directement observable : s'agit-il des décimales d'un nombre irrationnel, ou d'une séquence d'une suite modulaire arbitrairement choisie ? Mais peut-être as-tu une idée précise sur ce dernier point ...Il faudra aussi deux variables de type entier pour mémoriser la plus grande longueur observée (Lmax) et la position du premier terme (Kini); toutes deux initialisées à zéro.
Hors ligne
#7 13-12-2023 21:09:56
- Glozi
- Invité
Re : Afficher le debut de la plus longue suite consecutive de zeros
Bonsoir,
Pour comprendre un algorithme, le plus concret c'est de prendre un exemple de tableau T, et de suivre avec crayon et papier les différentes étapes de la boucle. Ça permet de comprendre ce qui se passe.
Bonne soirée
#8 13-12-2023 22:52:06
- Wiwaxia
- Membre
- Lieu : Paris 75013
- Inscription : 21-12-2017
- Messages : 427
Re : Afficher le debut de la plus longue suite consecutive de zeros
Bonsoir,
Soit une séquence binaire initialisée à T[0] = 1 .
Il suffit de parcourir l'ensemble des termes de rang positif, en comparant les deux valeurs consécutives concernées,
Ta = T[k - 1] , Tb = T[k] .
Trois cas se présentent, comme Glozi l'a pour l'essentiel indiqué:
a) Ta=1 et Tb=0: commence alors une séquence de zéros au rang Ki = k (valeur actuelle de l'indice courant) et de longueur L = 1;
b) Ta=0 et Tb=0: la séquence se poursuit et s'allonge d'une unité, d'où L = L + 1;
c) Ta=0 et Tb=1: la séquence de zéros s'est achevée, et si elle apparaît plus longue que la précédente enregistrée, on mémorise les nouvelles valeurs de la longueur et de l'indice initial: si Lmax<L , alors Lmax=L et Kini:= Ki .
Voici ce que l'on obtient sur une liste de 41 termes commençant par (1):
Le programme est écrit en Virtual Pascal, mais il se lit pratiquement comme du pseudo-code; j'ai ajouté quelques commentaires afin de rendre les instructions plus compréhensibles.
PROGRAM Nombre_Zeros_Consecutifs;
USES Crt, E_Texte; // Gestion de l'écran texte
CONST Nmax = 40;
T: ARRAY[0..Nmax] OF Byte = (1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0,
1, 0, 1, 1, 0, 1, 0, 1, 1, 1,
0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
0, 1, 1, 0, 0, 0, 1, 1, 1, 1);
VAR Ta, Tb: Byte;
k, Lmax, Ki, Kini, L: Word;
BEGIN
Lmax:= 0; Kini:= 0;
FOR k:= 1 TO Nmax DO
BEGIN
Ta:= T[k - 1]; Tb:= T[k];
IF (Ta=1) AND (Tb=0) THEN BEGIN
L:= 1; Ki:= k
END
ELSE IF (Ta=0) THEN IF (Tb=0) THEN Inc(L) // L:= L + 1
ELSE IF (Lmax<L) THEN BEGIN
Lmax:= L; Kini:= Ki
END
END;
E(1015); // Effacement, couleurs de l'écran / Ecriture d'un texte
Wt(5, 5, 'Longueur maximale de la séquence: Lmax = '); Write(Lmax:5);
Wt(5, 7, 'Emplacement du premier terme: Kini = '); Write(Kini:5);
A_ // Arrêt/suspension de l'exécution du programme
END.
Dernière modification par Wiwaxia (14-12-2023 00:46:45)
Hors ligne
#9 13-12-2023 23:37:51
- Glozi
- Invité
Re : Afficher le debut de la plus longue suite consecutive de zeros
Bonsoir,
Je ne connaissais pas du tout le Virtual Pascal, effectivement c'est presque du pseudo-code même si je trouve l'indentation un peu étrange.
Sinon, sur ton algo j'ai deux problèmes :
Le premier c'est que l'algo ne s'applique pas si T commence par 0 (pas un vrai problème, on peut artificiellement rajouter un 1 en première entrée, mais il ne faut pas oublier)
Le second, c'est que j'ai l'impression que l'algo échoue si la plus longue séquence de zéros est à la fin du tableau (Ex : T = [1,1,0,1,0,0,0])
Sinon dans mon post précédent dans les exemples j'appelle une fonction "find" au lieu d'appeler la fonction "max_zero_sequence" ("find" était l'ancien nom de la fonction que j'ai renommée a posteriori...)
Bonne soirée
#10 14-12-2023 00:55:39
- Wiwaxia
- Membre
- Lieu : Paris 75013
- Inscription : 21-12-2017
- Messages : 427
Re : Afficher le debut de la plus longue suite consecutive de zeros
Bonsoir,
J'ai rencontré beaucoup de difficultés dans le transfert en ligne du contenu du fichier, et l'indentation laissait en effet beaucoup à désirer. J'ai rectifié pour le mieux, par correction manuelle.
Pour le reste, je répondrai demain.
Bonne fin de soirée.
Dernière modification par Wiwaxia (14-12-2023 10:30:17)
Hors ligne
#11 14-12-2023 05:38:04
- pentium mix
- Membre
- Inscription : 27-10-2020
- Messages : 159
Re : Afficher le debut de la plus longue suite consecutive de zeros
Infiniment merci
Au final j'ai l'impression de n'avoir pas assez réfléchi pour cet exercice
Bonsoir,
Pour comprendre un algorithme, le plus concret c'est de prendre un exemple de tableau T, et de suivre avec crayon et papier les différentes étapes de la boucle. Ça permet de comprendre ce qui se passe.▼avec une boucle forBonne soirée
Dernière modification par pentium mix (14-12-2023 05:47:08)
Hors ligne
#12 14-12-2023 14:29:13
- Wiwaxia
- Membre
- Lieu : Paris 75013
- Inscription : 21-12-2017
- Messages : 427
Re : Afficher le debut de la plus longue suite consecutive de zeros
Bonjour,
J'avais effectivement laissé de côté le cas d'une séquence terminale de zéros. Une manière simple de pallier à cet oubli consiste à rajouter un terme supplémentaire égal à 1, mais je reconnais que l'apposition de cette seconde rustine manque d'élégance.
Il est possible de s'en tenir strictement au tableau initial ARRAY[1..Nmax] OF Byte par deux petites modifications:
a) l'affectation d'une valeur appropriée à la variable (Ta) tenant compte du rang (k) du terme envisagé dans le tableau, de valeur (Tb);
b) l'attribution d'une nouvelle valeur à (Lmax) et (Kini) une fois complètement parcourue la bouche "FOR".
Ci-dessous la nouvelle version du programme Pascal sous forme d'image, le transfert en ligne du texte source se révélant toujours aussi désastreux pour l'indentation:
et la vérification observée dans le cas de deux séquences:
Merci à Glozi pour ses remarques.
Dernière modification par Wiwaxia (14-12-2023 14:31:01)
Hors ligne