EFM - Algorithme - 2015-2016

I- Partie Théorique : (4 pts)

1. Ecrire algorithme du tri par sélection optimal (2pts)
2. Citer la différence entre la recherche séquentielle et la recherche dichotomique (2pts)

II- Partie Pratique : (38 Points)

Exercice 1 : (4 pts)

Pour un entier n strictement positif on associe n/2 si n est pair et 3n+1 si n est impair. En réappliquant cette transformation à l’entier obtenu, on définit un algorithme dit de Syracuse. On admettra que pour tout entier n strictement positif de départ on finisse toujours par arriver à 1.

Ecrire un algorithme qui permet de saisir un entier n et d’afficher la liste des entiers obtenus jusqu’à 1, ainsi que le nombre de fois qu’il est nécessaire d’appliquer la transformation pour y arriver.

Voici un exemple de déroulement de l’algorithme:

Exercice 2 : (6pts)

1. Ecrire une fonction qui reçoit en paramètre un tableau de taille n et un entier x, qui vérifie qui cet entier x possède son carré dans le tableau (t(i) * t(i)) en retournant un booléen et en arrêtant le parcours une fois trouvée. (4pts)
2. Ecrire un programme qui affiches les éléments du tableau qui possède leur carrée dans le même tableau (2pts)

         Exemple

Les éléments dans le carrés sont présent : 2, 4, 5

Exercice 3 : (16 pts)

Soit T1 un tableau de 100 valeurs ordonnées de manière croissante.

1. Ecrire un algorithme permettant de construire deux nouveaux tableaux ordonnés de manière décroissante contenant l’un les valeurs paires, l’autre les valeurs impaires. (4pts)

Tableau Initial  T1:

Tableau des valeurs paires T2 :

Tableau des valeurs impaires T3 :

2. Ecrire un algorithme qui permet d’insérer une valeur X dans le tableau T1, supposé triée, de façon à respecter l’ordre des éléments de T1. (4pts)

Exemple :

Si N=5 et T1: 

Si X=9 alors T1 devient:

3. Ecrire un algorithme qui permet de faire le décalage à droite des éléments du tableau T1, un certain nombre de fois. (4pts)

Exemple :

Si T1=

Nombre de décalage à droite est : 2

T1=

4. Ecrire un algorithme qui élimine toutes les occurrences d’un entier X saisit au clavier. (4pts)

Exercice 4 : (10 pts)

Soit A une matrice carrée à deux dimensions

1. Ecrire un algorithme qui calcul la trace de cette matrice.

      Trace(A)=la somme des éléments diagonaux   (3pts)

2. Ecrire l’algorithme qui vérifie si la matrice est triée en ordre croissant ou non. (3 pts)
3. Ecrire l’algorithme qui transfère cette matrice A à deux dimensions dans un tableau B à une seule dimension. (4 pts)