Exercices sur l'algorithmique

Modélisation des problèmes

[Modélisation et complexité] Traversée de rivière

Beatrix Kiddo, le Terminator T-800, Bill et Sarah Connor sont amenés à franchir une rivière. Pour cela ils ne disposent que d'une petite barque ne pouvant transporter plus de deux personnes à la fois et au moins une (laquelle doit ramer !). Sarah et le Terminator sont très fâchés, tout comme Beatrix et Bill : en aucun cas deux personnes fâchées ne doivent se retrouver seules ensemble, ni sur une rive ni sur la barque

1. Décrire les opérations primitives du problème.
2. Décrire à l'aide de ces opérations un algorithme permettant de résoudre le problème.
3. Définir une nouvelle opération (ou plusieurs si nécessaire), de niveau d'abstraction plus élevé que les opérations primitives, pour exprimer l'algorithme plus simplement.
4. Comparer et discuter les complexités des deux algorithmes proposés.

Bases du langage algorithmique

Conditions et boucles

Donner les affichages produits par l'exécution des algorithmes suivants :

Algorithme 1
Début
   Pour i←2 à 8 faire :
       Écrire('coucou')
       Écrire(i)
       ALaligne
   Fin pour
   Écrire('fin')
Fin 

Algorithme 2
Variable encore : booléen
Début 
     encore ← Faux
     Tant que encore
       Écrire('coucou')
     fin TQ
     Écrire('fin')
Fin 

Algorithme 3
Variables encore : booléen, n:entier
Début 
     encore ← Vrai
     n ← 0
     Tant que encore faire 
       Écrire(n)
       encore ← (n>0)
     fin TQ
     Écrire('fin')
Fin 

Algorithme 4
Variable encore : booléen
Début
     encore ← Vrai
     Répéter 
       Écrire('coucou')
     jusqu'à encore
     Écrire('fin')
Fin 

Algorithme 5
Variable encore : booléen
Début 
     encore ← Faux
     Répéter 
       Écrire('coucou')
     jusqu'à non encore
     Écrire('fin')
Fin 

Algorithme 6
Variable encore : booléen
Début 
     encore ← Faux
     Répéter 
       Écrire('coucou')
       encore ← Non(encore)
     jusqu'à non encore
     Écrire('fin')
Fin 

Passage de paramètres

Indiquer les affichages produits par les algorithmes suivants selon que le passage des paramètres se fait par valeur ou par par référence.

Algorithme plusun (n : entier)
Début
  n = n+1
  Écrire(n)
Fin

Algorithme Principal
Variable n : entier
Début
  n = 5
  Écrire(n)
  plusun(n);
  Écrire(n)
Fin

Écrire des algorithmes

[Boucles imbriquées] Tables de multiplication

1. Proposer un algorithme qui affiche une table de multiplication 10x10.
2. Compléter votre algorithme par des instructions affichant des balises HTML : le résultat doit être un code HTML bien formé qui permette de visualiser joliment la table de multiplication.

[Boucles imbriquées] : Figures géométriques

1. Écrire un algorithme qui dessine un carré plein 10x10 (rempli du caractère * par exemple).
2. Fournir de nouveaux algorithmes pour des triangles rectangles, isocèles, etc.
3. Idem, pour les mêmes figures, mais creuses cette fois.
4. Proposer des versions HTML de ces figures.

[Boucles imbriquées] : Figures et chiffres

Pour chacune des deux figures suivantes, écrire et commenter un algorithme qui la produise.

                                       0000000000
               X                        111111111
               XX                        22222222
               XOX                        3333333
               XOOX                        444444
               XOOOX                        55555
               XOOOOX                        6666
               XOOOOOX                        777
               XXXXXXXX                        88
                                                9

Si les algorithmes proposés n'utilisent pas de procédure, en donner une version avec procédures.

[Tableaux] : Position d'un élément

Proposer un algorithme position qui recherche un élément e dans un tableau t et fournit la position (le numéro de la case) à laquelle e est trouvé.

Si l'élément e n'est pas présent dans le tableau t, l'algorithme doit répondre -1.

Dérouler des algorithmes complexes

Algorithme classiques sur les tableaux

Dérouler les algorithmes de tri bulles et de recherche dichotomique vus en cours d'algorithmique pour les appels suivants :

Variable notes : tableau d'entiers
        _____________________________________
notes ← | 5 | 17 | 4 | 20 | 9 | 12 | 15 | 8 |
        ˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ
TriBulles(notes)
RechercheDichotomique(15,notes)
RechercheDichotomique(0,notes)

Algorithme « Mystère » sur les tableaux

Considérer l'algorithme suivant :

Algorithme Mystere (t : tableau d'entiers);
Variables i, j, jn, jx, sst, bst : entiers;
Début
   n ← taille(t)
   Pour i←1 à n/2 faire :
      jn       ← i;
      jx       ← i;
      Pour j←i+1 à n-i+1 faire :
         Si (t[j]<t[jn]) Alors
            jn ← j;
         Fin si
         Si (t[j]>t[jx]) Alors
             jx ← j;
         Fin si
      Fin pour
      sst      ← t[jn];
      t[jn]    ← t[i];
      Si (jx=i) Alors
         jx ← jn;
      Fin si
      bst      ← t[jx];
      t[jx]    ← t[n-i+1];
      t[i]     ← sst;
      t[n-i+1] ← bst;
   Fin pour
Fin

1. Sachant que la numérotation des cases des tableaux commence à 1, détailler, à travers un tableau donnant les valeurs des variables à chaque étape, l'exécution de cet algorithme pour l'appel suivant :

   Variable notes : tableau d'entiers
           _____________________________________
   notes ← | 5 | 17 | 4 | 20 | 9 | 12 | 15 | 8 |
           ˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ
   Mystere(notes)
   

2. Expliquer l'utilité de cet algorithme en explicitant le rôle de chaque partie. En particulier, donner le rôle de chacune des variables.