Page 1 of 1

Correction algo Olympiades Académiques 2013 1èreS Nice

Unread postPosted: 25 May 2013, 15:42
by critor
Intéressons-nous maintenant à l'algorithme qui est tombé en exercice 3 aux Olympiades Académiques 2013 de Première S dans l'Académie de Nice.

Image


Il s'agit donc ici d'un problème d'éclairage.
Notons que là encore l'auteur du sujet fait plus de la traduction de langage de programmation que de l'algorithmie, notamment avec le test '==' pour l'égalité.



Question 6)a)
Commençons par la question 6.
L'algorithme donné nous construit un lotissement quadrillé 5x5, en codant 0 les zones d'ombre, 1 les zones éclairées, et 2 les maisons.
On nous demande un plan, et il nous suffit d'utiliser l'objet matrice (tableau de nombres vu en spécialité ES) de la calculatrice afin d'obtenir directement un schéma du lotissement.

Voici par exemple la construction d'une solution en utilisant les calculatrice TI-82 à TI-84:
ImageImage
Image


Notre lotissement 5x5 est donc constitué de maisons en diagonale, et les terrains aux alentours ne sont pas du tout éclairés.

Nous obtenons heureusement le même résultat sur Casio Graph/Prizm...
ImageImage
ImageImage


... ou encore sur TI-Nspire:
Image




Question 5)
Maintenant que nous avons vu la question 6, nous savons mieux comment manipuler et parcourir des matrices.
Nous pouvons donc répondre à la question 5, et produire un algorithme disant si le lotissement est bien éclairé ou pas.

Deux boucles 'pour' imbriquées sur les 5 lignes et les 5 colonnes permettent de parcourir toutes les cases du tableau.

Un lotissement est mal éclairé si l'on trouve une case non éclairée (valeur 0).
Comme il peut y avoir plusieurs cases non éclairées, afin d'éviter les affichages multiples il va nous falloir stocker le résultat à l'aide d'un drapeau et l'afficher en fin de boucle.

Code: Select all
e prend la valeur 1
Pour i de 1 à 5
   Pour j de 1 à 5
      Si T[i,j]=0 alors
         e prend la valeur 0
      FinSi
   FinPour
FinPour
Si e=0 alors
   Afficher "Le lotissement est mal éclairé"
Sinon
   Afficher "Le lotissement est bien éclairé"
FinSi


Codons et testons cela tout-de-suite sur TI-82 à TI-84, avec le lotissement de la question 6:
ImageImage
Image


Sans surprise, ce lotissement est mal éclairé.

Voici maintenant le code pour Casio Graph/Prizm...
ImageImage
Image


... et pour TI-Nspire/89/92/V200:
Image




Lien:
Olympiades Acémiques 2013 de Première S (Académie de Nice)

Re: Correction algo Olympiades Académiques 2013 1èreS Nice

Unread postPosted: 25 May 2013, 15:52
by critor
Hors énoncé, dans le cadre d'un lotissement mal éclairé il est inutile et peut donc sembler dommage de parcourir tout le tableau alors que l'on connaît la réponse dès la 1ère case de valeur 0 trouvée.

Notre boucle n'étant alors plus de taille prédéfinie, et il nous faut utiliser une boucle 'Tant que'.

Même si dans le pire des cas cela ne changera rien, voici donc un algorithme qui aura en moyenne une meilleure complexité:
Code: Select all
e prend la valeur 1
i prend la valeur 1
j prend la valeur 1
Tant que e=1 et j≤5
   Si T[i,j]=0 alors
      e prend la valeur 0
   FinSi
   i prend la valeur i+1
   Si i>5 alors
      i prend la valeur 1
      j prend la valeur j+1
   FinSi
FinTantQue
Si e=0 alors
   Afficher "Le lotissement est mal éclairé"
Sinon
   Afficher "Le lotissement est bien éclairé"
FinSi