Vue linéaire de l'algorithme. Types d'algorithmes : linéaire, ramifié, cyclique. Méthodes de description des algorithmes

Boucle avec précondition

Dans le cadre de programmation structurée problèmes avec une solution algorithmique peuvent être décrits en utilisant ce qui suit structures algorithmiques:

• Suivant... Suppose l'exécution séquentielle des commandes de haut en bas. Si l'algorithme se compose uniquement de structures de succession, alors il est linéaire.
• Branchement... Performance le programme va l'une des deux, plusieurs ou plusieurs branches. Le choix d'une branche dépend de la condition à l'entrée de la branche et des données reçues ici.
• Cycle... Suppose la possibilité de répétition de certaines actions. Le nombre de répétitions dépend de l'état du cycle.
• Fonction (sous-programme)... Les commandes séparées du programme principal ne sont exécutées que si elles sont appelées depuis le programme principal (de n'importe quel endroit de celui-ci). La même fonction peut être appelée à partir du programme principal un nombre illimité de fois.

Description de diverses structures algorithmiques dans le langage des schémas fonctionnels

Branchement si
C'est le type de branchement le plus simple. Si le résultat de l'évaluation de l'expression conditionnelle renvoie vrai, alors l'exécution de l'algorithme se fait le long de la branche « Oui », qui inclut des expressions d'action supplémentaires. Si la condition retourne faux, alors l'exécution de l'algorithme suit la branche "non", c'est-à-dire que la branche principale du programme continue de s'exécuter.

Branchement if-else
Si l'expression de condition retourne vrai, alors l'exécution de l'algorithme passe par la branche "Oui", si la condition n'est pas remplie (faux), alors l'exécution passe par la branche "Non". Pour tout résultat de l'expression conditionnelle, il est impossible de revenir à la branche principale du programme, en contournant les étapes supplémentaires.

Branchement if-elif-else
Le nombre de conditions peut être différent. Si le premier est exécuté, après avoir effectué les actions, le programme passe à la branche principale sans vérifier d'autres conditions. Si la première condition renvoie faux, la deuxième condition est vérifiée. Si la deuxième condition retourne vrai, alors les actions incluses dans la deuxième branche de la construction sont exécutées. La dernière condition n'est vérifiée que si aucune des conditions précédentes n'a renvoyé la valeur true. Cette construction algorithmique (if - elif - else) ne doit pas être confondue avec la construction algorithmique Choice.

Alors que la boucle
Tant que la condition est remplie (résultat expression logique donne true), les actions du corps de la boucle seront exécutées. Après la prochaine exécution des actions imbriquées, la condition est à nouveau vérifiée. Pour que l'exécution de l'algorithme ne boucle pas, dans le corps de la boucle (entre autres actions), il doit y avoir une expression, à la suite de laquelle la variable utilisée dans la condition sera modifiée. Le corps de la boucle peut ne jamais être exécuté si la condition était fausse dès le début.

Faire une boucle
Dans cette boucle, la condition n'est vérifiée pour la première fois qu'après l'exécution des actions du corps de la boucle. Si la condition renvoie true, les expressions d'action sont à nouveau répétées. Quelle que soit la condition, le corps de ce cycle sera exécuté au moins une fois.

Pour boucle
Cette boucle est également appelée boucle « for ». Son titre précise trois paramètres : la valeur initiale de la variable (from), bien sûr la valeur (to) et son évolution à l'aide de opération arithmétiqueà chaque "tour" du cycle (pas).

>> Types d'algorithmes

Dans les algorithmes, les commandes sont écrites les unes après les autres dans un ordre spécifique. Ils ne sont pas nécessairement exécutés dans la séquence enregistrée : selon l'ordre dans lequel les commandes sont exécutées, on peut distinguer trois types d'algorithmes :

Algorithmes linéaires ;
algorithmes de branchement;
algorithmes avec répétitions.

Algorithmes linéaires

Dans lequel les commandes sont exécutées dans l'ordre dans lequel elles sont écrites, c'est-à-dire séquentiellement l'une après l'autre, est appelée linéaire.

Par exemple, l'algorithme de plantation d'arbres suivant est linéaire :

1) creuser un trou dans le sol;
2) abaisser le semis dans le trou;
3) remplir le trou avec le semis avec de la terre;
4) arroser le semis avec de l'eau.

À l'aide d'un schéma fonctionnel, cet algorithme peut être décrit comme suit :

Algorithmes de branchement

Les situations où la séquence des actions requises est connue à l'avance sont extrêmement rares. Dans la vie, vous devez souvent prendre une décision en fonction de la situation qui prévaut. S'il pleut, nous prenons un parapluie et mettons un imperméable ; s'il fait chaud, portez des vêtements légers. Il existe également des conditions de sélection plus complexes. Dans certains cas, le sort d'une personne dépend de la décision choisie.

La logique décisionnelle peut être décrite comme suit :

SI<условие>ALORS<действия 1>AUTREMENT<действия 2>

Exemples:

Si tu veux etre sain, ALORS soyez tempéré, AUTREMENT allongez-vous sur le canapé toute la journée;
SI les hirondelles volent bas, ALORS il pleuvra, SINON il ne pleuvra pas ;
SI les leçons sont apprises, ALORS allez vous promener, SINON apprenez les leçons.

Dans certains cas<действия 2>peut être absent;

SI<условие>ALORS<действия 1>

Exemple:

S'il s'appelait une charge, alors montez à l'arrière.

Une forme d'organisation d'actions dans laquelle, en fonction de la réalisation d'une certaine condition, l'une ou l'autre est exécutée sous-séquenceétapes est appelé branchement.

Représentons sous forme d'organigramme la séquence d'actions d'un élève de 6e année Vasya Mukhin, qu'il imagine comme suit : « Si Pavlik est à la maison, nous résoudrons des problèmes de mathématiques. Sinon, nous devrions appeler Marina et préparer un rapport de biologie ensemble. Si Marina n'est pas à la maison, alors vous devez vous asseoir pour rédiger. "

Et ainsi, à l'aide du schéma fonctionnel, vous pouvez très clairement représenter le raisonnement lors de la résolution du problème suivant.

Sur trois pièces de même valeur, une est contrefaite (plus légère). Comment le trouver à l'aide d'une pesée sur une balance sans poids ?

Algorithmes de répétition

Dans la pratique, il existe souvent des tâches dans lesquelles une ou plusieurs actions doivent être répétées plusieurs fois, tant qu'une condition prédéterminée est remplie.

Algorithme contenant cycles s'appelle un round robin ou un algorithme répétitif.

Une situation dans laquelle l'exécution d'une boucle ne se termine jamais est appelée une boucle sans fin. Des algorithmes devraient être développés pour éviter de telles situations.

Regardons un exemple des maths.

Un nombre naturel est dit premier s'il n'a que deux diviseurs : un et le nombre lui-même1.

2, 3, 5, 7 - nombres premiers ; 4, 6, 8 - non. Au 3ème siècle avant JC, le mathématicien grec Eratosthène a proposé l'algorithme suivant pour trouver tous les nombres premiers inférieurs à un nombre donné n :

1) écrivez tous les nombres naturels de 1 à n ;
2) supprimer 1 ;
3) souligner le plus petit des nombres non marqués ;
4) rayez tous les nombres qui sont des multiples du souligné à l'étape précédente ;
5) si la liste contient des nombres non marqués, passez à l'étape 3, sinon tous les nombres soulignés sont premiers.

Il s'agit d'un algorithme cyclique. Lorsqu'il est exécuté, les étapes 3 à 5 sont répétées jusqu'à ce qu'il y ait des numéros non marqués dans la liste d'origine.

Voici à quoi ressemble l'organigramme des actions d'un écolier, qui devrait être fait avant une promenade du soir devoirs mathématiques:

Rappelons que le nombre 1 n'est ni un nombre composé (ayant plus de deux diviseurs) ni un nombre premier.

La chose la plus importante

On distingue trois types d'algorithmes selon l'ordre d'exécution des commandes :

> algorithmes linéaires ;
> algorithmes de branchement ;
> algorithmes de répétition.

Un algorithme dans lequel les commandes sont exécutées dans l'ordre où elles sont écrites, c'est-à-dire séquentiellement les unes après les autres, est appelé linéaire.

La forme d'organisation d'actions, dans laquelle, en fonction de la réalisation d'une certaine condition, l'une ou l'autre séquence d'étapes est effectuée est appelée branchement.

La forme d'organisation d'actions dans laquelle l'exécution de la même séquence de commandes est répétée alors qu'une condition prédéterminée est remplie est appelée cycle (répétition).

Questions et tâches

1. Quels algorithmes sont appelés linéaires ?
2. Donnez un exemple d'algorithme linéaire,
3. Performer "Calculator" ne peut exécuter que deux commandes : multiplier par 2 et additionner. Proposez le plan le plus court pour obtenir le nombre 50 sur O.
4. Quelle forme d'organisation des actions est appelée embranchement ?
5. Quelles conditions l'héroïne du conte "Oies-Cygnes" devait-elle remplir ?
6. Donnez un exemple d'algorithme qui contient des branchements "
7. Lisez un extrait du poème de J. Rodari « À quoi ressemble l'odeur de l'artisanat ? » :

Chaque étui a une odeur particulière :
La boulangerie sent la pâte et les produits de boulangerie.
Vous passez devant l'atelier de menuiserie -
Ça sent les copeaux et la planche fraîche.
Le peintre sent la térébenthine et la peinture.
Le vitrier sent le mastic pour vitres.
La veste du chauffeur sent l'essence
Chemisier ouvrier - huile de machine.

Reformulersur les métiers en utilisant les mots "SI ... ALORS" /

8. Rappelez-vous les héros dont les contes populaires russes font des choix qui déterminent leur destin.
9. Sur 9 pièces de même valeur, une est fausse (plus légère). Combien de pesées sur une balance sans poids pouvez-vous la déterminer ?
10. Quelle forme d'organisation des actions est appelée répétition ?
11. Donnez un exemple d'algorithme qui contient des répétitions.
12. Dans quelles œuvres littéraires que vous connaissez prend place une forme cyclique d'organisation d'actions ?
13. Où sera l'artiste qui a complété le groupe d'équipes suivant 16 fois de suite ?

marcher 10 mètres en avant

tourner de 90 ° dans le sens des aiguilles d'une montre

14. Quel groupe d'actions et combien de fois faut-il les répéter pour résoudre le prochain problème ?

Quarante soldats se sont approchés de la rivière, le long de laquelle deux garçons se promènent dans un bateau. Comment les soldats peuvent-ils passer de l'autre côté si le bateau ne peut contenir qu'un soldat ou deux garçons, mais que le soldat et le garçon ne le peuvent plus ?

15. Rappelez-vous le problème d'une calculatrice qui ne peut que multiplier par 2 et ajouter 1. Il sera beaucoup plus facile de développer des algorithmes rationnels pour cela si vous utilisez le diagramme suivant :

À l'aide de cet organigramme, développez des algorithmes rationnels pour obtenir les nombres 1024 et 500 à partir du nombre 0.

Bosova L. L. Informatique : manuel pour la 6e année / L. L. Bosova. - 3e éd., Rév. et ajouter. - M. : BINOM. Laboratoire des Connaissances, 2005. - 208 p. : ill.

Pour écrire des algorithmes, ainsi que du langage naturel ou mathématique, il est pratique d'utiliser le langage des diagrammes. Un schéma fonctionnel est une représentation graphique d'un algorithme dans lequel chaque étape du processus de traitement des données est représentée sous la forme d'une figure géométrique de type fixe, appelée symbole. Les symboles sont reliés par des lignes indiquant le sens des flux d'informations. Chaque symbole contient une description de l'étape correspondante du traitement des données. Si la description est lourde, elle est enregistrée séparément en tant que commentaire. Les principaux symboles sont indiqués dans le tableau.

Les symboles sont reliés par des lignes de communication. Un point est mis à l'endroit où les personnages se confondent. Les symboles peuvent être numérotés pour faciliter l'affichage des connexions où le circuit est coupé. Ces nombres ne déterminent pas l'ordre d'exécution de l'algorithme, dépendant uniquement des lignes reliant les flux.

Tous les algorithmes sont divisés par leur structure en trois groupes :

Linéaire;

Branchement ;

Cyclique.

Un algorithme qui ne contient pas de conditions est dit linéaire. Cet algorithme détermine inconditionnellement le processus de transformation des données. Un exemple d'un tel algorithme est le calcul pas à pas d'une formule mathématique. Chaque opération élémentaire est effectuée dans l'ordre établi par les règles de calcul sans analyser le résultat précédemment obtenu. Le schéma fonctionnel d'un algorithme linéaire est une chaîne séquentielle de caractères "traiter", ayant la forme d'un rectangle, complété par des symboles "entrée sortie" et "Début Fin".

Riz. 8. Schéma fonctionnel de l'algorithme linéaire

Fourche algorithme contient au moins une condition. Pour la mise en œuvre de l'algorithme de branchement, une structure typique BRANCHING est utilisée. L'algorithme de branchement est basé sur l'élément logique de la condition, représenté sur le schéma par le symbole ROMB. Dans l'élément logique, un contrôle de condition est effectué, ce qui donne le résultat OUI ou NON. En fonction de cela, le flux d'informations est dirigé le long d'une des deux voies de sortie de l'élément logique.

Cet algorithme peut avoir deux options :

1. Si la condition est remplie, alors le flux d'informations est envoyé au bloc du processus de calcul pour lequel la condition a été vérifiée ; si la condition n'est pas remplie, le flux d'informations est dirigé vers les éléments suivants de l'organigramme. Ainsi, schéma logique peut être écrit comme SI (condition) - ALORS (formule).

2. Il existe DEUX FORMULES de calculs, et l'algorithme fonctionne selon le principe logique suivant : SI (condition) - ALORS (formule 1), SINON (formule 2).

Si vous devez vérifier plusieurs conditions, alors l'algorithme prend la forme d'un "arbre" avec des branches sous forme de "branches". Le nombre d'éléments logiques est toujours un de moins que le nombre de conditions, puisque chaque élément a une entrée et deux sorties. La section de l'algorithme avant le branchement est appelée baril, état - point de branchement, directions alternatives du processus de calcul après le point de branchement - branches.

9. Organigrammes des algorithmes de fork

Un tel algorithme est appelé cyclique, certaines des actions dans lesquelles sont répétées plusieurs fois. De telles actions répétitives sont appelées "cycle". Algorithmes cycliques contiennent les conditions de fonctionnement du cycle, ils peuvent donc être considérés comme une sorte d'algorithmes de branchement, dans lesquels l'une des branches fait partie du tronc, qui se répète plusieurs fois. Ces actions répétitives constituent un cycle.

Les algorithmes cycliques sont divisés en Deux types:

Avec un nombre connu de répétitions (cycles)

Algorithmes itératifs dans lesquels le nombre de cycles n'est pas connu à l'avance et la fin du cycle est déterminée par une certaine condition (principalement une précision de calcul donnée).

Considérons les deux types d'algorithmes.