Ecrire une fonction DéterminerSéquences Fermé

Question

Bonsoir,
svp est ce que quelqu'un peut m'aider à résoudre ce prob voila l'énoncé
Écrire une procédure déterminerSéquences, qui à partir d’un tableau d’entiers t d’au moins
un entier, fournit le nombre de sous-séquences strictement croissantes de ce tableau, ainsi que les
indices de début et de fin de la plus grande sous-séquence.
Par exemple, soit t un tableau de 15 éléments : 1; 2; 5; 3; 12; 25; 13; 8; 4; 7; 24; 28; 32; 11; 14. Les
séquences strictement croissantes sont :< 1; 2; 5 >;< 3; 12; 25 >;< 13 >;< 8 >;< 4; 7; 24; 28; 32 >
;< 11; 14 >. Le nombre de sous-séquence est : 6 et la plus grande sous-séquence est :< 4; 7; 24; 28; 32 >.
merci d'avance!

BadGuitarist · Answer

Bonsoir Ryuuga,

Désolé mais que recherches-tu : un algo ? un programme mais dans quel langage ?

BadGuitarist · Answer

Non pour le programme puisque tu ne dis toujours pas dans quel langage TU programmes.
Non quant à faire l'algo A TA PLACE (cf. charte de ce forum).

Par contre, je veux bien te mettre sur la voie :

Il te faut parcourir un tableau d'entiers (TabDonnees). Tu vas donc avoir besoin de ce type d'instruction pour le faire :

  POUR i ALLANT DE 1 A NBMAXELEMENTS FAIRE
     ...
  FINPOUR


Tu vas devoir comparer la valeur de la cellule courante de ton tableau d'entiers par rapport au contenu de la cellule suivante. L'instruction est la suivante :

  TabDonnees[i] >= TabDonnees[i+1]
 
Attention à la valeur de TabDonnees[i+1] en fin de tableau (quand i=NBMAXELEMENTS).

Quand le test ci-dessus est vrai, il te faut :
- incrémenter la longueur de la séquence en cours
- mémoriser le contenu de la cellule i+1 dans un tableau représentant la séquence en cours de création (TabSequence)
Quand le test ci-dessus est faux, il te faut :
- vérifier que la longueur de la séquence que tu viens de générer est plus longue que la précédente : si oui, la variable longueurSequenceLaPlusGde prend la valeur de la longueur que tu viens de générer
- enregistrer TabSequence (qui représente la dernière sequence que tu viens de générer) dans un tableau TabDesSequences (qui contient toutes les séquences découvertes jusque là)

Je te laisse sur cette première ébauche d'analyse. Avec cela, tu as déjà de quoi faire.

ryuuga · Answer

merci pour votre aide voila le résultat que j'ai pu avoir en suivant vos instructions

Entier*Entier*Entier DetrminerSequences(Tab[ ] entier,N)
Entier:i,nbr(nombre de sous-sequences strictement croissante),deb,fin ,nvdeb(debut d'une nouvelle sequences)

début
nbr<--1
déb<--0
fin<---0
nvdéb<--0
pour i<--1 à N faire
si(Tab[i]>Tab[i+1])alors
nbr<---nbr+1
si(i-nvdébu>fin-debu)alors
debu<--nvdébu
fin<--i
finsi
finsi
nvdebu<--i+1
si(n-nvdebu>fin-debu)alors
debu<--nvdebu
fin<---n-1
finsi
finpour
retourner (nbr,debu,fin)
finfct

voila j'espere que c'est correcte pour le titre j'aimerais bien avoir votre avis parceque je ne crois pas que c'est juste meme si notre prof nous di qu'il faut l'ecrire de la meme façon que j'ai utilisé!
et merci pour tout

BadGuitarist · Answer

Bonjour Ryuuga,

Concernant l'algo., je regarderai (promis) dans la matinée (avant midi) et je te donnerai mon algo en m'appuyant le plus possible sur ton travail.

Concernant l'écriture du titre, je suppose que tu veux parler de cela :

  Entier*Entier*Entier DetrminerSequences(Tab[ ] entier,N)

si ta prof dit que c'est correct, alors il faut l'écrire ainsi.
Il ne faut pas perdre à l'esprit que ce n'est qu'un algo., c'est à dire un ensemble de conventions d'écriture que se partage une équipe projet (ou une classe ;-) pour analyser un problème. Quand tu passeras à la programmation, il te faudra certainement faire des adaptations par rapport au langage choisi.

Je me permets juste de te poser une question : que veux-tu dire par Entier*Entier*Entier
dans l'entête de ton algo

  Entier*Entier*Entier DetrminerSequences(Tab[ ] entier,N)


A toute à l'heure pour la correction.

BadGuitarist · Answer

Voici ce que je te propose (n'oublie pas de l'adapter à votre convention d'écriture) :

  Entier*Entier*Entier DeterminerSequences(Tab[ ] entier, N entier)
  DEBUT
    // initialisations
    nbSequences <-- 1                     // nb de séquences trouvées
    lgSeqEnCreation <-- 1                // longueur de la séquence en cours d'identification
    idxDebSeqEnCreation <-- 1         // index début de la séquence en cours d'identification
    idxFinSeqEnCreation <-- 1         // index début de la séquence en cours d'identification
    tabSeqEnCreation[1] <-- Tab[1]  // tableau repsésentant la séquence en cours d'identification

    lgPlusGdeSeq <-- 1                    // longueur de la plus grande séquence trouvée
    idxDebPlusGdeSeq <-- 1             // index début de la plus grande séquence
    idxFinPlusGdeSeq <-- 1               // index fin de la plus grande séquence

    tabSequences[1] <-- Tab[1]       // tableau mémorisant toutes les séquences trouvées

    // Recherche des séquences
    POUR i ALLANT DE 1 A N-1 FAIRE
      SI Tab[i] > Tab[i+1] ALORS    // énoncé : on recherche les séquences STRICTEMENT croissante
        // on aggrandit la séquence en cours
        lgSeqEnCreation <-- lgSeqEnCreation + 1
        tabSeqEnCreation[lgSeqEnCreation] <-- Tab[i+1]
        idxFinSeqEnCreation <-- i+1
      SINON
        // on identifie une nouvelle séquence
        nbSequences <-- nbSequences + 1
        tabSequences[nbSequences] <-- tabSeqEnCreation[]  // chaque cellule de tabSequences contient un
                                                                                      // tableau représentatif d'une séquence
                                                                                      // identifiée
         SI lgSeqEnCreation > lgPlusGdeSeq ALORS
           lgPlusGdeSeq <-- lgSeqEnCreation
           idxDebutPlusGdeSeq <-- idxDebSeqEnCreation
           idxFinPlusGdeSeq <-- idxFinSeqEnCreation
         FINSI

         // réinitialisations avant de traiter une nouvelle séquence
         lgSeqEnCreation <-- 0
         idxDebSeqEnCreation <-- i+1
         idxFinSeqEnCreation <-- i+1 
      FINSI
    FIN POUR

    RETOURNER (nbSequences, idxDebPlusGdeSeq, idxFinPlusGdeSeq)
  FIN

Je pense que, dans ton algo, il manque l'affichage de la séquence la plus longue.
Comme je ne savais pas si tu en avais besoin, je ne l'ai pas non plus intégré à ma solution.

N'oublie pas de bien vérifier les règles d'écriture que tu as apprises et applique les à ton algo.

ryuuga · Answer

oui bonjour BG,bon pour le titre entier*Entier*Entier  ca représente les sorties de la fonction et comme j'ai 3 sorties  de type entier pour le prob donc je dois mettre  Entier*Entier*Entier, on peut aussi mettre booléen au cas ou nous avons des sorties booléen ou réel ca dépend du type des sorties demandé voila, merci pour tt!

Ecrire une fonction DéterminerSéquences

6 réponses

Discussions similaires