Université Paris 7 - Denis Diderot IF2 : Structures de données et Objets JAVA
L1 Sciences Année 2007-2008, 2ème semestre
TP n◦8
Récursivité
Exercice 1 Suite de Syracuse. La suite de Syracuse est définie par la relation suivante :
u0 >0
un+1 = un /2 si un est pair
un+1 = 3 ∗ un + 1 si un est impair
Dans une classe Syracuse :
1. Écrire une méthode récursive public static int syracuse(int n,int init) qui cal-
cule le nième terme de la suite de Syracuse telle que u0 = init.
2. Écrire le code suivant dans une méthode :
int s, n=0;
while((s = syracuse(n,init)) != 1){
System.out.println(s);
n++;
}
Quel est le rôle de l’instruction ((s = syracuse(n,init)) != 1) ? Donnez la valeur que
vous voulez à init. Quelle est la condition d’arrêt de ce programme ? Pour quelles valeurs
d’entrée s’arrête-t-il ? Pouvez vous montrer qu’il s’arrête pour toutes les valeurs d’entrée ?
3. Le programme précédent n’est pas optimal : en effet, lors de l’appel de syracuse(n+1,init),
on oublie que l’on a déjà calculé précédemment syracuse(n,init). Définissez une méthode
statique récursive void syracuseStop(int terme) qui :
– affiche à l’écran le terme courant.
– calcule le terme suivant de la suite de syracuse (en fonction du terme précédent passé
en argument).
– s’arrête si le terme courant vaut 1 et appelle syracuseStop(termeSuivant) sinon.
Testez le ensuite.
4. En fait, on sait (par des démonstrations informatiques) que pour (au moins) tout u0 < 262 ,
il existe un rang n tel que un = 1. La méthode que vous avez programmée termine-t-elle
pour toute valeur passée en argument ? Et si les entiers sont codés sur 64 bits ?
Exercice 2 Sudoku.
Un principe simple de résolution d’un problème de Sudoku est : on prend la première case libre,
on met le chiffre 1 (si cela est autorisé par les règles), puis on essaye de résoudre (récursivement,
donc) le problème à partir de la case suivante. Si on n’y arrive pas, on essaye de mettre le chiffre
2, etc, etc. Ce principe n’est pas applicable pour un être humain, mais il marche raisonnablement
bien avec les ordinateurs, car ils ont une grande puissance de calcul. Le but de cet exercice est
d’écrire un programme permettant de résoudre tous les problèmes de Sudoku de taille 9x9. La
classe Sudoku contient les objets de type Sudoku :
1
1. Chaque objet a un seul champ private de type int[][] nommé grille, qui sera de taille
9x9. Si le nombre de la case (i,j) est déjà connu (par l’initialisation), alors grille[i][j]
contient ce nombre, sinon il contient 0.
2. Écrire un constructeur Sudoku(int[][] init) qui prend une grille init et la recopie dans
le champ grille de l’objet.
3. Écrire une méthode String toString() qui retourne une chaı̂ne de caractère associée à
l’objet (la représentation en “mode texte” de la grille). Par exemple, cela pourrait être :
-------+-------+-------
| 0 0 0 | 0 0 8 | 0 3 0 |
| 7 0 0 | 0 0 0 | 0 0 5 |
| 0 0 0 | 0 1 0 | 0 0 6 |
|-------+-------+-------|
| 0 0 9 | 0 0 5 | 0 0 2 |
| 0 7 8 | 0 9 0 | 6 0 0 |
| 0 4 5 | 0 0 3 | 0 0 9 |
|-------+-------+-------|
| 0 6 0 | 0 0 1 | 0 0 0 |
| 8 0 0 | 0 6 7 | 9 0 3 |
| 0 0 4 | 8 0 0 | 0 0 0 |
-------+-------+-------
ou bien, si l’on veut faire plus simple :
000008030
700000005
000010006
009005002
078090600
045003009
060001000
800067903
004800000
4. Écrire une méthode récursive 1 boolean nApparaitPasLigne(int nombre,int i, int j)
qui teste si nombre n’apparaı̂t pas sur la ligne i entre les indices j, j+1, ..., 8. N’ou-
bliez pas le test d’arrêt ! Par exemple avec la grille ci-dessus, on a :
nApparaitPasLigne(5,3,0): false
nApparaitPasLigne(5,3,6): true
5. De même écrire une méthode récursive nApparaitPasColonne(int nombre,int i, int j)
qui teste si nombre n’apparaı̂t pas sur la colonne j entre les indices i, ..., 8.
6. Écrire une méthode itérative boolean nApparaitPasCarre(int nombre, int i, int j)
qui teste si nombre apparait dans le sous-carré de taille 3x3 associé à la case (i,j).
Indication : le coin supérieur gauche de ce sous-carré est repéré par les coordonnées
((i/3)*3,(j/3)*3) (pourquoi ?).
7. Écrire une méthode boolean nombrePossible(int nombre, int i, int j) qui teste
s’il est possible de mettre nombre dans la case (i,j).
8. Écrire une méthode boolean caseOccupee(int i, int j) qui teste si la case (i,j) est
déjà occupée. Par exemple, avec la grille précédente : jeu.caseOccupee(0,5) vaut true
tandis que jeu.caseOccupee(5,0) vaut false.
1
donc, ne contenant pas de boucle
2
9. Écrire une méthode récursive boolean resolution(int i,int j) qui retourne true s’il
a réussi à résoudre le problème (et dans le même temps, remplit correctement grille) et
false sinon. (i,j) représente la case de départ de la résolution. L’algorithme suivi sera
le suivant :
test d’arr^ et.
calcul de la case suivante.
si la case (i,j) est déjà occupée on résoud à partir de la case suivante.
sinon on essaye de mettre tour à tour tous les nombres dans la case, puis
de résoudre à partir de la case suivante.
si rien ne marche, on remet la case à 0 et on renvoie false.
10. Enfin, testez vos méthodes et la résolution.
