Répondre

Wiwaxia · 14-12-2023 14:29:13

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:

Merci à Glozi pour ses remarques.

pentium mix · 14-12-2023 05:38:04

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

Wiwaxia · 14-12-2023 00:55:39

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.

Glozi · 13-12-2023 23:37:51

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 · 13-12-2023 22:52:06

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.

Glozi · 13-12-2023 21:09:56

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

pentium mix · 13-12-2023 19:28:13

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.

pentium mix · 13-12-2023 19:27:01

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)

Fred · 13-12-2023 18:42:03

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)

Wiwaxia · 13-12-2023 18:30:29

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 · 13-12-2023 17:00:53

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.

pentium mix · 13-12-2023 15:04:38

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

Forum de mathématiques - Bibm@th.net

Répondre

Résumé de la discussion (messages les plus récents en premier)

Pied de page des forums