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








































b) Classe RectangleUtil

Écrivez une classe RectangleUtil comportant deux fonctions (méthodes static):





















c) Programme EssaiRectangle.java

Écrivez un programme nommé EssaiRectangle.java avec une fonction main qui effectue les opérations suivantes:




































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.