programme d'une sous suite extraite
Bonjour,
Svp je n'arrive pas a écrire le programme suivant en C++:
Soit une suite de nombres entiers positifs ordonnés par ordre croissant et terminée par le marqueur -1 . écrire un programme permettant de déterminer la longueur l de la plus longue sous suite extraite de s et ne comportant que des éléments identiques.
Exemple: pour s=1 3 3 5 5 5 5 9 9 on a l=4.
Merci de votre aide.
Bonjour,
c'est un algo relativement simple, le même que celui que tu peux appliquer à la main
Tableau 1 3 3 5 5 5 5 9 9 -1 valeur précédante -1 1 3 3 5 5 5 5 9 9 -1 longueur courante 1 1 2 1 2 3 4 1 2 1 longueur max 1 1 2 2 2 3 4 4 4 4 4
Je garde une valeur précédante (valant initialement -1), une longueur courante et une longueur max qu'on initialise à 0. Ensuite on parcours le tableau tant qu'on ne tombe pas sur la valeur -1,
si on a une valeur précédante différente de la valeur de l'élément c'est qu'on commence une nouvelle sous suite dont on va déterminer la longueur, nouvelle suite=>longueur de la suite=1, valeur précédante devient égale à la valeur de l'élément sur lequel on est pour le tour suivant de la boucle
sinon si on a une va;eur précédante égale à l'élément sur lequel on est ça signifie qu'on est dans une sous suite et qu'on a trouvé un élément qui l'allonge : longueur courante doit être incrémentée de 1
On vient de traiter un élément du tableau, longueur courante contient la longueur de la sous suite, on vérifie qu'elle est supérieur à la plus grande longueur trouvée jusqu'à présent; si c'est le cas alors longueur max devient égal à longueur courante.
Voilà, la première chose à faire est de pouvoir résoudre le problème à la main sur une feuille de papier. Il va également falloir vérifier deux ou trois trucs histoire de s'assurer que ça fonctionne même avec des cas de figures etrêmes : est-ce que ce que je raconte fonctionne toujours quand le tableau est vide (i.e.s={-1}), est-ce que ça fonctionne s'il y a plus d'une sous-suite de longueur max (i.e. s={1,1,2,2,-1}), etc ...
Ensuite la seconde chose à faire est de construire l'algorithme. Le travail est mâché ... tu devrais je pense y arriver sans trop de problèmes.
Et la toute dernière chose à faire : pisser le code et le vérifier (devient souvent trivial si les deux premières étapes ont été passées avec succès).
Je vous remercie sur votre explication bien détaillé.
Bonne nuit a vous.
