IFT1015, Hiver 2007
Professeur: Pascal Vincent
Examen Final
Lundi 23 avril 2007
Durée: 2h45
Prénom:
Nom:
Code premanent:
Veuillez répondre aux questions dans lez zones de blanc laissées à cet effet.
Lorsque l'énoncé vous
demande d'écrire un programme, vous devez écrire un
programme complet compilable (qui comporte une déclaration de
classe et une méthode main).
Lorsque l'énoncé vous demande d'écrire une
fonction ou une méthode, contentez-vous d'écrire
cette fonction ou méthode seulement.
1) Programme FizzBuzz (20 pts)
Écrivez ci-dessous un programme FizzBuzz.java comprenant une fonction (méthode statique) fizzbuzz et une fonction main.
- La fonction fizzbuzz prend trois paramètres entiers nommés fizz, buzz, et max, et affiche, séparés par un espace, les nombres de 1 à max inclus, sauf si le nombre est multiple du nombre fizz ou du nombre buzz. Si le nombre est multiple de fizz seulement il affiche le mot Fizz à la place du nombre. Si il est multiple de buzz seulement il affiche le mot Buzz à la place du nombre. Mais si il est multiple de fizz ET de buzz il affiche le mot FIZZBUZZ à la place du nombre.
- Écrivez la fonction main qui permettra d'utiliser le programme pour faire afficher la séquence fizzbuzz correspondant aux valeurs de fizz buzz et max passées en arguments sur la ligne de commande lors de l'appel du programme.
Ex. d'exécution du programme:
java FizzBuzz 3 5 20
1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FIZZBUZZ 16 17 Fizz 19 Buzz
2) Programmation objet (30 pts)
a) Classe Rectangle
Toutes les méthodes qu'on demande d'écrire dans cette classe sont des méthodes NON static.
- Écrivez une classe Rectangle comportant deux propriétés privées de type double: largeur et hauteur.
- Écrivez un constructeur prenant en paramètre la largeur et la hauteur désirée.
- Écrivez une méthode litLargeur qui retourne la largeur et une méthode et litHauteur qui retourne
la hauteur (ces méthodes ne lisent rien au clavier, elles
retournent simplement la valeur de le porpriété de
l'objet).
- Écrivez une méthode changeLargeur qui permet de changer la largeur et une méthode changeHauteur qui permet de changer la hauteur.
- Écrivez une méthode aire qui calcule et retourne l'aire (surface) du rectangle sans rien afficher.
- Écrivez une méthode afficheAire qui fait appel à la méthode aire et affiche une ligne de la forme ex:
Ce rectangle de lageur 2 et de hauteur 3 a une aire de 6.
- Écrivez une méthode transpose
qui échange la largeur et la hauteur (ainsi un rectangle qui
avait une largeur de 2 et une hauteur de 3, après l'appel
à cette méthode aura une largeur de 3 et une hauteur de
2).
- Écrivez une méthode duplique qui retourne un nouveau rectangle (une copie) qui a les mêmes propriétés que l'objet rectangle actuel.
b) Classe RectangleUtil
Écrivez une classe RectangleUtil comportant deux fonctions (méthodes static):
- multiplieLargeur qui
change la largeur d'un objet rectangle en la multipliant par une valeur
passée en paramètre (cette fonction ne retourne rien).
- transpose qui permet d'échanger la largeur et la hauteur d'un objet rectangle (cette fonction ne retourne rien).
c) Programme EssaiRectangle.java
Écrivez un programme nommé EssaiRectangle.java avec une
fonction main qui effectue les opérations suivantes:
- Crée un rectangle nommé r1 de largeur 2 et de hauteur 3.
- Crée un rectangle nommé r2 de largeur 2 et de hauteur 5.
- Crée un troisième rectangle appelé r3 qui est une copie de r2 à l'aide de la méthode duplique.
- Définit un rectangle r4 à l'aide de l'instruction suivante: Rectangle r4 = r1;
- Change la hauteur de r1 en la faisant passer à 2.
- Change la largeur de r2 en la faisant passer à 10.
- Affiche les aires des rectangles r1, r2, r3, r4 dans cet ordre avec la méthode afficheAire.
- transpose r1 à l'aide de la méthode non statique transpose.
- transpose r2 à l'aide de la fonction (méthode statique) transpose.
- multiplie la largeur de r3 par 10 à l'aide de la fonction multiplieLargeur.
d) Qu'affiche le programme EssaiRectangle?
3) Recherche dichotomique récursive dans un tableau trié (20 pts)
Écrivez une fonction récursive de recherche dichotomique
qui trouve efficacement la position d'un élément que l'on
recherche dans un tableau déjà trié.
La fonction a la signature suivante:
public static int recherche(int e, int[] t, int debut, int fin)
Ses arguments sont: l'élément recherché e, le tableau t qu'on suppose trié, les positions dans le tableau entre lesquelles on recherche (inclusivement).
La fonction doit retourner la position dans le tableau de
l'élément si on l'a trouvé, ou -1 si
l'élément n'a pas été trouvé entre
les positions debut et fin inclues.
Ex: pour un tableau t = { 1, 5, 10, 37, 512, 522, 605 }
recherche(10, t, 0, 6) retournera 2
recherche(10, t, 2, 5) retournera 2
recherche(10, t, 3, 6) retournera -1
La fonction doit
être récursive et ne doit donc pas utiliser de
boucle! (inutile d'écrire une fonction comporant une boucle,
ça vaudra 0 pour l'exercice).
4) Listes chaînées (20 pts)
On suppose qu'on a défini dans un fichier Noeud.java une classe Noeud représentant un noeud d'une liste simplement chaînée de String.
public class Noeud
{
public String e;
public Noeud next;
public Noeud(String e)
{
this.e = e;
this.next = null;
}
}
On donne aussi le programme suivant dans TestListe.java:
class TestListe
{
public static void main(String[] args)
{
Noeud n1 = new Noeud("A");
Noeud n2 = new Noeud("B");
n1.next = n2;
Noeud n3 = new Noeud("C");
n2.next = n3;
Noeud n4 = new Noeud("D");
n4.next = n3;
n2.next = n4;
n2 = n1;
n2.next = n2.next.next;
n4.next.next = n2;
}
}
a) Dessinez ci-dessous la structure chaînée résultante à la fin de l'exécution du main (avant la sortie du main).
Indiquez les variables n1, n2, n3, n4, et les noeuds
créés contenant la valeur de leur élément e
("A","B","C","D"). Représentez les pointeurs
(références) par des flêches.
Votre dessin doit être clair et sans rature: il est vivement conseillé de faire un brouillon où vous pourrez suivre pas à pas l'exécution du main et l'évolution des pointeurs. Ne soyez pas surpris si la liste résultante n'est pas tout à fait ordinaire...
b) Affichage récursif des éléments d'une liste simplement chaînée dans l'ordre inverse
On demande d'écrire une fonction (méthode statique) afficheListeInverse qui prend un paramètre un pointeur vers le premier Noeud
d'une liste simplement chaînée et affiche la valeur
des éléments de la liste dans l'ordre inverse, c.a.d. du
dernier au premier. Attention, il s'agit d'une liste simplement
chaînée, donc on n'a pas de pointeur vers
l'élément précédent! Écrivez la fonction de manière récursive (n'utilisez pas de boucle!). Indications: le dernier noeud a son attribut next qui vaut null; la fonction est très simple (il est possible de l'écrire en 3 lignes...).
public static void afficheListeInverse(Noeud n)
{
}
c) Que se passe-t-il si on appelle cette fonction sur n1 en
rajoutant l'instruction suivante à la fin de la fonction main du
programme TestListe?
afficheListeInverse(n1);
5) Passage de paramètres (10 pts)
On suppose qu'on a une fichier Cercle.java qui définit une classe
Cercle très simple:
public class Cercle
{
public double rayon;
public Cercle(double r)
{ rayon = r; }
}
On a par ailleurs un programme MonProgramme.java qui contient le code suivant:
class MonProgramme
{
public static void f(int a, int[] b, Cercle c)
{
a = b[0]+1;
b[0] = b[0]*2;
c.rayon = a;
System.out.println("f: " + a + " " + b[0] + " " + c.rayon);
}
public static void changeCercle(Cercle c)
{
c.rayon = 5;
c = new Cercle(10);
c.rayon = 20;
if(c!=null)
c.rayon = c.rayon*2;
System.out.println("changeCercle: "+c.rayon);
}
public static void main(String args[])
{
Cercle c = new Cercle(3);
System.out.println("main 1: "+c.rayon);
changeCercle(c);
System.out.println("main 2: "+c.rayon);
Cercle d = new Cercle(4);
int[] a = new int[10];
a[0] = 10;
int b = 20;
System.out.println("main 3: " + b + " " + a[0] + " " + d.rayon);
f(b, a, d);
System.out.println("main 4: " + b + " " + a[0] + " " + d.rayon);
}
}
Écrivez ci-dessous ce qui selon vous s'affiche à l'écran quand on lance le programme avec la commande
java MonProgramme
Indication: pensez précisément à ce qui se passe dans la mémoire de l'ordinateur.