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).

Répondre

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)?
trente neuf plus trente deux
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.

Retour

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

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:

MLojPNyvhEb_4-images-3ab-2ab.png

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

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.
 

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

Pied de page des forums