Types d'algorithmes informatiques. Structures algorithmiques (types d'algorithmes). Manière verbale d'écrire des algorithmes

L'algorithme illustré à la figure 12 est appelé algorithme de précondition cyclique, puisque la condition est vérifiée au début de la boucle ou à l'entrée de la boucle. > X à l'entrée de la boucle. Si la condition est remplie, passez au bloc 4, sinon au bloc 6.

Le quatrième bloc calcule la valeur de la variable à je= je+1 .

Le cinquième bloc affiche le résultat :

Valeur variable à,

je.

Exemple : Rédigez un exemple d'organigramme (Figure 12), en vérifiant la condition de sortie de la boucle. Dans cet exemple, la condition de la tâche ne change pas et la sortie est la même, mais l'organigramme sera différent.

Solution : Dans ce cas, la condition de sortie de boucle est vérifiée : oui<=x ... Dans cette condition, la boucle n'est pas exécutée. La condition dans le schéma fonctionnel doit être transférée à la fin du cycle, après avoir été imprimée. Le cycle est exécuté tant que la condition est remplie y> x.

L'algorithme, si la condition est transférée à la fin du cycle, est appelé algorithme de boucle avec postcondition... L'algorithme pour ce problème est montré dans la Fig. treize.

Le deuxième bloc présente oui=30 , X=4 .

Le troisième bloc calcule la valeur de la variable à , le nombre de cycles terminés est compté je= je+1 .

Le quatrième bloc affiche le résultat :

Valeur variable à,

Nombre de cycles terminés je.

Le cinquième bloc vérifie la condition oui <= X pour sortir de la boucle. Si la condition est remplie, passez au bloc 6, sinon, au bloc 3 et le cycle se répète.

13. Algorithme de boucle avec postcondition

Questions de contrôle

1. Le concept d'algorithme.

2. Types d'algorithmes.

3. Structures algorithmiques de base.

4. Les principaux blocs de l'algorithme graphique.

5. Structure algorithmique linéaire. Exemple.

6. Branchement. Exemple.

7. Structures algorithmiques cycliques. Exemple.

En pratique, les formes suivantes de présentation des algorithmes sont les plus courantes :

· Verbal (enregistrements en langage naturel);

· Graphique (images à partir de symboles graphiques);

· Pseudocodes (descriptions semi-formalisées d'algorithmes dans un langage algorithmique conditionnel, comprenant à la fois des éléments de langage de programmation et des phrases en langage naturel, notation mathématique généralement acceptée, etc.);

· Logiciel (textes en langages de programmation).

Voie verbale Les enregistrements d'algorithmes sont une description des étapes séquentielles du traitement des données. L'algorithme est défini sous forme libre en langage naturel. Par exemple. Écrivez l'algorithme pour trouver le plus grand diviseur commun (GCD) de deux nombres naturels.

L'algorithme peut être le suivant :

· Définir deux nombres ;

Si les nombres sont égaux, prenez l'un d'eux comme réponse et arrêtez-vous à

sinon, continuer l'exécution de l'algorithme ;

· Déterminer le plus grand des nombres;

· Remplacer le plus grand des nombres par la différence entre le plus grand et le plus petit des nombres ;

· Répétez l'algorithme de l'étape 2.

L'algorithme décrit est applicable à tous les nombres naturels et devrait conduire à la solution du problème.

Voie verbale n'est pas répandu pour les raisons suivantes :

· Ces descriptions ne sont pas strictement formalisées ;

· Souffrez de la verbosité des enregistrements;

· Permettre l'ambiguïté dans l'interprétation des règlements individuels.

Manière graphique la présentation des algorithmes est plus compacte et visuelle que celle verbale.

Cette représentation graphique est appelée diagramme d'algorithme ou diagramme.

Dans une présentation graphique, l'algorithme est représenté comme une séquence de blocs fonctionnels interconnectés, dont chacun correspond à l'exécution d'une ou plusieurs actions.

Dans l'organigramme, chaque type d'action (saisie de données initiales, calcul de valeurs d'expression, conditions de contrôle, contrôle de répétition d'actions, fin de traitement, etc.) correspond à une figure géométrique présentée sous la forme d'un bloc symbole. Les symboles de bloc sont connectés par des lignes de transition qui déterminent l'ordre dans lequel les actions sont effectuées.

1) Bloc début-fin

L'élément affiche la sortie vers l'environnement externe et l'entrée de l'environnement externe (l'utilisation la plus courante est le début et la fin d'un programme). L'action correspondante est enregistrée à l'intérieur de la forme.

2) Bloc d'action

Effectuer une ou plusieurs opérations, traiter des données de toute nature (modification de la valeur des données, forme de présentation, localisation). A l'intérieur de la figure, les opérations elles-mêmes sont écrites directement, par exemple, l'opération d'affectation : a = 10 * b + c

3) Bloc logique

Affiche une solution ou une fonction de type commutateur avec une entrée et deux ou plusieurs sorties alternatives, dont une seule peut être sélectionnée après évaluation des conditions définies dans cet élément. L'entrée dans un élément est indiquée par une ligne, entrant généralement dans le sommet supérieur de l'élément. S'il y a deux ou trois sorties, alors généralement chaque sortie est indiquée par une ligne sortant des pics restants (côté et bas). S'il y a plus de trois sorties, elles doivent être affichées sous la forme d'une seule ligne partant du haut (généralement du bas) de l'élément, qui se ramifie ensuite. Les résultats de calcul correspondants peuvent être écrits à côté des lignes représentant ces chemins. Exemples de solutions : en général - comparaison (trois sorties :>,<, =); в программировании − условные операторы if (два выхода: true, false) и case (множество выходов).

Conversion des données sous une forme adaptée au traitement (entrée) ou à l'affichage des résultats du traitement (sortie). Ce symbole ne définit pas un support de données (des symboles spécifiques sont utilisés pour indiquer le type de support de données).

Types d'algorithmes

Algorithme de bifurcation - un algorithme contenant au moins une condition, à la suite de la vérification de laquelle la division en plusieurs branches parallèles de l'algorithme peut être effectuée.

L'algorithme linéaire est un ensemble de commandes (instructions) exécutées séquentiellement dans le temps les unes après les autres.

Algorithme cyclique - un algorithme qui fournit une répétition multiple de la même action (les mêmes opérations) sur de nouvelles données source. La plupart des méthodes de calcul et d'énumération des options se réduisent à des algorithmes cycliques. Cycle de programme - une séquence de commandes (série, corps de boucle) qui peut être exécutée plusieurs fois (pour de nouvelles données initiales) jusqu'à ce qu'une certaine condition soit satisfaite.

Programmer, c'est écrire quelque chose en utilisant le langage inconnu de quelqu'un d'autre. Avec le développement de ce domaine de connaissances, les développeurs sont allés encore plus loin et ont appris à écrire "quelque chose" sans même comprendre comment cela sonne en russe. Les débutants apprennent à écrire du code directement en C++ ou en php, en utilisant de nombreuses bibliothèques, et ne comprennent même pas vraiment comment ce qu'ils créent des sons dans leur langue maternelle. L'algorithme s'occupe de clarifier et de rendre compréhensible ce « quelque chose ».

Algorithmisation

La plupart des exemples d'algorithmes en informatique, même dans les universités, sont étudiés à un niveau médiocre. Il est courant d'écrire sans cesse du code de plus en plus complexe. Les tentatives de programmeurs inexpérimentés pour commencer tout de suite à écrire des programmes dans un langage de programmation peuvent être comparées au travail d'un journaliste qui, maîtrisant à peine les bases d'une langue étrangère, écrit un article pour un magazine. Vous pouvez éviter un tel problème si vous commencez à enregistrer votre travail dans votre langue maternelle, l'éditez, vérifiez les erreurs et enfin le traduisez dans la langue requise.

L'avantage de cette approche réside principalement dans le fait que le développeur ne sera engagé dans la traduction que 25% du temps, tandis que lors de l'écriture d'un programme dans une nouvelle langue, il passera 100% à travailler avec une langue inconnue. Dans le même temps, il se retrouvera à l'étroit et ne pourra pas faire un bon contrôle des erreurs et réviser le projet.

L'algorithme permet, lors de la mise en œuvre d'un projet sur un ordinateur, de décrire le processus de solution dans un langage natif et compréhensible sous la forme d'un schéma d'algorithmes interconnectés, d'analyser des idées et d'obtenir le code le plus qualitatif et le mieux conçu qui sera plus résistant aux erreurs et fonctionnera plus efficacement.

Notion d'algorithme

Un ordinateur ne peut pas résoudre les problèmes, il ne peut effectuer que des actions simples dans l'ordre spécifié. « Et la calculatrice ? » - tu demandes. C'est aussi le fruit du travail de programmeurs qui ont créé un programme qui utilise certains algorithmes pour obtenir les résultats souhaités. Considérons une situation abstraite. Que faire si on vous demande de trouver les racines du trinôme quadratique d'une personne qui n'est pas familière avec les méthodes de résolution d'équations ?

De toute évidence, il doit être formé pour résoudre des équations quadratiques. Cela se passe selon le schéma suivant :

1. Choisissez une solution.
2. Étudiez tous les détails de la méthode choisie.
3. Expliquez les deux premiers points au futur interprète dans une langue qu'il comprend.

Ensuite, il sera possible de donner à l'interprète des tâches pour résoudre l'équation quadratique. Et si les deux premières étapes sont simples et directes - toutes les solutions sont décrites dans la littérature pertinente, alors la troisième étape est difficile.

Comment pouvez-vous vous assurer que les idées utilisées pour résoudre le problème seront perçues par l'interprète de la même manière que vous le comprenez ? On se rapproche ici du concept d'algorithme. La pratique montre que pour expliquer correctement quelque chose à quelqu'un, les étapes suivantes doivent être suivies :

• déterminer les données initiales (variable et coefficients de l'équation quadratique);
• diviser le processus de résolution en composants connus de manière unique pour l'interprète (formules discriminantes et recherche des racines) ;
• indiquer l'ordre des étapes (calculer d'abord le discriminant, puis les racines) ;
• établir la condition sous laquelle la solution est considérée comme complète (vérifier les racines trouvées en les substituant dans l'équation à la place des variables);
• indiquer exactement quel devrait être le résultat de la solution (les racines appartiennent à l'ensemble des nombres réels).

L'ensemble d'étapes décrit dans un sens général est un algorithme. Ainsi, un algorithme peut être compris comme une méthode de résolution d'une tâche, écrite à l'aide de certaines règles qui permettent une compréhension sans ambiguïté des actions effectuées et de leur ordre. Des algorithmes et des exemples de tâches seront discutés plus en détail ci-dessous.

Propriétés de base de l'algorithme

Discrétion. Le processus de résolution d'un problème consiste toujours en des actions strictement séparées les unes des autres, appelées étapes, qui ont un certain ordre d'exécution.

Certitude. Chaque étape doit être claire et sans ambiguïté tant dans le sens que dans la clé de l'action à accomplir.

Efficacité. L'algorithme doit donner un résultat. Dans ce cas, le nombre d'étapes peut se chiffrer en milliers ou en millions, mais elles doivent toujours conduire à un résultat.

Caractère de masse. Tout algorithme développé pour résoudre un problème doit être applicable à tous les problèmes de ce type pour toutes les données d'entrée valides.

Capacités informatiques

Pour la création correcte d'algorithmes pour les ordinateurs, il est important de comprendre leurs capacités. Considérons d'abord les quantités avec lesquelles l'ordinateur fonctionne. En général, ils peuvent être divisés en numérique et texte, constantes et variables.

Les nombres constants signifient tous les nombres : 3,15, 100, 105, leur caractéristique est l'invariabilité pendant toute l'opération du programme. Les variables changent de valeur pendant l'exécution du code et sont généralement désignées par des lettres : x, y, max, min, etc.

Les variables de texte, comme les variables numériques, peuvent être constantes ou variables. Dans le premier cas, il ne s'agit que de texte : "bien", "a et b", etc. Dans le second, c'est la même désignation symbolique que pour les variables numériques : nom, ville, etc. La différence entre elles réside principalement dans la mémoire informatique allouée pour stocker une telle variable.

Opérations que l'ordinateur est capable d'effectuer :

1. Lire les données des périphériques d'entrée (clavier, souris, fichiers).
2. Calcul de valeurs à l'aide de fonctions mathématiques: addition, soustraction, sin, cos, ln, etc. - chaque langage de programmation a son propre ensemble de fonctions intégrées.
3. Sortie des données (à l'écran, au papier, à l'interface réseau).
4. La transition entre les étapes du programme.
5. Comparaison de deux valeurs (supérieur, inférieur, égal).

Ce sont les opérations de base que la plupart des langages de programmation peuvent effectuer.

Méthodes de description des algorithmes

Verbal. C'est le moyen le plus simple. Une recette culinaire en est un exemple. L'utilisation de formules mathématiques simples est autorisée.

Graphique. Description à l'aide de schémas. C'est une façon particulière d'écrire des algorithmes en utilisant une sorte de langage algorithmique généralement accepté - des formes et des blocs qui ont une signification spécifique : un rectangle est une action simple, un parallélogramme oblique est une entrée/sortie, un losange est une condition, etc.

Utiliser un langage algorithmique. Semblable au graphique, c'est aussi une façon spéciale d'écrire l'algorithme. Il existe de nombreux langages algorithmiques disponibles. Leurs règles ne sont pas strictes, sinon ce serait un langage de programmation. Prenons un exemple d'algorithme de calcul des salaires en fonction de l'ancienneté, rédigé à l'aide d'un langage algorithmique.

Alg salaire (int ST, real ZP) arg ST res ZP start si ST

Le langage algorithmique peut être qualifié de forme de notation plus stricte que le langage verbal. Un ensemble limité de mots et de leurs constructions est utilisé, ainsi qu'un formatage avec des retraits. L'inconvénient de la forme verbale et du langage algorithmique est la détérioration de la clarté de l'algorithme avec une augmentation de sa taille. Par conséquent, ces méthodes ne peuvent être utilisées que pour transmettre le sens de petits algorithmes.

Types d'algorithmes

Il existe une grande variété d'algorithmes conçus pour résoudre une grande variété de problèmes. Par exemple, tout manuel de mathématiques supérieures contient des centaines d'algorithmes : résoudre un système d'équations linéaires, trouver les extrema d'une fonction, calculer une intégrale, etc. Cependant, après un examen détaillé de leur structure, il s'avère que tous les algorithmes peuvent être divisé en plusieurs types. Considérons ces types d'algorithmes avec des exemples.

• linéaire (calcul du résultat d'une addition ou d'une multiplication, échange de valeurs de plusieurs variables);
• ramification (détermination du plus grand de plusieurs nombres);
• cyclique (tri d'un tableau, calcul d'une factorielle).

Ce sont des types de base. Il convient également de noter que dans un certain nombre de littératures, il existe également un quatrième type - récursif. Mais il n'a pas de désignation spéciale dans la notation schématique et est mis en œuvre via les notations de base.

Plus de détails sur chaque algorithme de calcul avec des exemples seront décrits ci-dessous.

Principes d'algorithme

1. Déterminer les données sources.
2. Choisissez une solution.
3. Divisez la méthode sélectionnée en étapes en fonction des capacités de l'ordinateur (langage de programmation).
4. Exécutez l'algorithme sous la forme d'un diagramme, définissant un ordre clair des étapes.
5. Sortie des résultats de calcul.
6. Indiquer la transition vers la sortie du circuit.

Débogage de l'algorithme

L'homme fait des erreurs, et c'est un fait. Le paramètre principal de tout algorithme devrait être l'exactitude de son travail. Le débogage est le processus d'identification et de correction des erreurs dans un algorithme. Pour cela, un certain ensemble de données initiales, appelées données de test, est prélevé. Ce sont, en règle générale, toutes sortes de types de données sources. Par exemple, si un nombre est fourni à l'entrée, alors l'algorithme doit être vérifié pour un fonctionnement correct, en prenant en compte : nombres positifs, négatifs, entiers et réels, valeurs zéro, etc.

Le cerveau humain reste le principal outil pour vérifier l'exactitude d'un algorithme. Bien sûr, il est permis d'utiliser d'autres outils informatiques pour automatiser le contrôle, mais d'une manière ou d'une autre, c'est une personne qui prépare les tests et analyse les résultats. Dans ce cas, la question se pose, pourquoi avons-nous besoin d'un algorithme si une personne fait tout elle-même ? Ensuite, la tâche principale de l'algorithme est la résolution répétée d'un certain type de problème.

Algorithmes linéaires

Linéaire est un algorithme dans lequel les étapes sont séquentielles les unes après les autres. Tout algorithme qui ne contient pas de branches et de boucles est linéaire. Prenons un exemple d'algorithme qui résout le problème suivant : un loup et un lièvre sont assis dans deux cellules, vous devez les échanger.

La clé pour résoudre ce problème est une cage temporaire supplémentaire qui devrait être utilisée pour échanger des animaux.

Algorithmes de fork

Comme son nom l'indique, l'algorithme a plusieurs branches. L'essence du travail consiste à sélectionner l'une des options possibles pour le processus de calcul, en fonction de toutes les conditions. La ramification schématique est représentée par une boîte en forme de losange, à l'intérieur de laquelle la condition est indiquée, et sur les côtés de celle-ci se trouvent des branches de sélection selon que la condition est vraie ou fausse. L'algorithme de branchement et des exemples de son application peuvent être trouvés partout. En programmation, il s'agit d'une construction if-else typique que l'on trouve dans presque tous les langages.

Donnons un exemple d'algorithme pour résoudre le problème de trouver le plus grand parmi trois nombres.

Algorithme cyclique

Un algorithme cyclique est un algorithme dans lequel les mêmes étapes sont répétées plusieurs fois, dans lequel seule la valeur d'une variable particulière, sur laquelle les calculs sont effectués, peut changer. Les types d'algorithme de bouclage et un exemple seront discutés ci-dessous, mais pour l'instant, nous allons énumérer les principales étapes de construction d'une boucle.

1. Affectation d'une valeur initiale aux variables. Sans cette condition, la boucle échouera très probablement ou fera des erreurs.
2. Le bloc de calcul des résultats. C'est le corps principal de la boucle.
3. Vérification de la condition de fin du processus cyclique. Si vous oubliez de spécifier la condition dans laquelle la boucle doit se terminer, l'algorithme s'exécutera indéfiniment.
4. Changement de variables. Ce blocage prend effet après vérification de la condition de terminaison si elle était fausse. Si vous oubliez ce bloc, le cycle effectuera une action pour toujours et ne se terminera jamais. Par conséquent, il est important que les variables subissent des changements à chaque itération de la boucle.

Il existe plusieurs types d'algorithmes de bouclage : avec postcondition, précondition et paramètre.

Construisons un algorithme cyclique en utilisant l'exemple de la recherche de la factorielle du nombre N.

Autres types d'algorithmes

Il existe un certain nombre d'autres algorithmes qui diffèrent par leur classification ou leur origine.

• Algorithmes mécaniques. Par exemple, le fonctionnement d'un moteur à combustion interne ou d'une chaîne de montage.
• Algorithmes probabilistes. Leurs travaux sont basés sur la théorie des probabilités et les statistiques mathématiques.
• Algorithmes heuristiques. Utiliser des considérations pratiques dans leur travail, sans justification mathématique rigoureuse.
• Algorithmes génétiques. Appliquer des idées biologiques dans leur travail.

Les algorithmes peuvent être simples, complexes, mais ils ont tous des caractéristiques communes. C'est par ces caractéristiques qu'il est d'usage de distinguer trois types d'algorithmes, avec lesquels nous allons nous familiariser.

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. Des références internes à différentes équipes peuvent exister.

En général, l'exécution des commandes selon l'algorithme rappelle un peu les jeux de société dans lesquels les participants lancent des dés et marchent à tour de rôle à travers les champs. De plus, dans les marges, il peut y avoir des commentaires dans le style : "Retour de 2 cellules" ou "Avance de 5 cellules" (Fig. 1).

Riz. 1. Jeu de société ()

Le jeu bien connu "Monopoly" ou "Manager" est un modèle plus complexe de l'exécution de l'algorithme (Fig. 2).

Riz. 2. Le jeu "Monopoly" ()

La différence essentielle de ce jeu par rapport à la simple exécution de l'algorithme est que le but final des participants n'est pas le passage du chemin, mais l'accumulation d'argent au moyen de certaines actions.

Selon l'ordre d'exécution des commandes, on distingue trois types d'algorithmes :

Algorithmes linéaires ;

Algorithmes de branchement ;

Algorithmes de répétition.

"Monopole"

Le Monopoly est l'un des jeux de société les plus populaires. Ses règles sont assez simples et compréhensibles pour tous ceux qui y ont joué au moins une fois (Fig. 4).

Riz. 4. Jeu "Monopole" ()

Au moment du départ, les joueurs disposent d'un montant égal d'argent. En lançant des dés et en déplaçant leurs jetons sur le terrain de jeu en boucle, ils acquièrent de nombreux biens immobiliers de couleurs différentes. Une fois sur le site acquis par l'ennemi, le joueur est obligé de payer le loyer établi. Après avoir acheté toutes les parcelles du même groupe de couleur, le participant peut y construire des maisons et des hôtels, ce qui augmente la taille du bail. Le but de tout ce qui se passe est banal - ruiner tous les rivaux.

Selon des sources officielles - Parker Brothers, qui produit Monopoly depuis 1935 à ce jour - le légendaire jeu de société est né de la manière suivante. En 1934, un ingénieur au chômage Charles Darrow (Fig. 5) a invité le bureau ci-dessus à sortir un jeu qu'il avait inventé sur le commerce immobilier.

Riz. 5. Charles Darrow ()

Après avoir découvert 52 erreurs de conception dans le jeu de société, les frères Parker ont refusé l'inventeur. Lui, avec un esprit d'entreprise purement américain, s'est rendu à l'imprimerie, a commandé 5 000 exemplaires du jeu et les a vendus assez rapidement. Réalisant que les bénéfices leur échappaient du nez, Parker Brothers acquit à la hâte les droits de Monopoly, et l'année suivante, il devint le jeu de société le plus vendu aux États-Unis, et Darrow - l'incarnation vivante du rêve américain.

Cependant, en même temps, il existe également des jeux antérieurs connus qui rappellent de manière frappante "Monopoly". Il s'avère que Darrow n'était que le premier à se dépêcher et à recevoir un brevet pour s'amuser « folk » ? Oui et non. Les enquêtes de ces dernières années ont fait la lumière sur le mystère des origines du Monopoly.

Dans la seconde moitié du XIXe siècle, l'économiste politique Henry George a vécu et travaillé aux États-Unis. Il a proposé de remplacer tous les prélèvements par un seul impôt - sur les terres. Imprégnée de ses idées, Maggie obtient en janvier 1904 un brevet pour le jeu de société The Landlord's Game, qui, tant en termes de règles que d'apparence, ressemble à l'actuel « Monopoly ». On pense que le "Jeu du propriétaire du terrain" avait deux variantes de règles: après avoir joué à un jeu selon les lois fiscales en vigueur, les joueurs sont passés au modèle proposé par George - et seraient devenus convaincus de ses avantages nécessaires . Ainsi, le jeu n'était pas un divertissement, mais un instrument de lutte idéologique.

Il n'est pas venu à la production de masse, mais The Landlord's Game s'est progressivement répandu à travers l'Amérique du Nord en copies artisanales. Le regain d'intérêt pour le jeu de société est tombé sur les années de la Grande Dépression : des milliers de chômeurs étaient heureux de s'imaginer comme des sacs d'argent, du moins à la table de jeu. L'avènement d'un homme d'affaires comme Charles Darrow a pris plusieurs mois - et il a émergé, reprenant la renommée du seul inventeur du Monopoly pendant de nombreuses décennies.

Il y avait, bien sûr, ceux qui considéraient qu'il était nécessaire d'arracher une pièce aux détenteurs des droits d'auteur. Des monopoles sans licence ont inondé la Chine. Et dans notre pays, de minces rangées de clones étaient et sont produites - "Courtier", "Coopérative", "Gestionnaire" (Fig. 6) ...

Riz. 6. Jeu "Gestionnaire" ()

À la lumière de la récente remise en cause du rôle de Darrow dans la création du monopole et de l'expiration des droits d'auteur, ces sociétés ne seront pas poursuivies. Même si nous supposons qu'il n'y avait pas d'Elizabeth Maggie dans le monde, les règles du "Monopoly" sont depuis longtemps passées dans le domaine public. Cependant, Hasbro garde toujours une partie du brevet avec lui : la conception des puces, la conception graphique, la séquence de cellules sur le terrain de jeu.

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

Riz. 3. Ampoule ()

Par exemple, l'algorithme suivant pour remplacer une ampoule grillée est linéaire (Fig. 3) :

1. éteignez l'interrupteur d'éclairage ;

2. Dévissez l'ampoule grillée ;

3. visser une nouvelle ampoule ;

4. Allumez l'interrupteur pour vérifier que la lumière est allumée.

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

(schéma bloc (Fig. 7.) voir à la fin du synopsis)

Les situations où la séquence des actions requises est connue à l'avance sont extrêmement rares. Dans la vie, il faut souvent prendre une décision en fonction de la situation actuelle. 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<условие>, ENSUITE<действия 1>,

AUTREMENT<действия 2>

SI vous avez de l'argent, ALORS achetez du pain, NE L'ACHETEZ PAS AUTREMENT.

SI vous serez au centre aujourd'hui, appelez-moi, SINON ne le faites pas.

SI les leçons sont apprises, ALORS allez vous promener, SINON apprenez les leçons.

Dans certains cas<действия 2>peut être absent. Cela peut être dû à la fois à son évidence (comme, par exemple, dans le premier exemple - il est clair que si vous n'avez pas d'argent, vous ne pouvez tout simplement pas acheter de pain) et à l'absence d'en avoir besoin.

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

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

SI vous voulez être en bonne santé, alors tempérez.

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

Représentons sous forme d'organigramme la séquence d'actions d'un élève de 6e qui a oublié les clés de l'appartement, qu'il imagine ainsi : « Si ma mère est à la maison, alors je viendrai m'asseoir pour faire mes devoirs. Si maman n'est pas à la maison, j'irai jouer au football avec mes amis jusqu'à ce que maman vienne. S'il n'y a pas d'amis dans la rue, je monterai sur la balançoire jusqu'à ce que ma mère vienne."

(schéma bloc (Fig. 8.) voir la fin du synopsis)

Conditions nécessaires et suffisantes

Nous avons déjà discuté avec vous qu'il existe des conditions nécessaires et suffisantes.

Un exemple de prérequis serait :

Pour devenir médecin, vous devez obtenir un diplôme de médecine.

La condition d'avoir une formation médicale est nécessaire pour exercer la profession de médecin, mais elle n'est pas suffisante. En effet, tous les diplômés en médecine ne deviennent pas médecins.

Un exemple de condition suffisante serait :

Pour se rafraîchir, il suffit d'allumer le climatiseur.

Cette condition est suffisante : si vous allumez le climatiseur, il fait vraiment plus frais. Cependant, cette condition n'est pas nécessaire, car pour atteindre cet objectif, vous pouvez allumer le ventilateur, ouvrir une fenêtre, etc.

Bien sûr, il y a des conditions nécessaires et suffisantes à la fois (de telles conditions sont appelées Équivaut à). Par exemple:

Pour que l'été arrive, il faut et il suffit que le printemps se termine.

En effet, si le printemps est fini, alors l'été arrive, et si le printemps n'est pas fini, alors l'été ne peut pas venir. C'est-à-dire que les conditions pour la fin du printemps et le début de l'été sont équivalentes.

Les concepts de conditions nécessaires, suffisantes et équivalentes sont très importants dans une branche des mathématiques comme la logique mathématique. De plus, ils sont très courants pour prouver divers théorèmes.

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

Par exemple, si vous devez trier une boîte avec des pommes afin de séparer les pommes pourries des mûres, nous devons répéter les étapes suivantes :

1. Prenez une pomme.

2. Voyez s'il est pourri.

3. S'il est pourri - jetez-le, sinon - transférez-le dans une autre boîte.

Il est nécessaire d'effectuer cet ensemble d'actions jusqu'à épuisement des pommes dans la boîte.

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

La situation dans laquelle l'exécution de la boucle ne se termine jamais est appelée boucle.

Des algorithmes devraient être développés pour éviter de telles situations.

Considérons l'algorithme du réveil du téléphone, qui devrait sonner à 8h00 du matin, puis sonner toutes les 10 minutes jusqu'à ce qu'il soit éteint.

Dans ce cas, son schéma bloc ressemble à ceci : (diagramme bloc (Fig. 9.) voir à la fin du synopsis)

Dans cette leçon, nous avons abordé trois types d'algorithmes : les algorithmes linéaires, les algorithmes de branchement et les algorithmes répétitifs.

Dans la prochaine leçon, nous verrons comment écrire des algorithmes en pratique.

Tamis d'Eratosthène

Rappelons la définition d'un nombre naturel premier.

Un nombre naturel est dit premier s'il est n'a que deux diviseurs : un et le nombre lui-même. Le reste des numéros s'appelle constituant... De plus, le nombre 1 n'est ni simple ni composé.

Exemples de nombres premiers : 2, 3, 5, 7.

Exemples de nombres composés : 4, 6, 8.

Au 3ème siècle avant JC, le mathématicien grec Eratos-phene a proposé l'algorithme suivant pour trouver tous les nombres premiers inférieurs à un nombre donné P :

1.écrivez tous les nombres naturels de 1 à m;

2. supprimer 1 ;

3. soulignez le plus petit des nombres non marqués ;

4. Rayez tous les nombres qui sont des multiples du nombre 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.

Considérons le résultat de cet algorithme. Écrivons tous les nombres premiers de 1 à 25.

Écrivons les nombres de 1 à 25.

Supprimons 1. Maintenant, nous allons mettre l'accent sur les deux. Rayez tous les nombres pairs.

Comme tous les nombres ne sont pas marqués, soulignez 3. Maintenant, rayez tous les nombres divisibles par 3.

Comme tous les nombres ne sont pas marqués, soulignez 5. Maintenant, rayez le nombre 25.

Comme tous les nombres ne sont pas marqués, nous insistons sur 7.

Vous ne pouvez rien rayer, mais tous les chiffres ne sont pas marqués, nous insistons donc sur 11.

Vous ne pouvez rien rayer, mais tous les nombres ne sont pas marqués, nous soulignons donc 13. Encore une fois, nous ne pouvons rien rayer - nous soulignons 17, puis 19 et 23.

Tous les numéros sont maintenant marqués.

On obtient des nombres premiers : 2, 3, 5, 7, 11, 13, 17, 19, 23.

Riz. sept.Schéma fonctionnel pour changer une ampoule

Riz. 8. Organigramme des actions de la sixième année

Riz. 9. Schéma fonctionnel du réveil

Bibliographie

1. Bossova L.L. Informatique et TIC : manuel pour la 6e année. - M. : BINOM. Laboratoire des connaissances, 2012.

2. Bosova L.L. Informatique : Cahier d'exercices pour la 6e année. - M. : BINOM. Laboratoire de connaissances, 2010.

3. Bosova L.L., Bosova A.Yu. Cours d'informatique en 5e et 6e années : Guide méthodologique. - M. : BINOM. Laboratoire de connaissances, 2010.

1. Portail Internet "Notre réseau" ()

2. Portail Internet « Hypermarché de la connaissance » ()

3. Portail Internet "kaz.docdat.com" ()

Devoirs

1. §3.4 (Bosova L.L. Informatique et TIC : manuel pour la 6e année).

2. Feuilleter 81 tâches 2, 6 (Bosova L.L. Informatics and ICT: Textbook for grade 6).

3. Feuilleter 82 tâche 9, 11, 13, 14 (Bosova L.L. Informatics and ICT: Textbook for grade 6).

4. * Page 83 tâche 15 (Bosova L.L. Informatics and ICT: Textbook for grade 6).