ATELIER ALGORITHMIQUE

Exercice d'introduction

Un problème de recherche du nombre de boites nécessaire à la confection d’une tour « chamboule-tout » à N étages nous conduit à calculer la somme des entiers consécutifs jusqu'à un N donné. Construire un algorithme qui permet de calculer la somme des entiers consécutifs jusqu'à un N donné.

Problème des cars de supporters

Une entreprise de transport possède 4 cars de 50 places chacun et se propose d'assurer le transport des supporters d’une équipe de rugby. Chaque car se loue 800 € tout compris.

1. Comment donner de façon automatique le prix par supporter en fonction du nombre de supporters se rendant au stade.

2. Représenter graphiquement le prix par supporter en fonction du nombre de supporters se rendant au stade.

3. Combien l'organisateur peut-il accepter de supporters, s'il s'est engagé à ce que le prix d'une place ne dépasse pas 20 € ?

Exercices complémentaires

Exercice 1 Construire un algorithme donnant par balayage les minimum et maximum de la fonction f définie sur l'intervalle [ ]2;1− par ( ) 3 2 3 1f x x x x= + − − .

Exercice 2 Construire un algorithme permettant d'arrondir au centième près un nombre donné.

Structure SI … ALORS … SINON

Exercice 3 On tire de façon aléatoire, deux nombres x et y, compris entre 0 et 1 et on place dans le plan (rapporté à un repère orthonormal) le point M de coordonnées (x ; y). On effectue un grand nombre de tirages. Faire apparaître la fréquence des points dont la distance à l'origine est strictement inférieure à 1. Comparer cette

fréquence à 4π .

Remarque : Cette méthode est proche de celle des aiguilles de Buffon pour déterminer expérimentalement une valeur de π. Il faut faire un grand nombre de tirages car elle converge lentement. On utilise des méthodes probabilistes, appelées aussi méthode de Monte-Carlo, en calcul intégral pour approcher des surfaces et des volumes.

Exercice 4

Déterminer le nombre de triangles dans cette figure.

ÉLÉMENTS DE CORRECTION

Exercice d'introduction

Problème des cars de supporters Les exemples ci dessous donne des algorithmes ayant des différences de stratégies et des variations suivant le langage choisi. Toutes les stratégies exposées peut être exploitées avec tous les langages.

Question 1

Avec Scratch

Exemple sous AlgoBox avec TANT QUE.

Sur calculatrices Programme sur Graph 35 avec TANT QUE

Programme sur TI avec SI…ALORS…SINON

Question 2

Voici un scénario en quatre étapes (on modifie, perfectionne l'algorithme pour passer d'une étape à l'autre…)

a. Travail par disjonction (Quatre intervalles à envisager).

(On ne teste pas ici si N est un entier pour ne pas surcharger le programme). Ceci pourrait sembler fastidieux à taper, mais cela se fait rapidement en utilisant la fonction "Dupliquer" de Scratch. On tape en détail une structure "Si" que l'on duplique ensuite.

b. Des structures conditionnelles (alternatives) emboitées.

On observe le gain en nombre de tests ! Cette étape se construit naturellement à partir de la précédente : toute la puissance de Scratch s'exprime alors (on récupère une partie des structures précédentes, en déplaçant les blocs).

c. Une première tentative de tracé (problème de "bavures" : ce n'est pas une fonction !)

Utilisation d'une boucle : RÉPÉTER…

Ici aussi, il suffit d'intégrer la structure précédente dans un " Répéter jusqu'à…

d. Finalisation : on relève le stylet …et on travaille sur la notion de fonction et de courbe !

Question 3

Avec Algobox

Exercices complémentaires

Exercice 1 Construire un algorithme donnant par balayage les minimum et maximum de la fonction f définie sur

l'intervalle [ –2 ; 1 ] par f ( x ) = x3 + x2 – 3x – 1. (Niveau 2)

Proposition à l'aide d'AlgoBox.

Définition de la fonction :

Définition de la fenêtre graphique :

Le programme :

Le résultat :

Exercice 2 Construire un algorithme permettant d'arrondir au centième près un nombre donné.

Structure Si…alors…sinon Sur AlgoBox Sur Xcas

Exercice 3 : Méthode de Monte-Carlo

On tire de façon aléatoire, deux nombres x et y, compris entre 0 et 1 et on place dans le plan (rapporté à un repère orthonormal) le point M de coordonnées (x ; y). On effectue un grand nombre de tirages. Faire apparaître la fréquence des points dont la distance à l'origine est inférieure à 1 (x² + y² < 1). A la fin on multiplie par 4 pour obtenir une valeur approchée de π.

Exercice 4

Principe du raisonnement :

• Un triangle est défini par trois points … • Tous les triangles de cette figure passent par le point Ω (celui du haut).

• Appelons point de base les points du bas . On va supposer que l’on connait le nombre de triangles pour une figure comportant n points de base (n entier naturel supérieur ou égal à 2). Appelons Total ce nombre.

• Combien de triangles ajoute-t-on si on ajoute un unique point de base ? Ces nouveaux triangles passent par Ω et le nouveau point de base : il y a donc n nouveaux triangles… D’où le nombre de triangles pour n+1 points de base est : Total + n Remarques pour construire l’algorithme : on pourra remarquer que cela revient à calculer la somme des 25 premiers entiers naturels. Cependant cette vision est plutôt vue en classe de première.

En seconde l’algorithmique va permettre, sans passer par une démarche experte, de s’en sortir.

L’algorithme va donc s’attacher à coller au raisonnement du dessus (d’où quelques difficultés avec les initialisations et les indices...)

On initialise Total à 1 ce qui correspond à deux points de base. On construit une boucle pour n de 3 à 26 (nos points de base). On affiche les différentes étapes pour suivre le nombre de triangles.

Algorithme en langage naturel

Total prend la valeur 1

Pour n de 3 jusqu’à 26 Faire

Afficher Total

Total prend la valeur Total + (n-1)

Afficher Total

Traduction sous Algobox

Sous Casio

1 →T For 3 →N To 26 T W T+N-1→T Next T T W

Sous TI

1 STO T For( N,3,26,1) Disp T T+N-1 STO T End Disp T

La

difficulté

est ici !

Avec Scratch :

Attention une erreur dramatique de traduction a été commise sur le Scratch français.

Voici un extrait d’un forum sur le Net expliquant le problème :

« Lorsque vous choisissez Français ou Français Canada le logiciel utilise soit le fichier fr.po soit le fichier fr_CA.po. 1°) J'ai participé à la traduction du fichier fr.po. J'ai fait une grosse erreur de traduction dans un bloc de la catégorie variable ; en effet j'avais traduit : change "variable" by "1" , par changer "variable" par "1". En réalité change "variable" by "1" est : à "variable" ajouter "1". »

Attention : L’écran ci-dessous est donc en Français-Canada.