Portail informatique Année 2018 – 2019

CSC 3101 – Algorithmique et langage de programmation

Il est attendu que tous les étudiants fassent les exercices obligatoires : toute notion vue dans un exercice obligatoire peut faire l'objet d'un exercice en examen.

Quelques séries d'exercices obligatoires sont un peu longues et vont probablement nécessiter du travail en hors présentiel. Prenez le temps de terminer ces exercices, ils sont tous importants !

Les exercices d'entraînement ne sont, en revanche, pas obligatoires. Mais les faire est plaisant car vous pourrez approfondir les sujets étudiés. Pour les étudiants les plus à l'aise, vous pourrez probablement réussir à terminer les exercices d'entraînement en présentiel. Profitez en !

Les algorithmes que vous allez étudier dans les deux premières séances vous sont probablement connus. C'est bien le but recherché par l'équipe pédagogique : le but de ces séances n'est pas que vous appreniez de nouveaux algorithmes, mais que vous puissiez acquérir rapidement une bonne dextérité en programmation Java en mettant en œuvre des algorithmes que vous avez (probablement) déjà étudiés.
Dans cette série d'exercices, vous commencez à acquérir les bases du langage Java et vous apprenez des algorithmes simples (calcul du plus petit diviseur et mise en œuvre d'une calculette simple).

Durée des exercices obligatoires : 2h30 en présentiel
  • Exercice 1 : obligatoire (facile, ∼30mn)
  • Exercice 2 : obligatoire (facile, ∼30mn)
  • Exercice 3 : obligatoire (facile, ∼20mn)
  • Exercice 4 : obligatoire (moyen, ∼40mn)
  • Exercice 5 : obligatoire (moyen, ∼30mn)
  • Commencez par faire le DM avant d'attaquer les exercices d'entraînement !
  • Exercice 6 : entraînement (moyen, ∼30mn)
  • Exercice 7 : entraînement (ninja, ∼1h, pour les étudiants les plus aguerris qui veulent s'amuser)
Le but de cet exercice est de vous faire utiliser explicitement toute la chaîne de conception, compilation et exécution de Java. Dans cet exercice, on vous demande de ne pas utiliser une interface de développement avancée comme eclipse. Créez un répertoire csc3101 et placez-vous dans ce répertoire. Ouvrez ensuite un terminal et lancez un éditeur de texte simple pour éditer le fichier HelloWorld.java. Par éditeur de texte simple, nous entendons emacs, gedit, vi ou tout autre éditeur que vous avez apprécié utiliser en CSC3102 (Introduction aux systèmes d'exploitation).

Écrivez un programme affichant Bonjour, monde !!!. Compilez ce programme et exécutez le. On vous rappelle que pour compiler un programme Java, il faut utiliser la commande javac et que pour exécuter un programme Java, il faut utiliser la commande java. $ emacs HelloWorld.java $ javac HelloWorld.java $ java HelloWorld Bonjour, monde !!! $
Déplacez-vous dans votre répertoire racine et lancez java csc3101/HelloWorld. Que constatez vous ? Techniquement, l'interpréteur java est incapable de lancer un programme Java à partir de son chemin. Pour lancer un programme Java à partir d'un autre répertoire, il faut utiliser la variable d'environnement CLASSPATH, qui contient un ensemble de chemins séparés par des deux points (:). Lancez la commande suivante : CLASSPATH=~/csc3101 java HelloWorld. Que constatez vous ? Après être revenu dans le répertoire csc3101, modifiez votre programme de façon à afficher chacun des arguments sur une ligne séparée. Votre programme devrait générer la sortie suivante : $ java HelloWorld Ah que coucou Bonjour, monde !!! args[0]: Ah args[1]: que args[2]: coucou $
Dans ce cours, nous vous demandons d'utiliser un environnement de développement Java adéquat, par exemple eclipse ou intellij. En particulier, nous vous déconseillons fortement l'utilisation d'un éditeur de texte simple comme gedit : en utilisant un environnement de développement efficace, vous verrez rapidement que votre productivité sera améliorée. Comme prendre en main un environnement de développement n'est pas forcément évident, nous vous guidons pas à pas pour utiliser eclipse dans ce TP. Si vous vous sentez déjà à l'aise avec un autre environnement de développement, n'hésitez pas à l'utiliser : dans ce cours, il n'y aucune dépendance par rapport à un environnement de développement particulier (sauf dans cet exercice). Lancez eclipse en saisissant eclipse & dans le terminal. Vous remarquerez que eclipse vous demande de sélectionner votre workspace, c'est-à-dire votre espace de travail. Ce répertoire de travail est la racine à partir de laquelle eclipse enregistre vos projets. Vous pouvez laisser le répertoire par défaut, mais vous pouvez aussi sélectionner le répertoire ~/csc3101 que vous avez créé dans l'exercice précédent (votre programme HelloWorld.java n'apparaîtra probablement pas, c'est normal). Sélectionnez Workbench dans la fenêtre principale. Eclipse définit une notion de perspective : une perspective est une façon de vous présenter votre espace de travail. Par défaut, eclipse ouvre la perspective Java  qui vous présente votre espace de travail comme un ensemble de projets Java. Vous pouvez changer de perspective à tout moment via le menu Window->Perspective->Open Perspective, mais vous ne devriez pas avoir besoin de cette fonctionnalité pour le moment.

Vous pouvez maintenant créer un premier projet Java. Allez dans le menu File->New->Project. Dans le sous menu Java, sélectionnez Java Project. Donnez le nom bonjour à votre projet.
Une perspective est constituée de vues, c'est-à-dire de sous-fenêtres. Vous pouvez ajouter des vues via le menu Window->Show View, mais vous ne devriez pas encore avoir besoin de cette fonctionnalité à cette étape.

Dans la vue Package Explorer se trouvant normalement à gauche de votre écran, vous pouvez voir vos projets. Vous avez maintenant un unique projet appelé bonjour. Si vous cliquez sur ce projet, vous pouvez observer le contenu de ce projet : un répertoire src dans lequel seront stockés les fichiers sources Java de votre programme, ainsi qu'un ensemble de fichiers constituant la bibliothèque standard Java (JRE System Library). Vous pouvez maintenant créer votre première classe. Pour cela, sélectionnez le menu File->New->Class et donnez le nom Bonjour à votre classe. Vous devriez voir apparaître le contenu du fichier Bonjour dans la vue centrale de l'écran (l'éditeur de code). Vous remarquerez que, comparé au cours, eclipse vous a ajouté une ligne contenant package au début du fichier et le mot clé public devant le mot clé class. Ces deux notions vous seront présentées dans les cours suivants, ne vous en souciez pas pour le moment.
Nous allons maintenant écrire la méthode main de notre programme. Dans un premier temps, votre programme doit simplement afficher Bonjour, monde !!!. Pour tester votre programme, vous devriez remarquer un petit bouton vert avec le signe lecture en haut de votre fenêtre, comme celui entouré en rouge dans la figure ci-dessous :

Si vous cliquez sur ce bouton, le programme se lance et vous affiche le résultat dans la vue Console qui s'ouvre par défaut en bas de l'écran. Bravo, vous avez maintenant pris en main eclipse !!!
Comme dans l'exercice précédent, nous souhaitons maintenant afficher les paramètres du programme. Modifiez votre programme en conséquence. Vous pourrez remarquer que, avec Eclipse, si vous tapez quelques lettres et que vous saisissez la combinaison de touches Contrôle + Espace, Eclipse vous propose gentiment de compléter votre code pour vous. Usez et abusez de cette possibilité !

Pour spécifier des paramètres, vous devez aller dans le menu Run->Run Configurations. Dans l'onglet (x)=Arguments, vous pouvez spécifier des arguments dans la fenêtre Program arguments. Utilisez les arguments suivants : Que la force soit avec toi. Vérifiez, en utilisant le bouton run, que votre programme affiche bien ces paramètres.
Comme modifier les paramètres avec la procédure que nous venons de vous expliquer est long et fastidieux, vous avez le moyen de spécifier que vous voulez systématiquement interroger l'utilisateur pour qu'il saisisse les paramètres au moment du lancement de l'application. Pour cela, il suffit de spécifier que le paramètre du programme est ${string_prompt}. Vérifiez que vous arrivez bien à saisir des paramètres à chaque fois que vous lancez votre application avec cette procédure.
Cet exercice a pour but de vous familiariser avec les types de base de Java et avec les conversions de types. Créez un projet types avec une classe nommée Type contenant la méthode main. Lorsque vous créez la classe Type, vous devriez remarquer que eclipse vous propose gentiment de générer la méthode main pour vous, profitez-en !

Copiez-collez le code suivant dans la méthode main et expliquez la sortie que vous observez dans la console. Pour les heureux utilisateurs et utilisatrices de Linux, on vous rappelle que pour copier du texte, il suffit de le sélectionner avec la souris, et que pour coller du texte, il suffit de cliquer sur la touche du milieu (la molette) de la souris.

Expliquez la sortie générée par votre programme. int x = 5; int y = x / 3; double d = 5; double e = d / 3; double f = x / 3; int g = (int)e; /* type moins fort : conversion explicite nécessaire */ char r = 'a'; int s = r; int t = 98; char u = (char)t; /* type moins fort : conversion explicite nécessaire */ String s1 = "y vaut " + y; String s2 = "e vaut " + e; String s3 = "f vaut " + f; String s4 = "g vaut " + g; String s5 = "r vaut " + r; String s6 = "s vaut " + s; String s7 = "t vaut " + t; String s8 = "u vaut " + u; System.out.println(s1); System.out.println(s2); System.out.println(s3); System.out.println(s4); System.out.println(s5); System.out.println(s6); System.out.println(s7); System.out.println(s8); Pour les chaînes de caractères, l'opérateur + correspond à la concaténation car avant une opération, les opérandes sont convertis vers le type le plus fort, c'est-à-dire le type chaîne de caractère.

Pour y, comme les opérandes sont des entiers, le quotient est calculé dans l'ensemble des entiers.

Pour e, comme d est un flottant, l'entier 5 est d'abord convertit en flottant (type le plus fort) avant d'effectuer l'opération. En revanche, pour f, les deux opérandes étant des entiers, le calcul est effectué en entier (résultat 2) puis ensuite convertit en flottant. Finalement, pour g, la conversion explicite d'un flottant vers un entier (type moins fort) correspond à la troncature.

Pour r, le nombre représentant le caractère 'a' est 97. Pour u, 98 représente le caractère 'b'.
Le but de cet exercice est d'écrire un programme permettant de calculer le plus grand commun diviseur (pgcd) de deux entiers. Créez un projet nommé pgcd contenant une classe Pgcd, elle-même contenant une méthode main. Affichez les arguments de votre programme après avoir spécifié que ses paramètres sont 243 576. Modifiez votre programme de façon à vérifier que le nombre d'arguments est bien égal à 2. Si ce n'est pas le cas, votre programme doit afficher un message d'erreur et quitter à l'aide de la méthode System.exit(n), où n est le code de retour de votre programme. Si vous vous souvenez de votre cours d'introduction aux systèmes, vous devriez vous rappeler que toute valeur différente de 0 signifie que votre programme quitte avec une erreur. Vérifiez que votre programme se comporte correctement en modifiant les paramètres. Après vos tests, pensez à rétablir les arguments 243 et 576. Les arguments sont donnés sous la forme de chaînes de caractères. Il faut donc les convertir en entier avant de pouvoir calculer leur plus grand commun diviseur. Pour cela, définissez deux variables entières nommées p et q, et utilisez Integer.parseInt(uneChaine) pour convertir la chaîne de caractères uneChaine en entier. Affichez les valeurs de p et q. Un algorithme calculant le plus grand commun diviseur peut reposer sur la propriété suivante :
  • si p=0, alors pgcd(p ,q) = q,
  • si q=0, alors pgcd(p ,q) = p,
  • si p>q, alors pgcd(p ,q) = pgcd(p-q, q),
  • sinon: pgcd(p, q) = pgcd(p, q-p).
Mettez en œuvre un algorithme itératif (par opposition à récursif) utilisant cette propriété pour calculer le plus grand commun diviseur de p et q. Pour cela, utilisez une boucle while. Si vous obtenez pgcd(243, 576) = 9, vous avez gagné, bravo !
Le but de cet exercice est de vous familiariser avec les tableaux en programmant une petite calculette capable d'effectuer des additions. Créez un projet nommé calculette contenant une classe Calculette, elle-même contenant une méthode main. Affichez les paramètres de votre programme après avoir spécifié que les paramètres sont 8 6 1 3 5 2. Les paramètres sont donnés sous la forme d'un tableau de chaînes de caractères. Notre calculette doit additionner les valeurs numériques correspondant à ces paramètres, et doit donc commencer par convertir chaque chaîne de caractères en valeur entière. Pour commencer, créez une variable tab de type tableau d'entiers, et initialisez cette référence vers un tableau ayant autant d'éléments que le paramètre de la méthode main (args). Complétez votre programme de façon à afficher les éléments du tableau tab. Votre programme devrait afficher 6 fois l'entier 0 puisque vous avez 6 arguments et puisque un tableau est toujours pré-initialisé avec des 0 en Java. Avant d'afficher le tableau tab, utilisez une boucle pour stocker dans tab la conversion en entier de chacun des éléments du tableau de chaînes de caractères donné en paramètre (args). Pour convertir une chaîne de caractères en entier, utilisez la méthode Integer.parseInt(String s) qui renvoie le résultat de la conversion de la chaîne de caractères s en entier. Après avoir affiché le tableau tab, calculez la somme des éléments du tableau tab, puis affichez le résultat. Si votre programme vous affiche 25, vous avez gagné, bravo ! Écrivez un programme permettant de représenter un histogramme sur un écran (voir figure ci-dessous) à partir d'un tableau tab d'entiers. * * * * * ** * * ** +++++*++++ ** * ** * * * * L'histogramme doit être cadré en haut à gauche de l'écran. Chaque colonne i contient un nombre d'étoiles égal à la valeur de tab[i]. L'axe des abscisses est représenté comme une ligne de '+', mais si tab[i] vaut 0, votre programme doit afficher un '*'. L'histogramme représenté sur la figure correspond au tableau suivant : int[] tab = { -1, -3, 2, -2, 3, 0, 4, 2, -2, -1 };

On fait l'hypothèse que le tableau est compatible avec la taille de l'écran.

Pour réussir l'exercice, il faut savoir que System.out.print(String msg) affiche msg sans ajouter retour à la ligne, alors que System.out.println() affiche juste un retour à la ligne.

Commencez par écrire une boucle qui trouve les valeurs minimum et maximum du tableau. De façon à imposer que la ligne 0 soit affichée même lorsque le minimum et le maximum sont strictement supérieurs (resp. strictement inférieurs) à 0, vous devez pré-initialiser ces minimums et maximums à 0 avant de parcourir le tableau. À l'aide d'un indice line parcourez l'ensemble des valeurs se trouvant entre le maximum et le minimum dans le sens décroissant. À chaque tour de boucle, vous devez parcourir, avec l'indice col, le tableau et afficher le caractère adéquat.
  • Vous devez afficher une étoile dans trois cas :
    • si line est égal à 0 et si tab[col] est égal à 0,
    • si line est strictement supérieur à 0, si tab[col] est strictement supérieur à 0 et si tab[col] est plus grand que line,
    • si line est strictement inférieur à 0, si tab[col] est strictement inférieur à 0 et si tab[col] est plus petit que line.
  • Si vous n'affichez pas une étoile, vous devez afficher un caractère blanc lorsque line est différent de 0, et le caractère + lorsque line est égal à 0.
Le but de cet exercice est de concevoir un algorithme permettant de résoudre un sudoku. Un sudoku est défini par une grille de 9 colonnes sur 9 lignes. Chaque case doit contenir un nombre compris entre 1 et 9 inclus. Le but du jeu est de remplir la grille de façon à ce que chacun des chiffres compris entre 1 et 9 apparaisse au plus une fois dans (i) chaque ligne, (ii) chaque colonne et (iii) chacun des sous-carrés représentés sur la figure ci-dessous. Au début du jeu, une vingtaine de chiffres sont déjà placés dans la grille et le joueur doit trouver les chiffres se trouvant dans les autres cases. ---------------------------------- | . 1 . | 6 . 7 | . . 4 | | . 4 2 | . . . | . . . | | 8 7 . | 3 . . | 6 . . | ---------------------------------- | . 8 . | . 7 . | . 2 . | | . . . | 8 9 3 | . . . | | . 3 . | . 6 . | . 1 . | ---------------------------------- | . . 8 | . . 6 | . 4 5 | | . . . | . . . | 1 7 . | | 4 . . | 9 . 8 | . 6 . | ----------------------------------

La grille résolvant le sudoku représenté ci-dessus se trouve ci-dessous : ---------------------------------- | 9 1 3 | 6 2 7 | 5 8 4 | | 6 4 2 | 5 8 9 | 7 3 1 | | 8 7 5 | 3 4 1 | 6 9 2 | ---------------------------------- | 5 8 9 | 1 7 4 | 3 2 6 | | 2 6 1 | 8 9 3 | 4 5 7 | | 7 3 4 | 2 6 5 | 8 1 9 | ---------------------------------- | 1 2 8 | 7 3 6 | 9 4 5 | | 3 9 6 | 4 5 2 | 1 7 8 | | 4 5 7 | 9 1 8 | 2 6 3 | ---------------------------------- Pour commencer, créez un projet nommé sudoku avec une classe Sudoku contenant une méthode main. Une grille de sudoku est représentée par un tableau de 81 cases (9 lignes sur 9 colonnes). Si une case vaut 0, c'est qu'elle n'est pas encore initialisée, sinon, c'est qu'elle contient une valeur. Pour commencer, copiez-collez le code ci-dessous permettant de créer une grille. Ensuite, ajoutez une boucle permettant d'afficher la grille. Vous veillerez à afficher un point si la case contient 0. Vous devriez obtenir un affichage proche de celui utilisé pour la grille d'exemple, mais sans la représentation des carrés internes. int grid[] = { 0, 1, 0, 6, 0, 7, 0, 0, 4, 0, 4, 2, 0, 0, 0, 0, 0, 0, 8, 7, 0, 3, 0, 0, 6, 0, 0, 0, 8, 0, 0, 7, 0, 0, 2, 0, 0, 0, 0, 8, 9, 3, 0, 0, 0, 0, 3, 0, 0, 6, 0, 0, 1, 0, 0, 0, 8, 0, 0, 6, 0, 4, 5, 0, 0, 0, 0, 0, 0, 1, 7, 0, 4, 0, 0, 9, 0, 8, 0, 6, 0 }; Nous vous proposons de résoudre votre grille avec une méthode de retour arrière (backtracking en anglais). Cette méthode consiste à tenter des valeurs et, si elles ne permettent pas de résoudre la grille, de revenir en arrière pour essayer une nouvelle valeur. Comme nous aurons besoin de modifier la grille pour tenter des valeurs, il faut savoir quelles valeurs sont données initialement et quelles valeurs sont tentées. Vous devez donc définir un tableau de booléens nommée fixed et assigner à vrai la valeur d'une case si et seulement si la case contient initialement une valeur (c'est-à-dire si la case correspondante dans grid a une valeur différente de 0 initialement). Modifiez votre programme de façon à ce qu'il résolve le sudoku. Comme expliqué précédemment, le principe de l'algorithme est de parcourir la grille du début à la fin en tentant des valeurs. Dès qu'il est impossible de résoudre la grille avec une valeur précédemment rentrée, il faut revenir en arrière.

À haut niveau, il faut parcourir la grille avec une variable cur. Cette variable est initialisée à 0 et l'algorithme boucle tant que cur n'a pas atteint 81 (ce qui signifie que la grille a été résolue) et que cur n'est pas passé en dessous de 0 (ce qui signifie que la grille ne peut pas être résolue).

Pour un cur donné, l'algorithme doit tenter une nouvelle valeur sur la case grid[cur] (si cette dernière n'est pas donnée initialement) en incrémentant sa valeur. Si cette valeur atteint 10, c'est qu'une valeur tentée dans une case précédente ne permet pas de résoudre la grille. Il faut donc revenir en arrière. Sinon, si cette nouvelle valeur entre en conflit avec une valeur se trouvant dans la grille, il faut essayer la valeur suivante. Enfin, si la nouvelle valeur ne rentre pas en conflit, l'algorithme peut essayer de résoudre le reste de la grille en passant à la case suivante.

Techniquement, à chaque pas de boucle :
  • Si la case cur est initialement donnée, il faut avancer cur de 1,
  • Sinon, il faut incrémenter la case grid[cur]. Ensuite :
    • Si cette case vaut 10, c'est qu'une des valeurs tentées dans une case précédente ne permet pas de résoudre la grille. Il faut donc :
      • Remettre le contenu de la case 0,
      • Remonter cur jusqu'à la première précédente case qui n'est pas donnée initialement (pensez à utiliser fixed pour savoir si une case est donnée ou non initialement).
    • Sinon, l'algorithme doit vérifier que la nouvelle valeur de grid[cur] est valide, c'est-à-dire qu'elle ne duplique pas une valeur dans une colonne, une ligne ou un des 9 carrés. Si la valeur est valide, l'algorithme peut avancer cur de 1 pour tenter une valeur sur la case suivante. Si la valeur est invalide, il ne faut rien faire : lors du tour de boucle suivante, la valeur suivante de grid[cur] sera tentée.

Vérifier qu'une valeur est valide n'est pas évident. Nous vous conseillons d'effectuer une unique boucle avec une variable i allant de 0 à 9. Dans cette boucle, il faut vérifier que :
  • la valeur se trouvant sur la colonne de cur en iième ligne est différente de grid[cur],
  • la valeur se trouvant sur la ligne de cur en iième colonne est différente de grid[cur],
  • la iième case du carré interne est différente de grid[cur],

Nous vous conseillons d'utiliser 7 variables pour vérifier que la grille la dernière valeur tentée est valide :
  • line : indique sur quelle ligne se trouve cur : cur / 9,
  • col : indique sur quelle colonne se trouve cur : cur % 9,
  • sline : indique la première ligne du carré interne dans lequel se trouve cur : (line / 3) * 3,
  • scol : indique la première colonne du carré interne dans lequel se trouve cur : (col / 3) % 3,
  • icol : indice de la case à la iième ligne de la colonne de cur : line * 9 + i,
  • iline : indice de la case à la iième colonne de la ligne de cur : i * 9 + col,
  • isquare : indice de la iième case du carré interne de cur : 9 * (sline + (i / 3)) + scol + (i % 3)