Une approche de l'algorithmique
Jean Lpine
UNE APPROCHE DE L'ALGORITHMIQUE Lobjectif est de rendre les lves capables : de dcrire certains algorithmes en langage naturel, den raliser quelques uns (tableur ou petit programme sur calculatrice), dinterprter quelques algorithmes plus complexes. Le logiciel utilis pour ces exemples est le logiciel ALGOBOX c'est un logiciel trs simple et trs rapide de prise en main qui me semble parfaitement adapt la dcouverte de l'algorithmique. Vous trouverez l'aide complte de ce logiciel est sur le site http://algo.jeanlepine.com/ Vous trouverez tous les renseignements sur le site du logiciel ALGOBOX Je propose ici quelques acitivits progressives qui permettent un lve de seconde de dcouvrir les premires bribes de l'algorithmique comme prvu dans le programme de maths. L'activit autour du jeu du "c'est plus c'est moins" me parat une trs bonne activit pour dcouvrir les principes de l'algorithmique car elle est trs ouverte et permet aux lves de faire de nombreux tests et de dcouvrir de nombreuses solutions. Il ne faut pas hsiter utiliser le mode "pas pas" du logiciel Algobox car il permet de voir voluer les variables et permet de faire un parfait dbogage. Chacune des activits proposes commence par la mise en place d'un algorithme suivi de quelques exercices. Pour prolonger ces activits et faire de la programmation un autre niveau avec des constructions de procdures de fonctions etc, il faudra utiliser des langages standards comme le visual basic ou le pascal avec la plateforme Delphi ou bien encore le C avec C++. Sommaire I- Premire approche : La division II- PGCD de deux nombres entiers III- Travailler sur quatre semaines IV- Les chanes de caractres : les palindromes V- Le jeu du c'est plus - cest moins VI- Dans la foule : la dichotomie VII- Moyenne, cart-type, tri et mdiane VIII- Un peu de probabilit : la somme de deux ds
Page 1/24
Une approche de l'algorithmique
Jean Lpine
I* dcouverte de l'algorithmique : la division Commenons cette premire approche par un problme de calcul tout simple. Il s'agit d'entrer deux nombres entiers A et B et de rcuprer le quotient Q de ces deux nombres. Mthode : Demander la saisie du nombre A Demander la saisie du nombre B Calculer dans Q le quotient A/B Afficher la valeur de Q Variables utilises trois variables numriques A, B, Q Ralisation de l'algorithme 1* Lancer le logiciel Algobox 2* Cliquer sur dclarer une nouvelle variable
3* Taper la variable A en laissant bien nombre comme type de variable.
4* Cliquez alors sur le bouton Ajouter une ligne ou appuyez sur la combinaison de touches [Ctrl] [Entre] puis cliquez sur le bouton lire variable pour demander la saisie du nombre A
5* Faire la mme opration pour la saisie du nombre B. A cette tape votre algorithme doit tre comme ci-contre. Il nous faut, maintenant que les deux nombres A et B sont en mmoire, calculer le quotient en priant un peu pour que le nombre B ne soit pas nul !
6* Cliquez sur Nouvelle ligne puis sur le bouton Affecter valeur variable. Choisir la variable Q et la suite de prend la valeur taper A/B. Il nous reste afficher le quotient obtenu
Page 2/24
Une approche de l'algorithmique
Jean Lpine
7* Gnrer une ligne puis cliquez sur ajouter afficher message et taper le message La valeur du quotient A/B est. Ajouter une ligne puis cliquez alors sur ajouter afficher variable et choisir Q en ajoutant un retour la ligne. L'algorithme doit alors tre celui-ci.
Vous pouvez alors faire une sauvegarde de votre travail en faisant Fichier Sauver sous.
8* Il s'agit maintenant de tester notre algorithme. Cliquer sur le bouton tester puis sur le bouton lancer l'algorithme. Le rsultat s'affiche comme dans la fentre ci-contre aprs avoir tap les nombres 10 et 3.
Quelques amliorations dans l'algorithme. Il serait agrable d'avoir une petite explication avant de saisir les deux nombres afin d'viter de taper un diviseur gal zro !!! Vous pouvez utiliser le bouton Nouvelle ligne pour insrer deux lignes comme ci-contre et le bouton Afficher message pour obtenir l'algorithme cicontre.
La structure algorithmique Tant que Il est assez risqu de laisser l'utilisateur saisir un diviseur gal zro ! Pour cela nous allons demander de lire B tant que la valeur de B est de zro. Mthode : insrer une ligne aprs la ligne AFFICHER Votre second nombre B, SVP puis cliquer sur le bouton Ajouter Tant que. Comme condition taper B==0, en faisant bien attention de mettre deux signes = ! Ce double = pour indiquer que nous ne sommes pas sur une affectation de variable mais sur un test d'galit : la variable B est-elle gale zro ?
Page 3/24
Une approche de l'algorithmique
Jean Lpine
Entre les deux balises DEBUT et FIN ajouter la ligne LIRE B et supprimer l'ancienne ligne. Vous obtenez alors l'algorithme ci-contre.
Il ne reste qu' faire le test en essayant de taper la valeur zro pour le diviseur du quotient.
Nouvelle amlioration : fixer le nombre de dcimales afficher. Ce problme est mathmatique. De la rponse 3,257257257 il faut arriver 3,25 par exemple ! En fait, une solution simple consiste utiliser la fonction partie entire en procdant de la faon suivante 3,257257257*100 devient 325,7257257 dont on prend la partie entire 325. Il suffit alors de diviser le rsultat par 100 pour obtenir 3,25 ! La fonction partie entire, comme dans de nombreux langages informatiques, est la fonction floor(). Notre ligne de calcul devient donc celle-ci Q = floor(A/B*100)/100 Au niveau de l'algorithme il suffit de se positionner sur la ligne Q prend la valeur A/B puis de cliquer sur le bouton Modifier ligne ! Remplacer alors A/B par la formule floor(A/B*100)/100 Tester l'algorithme pour vrifier. Vos premiers essais : vous de chercher, modifier et tester. Quand l'algorithme ne fonctionne pas comme vous le dsirez n'hsitez pas utiliser le mode pas pas d'algobox pour voir comment volue le contenu de toutes vos variables. Exercice 1 : Modifier l'algorithme pour obtenir un affichage 3 dcimales. Exercice 2 : Il s'agit de rajouter une variable pour demander l'utilisateur le nombre de dcimales souhait. Note pour cet exercice : il faut utiliser la fonction puissance pow(x,n) qui correspond la puissance nieme de x,
Page 4/24
Une approche de l'algorithmique
Jean Lpine
Exercice 1 : Modifier l'algorithme pour obtenir un affichage 3 dcimales. Exercice 2 : Il s'agit de rajouter une variable pour demander l'utilisateur le nombre de dcimales souhait. Note pour cet exercice : il faut utiliser la fonction puissance pow(x,n) qui correspond la puissance nieme de x,
Solutions
Page 5/24
Une approche de l'algorithmique
Jean Lpine
Rigolo : la division l'ancienne. Les premiers processeurs ne faisaient que des additions et soustractions ! Comment alors raliser une division ? Voici la mthode directe employe pour faire la division entire de deux nombres A et B. On soustrait B de A tant que c'est possible et on compte le nombre de soustractions faites. C'est aussi simple que cela ! Exemple : soit chercher le quotient entier de 11 par 3 on calcule 11 3 = 8 et on compte 1 puis 8-3 = 5 et on compte 2 puis 5- 3 = 2 et on compte 3 puis 2-3 impossible dans IN donc on s'arrte de compter ! Le quotient de 11 par 3 est donc 3 ! Ci-contre l'algorithme.
Exercice 3 : que se passe-t-il si les lignes Q PREND LA VALEUR Q+1 et diff PREND LA VALEUR diff-B sont inverses ? L'algorithme fonctionne-t-il encore correctement ? Exercice 4 : Utiliser la variable R pour afficher le reste dans la division de A par B la place du quotient Q
Page 6/24
Une approche de l'algorithmique
Jean Lpine
II Le pgcd de deux nombres entiers Rappelons que le plus grand diviseur commun aux deux nombres 12 et 18 est 6 car les diviseurs de 12 sont {1; 2; 3; 4; 6; 12} les diviseurs de 18 sont {1; 2; 3; 6; 9; 18}, Les diviseurs communs aux deux sont {1; 2; 3; 6 } et le plus grand est donc 6 ! Voici ci-dessous un algorithme pour dterminer le PGCD de deux nombres entiers A et B
Page 7/24
Une approche de l'algorithmique
Jean Lpine
Algorithme correspondant avec algobox
Exercice : utiliser cet algorithme pour dterminer si deux nombres sont premiers entre eux. On rappelle que pour que deux nombres soient premiers entre eux il suffit que leur PGCD soit 1.
III- Travailler sur quatre semaines Dans certains emplois du temps il faut dcouper sur quatre semaines plutt que sur deux. C'est le cas pour certains lves de seconde en informatique dans notre lyce, En semaine 41 nous sommes en semaine 1 En semaine 42 nous sommes en semaine 2 En semaine 43 nous sommes en semaine 3 En semaine 44 nous sommes en semaine 4 En semaine 45 nous sommes en semaine 1 etc. On voudrait faire afficher, partir du numro de semaine du calendrier, le numro de semaine de l'emploi du temps (1, 2, 3 ou 4) Mthode : Prendre le numro de semaine du calendrier dans la variable semaine Calculer le reste dans la division entire par 4 de cette semaine et le stocker dans semaine_info Si semaine_info vaut zro le mettre 4 Les variables utiliser seront donc semaine, de type numrique semaine_info, de type numrique aussi.
Page 8/24
Une approche de l'algorithmique
Jean Lpine
Il faudra utiliser la fonction A%B qui donne le reste dans la division euclidienne de A par B.
Algorithme
Exercice 1 On sait que les cours d'informatique de la classe de 2C sont en semaine 4. crire un algorithme permettant d'afficher toutes les semaines 4 de l'anne. Il faudra donc utiliser une boucle pour explorer les 53 semaines de 1 53 La boucle aura la structure suivante. POUR semaine ALLANT DE 1 A 53 DEBUT POUR * * * FIN POUR
Exercice 2 : la mme problmatique, mais cette fois pour une des quatre semaines au choix de l'utilisateur. On va crer une nouvelle variable et demander l'utilisateur quelle liste de semaines il veut , 1, 2, 3 ou 4.
Page 9/24
Une approche de l'algorithmique
Jean Lpine
Solutions Exercice 1 On sait que les cours d'informatique de la classe de 2C sont en semaine 4. crire un algorithme permettant d'afficher toutes les semaines 4 de l'anne.
Exercice 2 : la mme problmatique, mais cette fois pour une des quatre semaines au choix de l'utilisateur. On va crer une nouvelle variable et demander l'utilisateur quelle liste de semaines il veut , 1, 2, 3 ou 4.
Page 10/24
Une approche de l'algorithmique
Jean Lpine
IV- Avec des chaines de caractres : les palindromes Le travail avec les variables alphanumriques dites chanes de caractres est toujours assez difficile en programmation. Les mots, les phrases, les structures n'obissant pas du tout des rgles mathmatiques mais tant bourre d'exceptions. Ici, il s'agit de crer un algorithme qui renverse un mot ou une expression pour vrifier s'il s'agit d'un palindrome (comme LAVAL, ERDRE ou RADAR ). Mthode : Un mot est saisi dans la variable CHAINE palind La variable CHAINE result va rcuprer une par une les lettres de palind partir de la dernire etc. Il est utile pour cet algorithme de connatre les fonctions de manipulation de chaines suivante : palind.length renvoi la longueur de la chaine (5 si vous avez tap laval) palind.substr(3,1) renvoie la chaine de longueur 1 situe en 3ieme position (v pour laval) Attention : en dclarant les variables il faut choisir le type chaine.
Voici l'algorithme :
Exercice : complter l'algorithme ci-dessus en ajoutant un test SI ALORS pour afficher un message de russite si le mot tap est bien un palindrome.
Page 11/24
Une approche de l'algorithmique
Jean Lpine
V- Le jeux du c'est plus c'est moins Classique jeu du c'est plus c'est moins avec un nombre entre 1 et 100 choisi au hasard par la machine. Pour calculer un nombre au hasard entre 1 et 100 on utilise la fonction random() qui renvoie une valeur dcimale entre 0 et 0,9999999 ! La formule classique pour obtenir un nombre entre 1 et 100 sera la suivante floor(random()*100+1) Explications : random() sort un nombre dcimal entre 0 et 0,99999999 random()*100 donne donc un dcimal entre 0 et 99,99999 random()*100+1 donne un dcimale entre 1 et 100,99999 il ne reste plus qu' prendre la partie entire floor() !!!
Algorithme ci-contre Nous avons l un problme algorithmique trs intressant car nous utilisons une instruction TANT QUE dans laquelle nous avons un test (proposition!=hasard) en dbut de boucle alors qu'il aurait fallu ce test en fin de boucle pour ne pas avoir faire un passage inutile !!! Si bien que nous nous trouvons souvent avec un c'est moins en trop. Nous devons donc ajouter un test dans le SINON pour empcher l'affichage du c'est moins en cas d'galit... l'algorithme devient donc celui-ci
Page 12/24
Une approche de l'algorithmique
Jean Lpine
Problme qui aurait pu tre solutionn aussi avec une variable sortie qui prend la valeur 1 en cas d'galit comme dans l'algorithme ci-contre. Lorsque vous modifiez votre algorithme vous pouvez utiliser les racouis claviers ci-aprs pour les lignes ou les blocs [Ctrl] [C] pour copier [Ctrl] [X] pour couper [Ctrl] [V] pour coller
N'oubliez pas dans les recherches cidessous d'utiliser la fonction pas pas qui vous permet de surveiller la valeur de vos variables chaque passage d'une boucle.
Exercice 1 :En dernire ligne proposer l'utilisateur le nombre de coups qui ont t ncessaires avec un affichage du genre : BRAVO, vous avez trouv en 7 coups ! Exercice 2 : Afficher l'intervalle dans lequel se trouve le nombre pour faciliter la tache l'utilisateur ! Par exemple : aprs avoir propos le nombre 50 l'utilisateur verra s'afficher un message du genre : C'est moins, le nombre est situ entre 0 et 50 puis aprs avoir propos 20 C'est plus, le nombre est situ entre 20 et 50 etc
Page 13/24
Une approche de l'algorithmique
Jean Lpine
Solutions Exercice 1 :En dernire ligne proposer l'utilisateur le nombre de coups qui ont t ncessaires avec un affichage du genre : BRAVO, vous avez trouv en 7 coups ! Exercice 2 : Afficher l'intervalle dans lequel se trouve le nombre pour faciliter la tache l'utilisateur ! Par exemple : aprs avoir propos le nombre 50 l'utilisateur verra s'afficher un message du genre : C'est moins, le nombre est situ entre 0 et 50 puis aprs avoir propos 20 C'est plus, le nombre est situ entre 20 et 50 etc
Page 14/24
Une approche de l'algorithmique
Jean Lpine
VI- Dans la foule la dichotomie Il s'agit de calculer la valeur (approche souvent !) qui annule une fonction donne F1(x). La mthode est simple : on se place sur un intervalle de continuit monotone et on calcule l'image du milieu de cet intervalle, en fonction du signe de cette image ce milieu remplace une des bornes et ainsi de suite. Exemple : nous considrons la fonction F1(x) = x 6 sur le graphique ci-contre sur l'intervalle [0;4]. Nous remarquons que le milieu est 2 et que F1(2) est ngatif donc notre intervalle de travail va devenir [2:4], Puis remarquons que F1[3] est positif, notre intervalle devient donc [2,3] etc.
Voici l'algorithme. Attention, il faut dfinir une fonction en utilisant l'onglet Utiliser une fonction numrique. Cette fonction aura pour nom prdfini F1(x). Dans l'exemple, si vous dsirez utiliser la fonction cidessus x 6 il faut taper pow(x,2) 6 ou bien tout simplement x*x 6. Vous pouvez aussi utiliser l'onglet Dessiner dans un repre pour voir le parcours fait par le point de recherche F1(middle). Exercice : Demander l'utilisateur les deux valeurs de min et de max. Mais il n'est pas possible de demander l'utilisateur de dfinir luimme la fonction F1(x).
Page 15/24
Une approche de l'algorithmique
Jean Lpine
VII Utiliser une liste : moyenne de notes Pour calculer la moyenne d'un certain nombre de notes (combien par exemple) nous devons utiliser une liste (mathmatiquement on dirait plutt un vecteur), note[1] contient la premire note, puis note[2] la seconde etc, Nous pouvons ainsi faire saisir les notes au sein d'une boucle de longueur combien. Il ne reste qu' faire la somme des notes et diviser par combien.
Voir l'algorithme ci-contre
Faites quelques recherches dans votre livre de maths pour rcuprer la formule permettant de calculer la Variance d'une srie. Exercice : Faire afficher la moyenne, la variance et l'cart-type de la srie de note.
Page 16/24
Une approche de l'algorithmique
Jean Lpine
Solution
Exercice : Faire afficher la moyenne, la variance et l'cart-type de la srie de note.
Page 17/24
Une approche de l'algorithmique
Jean Lpine
Continuons les statistiques : dtermination de la mdiane de la srie de notes Pour dterminer la mdiane il faut trier la srie ! Opration peu simple au niveau des algorithmes. Il existe de nombreuses faon de raliser un tri. Nous allons choisir la plus simple mais peut-tre pas la plus rapide au niveau de trs grandes sries statistiques. Ralisons un tri dans l'ordre croissant de la srie de notes cidessus. Le principe est le suivant : on fait parcourir la srie et ds que l'on trouve deux notes conscutives qui ne sont pas dans l'ordre on les inverse et on refait le parcours de la srie. La variable permute est mise zro puis on fait le parcours de la srie de 1 combien-1. Si on trouve note[i]<note[i+1] dans la srie on met la variable permute 1 et on inverse les deux notes. Quand la variable permute restera zro il n'y aura plus rien inverser et donc la srie sera dans l'ordre. On utilise un repre pour tracer l'histogramme de la srie. Il faut cliquer sur dessiner dans un repre pour pouvoir utiliser la fonction TRACER_SEGMENT de la couleur choisie et aprs avoir dfinis les intervalles X et Y du repre, Exercice : faire un tri dcroissant de la srie de notes Une fois la srie trie il ne reste plus qu' calculer la mdiane. Pour viter d'avoir tester la parit du nombre de notes on utilise une petite astuce : on calcule le centre de la srie et on fait la moyenne des valeurs entourant ce centre. Si la srie est impaire ces deux nombres seront les mmes sinon ils entoureront le centre. Nous calculons med1 = floor((1+combien)/2) puis med2=floor((1+combien)/2+0.5) le milieu sera (med1+med2)/2 (med1 = med2 si on a un nombre impair !) mediane sera (note[med1]+note[med2])/2. Il ne reste qu' tracer le mdiane aprs avoir trac la srie.
Page 18/24
Une approche de l'algorithmique
Jean Lpine
Trac de la mdiane de la srie de notes Solution
Page 19/24
Une approche de l'algorithmique
Jean Lpine
VIII Un peu de probabilits : la somme de deux ds Nous savons que la probabilit d'apparition de la somme 7 lors du jet de deux ds de couleurs diffrentes est de 1/6 c'est dire peu prs 17% ! Nous pouvons utiliser un algorithme pour vrifier si ce nombre thorique se retrouve sur 1000 lancers alatoires de la machine. Utilisons comme nous l'avons dj fait la fonction random() qui gnre un dcimal entre 0 et 0,99999999 Fabriquons la formule: random()*6 donne un nombre entre 0 et 5,999999 random()*6+1 est donc entre 1 et 6,99999 et il suffit d'utiliser la fonction partie entire floor() pour achever la formule floor(random()*6+1) Ce qui peut donner un algorithme tel celui-ci
Exercice 1 : demander l'utilisateur quelle somme il veut tester (entre 2 et 12 bien sur!) et sur combien de lancers il veut faire le test. Exercice 2 : demander le nombre de lancers dsirs et faire afficher toutes les sommes de 2 12, on utilisera une liste bien entendu.
Page 20/24
Une approche de l'algorithmique
Jean Lpine
Exercice 1 : demander l'utilisateur quelle somme il veut tester (entre 2 et 12 bien sur!) et sur combien de lancers il veut faire le test.
Voici une solution
Page 21/24
Une approche de l'algorithmique
Jean Lpine
Exercice 2 : demander le nombre de lancers dsirs et faire afficher toutes les sommes de 2 12, on utilisera une liste bien entendu. En voici l'algorithme.
Page 22/24
Une approche de l'algorithmique
Jean Lpine
Exercice 3 : en utilisant la partie dessiner dans un repre vous pouvez, partir de l'algorithme cidessus, faire un histogramme des pourcentages Il est intressant d'tudier la rgularit et symtrie de l'histogramme en fonction du nombre de lancers demands. Voici le graphe pour 100 lancers
Et voici celui pour 10 000 lancers
Page 23/24
Une approche de l'algorithmique
Jean Lpine
Exercice 3 : en utilisant la partie dessiner dans un repre vous pouvez, partir de l'algorithme cidessus, faire un histogramme des pourcentages En voici la solution
Page 24/24
