Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Inf 1042 introduction aux structures de donnees seance 3 boucles algorithmes recherche

Memento INF Semestre Année académique - Professeur Maurice TCHUENTE Section Boucles et application aux algorithmes de recherche Les Boucles Dé ?nition Une boucle est une construction algorithmique qui permet d ? exécuter de manière répétitive une instruction ou une suite d ? instructions Il existe trois formes de boucle La boucle Pour La boucle Jusqu ? à ? faire La boucle Tantque ? faire La boucle Faire ? jusqu ? à Boucle Pour Pour Indice ValeurInitiale à ValeurFinale faire Ceci s ? applique lorsqu ? on conna? t à l ? avance le nombre d ? exécutions et les éléments qui seront traités L ? instruction est exécutée pour les valeurs de l ? indice allant de ValeurInitiale à ValeurFinale Boucle Tantque ? faire Tantque faire Le contrôle se fait par la condition de continuation et avant exécution de l ? instruction Tant que cette condition est vraie on exécute l ? instruction Boucle Jusqu ? à ? faire Jusqu ? à faire Le contrôle se fait par la condition de continuation et avant exécution de l ? instruction Tant que cette condition n ? est pas vraie on exécute l ? instruction Boucle Faire ? jusqu ? à Faire Jusqu ? à Le contrôle se fait par la condition de sortie et après chaque exécution de l ? instruction Lorsque cette condition est vraie on s ? arrête Pour cette forme de boucle l ? instruction est donc exécutée au moins une fois CExercice Montrer comment on peut utiliser la forme Jusqu ? à faire Pour réaliser les trois autres formes de boucles Dans la suite nous privilégions la forme Jusqu ? à faire car elle a l ? avantage d ? indiquer clairement la condition de sortie de la boucle Technique de conception des algorithmes basés sur les boucles Pour concevoir un algorithme basé sur une boucle pour la résolution d ? un problème il est conseillé de commencer par bricoler sur un petit exemple en respectant la structure suivante Identi ?er le paramètre permettant de décrire la famille d ? instructions à exécuter Déterminer la valeur initiale v du paramètre Identi ?er les actions permettant d ? initialiser les traitements pour résoudre le problème Action avec paramètre v ??valeur initiale du paramètre ? Action avec paramètre v ? Action avec paramètre vi ??valeur générique du paramètre ? ? Action avec paramètre v ?nal ??valeur du paramètre correspondant à la condition de sortie ? Actions permettant de ?naliser les traitements pour résoudre le problème posé On peut ensuite mettre cet algorithme sous la forme suivante La forme générique d ? un algorithme basé sur une boucle est donc la suivante Jusqu ? à ?n Application à la recherche séquentielle de val dans un vecteur V n On désire déterminer le plus petit indice i correspondant à une occurrence de val dans un vecteur V n Une variable booléenne trouvé indiquera si une telle occurrence existe CL ? algorithme est le suivant trouve faux i Initialisations jusqu ? à