Forum de mathématiques - Bibm@th.net

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

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.

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.

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)
 

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)
 

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.

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.

▼avec une boucle for

Un algo pas du tout optimisé mais j'espère assez limpide.

def max_zero_sequence(T):
    """
    Entrée :
        T - une liste d'entiers/booléens
    Sortie :
        index_max, length_max
        où - length_max représente la longueur de la plus longue séquence de zéros consécutifs dans T (length_max=0 s'il n'y a aucun zéro dans T)
        - index_max représente l'indice de départ de cette séquence maximale (index_max=None s'il n'y a aucun zéro dans T)
    """
    index_max=None #contient l'indice du début de la plus longue séquence de zéros consécutifs découverte
    length_max=0 #la longueur de cette plus longue séquence découverte
   
    index_start_current = None #contient l'indice du début de la séquence de zéros consécutifs que nous sommes en train d'explorer
    length_current=0 #la longueur de cette séquence actuelle
   
    currently_in_zero_sequence = False #vaut True si et seulement si l'indice i précédent se situe dans une séquence de zéros.
   
    for i in range(len(T)): #boucle d'exploration
        if T[i]==0: ## si l'entrée qu'on regarde est un zéro alors :
            if currently_in_zero_sequence: #si on a déjà trouvé des zéros avant cette entrée
                length_current +=1 #alors on augmente juste la longueur de la séquence actuelle.
            else: #sinon c'est que ce zéro est le premier d'une séquence
                currently_in_zero_sequence = True #on démarre la séquence courante
                length_current = 1 #la longueur de la séquence actuelle vaut 1 pour le moment
                index_start_current = i #on dit que l'indice de départ de la séquence actuelle vaut i
        else: #sinon, si l'entrée qu'on regarde n'est pas un zéro :
            currently_in_zero_sequence = False # on dit qu'on n'est pas en train d'explorer une séquences de zéros
        if length_current > length_max: #si la longueur de la séquence courante est plus grande que la longueur max enregistrée
            length_max = length_current #on met à jour
            index_max = index_start_current #on met à jour
   
    return index_max, length_max
#Exemples :
print(find([0,0,1,0,1,0,0])) #(0,2)
print(find([1,0,1,0,1,0,0])) #(5,2)
print(find([0,0,0,0])) #(0,4)
print(find([1,1,1,1])) #(None, 0)
print(find([1,0,1])) #(1,1)
 

Bonne soirée

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)

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

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)

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 for

Un algo pas du tout optimisé mais j'espère assez limpide.

def max_zero_sequence(T):
    """
    Entrée :
        T - une liste d'entiers/booléens
    Sortie :
        index_max, length_max
        où - length_max représente la longueur de la plus longue séquence de zéros consécutifs dans T (length_max=0 s'il n'y a aucun zéro dans T)
        - index_max représente l'indice de départ de cette séquence maximale (index_max=None s'il n'y a aucun zéro dans T)
    """
    index_max=None #contient l'indice du début de la plus longue séquence de zéros consécutifs découverte
    length_max=0 #la longueur de cette plus longue séquence découverte
   
    index_start_current = None #contient l'indice du début de la séquence de zéros consécutifs que nous sommes en train d'explorer
    length_current=0 #la longueur de cette séquence actuelle
   
    currently_in_zero_sequence = False #vaut True si et seulement si l'indice i précédent se situe dans une séquence de zéros.
   
    for i in range(len(T)): #boucle d'exploration
        if T[i]==0: ## si l'entrée qu'on regarde est un zéro alors :
            if currently_in_zero_sequence: #si on a déjà trouvé des zéros avant cette entrée
                length_current +=1 #alors on augmente juste la longueur de la séquence actuelle.
            else: #sinon c'est que ce zéro est le premier d'une séquence
                currently_in_zero_sequence = True #on démarre la séquence courante
                length_current = 1 #la longueur de la séquence actuelle vaut 1 pour le moment
                index_start_current = i #on dit que l'indice de départ de la séquence actuelle vaut i
        else: #sinon, si l'entrée qu'on regarde n'est pas un zéro :
            currently_in_zero_sequence = False # on dit qu'on n'est pas en train d'explorer une séquences de zéros
        if length_current > length_max: #si la longueur de la séquence courante est plus grande que la longueur max enregistrée
            length_max = length_current #on met à jour
            index_max = index_start_current #on met à jour
   
    return index_max, length_max
#Exemples :
print(find([0,0,1,0,1,0,0])) #(0,2)
print(find([1,0,1,0,1,0,0])) #(5,2)
print(find([0,0,0,0])) #(0,4)
print(find([1,1,1,1])) #(None, 0)
print(find([1,0,1])) #(1,1)
 

Bonne soirée

Dernière modification par pentium mix (14-12-2023 05:47:08)

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)