Document d`accompagnement des stages de formation
Contents
1. Mode d emploi Python http inforef be swi python htm Document r dig par le groupe algorithmique de IREM de Grenoble Document r dig par le groupe algorithmique de PIREM de Grenoble Premi re partie Quelques l ments de base Cette introduction est un pr ambule la compr hension des algorithmes propos s dans la progression p dagogique qui lui fait suite D finition Un algorithme est l expression d une solution un probl me par composition d actions plus l mentaires Il y a 4 mani res de composer des actions La composition s quentielle La composition s quentielle de deux actions A1 et A2 not e A1 A2 indique que l action Al est effectu e puis une fois A1 termin e l action A2 est effectu e son tour Exemple moyenne M de deux nombres N1 et N2 S Ni N2 M S 2 On peut aussi exprimer la composition s quentielle de deux actions par un simple changement de ligne La composition conditionnelle La composition conditionnelle de deux actions A1 et A2 selon une condition C not e si C alors A1 sinon A2 indique que l action A1 est effectu e si C est vraie ou bien l action A2 est effectu e si C est fausse Une variante not e si C alors A indique que l action est effectu e seulement si la condition C est vraie Exemple maximum M de deux nombres N1 et N2 si N1 gt N2 alors M N1 sinon M N2 La composition it rative La composi2. print Un nombre i et son carr j Listes et op rations li es Qu est ce qu une liste c est un ensemble de N l ments num rot s de 0 N 1 L acc s l l ment i de la liste L se fera par Lfi Document r dig par le groupe algorithmique de PIREM de Grenoble 62 Exemple Liste de 5 entiers L 0 1 2 3 4 Affichage de la liste en une seule instruction c est la liste en tant que telle entre print L Affichage de chacun des l ments de la liste c est la succession de chacun des l ments de la liste print L 0 L 1 L 2 L 3 L 4 Une liste particuli re l instruction list range N permet de cr er la liste des N premiers entiers de 0 N 1 Entrer un entier N input L list range N Affichage de la liste print L Des op rations bien utiles l instruction L L construit la liste consistant mettre L deux fois l une apr s l autre L instruction L x 4 met 4 fois bout bout la liste L Entrer un entier N input L 0 On reproduit N fois la liste L L L N Affichage de la liste print L Comment entrer une liste de N l ments Entrer un entier N input Constitution d une liste de N l ments nuls L 0 N for i in range N Li input Affichage de la liste print L Les fonctions Il ne faut tout d abord pas confondre a
3. 0 S 0 tantque I lt N S S AI II 1 S S N 1 crire S Document r dig par le groupe algorithmique de PIREM de Grenoble 17 3 Sch mas conditionnels Pr requis algo manipulation des m moires des collections d objets Objectif algo prise en main de l instruction conditionnelle mise en place de la r p tition d une action complexe 3 1 Le coin des profs Exercice 1 Question 1 crire un algorithme qui calcule le maximum de deux variables et B Question 2 crire un algorithme qui calcule le maximum de trois variables B et C Question 3 Votre algorithme se g n ralise t il N variables Question 4 crire un algorithme qui calcule le maximum de N variables Indiquer le nombre de comparaisons de l algorithme Question 5 crire un algorithme qui trie un ensemble de N variables Indiquer le nombre de comparaisons de votre algorithme Question 6 Programmer en Python l un des algorithmes pr c dents Question 7 crire un algorithme qui calcule les deux plus grandes valeurs parmi N variables Question 8 Tester l algorithme crit dans la question pr c dente avec la liste 2 4 3 1 le programme devra renvoyer 4 et 3 puis avec la liste 4 1 4 2 le programme devra renvoyer 4 et 2 Que se passe t il avec la liste 4 4 4 4 Document r dig par le groupe algorithmique de PIREM de Grenoble 18 3 2 Situation pour la classe prise e
4. Document r dig par le groupe algorithmique de lIREM de Grenoble 15 I 0 tantque I lt 4 A I amp I II 1 Question 2 Avec les valeurs ainsi calcul es que fait l algorithme suivant I 0 S 0 tantque I lt 4 S S A I I I i Exercice 2 crire un algorithme qui l ment par l ment change les valeurs de la liste A 0 Af1 A 2 Af3 A 4 avec les valeurs de la liste B B 0 B 1 B 2 B 3 B 4 Exercice 3 Question 1 Que fait l algorithme suivant I 0 tantque I lt 2 B I Af4 1 I I i Question 2 Que fait l algorithme suivant Ix 0 tantque I lt 2 ATI Af4 1 I I i Exercice 4 crire un algorithme qui partir de la liste A A 0 A 1 A 2 A 3 A 4 renvoie la liste B 0 B 1 B 2 B 3 B 4 comportant les valeurs de la liste A dans l ordre inverse Exercice 5 On consid re l ensemble de valeurs num rot es A 0 Af A 2 A 3 AS AIN Document r dig par le groupe algorithmique de IREM de Grenoble 16 B 0 B 1 B 2 BI3 BIN crire un algorithme qui change l ment par l ment les valeurs de A J et B I pour toutes les valeurs de 7 0 1 2 3 N Exercice 6 On consid re l ensemble des valeurs num rot es N tant un entier strictement positif Question 1 Combien il y a t il d l ments dans la liste Question 2 Que fait l algorithme suivant I
5. i 0 while i N Li randint 0 10 i i 1 print L On peut disposer galement entre autre de la loi uniforme uniform a b et de la loi gaussienne gauss mu sigma Document r dig par le groupe algorithmique de PIREM de Grenoble 64 Le module TORTUE Le module TORTUE qu on appellera par l instruction from turtle import est particuli rement int ressant pour l apprentissage de l algorithmique Il s agit d un en semble d instructions de dessins l mentaires Dans un premier temps les instructions sui vantes suffiront reset goto x y forward distance backward distance up down color couleur left angle right angle xcor ycor seth angle heading effacer le dessin aller l endroit de coordonn es x y avancer d une distance donn e reculer d une distance donn e relever le crayon pour ne plus dessiner abaisser le crayon pour dessiner lt couleur gt est une cha ne red blue green tourner gauche d un angle exprim en degr s tourner droite d un angle exprim en degr s renvoyer l abscisse de la position de la tortue renvoyer l ordonn e de la position de la tortue positionner la t te de la tortue de l angle angle avec l horizontal retourner la position de la t te de la tortue Attention par d faut pour la tortue les angles sont donn s e
6. par le groupe algorithmique de PIREM de Grenoble 12 2 Sch mas it ratifs et manipulations des listes Pr requis algo manipulation des m moires Objectif algo manipuler des collections d objets prise en main d un sch ma it ratif L objectif de cette section est la prise en main d un sch ma it ratif l mentaire ainsi que la manipulation de listes Pour le sch ma it ratif nous nous limiterons pour le moment au lt tant que gt 2 1 Situation pour la classe prise en main d un sch ma it ratif Exercice 1 Question 1 Comparer les deux algorithmes suivants I 0 A 0 A A I en tantque I lt 2 A A I Fit I6I 1 ELENEI A A I II 1 en portant dans chacun des deux cas les valeurs prises par A et I apr s chaque instruction dans un tableau cf partie sur la manipulation des m moires Quel est l int r t de l instruction tantque Question 2 Pour suivre le d roulement d un algorithme comprenant plusieurs it rations on peut se contenter d crire les valeurs prises par chaque variable une fois par it ration c est ce que l on fera dans les exercices suivants il faut alors choisir si on le fait au d but ou la fin de l it ration En pratique cela revient choisir entre les deux tableaux suivants I A I A D but it ration 1 Fin it ration 1 D but it ration 2 Fin it ration 2 D but it ration Fin it ration D but it r
7. tres une syntaxe impliquant l criture d un code lisible proche d un langage algorithmique na turel l utilisation de tr s peu d instructions de mot cl s De plus PYTHON est un logiciel libre que chacun pourra se procurer et utiliser et ceci sous n importe quel environnement WINDOWS LINUX MACOS Python versions 2 ou 3 Lorsqu un logiciel volue au cours du temps on num rote ses versions souvent par deux nombres ou plus s par s par des points Le premier nombre ne change que lors d volutions majeures les suivants des changements moins importants Ainsi Python existe entre autres en versions 2 6 2 7 que l on peut regrouper sous le nom de version 2 mais aussi 3 1 3 2 3 3 qui sont toutes des version 3 Suivant les tablissements on trouve les versions 2 ou 3 du langage Python entre lesquelles il y a donc des diff rences significatives Dans la pr sentation qui suit nous donnons le strict n cessaire l illustration des stages et au travail en classe en donnant les quelques diff rences lorsque cela est incontournable Modes op ratoires de Python Python poss de deux modes op ratoires un mode interactif travail partir d un programme crit dans un fichier Travailler partir d un programme crit dans un fichier nous semble plus adapt un ap prentissage coh rent de l algorithmique qui consiste consid rer une s quence d instructions dans
8. 7 9 0 2 7 Ceci sugg re probablement d autres fa ons d entrer des nombres sous forme de liste Rappe lons que nous ne consid rons que des bases b lt 10 Le symbole ou caract re utilis dans l ensemble 0 1 2 3 4 5 6 7 8 9 sera appel un chiffre Exercice 1 Ecrire un algorithme puis un programme Python faisant l acquisition d un nombre A de N chiffres sous la forme 2 en entrant un par un chacun de ses chiffres avec une criture naturelle de la gauche vers la droite Exercice 2 Suivant le mod le de la seconde solution de l exercice pr c dent crire un algo rithme puis un programme Python faisant l acquisition d un nombre de N chiffres dans une liste de M gt N chiffres Document r dig par le groupe algorithmique de PIREM de Grenoble 32 Exercice 3 crire un algorithme puis un programme Python cr ant partir d un nombre repr sent par une liste N chiffres une liste B de M gt N chiffres 6 4 Changement de base Exercice 1 Question 1 Soit le nombre LXIII Donner son criture en base 10 en base 2 en base 7 en base b Question 2 Un nombre N est crit en base b b entier naturel non nul inf rieur 10 Donner un algorithme permettant d obtenir son criture en base 10 On ne v rifiera pas que ce nombre a une criture valide en base b Question 3 Un nombre N est crit en base 10 Donner un algorithme permettant d obtenir son criture e
9. branches dont on donne la dimension Document r dig par le groupe algorithmique de PIREM de Grenoble 42 Python Fiche 3 Exercice 1 Tracer un carr puis l int rieur le cercle tangent d une autre couleur figure 1 Exercice 2 Tracer un carr puis le carr qui joint les milieux des c t s Ecrire un programme qui permet de faire n carr s embo t s de la sorte figure 2 Exercice 3 Tracer un carr puis n carr s imbriqu s dans celui ci ayant le m me coin inf rieur gauche et les longueurs des cot s qui soient les multiples successifs du plus petit figure 3 figurel figure2 figure3 Exercice 4 Tracer le colima on de Pythagore Exercice 5 On veut dessiner le drapeau europ en Ecrire un programme qui trace une toile a cinq branches Ecrire une fonction toile Ecrire le programme qui permet de tracer le drapeau europ en Exercice 6 Faire tracer une toile puis une deuxi me toile plus petite au bout de chaque branche de l toile initiale Document r dig par le groupe algorithmique de PIREM de Grenoble 43 Mini formulaire Python 2 Commencer le programme par from math import Si on veut faire des calculs avec des cos sin racine etc from turtle import Si on veut des dessins graphique etc from random import Si on ve
10. de l algorithme AB BA Question 2 En utilisant une troisi me variable C crire un algorithme qui permute les valeurs des variables A et B Question 3 Porter sur le sch ma suivant les valeurs des variables et B lors du d roulement de l algorithme A B a b A A B B lt A B ASSA B Exercice 4 Trouver un algorithme qui transforme le contenu des variables B et C B C a b c en le contenu suivant permutation circulaire A B C c a b On utilisera une autre variable D Document r dig par le groupe algorithmique de PIREM de Grenoble 11 Exercice 5 On consid re la recette suivante Choisir un nombre entier N Lui ajouter 4 Multiplier la somme obtenue par le nombre N choisi Ajouter 4 ce produit crire le r sultat Question 1 Faire fonctionner cette recette pour les entiers N compris entre 0 et 6 Question 2 Formuler une conjecture sur la valeur du r sultat obtenu pour un entier N quelconque Question 3 crire un algorithme qui prend en entr e un nombre entier N et qui renvoie le r sultat de la recette dans une variable R l algorithme devra contenir exactement trois instructions d affectation Question 4 Programmer cet algorithme en Python et tester la conjecture pour d autres nombres entiers Question 5 Prouver la conjecture Document r dig
11. des expressions prenant des valeurs lt vrai gt ou lt faux gt A gal B s crira en Python A pour distinguer de l affectation A inf rieur ou gal ou strictement inf rieur B s criront en Python A lt B A lt B A gt B A gt B A diff rent de B A B Document r dig par le groupe algorithmique de PIREM de Grenoble sup rieur ou gal ou strictement sup rieur B s criront en Python ce 61 Instruction it rative Python poss de une instruction it rative correspondant au sch ma algorithmique Tantque condition alors Instructioni Instruction En voici un exemple en langage Python entr e sortie Python 2 N 5 I 1 while I lt N print I I I 1 L instruction lt pour gt En Python 2 et Python 3 range M N d signe l ensemble des entiers de M N 1 et range N d signe l ensemble des N entiers de 0 N 1 En utilisant cet ensemble range les programmes Python suivant donnent des exemples de l instruction lt for gt entr e sortie Python 2 Entrer un entier N input L range N Parcours des l ments 0 1 N 1 et criture de chaque l ment for i in L print i On peut pour chaque l ment effectuer un ensemble d instructions par exemple Entrer un entier N input Parcours des l ments 0 1 N 1 for i in range N j i i
12. en rep rant chaque objet de la collection par un num ro appel aussi indice par exemple A 0 A 1 A 2 A 3 A 4 d signeront 5 objets d une collection ou plus g n ralement A0 Af1 Af2 Af3 ALN avec N entier naturel quelconque d signeront N 1 objets d une collection Dans la suite s appelera une liste et en g n ral les l ments de seront des nombres ou des caract res Dans cette partie algorithmique nous ne ferons pas r f rence un langage de programmation Signalons cependant que selon le langage de programmation utilis on pourra rencontrer les termes liste tableau vecteur de m me on trouvera les notations A 7 ou A T pour d signer l l ment d indice I Suivant les langages les tableaux commenceront l indice 0 ou l indice 1 chaque option ayant ses avantages et inconv nients Nous ferons abstraction dans la partie algorithmique de ces diff rences dues aux langages de programmation A titre d exemple pour cr er la liste A dont les l ments sont A 0 A 1 A 2 A 3 A 4 nous utiliserons l algorithme I 0 tantque I lt 4 Entrer A I II 1 ou plus g n ralement pour cr er une liste A depuis l l ment A DEBUT l l ment A FIN I DEBUT tantque I lt FIN Entrer A I II 1 Exercice 1 Question 1 On consid re l ensemble des valeurs num rot es Al Af1 A 2 A 3 A 4 Que fait l algorithme suivant
13. gaux cet entier crire une fonction auxiliaire qui prend en entr e un entier N et renvoie la d composition en facteurs premiers de cet entier sous la forme de deux listes une liste de facteurs premiers une liste des exposants associ s crire enfin une fonction qui prend en entr e deux entiers naturels et renvoie leur PGCD Document r dig par le groupe algorithmique de lIREM de Grenoble 28 5 2 Id es pour des situations pour la classe PGCD Les documents d accompagnement relatifs l algorithmique en classe de Seconde indiquent que lt l introduction de chaque nouvel l ment variable boucle it ration etc devrait appara tre lors de la r solution de probl mes pour lesquels les d marches habituelles sont malcommodes ou peu performantes par exemple dans le cas de r p tition d une t che ou dans le cas d un traitement trop long pour tre envisag la main Ces situations peuvent tre rencontr es lors de l extension des cas plus g n raux de situations d j rencontr es recherche du pgcd de nombres tr s grands tri d un tr s grand nombre de valeurs num riques simulations sur des chantillons de grande taille gt Exercice 1 Tester si un nombre est premier Question 1 Le nombre 119 est il un nombre premier Question 2 Le nombre 139 est il un nombre premier Question 3 crire un algorithme permettant de tester si un nombre entier est un nombre p
14. inspir s de constats faits dans le document officiel d accompagnement proposant les pistes suivantes Les comp tences suivantes pourront tre identifi es et travaill es comprendre et analyser un algorithme pr existant modifier un algorithme pour obtenir un r sultat particulier analyser la situation identifier les donn es d entr e de sortie le traitement mettre au point une solution algorithmique comment crire un algorithme en langage courant en respectant un code identifier les boucles les tests des op rations d criture d affichage valider la solution algorithmique par des traces d ex cution et des jeux d essais simples adapter l algorithme aux contraintes du langage de programmation identifier si n cessaire la nature des variables valider un programme simple Nous avons choisi d orienter l tude de l algorithmique en liaison avec les math matiques et l apprentissage du raisonnement Ceci nous am ne privil gier l laboration de solutions dont on pourra ais ment v rifier l exactitude Nous avons galement labor sur la plupart des th mes des propositions de situations pour la classe que les professeurs pourront mettre en uvre avec leurs l ves Ces situations pourront servir de base pour la construction d autres exercices pour la classe Webographie Les cours de G rard Berry au coll ge de France http wuw college de france fr
15. solution unique cherch e est galement dans l intervalle a c Dans le cas contraire o le test v rifie f c lt 0 Si la quantit exacte f c est effectivement strictement n gative alors la solution unique cherch e est dans l intervalle c b m me c b si du fait de l approximation la valeur exacte de f c est effectivement nulle alors la solution unique cherch e est galement dans l intervalle c b Dans les deux cas on peut donc remplacer l intervalle a b soit par l intervalle a c soit par l intervalle c b et l algorithme d j pr sent Entrer a Entrer b Entrer precision tantque b a gt precision c a b 2 si f c gt 0 bec sinon a crire c se trouve robuste aux calculs approch s mais attention des probl mes de pr cision peuvent appara tre si l on demande un encadrement trop pr cis Document r dig par le groupe algorithmique de lIREM de Grenoble 39 8 Une activit au lyc e de Moirans par Marie Jo Schmitt Jean Pierre Peyrin et des enseignants du lyc e Pierre B ghin Programmation Python fiche n 1 On peut t l charger Python sur le site http www python org download c est gratuit Attention toute cette activit est r dig e pour la version 2 7 de Python Ouvrir Python avec Idle nous sommes dans la page Python Shell 1 D but de programme Un programme commence souvent p
16. 0 Question 4 A votre avis le jeu est il l avantage du li vre ou de la tortue Document r dig par le groupe algorithmique de IREM de Grenoble 56 Exercice 4 Probabilit Question 1 A l aide d un arbre d terminer le probabilit que la tortue gagne Question 2 En d duire la probabilit que le li vre gagne Question 3 Comparer les r sultats avec ceux obtenus dans l exercice 3 Exercice 5 Modifications possibles Question 1 On peut modifier les r gles du jeu et d cider que la tortue avance de 2 ou 3 ou cases la fois Question 2 On peut galement modifier le nombre de cases parcourir par la tortue Document r dig par le groupe algorithmique de PIREM de Grenoble 57 Quatri me partie Python le strict n cessaire Traduire un algorithme dans un langage de programmation est n cessaire l objectif d un algorithme con u par lt un tre humain gt est de faire ex cuter de fa on automatique ces op rations une machine gt Le passage sur machine permet de constater que l algorithme a t bien con u il donne un retour positif concret du travail th orique effectu C est important d un point de vue p dagogique en particulier pour les l ves Le choix d un langage est en m me temps important et pas important Nous avons trouv en PYTHON un langage lt simple gt une interface utilisateur r duite 2 ou 3 fen
17. 4 1679027 ce qui veut dire qu il traduit la cha ne de caract res pr c dente en un nombre machine sur lequel on va pouvoir faire les op rations arithm tiques Plus pr cis ment l ordinateur est capable d appliquer des op rateurs arithm tiques sur cette repr sentation ce n est pas le cas sur les autres repr sentations et par exemple l algorithme suivant a un sens A lt 1679027 B A 1 C lt AxB 6 2 Syst me en base quelconque La liste 1 6 7 9 0 2 7 fait explicitement r f rence la notion de repr sentation et donc pose la question de la base Par contre consid rons les repr sentations en binaire du nombre 101 comme on l crit en math matique Si on crit ce nombre sous la forme 1 l instruction 101 affectera videmment A le nombre d cimal 101 et non 1 x2 0 x21 1 x 20 5 Si on travaille en base quelconque ventuellement sup rieure 10 seules les repr sentations 3 et 4 sont valables en y ajoutant des symboles ad quats par exemple pour le syst me hexad cimal 0 1 2 3 4 5 6 7 8 9 A B C D E F Pour simplifier nous ne traiterons ici que de bases b lt 10 et seules les repr sentations 1 et 2 pourraient tre utilis es Il nous para t donc plus clair d utiliser uniquement la repr sentation 2 pour une base b lt 10 m me si elle est plus lourde et se permettre les deux repr sentations 1 et 2 pour les nombres d cimaux Tous nos algorithmes seront la
18. Document d accompagnement des stages de formation l algorithmique Document r dig par le groupe Algorithmique de PIREM de Grenoble Mise jour F vrier 2013 Ont particip au groupe Algorithmique de PIREM de Grenoble Mich le Benois Anne Bil got Nadia Brauner Martine Brilleaud Christian Davin Damien Jacquemoud Anne Krotoff Bernard Lacolle Pascal Lafourcade Michel Lamarre Simon Modeste Gilles Mounier Jean Pierre Peyrin Marie Jo Schmitt Benjamin Wack Contact Pascal Lafourcade imag fr Table des mati res I Quelques l ments de base 1 Manipulation des m moires et affectation II 1 1 Le coin des profs 1 2 Situation pour la classe manipulation des m moires et affectation Sch mas it ratifs et manipulations des listes 2 1 Situation pour la classe prise en main d un sch ma it ratif 2 2 Situations pour la classe manipulation des listes Sch mas conditionnels 3 1 Le coin des profs 3 2 Situation pour la classe 3 3 Situation pour la classe 3 4 Situation pour la classe 3 5 Situation pour la classe Activit s Dessine moi un carr PGCD et preuve 5 1 Le coin des profs prise en main de l instruction conditionnelle maximum minimum tri de 2 nombres maximum minimum tri de 3 nombres maximum minimum dans un ensemble de valeurs 5 2 Id es pour des s
19. algorithme pour 330m et comparer le r sultat obtenu avec votre estimation Document r dig par le groupe algorithmique de IREM de Grenoble 50 12 Le jeu des allumettes par Romain Janvier et Franck Chambon Pr requis Boucles tests affichages m lant texte et variables Deux joueurs doivent tour de r le prendre une deux ou trois allumettes parmi celles pr sentes devant eux Celui qui prend la derni re a gagn Pour l instant nous supposerons qu il y a 10 allumettes au d but du jeu Exercice 1 Dans un premier temps nous allons essayer de faire un jeu simple permettant deux joueurs de s affronter Question 1 Lorsqu un joueur d cide du nombre d allumettes qu il veut prendre quelles sont les conditions que doit satisfaire sa r ponse Question 2 crire un algorithme qui fait jouer deux adversaires tour de r le On pourra utiliser une variable J pour indiquer le joueur courant qui vaudra 1 ou 2 et une variable N pour le nombre d allumettes restantes Question 3 Faire un programme en python correspondant cet algorithme Voici un exemple d utilisation joueur 1 a toi de jouer il reste 10 allumettes tu en prends 3 joueur 2 a toi de jouer il reste 7 allumettes tu en prends 3 joueur 1 a toi de jouer il reste 4 allumettes tu en prends 3 joueur 2 a toi de jouer il reste 1 allumettes tu en prends 1 Bravo joueur 2 tu as gagne Pour afficher la valeur d une
20. ar from math import Si on veut faire des calculs avec des cos sin racine etc from turtle import Si on veut des dessins graphique etc from random import Si on veut faire des probabilit s et avoir des nombres au hasard gt 2 Quelques bases du langage python a input entrer un nombre L ordinateur affiche Entrer un nombre si l utilisateur tape 4 alors a 4 print le nombre a a L ordinateur affiche Le nombre a 4 b axa i L ordinateur calcule a a 1 et affecte le r sultat dans la m moire b print b L ordinateur affiche b c est dire 3 Premier programme L utilisateur doit entrer 2 nombres et l ordinateur affiche la somme puis le produit de ces 2 nombres a input entrer un premier nombre b input entrer un deuxi me nombre print La somme de ces 2 nombres est a b print Le produit de ces 2 nombres est a b Document r dig par le groupe algorithmique de PIREM de Grenoble 40 Exercice 1 Vous pensez deux nombres l ordinateur doit les trouver Pour cela vous lui donnez la somme et la diff rence de ces deux nombres Ecrivez le programme correspondant Exercice 2 Nous voulons crire un programme qui permet de donner l heure Tokyo quand on conna t celle Moirans en t d calage de 7H Aide il faut donner un format d entr e e
21. ation Fin it ration Remplir chacun des deux tableaux pour le deuxi me algorithme Document r dig par le groupe algorithmique de PIREM de Grenoble 13 Exercice 2 D tailler le fonctionnement de l algorithme suivant et le comparer au deuxi me algorithme de l exercice 1 I 0 A 0 tantque I lt 2 I lt Il i At A I Exercice 3 Que pensez vous de l algorithme suivant I 0 A 0 tantque I lt 2 At A I Exercice 4 On consid re l algorithme suivant I 0 Seo Entrer N tantque I lt N S S I II 1 SssS N crire S Question 1 Sachant que l on a pour un entier N positif N N 1 1 2 4 4 N se que calcule cet algorithme Question 2 Le r sultat est il exact pour N 0 Question 3 Que pensez vous du cas N lt 0 Exercice 5 crire un algorithme qui tant donn un entier N renvoie la somme des carr s des N premiers entiers naturels Document r dig par le groupe algorithmique de PIREM de Grenoble 14 2 2 Situations pour la classe manipulation des listes Jusqu pr sent quand nous avions plusieurs variables plusieurs emplacements m moire nous avons d sign chacun e d elles par un nom diff rent par exemple A B C D Pour pouvoir d signer facilement un grand nombre d objets du m me type sans attribuer un nom diff rent chacun il devient indispensable d utiliser un nom unique pour d signer une collection d objets
22. bor s en supposant que nous pouvons faire les op rations usuelles sur les nombres entiers en machine addition soustraction multiplication quotient et reste de la division enti re Document r dig par le groupe algorithmique de lIREM de Grenoble 31 6 3 Travailler avec une repr sentation en liste 6 3 1 Des choix faire Tout d abord il nous faudra toujours faire r f rence la base b consid r e Pour des raisons de simplicit nous ne consid rons que des bases b lt 10 Consid rons maintenant la liste A 1 6 7 9 En supposant que les indices commencent z ro nous avons donc A 0 1 A 1 6 A 2 7 A 3 9 et le nombre correspondant est alors A o x b A 1 x b A 2 x b A 3 x b et nous n avons pas une correspondance directe entre les indices de la liste et les puissances de b contrario le nombre AJO x b Af1 x bt A 2 x b A 3 x b3 ne correspond plus au visuel A 1 6 7 9 mais au visuel A 9 7 6 1 Le tout est de faire un choix et de s y tenir nous pr f rons le premier choix visuel et d ailleurs nous serons galement amen utiliser des repr sentations comme 0 0 6 7 9 6 3 2 Entrer un nombre sous forme d une liste On notera d abord que l algorithme l mentaire suivant et sa traduction en Python 2 Demander A A input accepte aussi bien une entr e 1679027 qu une entr e 1 6
23. cas contraire f c lt 0 la solution unique est dans l intervalle fc bf Remarque 2 Consid rons l exemple suivant Soit n un entier 0 lt n lt 1000 et consid rons la fonction f d finie sur 0 1001 par f x 1 xe On f n 0 f x 1 x n 1001 On remarquera que l algorithme de dichotomie r sout le probl me de la recherche du nombre n condition que la longueur de l intervalle r sultant soit inf rieur 1 ce qui est r alis apr s 10 it rations Calcul exact et arr t ventuel de l algorithme sur la valeur exacte Nous supposons toujours que le calcul se fait de fa on exacte et nous voulons int grer dans l algorithme un arr t ventuel quand la valeur exacte est trouv e Nous partons de l hypoth se que la solution recherch e est dans l intervalle a b ce qui signifie que l on a test auparavant les valeurs extr mes a et b L adaptation de l algorithme propos e est la suivante Entrer a Entrer b Entrer precision trouve 0 tantque b a gt precision et non trouve c a b 2 si f c 0 trouve 1 sinon si f c gt 0 bec sinon a si trouve 1 crire solution exacte c sinon crire solution approch e dans a bl Document r dig par le groupe algorithmique de PIREM de Grenoble 38 Calcul approch Nous abordons le cas de calcul approch comme le pratiquent les ordinateurs en arithm tique flottante Nous ferons les hypoth ses ra
24. cci inf rieurs 500 Document r dig par le groupe algorithmique de PIREM de Grenoble 49 11 Incroyable mais vrai par Raphael Brakha On prend une feuille de papier ordinaire d paisseur 0 2 mm On plie cette feuille en deux puis en deux etc Exercice 1 Le nombre de pliages est connu On se propose de d terminer l paisseur de la feuille l issue de N pliages Question 1 la main calculer l paisseur de la feuille au bout de 5 pliages Question 2 votre avis quelle est l paisseur de la feuille au bout de 15 pliages Question 3 crire un algorithme permettant de calculer l paisseur de la feuille au bout de N pliages Question 4 Programmer cet algorithme sur machine Question 5 Faire fonctionner votre algorithme pour 15 pliages et comparer le r sultat obtenu avec votre estimation Exercice 2 Le nombre de pliages d pend d une condition On se propose maintenant de d terminer combien de pliages seront n cessaires pour d passer une certaine paisseur Question 1 votre avis combien de pliages sont n cessaires pour que l paisseur d passe la hauteur de la Tour Eiffel 330m Question 2 crire un nouvel algorithme permettant de d terminer le nombre de pliages de la feuille pour que l paisseur d passe une hauteur donn e choisie par l utilisateur Question 3 Programmer cet algorithme sur machine Question 4 Faire fonctionner votre
25. e X et Y ont la m me longueur n Question 4 M me question lorsque X et Y n ont plus la m me longueur Question 5 Programmer cet algorithme en Python Exercice 2 crire un algorithme permettant de calculer le produit aX o a est un entier inf rieur 10 Exercice 3 crire un algorithme permettant de calculer le produit XY Exercice 4 Modifier les algorithmes pr c dents pour les faire fonctionner dans une autre base Exercice 5 Programmer l un des algorithmes pr c dents en langage Python Document r dig par le groupe algorithmique de PIREM de Grenoble 34 6 6 Id e de situation pour la classe somme produit Exercice 1 crire un algorithme qui affiche le r sultat de l addition de 2 nombres de 20 chiffres Exercice 2 crire un algorithme qui double un nombre de 20 chiffres Exercice 3 crire un algorithme qui affiche le r sultat de la multiplication d un nombre de 30 chiffres par 7 Exercice 4 crire un algorithme qui affiche le r sultat de la multiplication de 2 nombres de 20 chiffres Document r dig par le groupe algorithmique de PIREM de Grenoble 39 7 Recherche dichotomique 7 1 Je cherche un nombre entre 1 et 1000 Pr requis algo Instructions conditionnelles et boucles conditionnelles Pr requis math Math matiques du coll ge R currence pour la preuve de la derni re question Ce jeu se joue deux joueurs A et B Le joueur A choisit secr teme
26. e d une distance donn e tourne gauche d un angle exprim en degr tourne droite trace un cercle du rayon voulu oriente la t te de la tortue de cet angle par rapport l orientation initiale de la tortu Il faut terminer le programme par mainloop Les boucles lt tant que gt ou lt pour gt while condition Tant que la condition est v rifi e alors on ex cute les ins Instructions ex cuter tructions Cette instruction s appelle une boucle for i in range debut fin 1 Si on veut r peter une ou plusieurs instruction plusieurs Instructions ex cuter fois de suite du nombre debut jusqu au nombre fin Cette instruction s appelle une boucle colormode 255 color 255 1 1 color i 255 1 color 1 1 255 Enclenche le mode RGB gt des couleurs Red Green Blue Donne la couleur rouge Donne la couleur verte Donne la couleur bleue On peut utiliser tous les nombres de 1 255 pour avoir toutes les couleurs possibles Document r dig par le groupe algorithmique de PIREM de Grenoble 45 Troisi me partie Situations pour la classe propos es par des participants Document r dig par le groupe algorithmique de PIREM de Grenoble 46 9 L escalier par Raphael Brakha On peut consid rer qu un escalier est compos de cubes juxtapos s et ou empil s comme sur le dessin ci dessous HE escalier u
27. e dans tout le paragraphe Nous ferons l hypoth se que la fonction f est d finie croissante sur l intervalle a b et que l quation f x 0 poss de une solution unique sur fa b La propri t de continuit n est pas n cessaire Calcul exact Partons tout d abord avec l hypoth se que le calcul de f x se fait de fa on exacte et exami nons l algorithme suivant Entrer a Entrer b Entrer precision tantque b a gt precision c a b 2 si f c gt 0 bec sinon ac crire c Argumentation consid rons le point c 44 et regardons ce que nous pouvons d duire du 2 test si f c gt 0 comme la fonction est croissante la solution unique cherch e est dans l intervalle a c m me fa cl dans le cas contraire f c lt 0 la solution cherch e est dans l intervalle c b Conclusion en chaque d but d it ration on peut affirmer que la solution appartient l in tervalle a b l amplitude de l intervalle tant divis par 2 chaque tape il est assez facile de prouver que l algorithme s arr te Document r dig par le groupe algorithmique de PIREM de Grenoble 37 Remarque 1 on peut galement montrer que si la solution appartient l intervalle a b alors cette condition est maintenue tout au long de l algorithme En effet si f c gt 0 comme la fonction est croissante la solution unique cherch e est dans l intervalle fa c dans le
28. e la division r elle 3 2 donne 1 0 partie enti re de la division r elle Instruction conditionnelle et tests logiques Tout d abord consid rons l instruction conditionnelle simple lt si gt correspondant au diff rents sch ma algorithmique Si condition Alors Instructionli Instruction2 Python 2 et Python 3 if condition instructioni instruction2 Suite du programme Exemple de programme Python entr e sortie de Python 2 Calcul de la valeur absolue X input Entrez un nombre print Nombre entr X On examine si X est positif ou nul if X gt O Y X On examine si X est strictement n gatif if X lt O Y X print Valeur absolue du nombre Y Document r dig par le groupe algorithmique de PIREM de Grenoble 60 On consid re maintenant l instruction conditionnelle lt si alors sinon gt correspondant au sch ma algorithmique Si condition alors Instructionli Instruction2 sinon Instructions Instructions Exemple de programme Python entr e sortie de Python 2 Calcul de la valeur absolue X input Entrez un nombre print Nombre entr X On examine si X est positif ou nul et on fait Y X et dans le cas contraire Y X if X gt 0 Y X else Y X print Valeur absolue du nombre Y En marge des instructions conditionnelles nous avons rencontr des lt tests logiques gt sont
29. fficher S A B B S S A B Afficher S A B B S S A B Afficher S ASB B amp sS S A B Afficher S A B B S S A B Afficher S Question 2 L algorithme affiche la suite de nombres 1 2 3 5 8 Quel serait le nombre suivant de la suite Comment est calcul chaque nombre de la suite Cette suite de nombres s appelle la suite de Fibonacci Question 3 En s inspirant de l algorithme ci dessus pour afficher les 10 premiers nombres de cette suite il faudrait r p ter 10 fois les instructions AB Bs S A B Comment am liorer alors l criture de l algorithme Document r dig par le groupe algorithmique de PIREM de Grenoble 48 Question 4 crire l algorithme en utilisant l instruction pour I 1 10 Question 5 Adapter l algorithme pr c dent pour afficher les N premiers nombres de la suite de Fibonacci Question 6 Saisir et tester le programme suivant N input N B 1 S 1 print S for I in range N 1 A B B S S A B print S Pour aller plus loin Afficher le quotient 4 Que se passe t il quand N augmente Exercice 2 Question 1 Que fait l algorithme suivant S 0 Saisir N Pour 1 1 N Se S I Afficher S Question 2 Programmer et tester un programme affichant la somme des N premiers entiers S ance ult rieure pour introduire le Tant Que Algorithme affichant tous les termes de la suite de Fibona
30. gle a et une distance d tracer le segment depuis lt x y gt de direction a et de longueur d a a T Y Exercice 3 tant donn un point lt x y gt et une distance d tracer le carr depuis lt x y gt de c t d z y Document r dig par le groupe algorithmique de PIREM de Grenoble 25 Exercice 4 tant donn un point lt x y gt et une distance d tracer le carr depuis lt y gt de c t d et n carr s int rieurs 8 e a Exercice 5 tant donn un point lt x y gt et une distance d tracer le carr depuis lt x y gt de c t d et n carr s int rieurs JAN L Exercice 6 Etant donn un point lt x y gt et une distance d tracer le carr depuis lt x y gt de c t d et n carr s int rieurs sans lever la plume et sans repasser deux fois sur le m me trait JAN LY Document r dig par le groupe algorithmique de PIREM de Grenoble 26 5 PGCD et preuve Pr requis math savoir ce qu est le pgcd de deux nombres et les algorithmes appris en troisi me Pr requis algo les instructions si et tant que doivent tre connues Objectif math r investir l algorithme d Euclide enseign en troisi me Objectif algo programmer un algorithme connu pour automatiser une t che r p titive 5 1 Le coin des profs Exercice 1 Deux algorithmes de calcul du pgcd de deux entiers naturels figurent dans le programme de Troisi me l al
31. gorithme des soustractions gt et l algorithme d Euclide Exemple calcul du PGCD de 90 et 28 En appliquant l algo des soustractions En appliquant l algo d Euclide 90 28 62 90 28 x 3 6 62 28 34 28 6x4 4 34 28 6 6 4x1 2 28 6 22 4 2x2 0 22 6 16 Le pgcd de 90 et de 28 est donc gal 2 16 6 10 10 6 4 6 4 4 2 2 Le pgcd de 90 et de 28 est donc gal 2 Question 1 crire l algorithme des soustractions entr e deux entiers entr s par l utilisa teur sortie PGCD de ces deux entiers Question 2 Le coder en langage Python Question 3 crire l algorithme d Euclide entr e deux entiers entr s par l utilisateur sortie PGCD de ces deux entiers Question 4 Le coder en langage Python On peut galement calculer le PGCD de deux entiers l aide des d compositions en facteurs premiers de ces deux entiers Exemple calcul du PGCD de 90 et 28 90 2 x 3 x 5 28 2 x 7 donc PGCD 90 28 2 x 30 x 50 x 70 2 Question 5 crire un algorithme permettant de calculer le PGCD de deux entiers naturels en utilisant cette m thode et le programmer en Python Suggestions on pourra par exemple crire une fonction auxiliaire qui prend en entr e un entier naturel et renvoie la liste des Document r dig par le groupe algorithmique de IREM de Grenoble 27 nombres premiers inf rieurs ou
32. ien s r ses contraintes de Document r dig par le groupe algorithmique de lIREM de Grenoble 53 fabrication Question 1 Dans cette question on ne tient pas compte de la contrainte sur le temps de travail crire un algorithme qui pour un nombre de portes en ch ne fabriqu es donn permette l artisan de calculer le b n fice fait en fonction du nombre de portes en h tre fabriqu es Attention ne pas oublier la contrainte de stockage Question 2 Comment modifier l algorithme pour que l artisan puisse obtenir les b n fices dans tous les cas de fabrication possible Question 3 Comment modifier l algorithme pr c dent pour tenir compte aussi de la contrainte sur le temps de travail Question 4 Quel est le b n fice maximum Pour combien de portes de chaque type est il obtenu Document r dig par le groupe algorithmique de lIREM de Grenoble 54 14 Le li vre et la tortue par H l ne Langlais Julien Duval Martine Pi tu Dominique Callies R gle du jeu chaque tour on lance un d Si le 6 sort alors le li vre gagne la partie sinon la tortue avance d une case La tortue gagne quand elle a avanc de 5 cases L objectif est de d terminer si le jeu est l avantage du li vre ou de la tortue Exercice 1 On joue Question 1 Lancer le d et remplir le sch ma ci dessous Tortue C Qui gagne Li vre Question 2 Faire deu
33. isonnables suivantes pour l valuation approch e d une quantit si la valeur exacte lt 0 alors sa valeur approch e est strictement n gative si la valeur exacte 0 alors sa valeur approch e est soit nulle soit strictement positive soit strictement n gative en fait on ne peut rien conclure si la valeur exacte gt 0 alors sa valeur approch e est strictement positive Avec ces hypoth ses quelle signification peut on alors donner au test f c gt 0 sachant que le calcul de f c a t fait de fa on approch e soit la valeur exacte de f c est effectivement strictement positive soit du fait de l approximation on a pour la valeur exacte f c 0 Avec ces m mes hypoth ses dans le cas contraire o la valeur approch e de f c v rifie le test f c lt 0 alors soit la valeur exacte de f c est effectivement strictement n gative soit du fait de l approximation on a pour la valeur exacte f c 0 Avec une fonction f d finie continue croissante sur l intervalle fa b et une solution unique de l quation f x 0 sur fa b consid rons le point c ape et regardons ce que nous pouvons d duire du test f c gt 0 Si la quantit exacte f c est effectivement strictement positive alors la solution unique cherch e est dans l intervalle a c m me a cf si du fait de l approximation la valeur exacte de f c est effectivement nulle alors la
34. ituations pour la classe PGCD propos des nombres entiers 6 1 Syst me d cimal Document r dig par le groupe algorithmique de P IREM de Grenoble 12 12 14 17 17 18 18 19 20 23 24 26 26 28 30 6 2 Syst me en base quelconque 6 3 Travailler avec une repr sentation en liste 6 4 Changement de base 6 5 Somme produit et complexit 6 6 Id e de situation pour la classe somme produit 7 Recherche dichotomique 7 1 Je cherche un nombre entre 1 et 1000 7 2 Recherche de la solution d une quation f x 0 par dichotomie 8 Une activit au lyc e de Moirans III Situations pour la classe propos es par des participants 9 L escalier 10 Introduction sur les boucles 11 Incroyable mais vrai 12 Le jeu des allumettes 13 Fabrication de portes 14 Le li vre et la tortue IV Python le strict n cessaire Document r dig par le groupe algorithmique de PIREM de Grenoble 35 39 36 39 45 46 A7 49 50 52 54 57 Introduction De tr s nombreuses pistes ont t propos es pour laborer le contenu d un stage de formation des enseignants de math matiques des l ments d algorithmique Pour laborer le sch ma de ce stage nous nous sommes
35. les l ves avec de vraies allumettes Il est fort probable que le gagnant trouve ou connaisse la strat gie gagnante Il peut alors l expliquer aux autres l ves Ou alors les l ves peuvent affronter le professeur afin de tester leurs strat gies On peut poser la limite d une tentative par l ve pour les obliger r fl chir avant de se lancer r pondre Document r dig par le groupe algorithmique de IREM de Grenoble 52 13 Fabrication de portes par Bernadette Oury Rabourdin Ce qui suit est plut t une suite d activit s pour introduire petit petit les diff rentes no tions d algorithmique du programme en enrichissant progressivement une situation initiale Chaque notion tant ensuite retravaill e avec des exercices s int grant dans les chapitres tudi s en cours Id e de d part si on programme une fonction f dans l diteur de fonction de la calculatrice et qu on lui donne le r el x elle nous renvoie f x Comment pourrait on faire pour avoir la m me chose avec une fonction de deux variables x et y Une situation un artisan fabrique des portes en h tre et des portes en ch ne Il met 3 5h pour fabriquer une porte en h tre et 2 5h pour fabriquer une porte en ch ne Il fabrique x portes en h tre et y portes en ch ne par semaine Exercice 4 On s int resse au temps de travail hebdomadaire de l artisan Question 1 L artisan fabrique 5 portes en h tre et 3 portes en ch ne u
36. les algorithmes naturels suivants pour r aliser les deux s quences d instructions labor es ci dessus Entrer A O A 1 A 2 A 3 A 4 Af5 lt Calculer le maximum de A O et A 1 dans MAXIMUM gt pour i 2 4 faire lt Calculer le maximum de A i et MAXIMUM dans MAXIMUM gt Entrer A O A2 A 3 A 4 Af5 MAXIMUM A O pour i 1 4 faire lt Calculer le maximum de Ali et MAXIMUM dans MAXIMUM gt Pour aller plus loin Exercice 1 Traiter le cas A 0 A 1 A 2 Af 3 A N Exercice 2 Appliquer la m thode la d termination du maximum et minimum d une fonc tion que l on a valu e en des points Exercice 3 crire les algorithmes permettant de trouver le maximum des l ments A DEBUT A FIN et laborer un algorithme de tri Document r dig par le groupe algorithmique de PIREM de Grenoble 22 Document r dig par le groupe algorithmique de PIREM de Grenoble 23 Deuxi me partie Activit s Document r dig par le groupe algorithmique de PIREM de Grenoble 24 4 Dessine moi un carr Les questions sont progressives Chaque question doit conduire un programme Python Pour importer la librairie de dessin from turtle import Exercice 1 tant donn deux points lt 1 y1 gt et lt x2 y2 gt tracer le segment qui relie les deux points T1 Y Exercice 2 tant donn un point lt x y gt un an
37. n 2 crire un algorithme qui permute les valeurs stock es dans B et C en effectuant une permutation circulaire Question 3 Programmer chacun des deux algorithmes en Python Document r dig par le groupe algorithmique de PIREM de Grenoble 1 2 Situation pour la classe manipulation des m moires et affectation On expliquera d abord ce que signifie M N en comparant l affectation au lt copier coller gt pour que les l ves comprennent que ce que l on a mis dans M reste dans N Exercice 1 Question 1 Porter sur le sch ma suivant les valeurs des variables A B et C lors du d roulement de l algorithme B C 1 1 1 2 B 10 C A B C B C Question 2 Qu obtient on en derni re ligne si la premi re tape on met 5 dans la variable A au lieu de mettre 2 Et si l on met 3 Question 3 M me question pour des valeurs initiales quelconques mises dans les variables A B et C C A B C B cC Exercice 2 Porter sur le sch ma suivant les valeurs prises de la variable X lors du d roulement de l algorithme X 0 A B 9 C 4 D 8 X X X x10 B X amp X 10 C X X x10 D Document r dig par le groupe algorithmique de PIREM de Grenoble 10 Exercice 3 Question 1 Porter sur le sch ma suivant les valeurs des variables et B lors du d roulement
38. n base b b entier naturel non nul inf rieur 10 Question 4 Un nombre N est crit en base b b entier naturel non nul inf rieur 10 Donner un algorithme permettant d obtenir son criture en base 10 apr s avoir v rifi que ce nombre a une criture valide en base b Document r dig par le groupe algorithmique de IREM de Grenoble 33 6 5 Somme produit et complexit On consid re deux nombres entiers X et Y comportant respectivement n et m chiffres on imagine n et m assez grands On souhaite crire les algorithmes permettant de calculer par les techniques pos es classiques en colonnes la somme X Y et le produit X x Y Les algorithmes de ce paragraphe manipulent des listes qui contiennent les chiffres de X et de Y Les nombres consid r s sont donc repr sent s par des listes chaque chiffre du nombre est un l ment de la liste Cela permet de manipuler des nombres tr s longs voir la section sur les manipulations de liste Exercice 1 Question 1 Pour X 1 2 3 4 et Y 3 1 4 1 que contient la liste Z la fin de l algorithme suivant Entr e Deux listes X et Y de m me taille n Sortie Une liste Z pour i allant de O n 1 Z i max X i Y i Question 2 Lorsque les deux nombres entiers X et Y comportent respectivement n et m chiffres combien de chiffres peut contenir au maximum leur somme X Y Question 3 crire un algorithme permettant de calculer la somme X Y lorsqu
39. n degr Attention pour que l utilisateur puisse fermer la fen tre de la tortue suivant le processus usuel il faut achever le programme par l instruction mainloop Le programme suivant combine l utilisation de la notion de fonction et un dessin l aide du module turtle from turtle import def segment x1 y1 x2 y2 up goto x1 y1 down goto x2 y2 color red segment 0 0 100 100 color green segment 100 100 100 200 mainloop Document r dig par le groupe algorithmique de PIREM de Grenoble
40. n main de l instruction conditionnelle Exercice 1 Que fait l algorithme suivant Entrer X Si X gt 0 alors Y X Si X lt 0 alors Y X Exercice 2 Que fait l algorithme suivant Entrer X Si X gt 0 alors Y x sinon Ye X 3 3 Situation pour la classe maximum minimum tri de 2 nombres Exercice 1 crire un algorithme lisant les valeurs de et B et affectant le maximum de A et B la variable MAXIMUM Une solution Entrer A B Si A gt B alors MAXIMUM A Sinon MAXIMUM B Note on fera r fl chir les l ves au cas o A B Exercice 2 Compl ter l algorithme pr c dent pour affecter le maximum de A et B la variable MAXIMUM et le minimum de A et B la variable MINIMUM Une solution Entrer A B Si A gt B alors MAXIMUM A MINIMUM B Sinon MAXIMUM B MINIMUM A Document r dig par le groupe algorithmique de PIREM de Grenoble 19 Exercice 3 Notre but est maintenant d crire un algorithme lisant les valeurs de A et B et affectant le maximum de et B la variable et le minimum de et B la variable B Question 1 Que pensez vous de l algorithme suivant Entrer A B Si A lt B alors AB B A Question 2 crire l algorithme correct en utilisant une variable suppl mentaire C Exercice 4 Refaire les exercices pr c dents dans le cas du minimum 3 4 Situation pour la classe maximum minimum tri de 3 n
41. ne certaine semaine Quel est son temps de travail pour cette semaine Question 2 L artisan fabrique x portes en h tre et y portes en ch ne une certaine semaine Exprimer en fonction de x et de y son temps de travail pour cette semaine Question 3 crire un algorithme qui permette de calculer le temps de travail hebdomadaire de l artisan connaissant le nombre de portes en h tre et celui de portes en ch ne fabriquer durant une semaine Question 4 L artisan a une contrainte son temps de travail ne doit pas d passer 40h par semaine Ecrire un algorithme qui lui permette de savoir s il peut fabriquer dans la semaine le nombre de portes en h tre et le nombre de portes en ch ne qu il a en commande Exercice 5 L artisan a une deuxi me contrainte les portes sont toutes livr es en fin de semaine aux clients et il ne peut pas stocker plus de 13 portes dans son atelier Question 1 crire une in quation traduisant cette contrainte Question 2 Modifier l algorithme pr c dent pour qu il permette l artisan de savoir s il peut fabriquer dans la semaine le nombre de portes en h tre et le nombre de portes en ch ne qu il a en commande Exercice 6 La vente d une porte en h tre rapporte 90 euros et que celle d une porte en ch ne rapporte 80 euros L artisan souhaite savoir combien de portes de chaque sorte il doit fabriquer chaque semaine pour avoir un b n fice maximum en respectant b
42. ne marche escalier deux marches escalier trois marches Exercice 1 Question 1 Dessiner un escalier de 5 marches Question 2 Calculer le nombre de cubes n cessaires pour fabriquer un escalier de 6 marches puis un escalier de 7 marches On cherche le nombre de cubes n cessaires pour fabriquer un escalier comportant 365 marches comme dans le phare des baleines l le de R Question 3 Ecrire un algorithme qui permet de calculer le nombre de cubes n cessaires pour N marches Question 4 Programmer cet algorithme Exercice 2 On donne maintenant N cubes On cherche d terminer le nombre de marches du plus grand escalier que l on peut ainsi construire quitte ce que certains cubes ne servent pas Question 1 Avec 20 cubes quel est le plus grand escalier que l on peut construire Question 2 crire un algorithme qui permet de r pondre la question pos e Question 3 Programmer cet algorithme Document r dig par le groupe algorithmique de PIREM de Grenoble 47 10 Introduction sur les boucles Pr requis Affectations de m moires et si alors sinon avec programmation sur Python Objectif Premi res boucles avec pour Attention en Python l instruction for i in range 10 donne les entiers de 0 9 Exercice 1 Question 1 D rouler l algorithme suivant et crire les valeurs successives de B et S A B S A 0 B 1 S A B A
43. nt un nombre cible compris strictement entre 1 et 1000 Le joueur B doit deviner ce nombre en faisant le minimum de propositions chaque proposition du joueur B le joueur r pond par le nombre cherch est plus grand gt lt x le nombre cherch est plus petit gt ou bravo vous avez gagn gt selon la position de la proposition par rapport la cible atteindre Exercice 1 Le but de cet exercice est de jouer contre l ordinateur Question 1 Proposer un algorithme pour que l ordinateur tienne le r le du joueur A Question 2 Programmer et tester cet algorithme en langage Python On utilisera les ins tructions suivantes from random import pour importer la librairie randrange 1000 pour tirer un nombre entre 0 et 999 Question 3 Imaginer une strat gie lt optimum gt qui permette au joueur B de toujours gagner avec un maximum de 10 propositions Tester cette strat gie avec le programme de la Question 2 Question 4 Proposer un algorithme pour que l ordinateur tienne maintenant le r le du joueur B et applique la strat gie lt optimum gt pr c dente chaque proposition de l ordinateur vous r pondrez par gt gt ou lt x bravo gt pour le nombre cherch est plus grand gt lt le nombre cherch est plus petit gt ou lt c est gagn gt Question 5 crire et tester cet algorithme en langage Python Question 6 Quels sont les nombres ch
44. oisir pour que l ordinateur trouve la solution en au moins 9 coups Question 7 Montrer que l algorithme lt optimum gt permet de toujours trouver l entier en au plus 10 essais Indication On peut utiliser un raisonnement par r currence sur K si B A lt 2 alors on peut trouver le nombre compris strictement entre et B en au plus K essais Remarque Dans une situation pour la classe avec les m mes exercices sans les questions 6 et 7 on essayera de faire merger chez les l ves la m thode de recherche par dichotomie Document r dig par le groupe algorithmique de IREM de Grenoble 36 7 2 Recherche de la solution d une quation f x 0 par dichotomie Pr requis math fonction fonction croissante d croissante Pr requis algo tantque instruction conditionnelle Objectif math solution d une quation f x 0 Objectif algo mettre en place un algorithme it ratif de calcul Cet exercice souvent pr sent comme l un des plus naturel pour illustrer la liaison entre math matique et algorithmique se r v le en fait assez complexe La principale difficult est que les calculs sont effectu s de fa on approch e Un test f x 0 pose probl me car la quantit f x n est valu e que de fa on approch e Dans certains cas calcul exact cette question peut ne pas se poser mais dans le cas g n ral il nous faudra r fl chir au pr alable cette question Hypoth se fait
45. ombres Exercice 1 On souhaite crire un algorithme lisant les valeurs de B et C et affectant le maximum de B et C la variable MAXIMUM On essaiera de privil gier une solution utilisant le travail d j fait On pourra proposer une solution de ce type en amenant petit petit la suppression des instructions inutiles Entrer A B C Calcul du maximum de A et B Si A gt B alors MAXIMUM A Sinon MAXIMUM B Calcul du maximum de MAXIMUM et C Si C gt MAXIMUM alors MAXIMUM C Sinon Ce calcul est inutile MAXIMUM MAXIMUM Il y aura certainement d autres propositions avec des lt si alors sinon gt pas toutes faciles analyser Il serait bon de privil gier pour les l ves les solutions qui se lt lisent facilement sans ambigu t gt Document r dig par le groupe algorithmique de PIREM de Grenoble 20 Exercice 2 Tri des 3 nombres A B C On essaiera de privil gier ce qui a d j t crit la lisibilit des algorithmes crits Question 1 On utilise l algorithme de l exercice la suite duquel les valeurs de A et B ont t ordonn es par valeurs d croissantes le maximum dans A On r sumera le r sultat de cet algorithme par lt Ordonner A et B gt Montrer que la succession des instructions Ordonner A et B gt Ordonner A et C gt Ordonner B et C gt donne le r sultat attendu et d tailler cet algorithme Un r sulta
46. print devient une fonction Entr e et sortie d un nombre can Mpaspal Ceci se traduit par les changements suivants A input Entr e et sortie d un nombre print sans texte Entr e et sortie d un nombre A eval input avec texte print A A input A Entr e et sortie d un nombre print A A avec texte A eval input A print A A Par commodit dans toute la suite de ce document nous utilisons la syntaxe Python 2 Le lecteur fera facilement la traduction s il utilise une autre version Instruction d affectation en Python 2 et Python 3 A A 1 Document r dig par le groupe algorithmique de PIREM de Grenoble 59 La division quelques diff rences entre Python 2 et Python 3 Parmi les op rations arithm tiques seule la division m rite une attention particuli re pour viter des erreurs En Python 2 et Python 3 lt gt d signe la division et lt gt la division enti re Mais il y a quelques diff rences entre les deux versions illustr es par les exemples suivants Python2 3 2 donne 1 division enti re r sultat entier 3 2 donne 1 5 division r elle r sultat r el 3 2 donne 1 division enti re r sultat entier Python3 3 2 donne 1 5 division r elle r sultat r el 3 2 donne 1 5 division r elle r sultat r el 3 2 donne 1 division enti re r sultat entier 3 2 donne 1 0 partie enti re d
47. remier Question 4 Le coder en langage Python Exercice 2 PGCD et simplification de fractions Partie 1 Brevet des Coll ges 2005 Aix Marseille Corse Montpellier Nice Toulouse Question 1 Trouver le PGDC de 6209 et 4435 en d taillant la m thode Question 2 En utilisant le r sultat de la question pr c dente expliquer pourquoi la fraction 4435 p CR 609 2 est pas irr ductible Question 3 Donner la fraction irr ductible gale o Partie 2 G n ralisation Question 4 crire un algorithme de calcul du PGCD de deux entiers naturels Question 5 crire un algorithme permettant de d terminer si une fraction est irr ductible et si elle ne l est pas permettant de donner sa forme simplifi e Entr e deux nombres entiers le num rateur et le d nominateur de la fraction tester Sortie deux nombres entiers le num rateur et le d nominateur de la fraction simplifi e Document r dig par le groupe algorithmique de PIREM de Grenoble 29 Exercice 3 Partie 1 CRPE Bordeaux Caen 2000 Le service des espaces verts veut border un espace rectangulaire de 924m de long sur 728m de large l aide d arbustes r guli rement espac s Un arbuste sera plac chaque angle du terrain La distance entre deux arbustes doit tre un nombre entier de m tres Question 1 D terminer toutes les valeurs possibles de la distance entre deux arbustes Question 2 D terminer dans chaq
48. son ensemble Nous constaterons que les programmes crits feront au plus une dizaine Document r dig par le groupe algorithmique de PIREM de Grenoble 58 ou une vingtaine d instructions Il est pr f rable d utiliser l extension py pour le fichier qui contient le programme Ceci permet l diteur de reconna tre qu il s agit d un programme crit en Python et d utiliser si possible la coloration syntaxique Python propose un environnement permettant de disposer en m me temps de la fen tre lt interactive gt Python Shell elle permettra d ex cuter ventuellement des instructions isol es mais surtout d entrer des donn es de sortir des r sultats des calculs d une fen tre correspondant un lt diteur de texte gt int gr diteur IDLE qui proposera une fa on tr s ergonomique d crire le programme et d ex cuter directement ce programme partir de l diteur Apprendre travailler avec ces deux fen tres l cran procurera un confort que chacun appr ciera Commenter un programme Dans l criture d un programme Python tout texte pr c d du signe et ceci jusqu la fin de ligne ne sera pas pris en compte Instructions lt entr e sortie gt Python2 Python3 On utilisera les instructions En Python 3 input renvoie input et print une cha ne de caract re qu il faut valuer et
49. t possible Entrer A B C Ordonner A et B Ordonner A et C Ordonner B et C Si A lt B alors Si A lt C alors Si B lt C alors XA X A XB A B At C Bec B X Cex Cex Question 2 Essayer de proposer d autres solutions 3 5 Situation pour la classe maximum minimum dans un ensemble de valeurs Exercice 1 Nous consid rons un ensemble de valeurs num rot es gt que nous appellerons A 0 A 1 A 2 Af3 A4 On reprendra la question 1 de l exercice 1 o l on a crit un algorithme affectant le maximum de A et B la variable MAXIMUM On r sumera cette action l mentaire par lt Calculer le maximum de A et B dans MAXIMUM gt Question 1 Que fait la suite d instructions suivantes Calculer le maximum de A O et A 1 dans MAXIMUM gt Calculer le maximum de A 2 et MAXIMUM dans MAXIMUM gt Calculer le maximum de A 3 et MAXIMUM dans MAXIMUM gt Calculer le maximum de A 4 et MAXIMUM dans MAXIMUM gt Document r dig par le groupe algorithmique de PIREM de Grenoble 21 Question 2 Que fait la suite d instructions suivantes MAXIMUM prend la valeur A 0 lt Calculer le maximum de A 1 et MAXIMUM dans MAXIMUM gt Calculer le maximum de A 2 et MAXIMUM dans MAXIMUM gt lt Calculer le maximum de A 3 et MAXIMUM dans MAXIMUM gt lt Calculer le maximum de A 4 et MAXIMUM dans MAXIMUM gt Question 3 Lire interpr ter et compl ter
50. t sortie du r sultat print Donner une heure Moirans sous la forme heures minutes secondes Hmoirans minutes secondes input Donner une heure Moirans Exercice 3 a Recopier et utiliser le programme suivant sans oublier les tabulations essentielles avec python from random import myst int random x100 1 n 1 reponse input Choisir un nombre entier entre 1 et 100 while reponse myst if reponse gt myst print Trop grand n n i else print trop petit n n i reponse input Choisir un nombre entier entre 1 et 100 print Gagn en n coups b Expliquer tape par tape ce que fait ce programme Document r dig par le groupe algorithmique de PIREM de Grenoble 41 Fiche 2 Exercice 1 Tracer un segment connaissant les deux extr mit s Tracer un segment connaissant le point de d part l angle avec l horizontale et sa longueur Exercice 2 Faire un programme qui permet de tracer un triangle quilat ral un carr un pentagone r gulier un hexagone r gulier un polygone r gulier 10 c t s 22 c t s 50 c t s un polygone r gulier n c t s Exercice 3 Maintenant on veut qu il soit inscrit dans le cercle de centre l origine et de rayon 400 Exercice 4 Maintenant on veut que le premier segment trac soit horizontal Exercice 5 Tracer une toile 5
51. tion it rative d une action A avec elle m me selon une condition de terminaison C not e tantque non faire A indique que l action est r p t e jusqu ce que la condition C devienne vraie Si C est vraie au d part l action A n est pas effectu e Exemple somme S des N premiers nombres entiers N gt 1 i 1 S 1 tantque i N faire i i 1 SS i Remarque La condition d arr t C est i N La composition r cursive Une action A est r cursive si elle est exprim e par une composition d actions dont elle fait elle m me partie Cette composition rend n cessaire la d nomination de l action et l introduction de param tres Nous en verrons l usage dans le cadre de la progression p dagogique Document r dig par le groupe algorithmique de PIREM de Grenoble 1 Manipulation des m moires et affectation Objectif algo s approprier la notion de variable effectuer des op rations simples sur les variables affecter une valeur changer des valeurs utiliser des valeurs stock es dans des variables pour construire une op ration dont le r sultat est stock dans une autre variable 1 1 Le coin des profs Exercice 1 On consid re deux variables et B dans lesquelles on stocke deux valeurs arbitraires a et b Question 1 crire un algorithme qui change les valeurs stock es dans les variables et B en utilisant une autre variable et ou sans utiliser une autre variable Questio
52. uations gagnantes Question 2 Donnez une situation qui n est pas gagnante Assurez vous que quel que soit le nombre d allumettes prises dans cette situation le joueur suivant sera dans une position gagnante On parle alors de situation perdante Question 3 Pour trouver les autres situations gagnantes on cherche celles mettant l autre joueur dans une situation perdante Dire pour toutes les situations de moins de 15 allumettes si elles sont perdantes ou gagnantes Question 4 Comment faire lorsqu un joueur est dans une situation gagnante pour mettre l autre joueur dans une situation perdante Question 5 Faire l algorithme qui correspond un tour de jeu de l ordinateur en appliquant la strat gie au dessus S il se trouve dans une situation perdante il pourra par exemple prendre une seule allumette Question 6 Modifier votre programme pour que le r le du joueur 2 soit tenu par l ordinateur Question 7 Changer le programme pour demander au d but de la partie le nombre maxi mum d allumettes pouvant tre prises en un tour Que faut il modifier dans la strat gie de l ordinateur pour tenir compte de ce changement Remarque Peut tre qu il faut donner la strat gie gagnante aux l ves pour leur permettre de ne pas tre bloqu s Ou alors on peut laisser plusieurs jours semaines aux l ves pour trouver la strat gie gagnante Remarque On peut aussi imaginer organiser un tournoi entre
53. ue cas le nombre d arbustes n cessaires la plantation Partie 2 G n ralisation Question 3 crire un algorithme permettant de dresser la liste de tous les diviseurs d un nombre entier Question 4 Le coder en langage Python Question 5 Ecrire un algorithme permettant de dresser la liste de tous les diviseurs communs entre deux nombres entiers Question 6 Le coder en langage Python Question 7 On revient au contexte donn en partie 1 crire un algorithme qui tant donn les dimensions d un espace rectangulaire renvoie les distances possibles entre arbustes et le nombre d arbustes n cessaires la plantation Question 8 Le coder en langage Python Document r dig par le groupe algorithmique de lIREM de Grenoble 30 6 propos des nombres entiers 6 1 Syst me d cimal Il s agit d une suite de chiffres mais regarder de plus pr s cela pourrait prendre plusieurs formes 1 l criture d cimale usuelle 1679027 2 une liste de chiffres 1 6 7 9 0 2 7 3 une liste de caract res 1679027 4 une liste de caract res 1 6 7 9 0 2 7 Des ss La repr sentation 1 la plus naturelle est en fait complexe et a un double r le 1 cette repr sentation n est en fait que la cha ne de caract res 3 sans guillemets repr sentant le nombre en question 2 l ordinateur comprend une instruction du type
54. ut faire des probabilit s et avoir des nombres lt au hasard gt Instruction d affectation a 1 a i a Instruction entr e sortie Entr e et sortie d un nombre sans texte a input print a Entr e et sortie d un nombre avec texte a input Entrer un nombre L ordinateur affiche Entrer un nombre si l utilisateur tape 4 alors a 4 print Le nombre a a L ordinateur affiche Le nombre a 4 Instruction conditionnelle et test logique if condition se traduit par lt lt si condition alors sinon gt gt Instruction 1 Instruction 2 else Instruction 3 Instruction 4 Test logique en Python a gal b s crit a a diff rent de b s crit a b a inf rieur ou gal b s crit a lt b Document r dig par le groupe algorithmique de PIREM de Grenoble A4 Instructions de base pour dessiner On appelle le module tortue from turtle import La tortue part du point 0 0 de gauche droite horizontalement c est sa position initiale reset up down goto x y forward distance backward left angle right angle circle Rayon seth angle efface le dessin l ve le stylo baisse le stylo d place le stylo jusqu au point voulu de coordonn es x y avance d une distance donn e recul
55. variable entre deux textes sur la m me ligne on peut utiliser print textel variable texte2 ins rer des parenth ses en Python 3 Question 4 Donner des exemples d utilisation de votre programme pour montrer que vous tenez bien compte de toutes les conditions donn es dans la premi re question Exercice 2 Nous allons maintenant essayer d apporter quelques am liorations au programme Ces optimisations sont optionnelles et vous pouvez si vous le voulez passer l exercice sui vant sans les avoir toutes trouv es Document r dig par le groupe algorithmique de PIREM de Grenoble 5l Question 1 Si ce n est pas encore le cas modifier la partie du programme pour changer de joueur sans utiliser de test mais uniquement une soustraction Question 2 Modifier le programme pour demander le nombre d allumettes au d part Question 3 Changer l affichage du nombre d allumettes en affichant des barres la place d un nombre Par exemple Il reste Exercice 3 Nous allons maintenant modifier le programme pour qu un joueur puisse affronter l ordinateur Question 1 Il existe une strat gie permettant de toujours gagner ce jeu Afin de la trouver il faut identifier les situations gagnantes c est dire celles qui assurent la victoire du joueur dont c est le tour Par exemple s il reste une seule allumette la victoire est garantie Trouver deux autres sit
56. vec la notion de fonction dont l introduction fait partie du programme de math matique Pour dire court une fonction en Python sera une suite d instructions qui seront ex cut es l appel de la fonction Document r dig par le groupe algorithmique de PIREM de Grenoble 63 Par exemple dans le programme suivant la fonction cube permet d lever au cube le pa ram tre x de la fonction le programme joint calcule les cubes gt des entiers de 0 10 def cube x return x x Xx for i in range 11 print i cube i Le sch ma g n ral d une d claration de fonction est def fct arguments corps de la fonction return resultat Une fonction peut comporter plusieurs param tres et m me aucun param tre Les modules externes Si nous devons utiliser des fonctions math matiques comme sinus cosinus il nous faut importer le module math matique en faisant figurer au d but du programme from math import Si nous voulons utiliser des g n rateurs de nombres al atoires il nous faut importer le module correspondant from random import Par exemple pour g n rer un entier al atoire entre deux entiers a et b on utilisera randint a b Le programme suivant apr s avoir construit un tableau contenant les entiers 0 1 2 N lui affecte N l ments al atoires entre 0 et 10 from random import N input L range N
57. x autres parties Tortue O Er O Qui gagne Li vre Tortue Om 0 Qui gagne Li vre Question 3 A votre avis le jeu est il l avantage du li vre ou de la tortue Exercice 2 Algorithme Question 1 Compl ter l algorithme ci dessous crit en langage naturel Document r dig par le groupe algorithmique de PIREM de Grenoble 59 Les variables PositionTortue PositionLi vre D Initialisation PositionTortue 0 PositionLievre 0 Course Tant que PositionTortue lt OT uses mes cas D nombre entier al atoire entre 1 et 6 Si D alors PositionLievre Sinon PositionTortue 4 444548484ssiecseuuses R sultat Si PositionLievre 5 alors Afficher a he em TRS Re set Sinon Afficher seras sheet rt Question 2 Traduire en Python l algorithme pr c dent et le tester Exercice 3 Fluctuation d chantillonnage Question 1 Avec une boucle while modifier l algorithme pr c dent pour simuler 1000 parties Question 2 Compter le nombre de parties gagn es par le li vre et par la tortue et afficher ces r sultats Question 3 Faire tourner l algorithme pr c dent plusieurs fois et remplir le tableau ci dessous Echantillon num ro Nombre parties gagn es par le li vre Nombre parties gagn es par la tortue 1 2 3 4 5 6 7 8 9 1
Download Pdf Manuals
Related Search