UNIVERSITE de la POLYNESIE FRANCAISE

Examen Deug MIAS 2 – Algo/Prog. C Année Universitaire 2002-03 Janvier 2003 – première session

Modalités

1.Vous disposez de trois heure,

2.vos documents personnels sont autorisés,

3.le barème sur 21 est donné à titre indicatif et est susceptible d'être modifié.

1. Détection d’une chaîne dans une autre (env. 5 pts)

On souhaite détecter une chaîne de caractères à l’intérieur d’une autre (classique fonction « substring » disponible dans tous les langages de programmation). Vous écrirez donc en pseudo-code un algorithme de recherche de la chaîne rech de taille long_rech dans la chaîne chaine de taille long_chaine.

Cet algorithme rendra la position du début de rech dans chaine si rech est contenue dans chaine et rendra –1 si rech n’est pas contenue dans chaine.

Exemples :

chaine	Rech	Résultat
« bonjour »	«jour»	3
« bonjour »	«bon»	0
« bonjour »	«toto»	-1
« Hello »	«lo»	3
« Hello »	« Helli »	-1

2. Palindromes

Un palindrome est une chaîne de caractères qui se lit de la même manière dans un sens et dans l’autre. Exemples :

1. radar

2. esoperesteicietserepose (« esope reste ici et se repose » sans les caractères blancs)

3. engagelejeuquejelegagne (« engage le jeu que je le gagne » sans les caractères blancs)

2.1. Donner en pseudo-code un algorithme itératif de détection d’un palindrome(env. 2 pts)

2.2. Donner en pseudo-code un algorithme récursif de détection d’un palindrome (env. 2 pts)

2.3. Ecrire en langage C une procédure ou fonction codant l’algorithme récursif (env. 1 pts)

3. Les carrés magiques

Vous disposez de la structure de données ci-dessous :

#define TAILLE_MAX 6

typedef struct matrix {

int coldim, rowdim;

int elts[TAILLE_MAX][TAILLE_MAX];

} matrix;

Un carré magique d’ordre n est une matrice carrée de dimension n telle que la somme de chaque ligne, la somme de chaque colonne et les sommes des deux diagonales soient identiques.

Exemple : 4 9 2

3 5 7

8 1 6

3.1. écrire en C un prédicat (fonction rendant un booléen) indiquant si une matrice carrée donnée est un carré magique (env. 3 pts)

3.2. écrire en C une procédure ou fonction initialisant une matrice à zéro (env. 1 pt)

3.3. écrire en C une procédure ou fonction permettant de construire un carré magique d’ordre impair (env. 3 pts)

1.On initialise la matrice à zéro,

2.On met 1 au milieu de la dernière ligne,

3.On suit, à partir de cette position, la première diagonale (une case en dessous et une case à droite avec passages en haut (resp. à gauche) lors d’une sortie de la matrice par le bas (resp. par la droite) en mettant successivement 2, 3, 4, ....

4.Dès que le déplacement sur la diagonale vous fait rencontrer un élément déjà entré (non nul), on remonte d’une ligne par rapport à la position courante (avant tentative de déplacement), on pose son nombre et on continue.

Voici la construction pas à pas du carré magique d'ordre 3

0	0	0	0	0	2	0	0	2	4	0	2
0	0	0	0	0	0	3	0	0	3	0	0
0	1	0	0	1	0	0	1	0	0	1	0
4	0	2	4	0	2	4	0	2	4	0	2
3	5	0	3	5	0	3	5	7	3	5	7
0	1	0	0	1	6	0	1	6	8	1	6

3.4. donner le carré magique d’ordre 5 en faisant tourner à la main l’algorithme ci-dessus (env. 2 pts)

Remarque : On ne vous demande pas d’écrire toutes les étapes.

4. Exponentiation (env. 2 pts)

Ecrire en pseudo-code un algorithme récursif qui calcule x à la puissance y.