Algorithmes typiques

Dans la plupart des cas les algorithmes des problèmes plus compliqués sont basés sur l`application des algorithmes plus simples qui sont appelés t y p i q u e s.

On appele les algorithmes t y p i q u e s ceux qui sont appliqués plus souvant . Ces algorithmes sont présentés au-dessous.

2.2.1 Calcul de la somme des nombres d`une série arbitraire

On a donné : une série de nombres arbitraires

Il faut calculer : la somme de ces nombres, c`est-à-dire

L`algorithme de la résolution de ce problème est représenté sur la fig. 2.2.

fig. 2.2 Organigramme du calcul de la somme d`une série de nombres.

L`algorithme prévoit l`utilisation de l`opération cyclique. À titre du paramètre du cycle on a pris l`indice de l`élément ou bien son numéro d`ordre qui est le méme. Le corps du cycle est présenté par la formule dite r é c u r r e n t e .

On appele la formule r é c u r r e n t e celle qui prévoit le calcul de la valeur suivante d`un paramètre d`après sa valeur précédente. Cet algorithme posséde une opération importante (S = 0). Elle assure le nettoyage par zéro la cellule, réservée pour la variable S. Le nettoyage est nécessaire pour éliminer l`erreur dans le résultat obtenu. Cette opération est provoquée par la circonstance suivante. Chaque fois on réserve des cellules dans la mémoire centrale pour toutes les données qui prennent part au processus du calcul. Après l`achèvement de l`exécution du programme précédent toutes les cellules réservées pour les données restent occupées. Ils ne s`émancipent pas automatiquement. Les données restantes du programme précédent sont les « ordures » pour un nouvau programme.Voila pourquoi les cellules réservées pour les données qui prennent part aux formules reccurentes doivent être nettoyées. Pour les autres données cette action n`est pas obligatoire.

2.2.2 Calcul du produit des nombres d`une série arbitraire

On a donné :une série de nombres arbitraires .

Il faut calculer :le produit des nombres , c`est-à-dire

L`organigramme du processus de calcul qui résout ce problème est représenté sur la fig.2.3.

Fig. 2.3 Organigramme du calcul du produit d`une série de nombres

Il est analogue à l`organigramme précédent. Le produit des nombres P est calculé par la formule réccurrente . C`est pourquoi la cellule de mémoire réservée pour cette variable doit être nettoyée. À la différence de la cellule réservée pour la somme la cellule réservée pour le produit est nettoyée par unité. Le nettoyage par zéro dans ces cas provoque la transformation du produit à zéro ce qui fausse le résultat final.

2.2.3 Détermination d`un élément maximal (minimal) d`une série de nombres

On a donné :une série de nombres arbitraires

Il faut déterminer : un élément maximal de cette série.

L`algorithme de la résolution de ce problème est représenté sur la fig.2.4.Il est basé sur l`utilisation de l`opération cyclique.Dans ce cycle un élément maximal est comparé successivement avec tous les autres éléments de la série . Au début à titre de l`élément maximal on prend le premier élément de la série indépendemant de sa valeur véritable. Cette opération doit être réalisée avant le cycle. Dans le corps du cycle (bloc 7) s`éffectue l`opération de comparaison. Si le résultat de cette comparaison est positif le rôle de l`élément maximal prend l`élément courant . En même temps dans la cellule réservée pour la variable kest mémorisée l`adresse de cet élément. Si le résultat de comparaison est négatif la variable reste inchangée. Comme résultat d`une telle analyse on obtient la valeur de l`élément maximal et son adresse k dont les valeurs sont indiquées sur l`écran de l`afficheur (bloc 11).

La détermination d`un élément minimal s`éffectue de la manière analogue. Dans ce cas, l`organigramme présenté sur la fig. 2.4 est utilisé avec les changements suivants :

- la signification est changée de ,

- l`opération est changée de .

2.2.4 Détermination de la valeur maximale (minimale) d`une fonction calculée

- On a donné :une fonction dont l`argument varie dans le diapason de jusqu`à avec un pas h

Il faut déterminer : la valeur maximale de cette fonction calculée.

L`organigramme de la résolution de ce problème (fig. 2.5) est analogue à celui présenté sur la fig.2.4. Au début, la première valeur calculée de la fonction y=f( ). est pris à titre de valeur initiale de la variable . L`argument x qui varie avec le pas h (bloc 11) est utilisé à titre du paramètre du cycle dans la tête du cycle (bloc 6), La valeur courante de la fonction y=f(x) calculée préalablement (bloc 7) est comparée avec la valeur maximale (bloc8) dans le corps du cycle . Si le résultat de comparaison est positif (+) , prend sa nouvelle valeur égale à la valeur courante de la fonction y=f(x) (bloc 9). En même temps, la valeur courante de l`argument x (bloc 10) est mémorisée dans la cellule reservée pour la variable x. Finalement après l`achèvement du cycle le résultat et (bloc 12) est indiqué.

La détermination de la valeur minimale de la fonction calculée est éffectuée de la manière analogue. Dans ce cas il est nécessaire de changer de et l`opération de dans l`organigramme (fig.2.5) .

2.2.5 Rangement d`une série de nombres

On appele le r a n g e m e n t la disposition des nombres d`une série en accroissement ou décroissement de ses valeurs.

Il existe quelques méthodes de la résolution de ce problème. Mais les méthodes le plus répandues sont les suivantes :

- la méthode des paires voisines ( dites méthode de « bulle »)

- la méthode de la recherche d`un élément minimal (maximal).

2.2.5.1 Méthodes des paires voisines

L`idée de l`algorithme est basée sur la comparaison successive des paires voisines des nombres. L`organigramme de la résolution de ce problème est représenté sur la fig. 2.6.

Fig. 2.6 Organigramme du rangement d`une série de nombres en accroissement par la méthode des paires voisines

Un cycle réalise cette comparaison. Si la comparaison de deux nombres voisins donne le résultat positif (+), on fait l`échangement de ces nombres. Ce dernier se fait à l`aide d`une variable intermédiaire R( blocs 8,9,10). Le fait de cette action est fixé par la variable F, qui prend dans ce cas sa valeur ‘1’ (bloc 11). Une telle comparaison déplace le nombre maximal à la fin de la série. Donc après la première réalisation du cycle le nombre maximal occupe la dernière place dans la série. Pour éliminer ce nombre de l’examen suivant on raccourcit la série à cet élément (bloc 14 ). Après chaque réalisation du cycle, on vérifie la valeur de la variable F (bloc 13). Si sa valeur est égale à zéro, cela indique que tous les membres sont rangés, par contre la nouvelle réalisation du cycle s`effectue. Avec cela , on établit préalablement la valeur ‘0’ pour la variable F (bloc 4), c`est-à-dire on la retourne en état initial. Les opérations cycliques se répétent jusqu`à ce que la valeur zéro de la variable F reste inchangée. L`organigramme du rangement en décroissement est analogue à celui présenté sur la fig.2.6. Dans ce cas, il faut changer la signe ‘>’ dans le bloc 7 de signe ‘<’. Du point de vue de la dépense du temps cette méthode est efficace. Si la série de nombres est rangée d`avance il faut faire seulement une fois l`opération cyclique pour fixer le fait que la valeur zéro (initiale) de la variable F reste inchangée. Ce fait signale que pendant l`opération cyclique on n`a pas fixé les échangements des nombres. Cela signifie que tous les nombres sont disposés comme il faut.

2.2.5.2 Méthode du rangement par la recherche d`un élément minimal (maximal)

L`idée de cette méthode est basée sur la recherche du nombre minimal (pour le rangement en accroissement) ou du nombre maximal (pour le rangement en décroissement). Après cela , l`élément trouvé (minimal ou maximal)est échangé de premier élément de la série examinée. Une telle opération est répétée n-1 fois, où n- est la quantité des nombres de la série examinée. Chaque fois la série de nombres se raccourcit de premier élément. Donc ces opérations sont commencées en partant de la série initiale (avec n éléments) et sont finites avec la série qui se compose de deux nombres.

L`organigramme du rangement d`une série de nombres en accroissement est présenté sur la fig. 2.7 .

Les opérations 5-12 représentent l`algorithme typique de la détermination d`un élément maximal d`une série ( ). La variable consérve l`adresse de cet élément. Les opérations 13,14 effectuent l`échangement de l`élément minimal al et premier élément de la série examinée dans ce cycle.

Cet échangement se fait à l`aide de la variable . Le cycle externe chaque fois diminue en unité la limite gauche du diapason de la variation du paramètre i du cycle imbriqué (opération 16).

Le rangement d`une série de nombres en décroissement par cette méthode s`effectue de façon analogue. Dans ce cas il faut changer dans organigramme (fig.2.7) de et l`opération 9 ( ) de ( ).

Cette méthode utilise l`algorithme sévère du rangement. Elle prévoit toujours n-1 opérations de la recherche de l`élément minimal (maximal) independement de la disposition initiale des nombres de la série examinée. Cela signifie que n-1 opérations réaliseront et même dans le cas, quand la série de départ sera rangée d`avance.

L`analyse de ces deux méthodes examinées montre que la méthode du rangement par des paires voisines est plus efficace que celle du rangement par la recherche d`un élément minimal (maximal) du point de vue de la dépense du temps.

2.2.6 Algorithmes typiques de la résolution des problèmes avec utilisation des matrices

Le cycle externe est déstiné à la fixation de l`adresse courante d`une ligne de la matrice et le cycle interne (imbriqué) est déstiné à la fixation de celle d`une colonne.

Dans certains cas il est nécessaire de connaître quel cycle doit être externe et quel cycle doit être interne. Dans ce cas, il faut se guider par la règle suivante. Si le problème posé prévoit n`importe quelles opérations dans les lignes de la matrice le cycle est pris comme externe qui donne l`adresse courante des lignes, alors le cycle interne donne l`adresse des colonnes. Si les opérations sont prévues dans les colonnes ces cycles sont disposés de la manière inverse. En tels cas, quand la place des opérations dans la matrice ne sont pas accentuées (par exemple le calcul de la somme ou du produit de tous les éléments de la matrice) il n`y a pas de différence dans la disposition des cycles l`un par rapport à l`autre.

Exemple 1 . Il faut déterminer l`élément maximals dans chaque ligne dans la matrice donnée

L`organigramme de la résolution de ce problème est présenté sur la fig.2.9.

Exemple 2. Il faut déterminer l`élément maximal dans chaque colonne dans la matrice donnée

Ce problème est en quelque sorte inverse par rapport au problème précédent. En vue que les opérations sont prévues dans les colonnes de la matrice le cycle est pris comme externe qui donne l`adresse courante de chaque colonne. Alors le cycle interne donne l`adresse courante de chaque ligne (fig.2.10).

Toutes les autres opérations restent les mêmes que dans l`organigramme précédent.

R é s u m é.

Les organigrammes présentés ne sont pas l`énumération complete de toutes les opérations avec les matrices. Mais ils peuvent être utilisés comme les fragments lors de l`élaboration des algorithmes plus compliqués.

Il est nécessaire de bien comprendre la logique des algorithmes typiques, de les rappeler et de les appliquer savannement lors de la résolution des problèmes plus compliqués. Cela permet d`économiser le temps nécessaire pour élaboration des algorithmes des autres problèmes.

3. INFORMATION BRÈVE SUR LE LANGAGE C++

Le langage C++ est le langage algorithmique orienté objet qui a hérité toutes les propriétés principales du langage C orienté structure auquelle il a ajouté des nouveaux types des variables nommées les objets. Ce complément a donné au langage les nouvelles qualités, qui ont beaucoup élargis de possibilités de la langue.

Le langage C++ est fondé sur trois conceptions principales :

- e n c a p s u l a t i o n,

- p o l i m o r p h i s m e,

- h é r i t a g e .

L`auteur du langage C++ est M. Biarne Straoustroup, le collaborateur scientifique du centre de la recherche et de la science AT & T Bell Laboratoiries ( ville New Jerci, USA ). L`an de la création est 1979.

Le langage C++ a été modernisé considérablement deux fois en 1985 et en 1990. Après cela, la troisième et la dernière modernisation qui est liée au processus de la standardisation du langage a eu lieu.

À l`heure actuelle il existe le standard du langage C++ qui a été élaboré par le comité de la standardisation ANSI ( American National Standards Institute ) et par l`organisation internationale de standards ISO ( International Standards Organisation ).

Le langage C++ est devenu le langage universel pour les programmeurs du monde entier. C`est un langage unique que chaque programmeur professionnel doit connaître obligatoirement. Beaucoup d`auteurs des livres estiment ce langage comme langage de XXI siècle.

Toutes les recommandations pour l`exécution des travaux pratiques sont données en correspondance à la version Borland C++ 3.2.

4. RECOMMANDATIONS MÉTHODOLOGIQUES POUR L`EXÉCUTION DES TRAVAUX PRATIQUES

4.1 Ordre de l`exécution des travaux pratiques

Certain travail préparatoire à domicile doit être précedé chaque travail pratique (TP) . Le travail doit comprendre les étapes suivantes :

- révision de la matière théorique exposé pendant le cours qui concerne le sujet du travail pratique ;

- étude attentive du sujet du travail et des recommandations présentées pour l`exécution ;

- élaboration de l`algorithme du processus de calcul (organigramme) ;

- composition du programme ;

- préparation des réponses aux questionsprésentées dans le paragraphe « Questions de contrôle et devoirs » à la fin de chaque travail pratique.

Avant de commencer à faire le travail pratique, l`étudiant est obligé de montrer au professeur l`organigramme et le programme du processus de calcul et de répondre aux questions concernant le sujet du travail pratique. Après avoir reçu la permission, l`étudiant commence à faire le travail pratique.

Les travaux pratiques sont faits dans le laboratoire équipé par les ordinateurs. Au cours de l`exécution du travail pratique, l`étudiant, doit créer le fichier qui comprend le texte du programme écrit d`avance, déboguer le programme et faire la réalisation. Après avoir obtenu les résultats du calcul l`étudiant doit les montrer au professeur. La partie pratique du travail est reconnue comme terminée si le professeur a mis la note positive pour ce travail.

L`étape suivante est la préparation du compte rendu sur le travail et sa soutenance. Le compte rendu est fait au-dehors de la séance pendant le temps libre par l`étudiant lui-même. La forme et la contenue du compte rendu doivent satisfaire à toutes les exigences présentées au-dessous. Au début de la séance suivante l`étudiant doit soutenir son compte rendu. La soutenance consiste en exposition du sujet du travail pratique par l`étudiant et en réponses à toutes les questions du professeur concernant le sujet du travail. L`étudiant reçoit la permission pour l`exécution du travail pratique suivant après la soutenance du compte rendu sur le travail précédent et l`exécution du travail préparatif pour le travail suivant. Si l`étudiant n`a pas fait le travail pratique au cours de la séance, il doit le términer lui-même pendant le temps libre.

Chaque travail pratique comprend quelques variantes des devoirs. Le numéro de la variante est le numéro d`ordre de l`étudiant dans la liste du groupe qui a le professeur. Le professeur annonce à l`étudiant le numéro de sa variante.

4.2 Exigences posées à la préparation du compte rendu sur le travail pratique

1. Le texte du compte rendu doit être pésenté sur les feuilles de papier du format A4 sur un côté .

2. La première page doit être présentée par la page de titre selon la forme illustrée sur la fig. 4.1.

1. Sur les pages suivantes doivent être présentés

- but du travail,

- énoncé du problème,

- organigramme du processus du calcul,

- programme (impression),

- résultat du calcul (impression),

- analyse des résultats obtenus et conclusion.

2.

// étudiant du groupe F01a, M. Duran, var. 10

TRAVAUX PRATIQUES

Date: 2015-12-24; view: 1777