Bases algorithmiques
Conditions et boucles
Donner les affichages produits par l'exécution des algorithmes suivants :
Algorithme 0
Début
Pour i←2 à 8 faire :
Afficher('coucou')
Afficher(i)
ALaligne
Fin pour
Afficher('fin')
Fin
Algorithme 1
Variable encore : booléen
Début
encore ← Vrai
Répéter
Afficher('coucou')
jusqu'à encore
Afficher('fin')
Fin
Algorithme 2
Variable encore : booléen
Début
encore ← Faux
Tant que encore
Afficher('coucou')
fin TQ
Afficher('fin')
Fin
Algorithme 3
Variable encore : booléen
Début
encore ← Faux
Répéter
Afficher('coucou')
jusqu'à non encore
Afficher('fin')
Fin
Algorithme 4
Variable encore : booléen
Début
encore ← Faux
Répéter
Afficher('coucou')
encore ← Non(encore)
jusqu'à non encore
Afficher('fin')
Fin
Algorithme 5
Variables encore : booléen, n:entier
Début
encore ← Vrai
n ← 0
Tant que encore faire
Afficher(n)
encore ← (n>0)
fin TQ
Afficher('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 Afficher(n) Fin Algorithme Principal Variable n : entier Début n = 5 Afficher(n) plusun(n); Afficher(n) Fin
Écrire des algorithmes
[Modélisation et complexité] Les maris jaloux
Lors d'une randonnée, deux couples 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. Les deux maris, extrèmement jaloux se refusent à laisser leur épouse seule en présence de l'autre homme.
- Décrire les opérations primitives du problème.
- Décrire à l'aide de ces opérations un algorithme permettant de résoudre le problème.
- 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.
- Comparer et discuter les complexités des deux algorithmes proposés.
[Boucles imbriquées] Tables de multiplication
- Proposer un algorithme qui affiche une table de multiplication 10x10.
- 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
- Écrire un algorithme qui dessine un carré plein 10x10 (rempli du caractère * par exemple).
- Fournir de nouveaux algorithmes pour des triangles rectangles, isocèles, etc.
- Idem, pour les mêmes figures, mais creuses cette fois.
- 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 ; n : entier);
Variables i, j, jn, jx, sst, bst : entiers;
Début
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
- 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,8) - Expliquer l'utilité de cet algorithme en explicitant le rôle de chaque partie. En particulier, donner le rôle de chacune des variables.
Voir aussi...
- Introduction à l'algorithmique
Cours d'initiation à l'algorithmique : langage de description, utilisation de boucles, types abstraits, algorithmes sur les tableaux, notions de complexité et de calculabilité.
- Séances de travaux pratiques en programmation
Exercices sur les différents langages de programmation vus en cours.
