Thème 2 : Découverte des tableaux

Visite de la mine

Algorithme

Dans le principe, on commence par lire tous les déplacements faits puis il faut les afficher, en partant de la fin, en inversant à chaque fois les déplacements. On pourrait donc avoir un code du type

  Si deplacement = 1
     deplacement <- 2
  SinonSi deplacement = 2
     deplacement  <- 1
  SinonSi deplacement = 4
     deplacement <- 5
  SinonSi deplacement = 5
     deplacement <- 4

C'est cependant assez répétitif et on sent qu'il est possible de faire mieux. On peut en effet utiliser un tableau qui nous donnera, pour chaque déplacement, le déplacement inverse :

  deplacementInverse <- [0, 2, 1, 3, 5, 4]
  deplacement <- deplacementInverse[deplacement]

Cette technique est très courante et permet d'avoir des codes plus courts. Vous aurez l'occasion de la réutiliser à de nombreuses occasions.

On notera que si un tableau a nbDeplacements éléments, alors son dernier élément a pour indice nbDeplacements - 1.

Programme

   deplacementInverse = [0, 2, 1, 3, 5, 4]
   nbDeplacements = int(input())
   chemin = [0] * nbDeplacements
   for numero in range(nbDeplacements):
      chemin[numero] = int(input())
   for numero in range(nbDeplacements-1, -1, -1):
      deplacement = chemin[numero]
      print(deplacementInverse[deplacement])

---

Banquet municipal

Algorithme

L'algorithme est constitué de trois parties : lire les numéros initiaux, faire les changements, afficher les valeurs finales. Seule la deuxième partie demande à être détaillée. En effet, la principale difficulté est de savoir comment inverser les valeurs de deux éléments d'un tableau.

Une première idée, pour inverser les éléments d'indices 0 et 2, consiste à utiliser le code suivant :

  numero <- [1, 2, 3]    # numero contient 1,2,3
  numero[0] <- numero[2] # numero contient 3,2,3
  numero[2] <- numero[0] # numero contient 3,2,3

mais on voit que cela ne marche pas, car on a effacé la valeur de "numero[0]" avant de pouvoir la lire pour la mettre dans "numero[2]". Il faut donc trouver un moyen de stocker cette valeur quelque part, par exemple dans une autre variable :

  numero <- [1, 2, 3]    # numero contient 1,2,3
  temp <- numero[0]      # numero contient 1,2,3 et temp contient 1
  numero[0] <- numero[2] # numero contient 3,2,3 et temp contient 1
  numero[2] <- temp      # numero contient 3,2,1 et temp contient 1

Une fois cette difficulté surmontée, le reste du programme est facile à écrire.

Programme

   nbPersonnes = int(input())
   nbChangements = int(input())
   identifiant = [0] * nbPersonnes
   for idPersonne in range(nbPersonnes):
      identifiant[idPersonne] = int(input())
   for idChang in range(nbChangements):
      premier = int(input())
      second = int(input())
      temp = identifiant[premier]
      identifiant[premier] = identifiant[second]
      identifiant[second] = temp
   for idPersonne in range(nbPersonnes):
      print(identifiant[idPersonne])

---

Choix des emplacements

Algorithme

Dans l'entrée, on nous fournit pour chaque emplacement le numéro du marchand qui s'y trouve. On pourrait donc créer le tableau suivant :

  Pour iEmp de 0 à nbEmplacements - 1
     marchands[iEmp] <- lireEntier()

Or, ce qu'on nous demande au contraire, c'est d'afficher la liste des emplacements correspondant à chaque marchand dans l'ordre de leurs numéros, ou plus simplement d'indiquer pour chaque marchand son emplacement. Il faut donc « inverser » les données ! Au lieu d'un tableau qui met les marchands à leur emplacement, on crée un tableau dans lequel on va mettre les emplacements au numéro du marchand qui le possède. On peut découper la lecture et la mise à jour du tableau (ce qui permet de nommer la valeur) :

  iMarchand <- lireEntier()
  emplMarchands[iMarchand] <- iEmp

Dans certains langages, on n'a d'ailleurs pas d'autre choix. Remarquez que dans un sens, on nomme le tableau marchands, donc uniquement en fonction du rôle des valeurs contenues, et dans l'autre sens, on le nomme emplMarchands (raccourci pour « emplacements des marchands »), donc en combinant le contenu et le rôle des indices. Nous estimons ainsi que les emplacements sont des éléments que l'on se représentera plus intuitivement sous une forme numérique et ordonnée, et donc qu'en nommant notre tableau simplement marchands, on comprend à partir de l'énoncé du problème que les cases correspondent aux emplacements, et les valeurs aux marchands. Nous vous invitons à juger par vous-même.

Programme

   nbEmplacements = int(input())
   emplMarchands = [0] * nbEmplacements
   for iEmp in range(nbEmplacements):
      emplMarchands[int(input())] = iEmp
   for iMarchand in range(nbEmplacements):
      print(emplMarchands[iMarchand])

---