Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#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

Fred a écrit :

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

Wiwaxia a écrit :

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.

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

#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):

MLnuzAF1kvb_2-images.png

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

Glozi a écrit :

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)

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:

MLojRGgCTub_Program-s%C3%A9quence-Z%C3%A9ros.png

et la vérification observée dans le cas de deux séquences:

MLojPNyvhEb_4-images-3ab-2ab.png

Merci à Glozi pour ses remarques.

Dernière modification par Wiwaxia (14-12-2023 14:31:01)

Hors ligne

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de l'opération suivante (donner le résultat en chiffres)?
dix-neuf plus trente huit
Système anti-bot

Faites glisser le curseur de gauche à droite pour activer le bouton de confirmation.

Attention : Vous devez activer Javascript dans votre navigateur pour utiliser le système anti-bot.

Pied de page des forums