Exercice complexité d'algorithme.

Fermé
Algolover - 10 nov. 2020 à 16:13
yg_be Messages postés 22726 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 26 avril 2024 - 10 nov. 2020 à 22:48
Bonjour, voici l'énoncé de mon exercice, je dois déterminer le role, les opérations significatives puis le meilleur et pire cas.

début
/* ENTRÉES : un entier x et un vecteur V de n entiers trié en ordre décroissant*/
/* SORTIE : le vecteur V modifié */
i ← 1
m ← n
tant que i ≤ m et V(i) ≥ x faire
si V(i) mod x = 0 alors
pour j = i → m−1 faire
V(j) ← V(j +1)
m ← m−1
sinon
i ← i+1
retourner V et m
fin

je ne suis pas sur des résultats mais pour moi, le rôle est de supprimer tout les doublons x dans un vecteur.
les opérations significatives sont v(i) mod x = 0, v(j) = v(j+1) et v(i) => x.
le meilleur cas est lorsque que v(1) > x car l'algorithme s'arrête on a une comparaison et zéro affectation
et le pire cas est lorsque notre vecteur est composé que de multiple de x et que x soit le dernier élement du vecteur, on a 2n comparaison + n affectation

Merci pour votre aide




Configuration: Windows / Chrome 86.0.4240.183

1 réponse

yg_be Messages postés 22726 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 26 avril 2024 1 476
Modifié le 10 nov. 2020 à 22:41
bonjour,
as-tu remarqué que tu ne nous donnes aucun moyen de savoir quand se terminent tes structures de boucle et de test. peux-tu poster plus clairement?
n'est-ce pas plus clair ainsi?
ou bien ajoute des lignes de fin de boucle et de fin de text.
/* ENTRÉES : un entier x et un vecteur V de n entiers trié en ordre décroissant*/
/* SORTIE : le vecteur V modifié */
i ← 1
m ← n
tant que i ≤ m et V(i) ≥ x faire
si V(i) mod x = 0 alors
pour j = i → m−1 faire
V(j) ← V(j +1)
m ← m−1
sinon
i ← i+1
retourner V et m
fin
0
yg_be Messages postés 22726 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 26 avril 2024 1 476
10 nov. 2020 à 22:48
qu'appelles-tu un "doublon x"?
où vois-tu "v(i) => x"?
où puis-je trouver des définitions de ce que tu appelles "role", "opération significative", "meilleur", et "pire cas"?
0