CSC 3101 – Algorithmique et langage de programmation

Introduction

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 sûrement 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.

CI1 : Premiers pas et tableaux

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, ∼10mn)
Exercice 2 : obligatoire (facile, ∼30mn)
Exercice 3 ou 4 : obligatoire (facile, ∼30mn)
Exercice 5 : obligatoire (facile, ∼20mn)
Exercice 6 : obligatoire (moyen, ∼40mn)
Exercice 7 : obligatoire (moyen, ∼30mn)
Commencez par faire le DM avant d'attaquer les exercices d'entraînement !
Exercice 8 : entraînement (moyen, ∼30mn)
Exercice 9 : entraînement (ninja, ∼1h, pour les étudiants les plus aguerris qui veulent s'amuser)

Installation (∼10mn – facile – obligatoire)

Cet exercice a pour but de vous accompagner pour installer les logiciels de base nécessaires pour faire le module. Vous avez besoin de deux logiciels :

Un environnement de compilation et d'exécution Java, aussi appelé le jdk (Java Development Kit). Il faut choisir nécessairement une version de Java supérieure à la version 11.
Un environnement de développement. Vous pouvez choisir n'importe quel environnement de développement (Eclipse, IntelliJ, VSCode, CodeBlocks, Visual Studio, etc.) : il n'y a aucune adhérence particulière à un environnement particulier. Toutefois, l'équipe enseignante ayant l'habitude de Eclipse, nous vous guidons pas à pas pour utiliser cet environnement à cette séance.

Les machines de TP utilisent uniquement Eclipse.

Si vous avez un Linux (Ubuntu ou Debian)

La plupart d'entre vous devriez avoir un Linux récent avec Ubuntu ou Debian. Pour installer Java, il vous suffit de saisir la commande suivante dans un terminal :

$ sudo apt install default-jdk

Vous pouvez vérifier que Java est bien installé en saisissant la commande java -version qui devrait vous donner la version installée.

Si par hasard cette commande échoue, vous pouvez lister les versions que vous pouvez installer avec

apt search openjdk

Il vous suffit alors de choisir une version quelconque du jdk (suffixe -jdk) supérieure à 11, par exemple : sudo apt install openjdk-11-jdk.

Pour installer Eclipse, la meilleure méthode est de suivre la procédure décrite ici. Il faut installer la version Eclipse IDE for Java Developers. Si par hasard vous bloquez quelque part et que vous avez une Ubuntu, vous pouvez aussi saisir la commande suivante :

sudo apt-get install -y snapd && sudo snap install --classic eclipse

Si vous avez un MacOS

Avec MacOS, il vous suffit d'installer Java à partir d'ici. Il faut sélectionner macOS. Ensuite, si vous avez un Apple M1, il faut sélectionner le dmg installer pour processeur Arm, et si vous avez un Apple Intel, il faut sélectionner le dmg installer pour processeur x64. Une fois Java installé, si vous lancez la commande java -version dans un terminal, vous devriez voir la version que vous avez installée.

Pour Eclipse, il vous suffit de le télécharger à partir d'ici. Pour Eclipse, il n'existe actuellement que la version x64. Si vous avez un Apple M1, la procédure d'installation va vous proposer d'installer Rosetta 2 qui permet d'émuler un processeur Intel sur votre ARM, ce qu'il faut autoriser. Pour Eclipse, il faut installer la version Eclipse IDE for Java Developers.

Vous pouvez manuellement installer Roseta 2 avec la commande suivante : softwareupdate --install-rosetta dans un terminal.

Si par hasard vous avez un MacOS assez ancien (plusieurs années) et que la dernière version de Java ne fonctionne pas, il faut installer une ancienne version. Vous pouvez alors vous rabattre sur une version 11 de Java que vous trouverez ici, ou même une version 8 encore plus ancienne que vous trouverez ici.

Si vous avez un Windows

Si vous avez un Linux et un Windows, nous vous conseillons vivement d'utiliser Linux, car l'équipe enseignante étant beaucoup moins à l'aise avec Windows ne pourra que difficilement vous dépanner. Toutefois, si vous n'arrivez pas à avoir un Linux fonctionnel avec le réseau et les connexions aux salles de cours en même temps que Java/Eclipse, vous pouvez vous rabattre vers la procédure qui se trouve à cette adresse.

Cette procédure est aussi beaucoup plus complexe car Windows est, contrairement à l'intuition, un système plus difficile à administrer que Linux ou MacOS.

Si vous avez un autre système

Si vous avez du mal avec votre système, n'hésitez pas à demander à vos professeurs qui pourront essayer de vous aider s'ils connaissent ce système (archlinux, gentoo, OpenBSD, etc.).

Mise en route (∼30mn – facile – obligatoire)

Le but de cet exercice est de vous faire utiliser explicitement toute la chaîne de conception, compilation et exécution de Java. Si jamais vous utilisez Windows ou que vous n'avez pas Java installé sur votre machine, vous pouvez utiliser les machines de l'école pour cet exercice. Par la suite, nous utiliserons un IDE qui gèrera pour nous 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 avec javac puis exécutez-le avec java.

HelloWorld.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
$

HelloWorld.java

Prise en main de eclipse (∼30mn – facile – obligatoire/recommandé)

Cet exercice ou le suivant est obligatoire. Toutefois, pour avoir le même environnement de travail que les salles de TP, nous recommandons de quand même le faire (hors présentiel).

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 a aucune dépendance par rapport à un environnement de développement particulier (sauf dans cet exercice).

Lancez eclipse. Si vous êtes sur votre propre machine ou sur les machines de TP, il suffit de saisir eclipse & dans le terminal. Sur les machines de TP, si vous lancez Eclipse depuis les menus, vous devez utiliser eclipse-java.

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).

Une fois Eclipse lancé, il est possible, sur d'ancienne version, qu'il faille sélectionner 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 désormais 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). Pour les utilisateurs d'un environnement Java récent, vous aurez aussi un fichier nommé module-info.java. Cette notion de module vous sera brièvement présentée au dernier TP. Pour le moment, laissez ce fichier qui est nécessaire au bon fonctionnement des programmes Java sans y toucher.

Vous pouvez maintenant créer votre première classe. Pour cela, sélectionnez le menu File->New->Class.

Ne cliquer sur Finish qu'une fois que vous avez intégralement lu la question !

Dans la fenêtre qui vient de s'ouvrir, donnez le nom Bonjour à votre classe dans le champ Name. Ensuite, il faut s'assurer que votre fichier source va être bien rangé. Java range les classes dans des packages. Nous reviendrons sur cette notion en CI4, mais à haut niveau, les packages sont des sortes de répertoires dans lesquelles on range les fichiers sources d'un programme. Il faut savoir que tout fichier source doit être rangé dans un package, et qu'il ne faut pas utiliser le package racine (appelé default). Assurez-vous donc que dans le champ Package (un peu au-dessus du champ Name qui donne un nom à votre classe), vous avez bien un nom. Si c'est déjà le cas, gardez le nom qu'Eclipse a choisi pour vous. Si ce n'est pas le cas, donnez le nom bonjour à votre package (vous pouvez choisir n'importe quel nom).

Comme vous aurez besoin d'ajouter un main dans notre classe, vous pouvez demander à Eclipse de générer pour vous le code public static void main(String[] args) { ... } qui est bien fastidieux à écrire. Pour cela, il vous suffit, en bas de la fenêtre, de cliquer sur public static void main(Strings[] args) à la question Which method stubs would you like to create. Laissez systématiquement le Inherited abstract methods. Vous comprendrez l'intérêt de cette fonctionnalité au CI6.

Vous pouvez maintenant cliquer sur Finish pour générer votre première classe.

Comme nous ne vous le rappellerons plus dans la suite, à chaque fois que vous créez une classe, pensez à vous assurer vous qu'elle soit bien rangée dans un package : si vous placez une classe dans le package par défaut, vous aurez des erreurs.

À présent que la classe est générée, dans la vue centrale de l'écran (l'éditeur de code), vous devriez voir apparaître le contenu du fichier Bonjour 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. Comme expliqué plus haut, la notion de package vous sera expliquée en CI4 et il faut laisser cette ligne. La notion de public vous sera aussi présentée en CI5, vous pouvez laisser la déclaration telle qu'elle est.

Nous allons maintenant écrire la méthode main de notre programme. Dans un premier temps, votre programme doit simplement afficher Bonjour, monde !!!.

Si vous tapez Control + (barre d'espace) sur un symbole en cours d'écriture, Eclipse vous propose les différentes complétions possibles. Par exemple, si vous saisissez System.out.pr et tapez Control + Espace, Eclipse va vous proposer de compléter avec println. Usez et abusez de cette possibilité dès que vous avez besoin d'écrire un symbole qu'Eclipse a déjà rencontré (y compris des noms de variables locales), vous gagnerez beaucoup de temps !

Nous allons désormais tester notre programme, c'est-à-dire que nous allons le compiler en bytecode puis l'exécuter. 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 à présent 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.

Bonjour.java

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 revenir dans l'onglet (x)=Arguments du menu Run->Run Configurations (voir question précédente) et de remplacer le Que la force soit avec toi par ${string_prompt}. Vérifiez que vous arrivez bien à saisir des paramètres à chaque fois que vous lancez votre application avec cette procédure.

Prise en main d'IntelliJ (∼30mn – facile – obligatoire/facultatif)

Cet exercice est obligatoire si vous voulez utiliser IntelliJ.

Ce cours s'adresse à ceux ayant installé IntelliJ. Si vous voulez l'installer, suivez le tutoriel sur le site officiel qui vous fait installer la Toolbox App. Ensuite, vous pouvez installer soit la version gratuite (Community Edition), soit la version payante qui est gratuite pour les étudiants (il faut s'inscrire ici).

Pour lancer IntelliJ, vous pouvez utiliser idea &. Si cette commande ne marche pas (votre variable PATH est peut-être mal configurée) vous pouvez le chercher dans la liste des applications ou à travers la Toolbox.

Vous pouvez maintenant créer un premier projet Java. Si c'est la première fois que vous ouvrez IntelliJ, vous devriez trouver un bouton pour créer un nouveau projet. Sinon, allez dans le menu File->New->Project. Donnez le nom bonjour à votre projet. Définissez le dossier où votre projet sera enregistré. Le langage est Java et le Build System est IntelliJ. Enfin, il y a une dernière option à remplir : la JDK. Si Java est déjà installé sur votre machine, un numéro de version devrait apparaître. Sinon, cliquez sur la case de sélection puis Download JDK. Sélectionnez la version 20, et ensuite cliquez sur Download. Une fois le téléchargement terminé, revenez sur la fenêtre de création de projet. Un numéro de JDK devrait apparaitre. Sinon, sélectionnez le manuellement. Finalement, cliquez sur Create.

À gauche de votre écran, vous pouvez voir votre projet avec la liste des fichiers qu'il contient. En particulier, vous trouverez un répertoire src dans lequel seront stockés les fichiers sources Java de votre programme, un dossier .idea qui contient les configurations d'IntelliJ, 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->Java Class ou click droit sur le dossier src et New->Java Class.

Dans la fenêtre qui vient de s'ouvrir, donnez le nom Bonjour à votre classe dans le champ Name.

Comme vous aurez besoin d'ajouter un main dans notre classe, vous pouvez demander à IntelliJ de générer pour vous le code public static void main(String[] args) { ... } qui est bien fastidieux à écrire. Pour cela, il vous suffit de taper main dans la classe et IntelliJ vous proposera de compléter le code pour vous !

À présent que la classe est générée, dans la vue centrale de l'écran (l'éditeur de code), vous devriez voir apparaître le contenu du fichier Bonjour

Nous allons maintenant écrire la méthode main de notre programme. Dans un premier temps, votre programme doit simplement afficher Bonjour, monde !!!.

Quand vous tapez du code sur IntelliJ, il vous proposera de compléter ce que vous écrivez. Vous pouvez rapidement choisir l'option qui vous convient dans le menu déroulant. Par exemple, si vous saisissez System.out.pr, vous devriez voir toutes les possibilités de complétion avec les types associés. IntelliJ possède aussi de nombreux raccourcis. Par exemple, si vous tapez sout, IntelliJ comprend que vous voulez écrire System.out.println qui est beaucoup plus long. Usez et abusez de cette possibilité dès que vous avez besoin d'écrire un symbole qu'IntelliJ a déjà rencontré (y compris des noms de variables locales), vous gagnerez beaucoup de temps !

Nous allons désormais tester notre programme, c'est-à-dire que nous allons le compiler en bytecode puis l'exécuter. Pour tester votre programme, vous devriez remarquer un petit bouton vert avec le signe lecture en haut de votre fenêtre. Un bouton vert similaire s'affiche également à gauche de la fonction main et à gauche du nom de la classe si cette classe contient une fonction main

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 à présent pris en main IntelliJ !!!

Comme dans l'exercice précédent, nous souhaitons maintenant afficher les paramètres du programme. Modifiez votre programme en conséquence.

Pour spécifier des paramètres, vous devez aller dans le menu Run->Edit Configurations. Dans Program Arguments, vous pouvez spécifier des 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.

Bonjour.java

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 revenir dans Run->Edit Configurations (voir question précédente) et de remplacer le Que la force soit avec toi par $Prompt$. Vérifiez que vous arrivez bien à saisir des paramètres à chaque fois que vous lancez votre application avec cette procédure.

Les types de base (∼20mn – facile – obligatoire)

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 ! IntelliJ a des fonctionnalités similaires (voir plus haut).

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 converti 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 converti 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'.

Calcul du plus grand commun diviseur (∼40mn – moyen – obligatoire)

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 !

Pgcd.java

Estimez la complexité de cet algorithme de PGCD dans le pire des cas en fonction de n = p + q.

Pour répondre à cette question, nous devons estimer la complexité des étapes de l'algorithme. Ici, tout est en

𝒪 (1)

. Ensuite, il nous faut borner le nombre maximum de passages dans la boucle while en fonction de n. Étant donné que p et q décroissent strictement à chaque tour de boucle, le nombre maximum d'itérations est n. En particulier, ce nombre d'itérations est atteint pour p=n-1 et q=1.
La complexité finale est donc

𝒪 (n)

Il est possible d'implémenter un algorithme de PGCD plus efficace en remarquant que si p ≥ q, pgcd(p, q) = pgcd(q, p mod q). Implémenter cette variation du PGCD.

Pgcd2.java

(Difficile) Estimez la complexité de ce nouvel algorithme dans le pire des cas en fonction de n = p + q. Pour cela, nous montrerons la propriété suivante : Soit

(p_{i}, q_{i})

tel que

p_{i} \geq q_{i}

et i le nombre d'itérations dans la boucle (si vous n'avez pas utilisé une structure récursive) avec ces deux entrées. Alors, nous avons

q_{i} \geq F i b_{i}

avec Fib la suite de Fibonacci. On rappelle que

F i b_{i} \underset{i \to + \infty}{\sim} ϕ^{i}

. Vous pouvez commencer par estimer la complexité de

p g c d (F i b_{i + 1}, F i b_{i})

en fonction de i, puis la traduire en une complexité en

F i b_{i}

Pour calculer la complexité de

p g c d (F i b_{i + 1}, F i b_{i})

, nous calculons

F i b_{i + 1} \equiv F i b_{i} + F i b_{i - 1} \equiv F i b_{i - 1} [F i b_{i}]

. Nous observons qu'à chaque étape, nous descendons d'un élément dans la suite de Fibonacci. On a donc une complexité linéaire en i. Comme

F i b_{i} \underset{i \to + \infty}{\sim} ϕ^{i}

on obtient une complixité en

𝒪 (l o g (F i b_{i}))

quand i tend vers l'infini.
Ensuite, on peut prouver la propriété par induction.

Si i = 0, alors $b_1=0 \ge Fib_0$
Si i = 1, alors $b_2 \ge 1 = Fib_1$
Pour k ≥ 1 itérations, on a l'enchainement $(a_{k+1}, b_{k+1}) \rightarrow (a_{k}, b_{k}) \rightarrow (a_{k-1}, b_{k-1})$ . Par conséquent, $a_k = b_{k+1}, a_{k-1} = b_k, b_{k-1} \equiv a_k [b_k]$ . On a donc $a_k = q*b_k+b_{k-1}, q \ge 1$ et $b_{k+1} \ge b_k+b_{k-1} \ge Fib_{k-1} + Fib_{k-2} = Fib_{k}$ .

À partir de là, on a informellement pour i très grand :

b_i \ge \phi^i

et donc

i \le \frac{log(b_i)}{log(\phi)}

. On en déduit que la complexité est en

\mathcal{O}(log(n))

Notons que le pire des cas se produit quand les entrées sont deux nombres de Fibonacci consécutifs.

Ma première calculette (∼30mn – moyen – obligatoire)

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 parce qu'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 !

Calculette.java

Histogramme (∼30mn – moyen – entraînement)

É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(char c) affiche le caractère c 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.

Histogram.java

Quelle est la complexité de l'algorithme en fonction du tableau utilisé ? Réfléchissez à quelles sont les propriétés du tableau qui doivent entrer en jeu.

Nous allons avoir besoin de la taille n du tableau, ainsi que de la valeur maximale M et la valeur minimale N.
Trouver le maximum et le minimum est linéaire en la taille du tableau. Pour afficher l'histogramme, nous devons faire une boucle entre le min et le max. Dans cette boucle, nous avons une autre boucle sur la taille du tableau. La complexité finale est donc

\mathcal{O}((M - m) * n)

Sudoku (∼1h30 – ninja – entraînement)

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é 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é auparavant, 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 i^ième ligne est différente de grid[cur],
la valeur se trouvant sur la ligne de cur en i^ième colonne est différente de grid[cur],
la i^iè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 i^ième ligne de la colonne de cur : line * 9 + i,
iline : indice de la case à la i^ième colonne de la ligne de cur : i * 9 + col,
isquare : indice de la i^ième case du carré interne de cur : 9 * (sline + (i / 3)) + scol + (i % 3).

Sudoku.java