IFT1015, Hiver 2008

Professeur: Pascal Vincent

Examen Final

Lundi 21 avril 2008

Durée: 2h45

Documentation papier permise

Prénom:

Nom:


Code permanent:


Veuillez répondre aux questions dans les 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.
Si vous voulez, vous pouvez abréger
System.out.println  en s.o.p

1 Chaîne miroir et palindrome

a) Écrivez une fonction static nommée miroir qui prend en paramètre une chaîne de caractère (String) et qui retourne la String miroir correspondante, c'est à dire la string de départ écrite à l'envers. Ainsi le miroir de "Bonjour" serait "ruojnoB". On vous demande de ne pas utiliser de for pour écrire cette fonction, mais plutôt un while.


















b) Écrivez une fonction static palindrome qui prend en paramètre une chaîne de caractères (String) et qui retourne un boolean qui vaudra true si et seulement si la chaîne en question est un palindrome (et false sinon). Un palindrome est une chaîne qui est égale à son miroir. Exemples de palindromes: "kayak", "radar", "laval", "robert trebor". Vous devriez bien-entendu utiliser votre fonction miroir, et palindrome peut alors s'écrire en une ligne...















c) Écrivez la méthode main d'un programme qui affichera tous les paramètres passés sur la ligne de commande (les args) sauf ceux qui sont des palindromes (vous devez évidemment faire appel à votre fonction palindrome pour cela).


























2 Objets et tableaux

Pour cet exercice, vous devez écrire le contenu de 2 fichiers: Imagette.java et TestImagettes.java

a) On demande de définir une classe appelée Imagette qui servira à représenter une petite "image" stockée sous la forme d'un tableau à 2 dimensions de char. Chaque imagette a aussi un nom.

La classe Imagette devra donc avoir les propriétés private suivantes:
Elle devra aussi avoir les méthodes suivantes:
Ainsi une imagette créée par la fonction creeImagetteSimple avec une hauteur de 2, une largeur de 4, et le nom "Mon imagette" devra s'afficher ainsi (notez qu'elle est "remplie" de M car M est le premier caractère de la chaîne "Mon imagette")
Mon imagette
MMMM
MMMM












































































b) Écrivez un programme TestImagettes.java comportant une fonction main. Ce programme devra (dans sa méthode main):
Le programme devrait donc afficher:
 
im1
###
###
###

im2
iiii
iiii
iiii
iiii













3 Passage de paramètres et copies (par valeur ou par référence...)

Dans le programme suivant, écrivez à côté de chaque System.out.println du main, ce qui s'affichera à l'écran.
public class Obj
{
public int y;

public static int f1(int x)
{ return x+1; }

public static void f2(int x)
{ x = x+1; }


public static void f3(int[] t)
{ t[0] = t[0]+1; }

public static void f4(int[] t)
{
int x = t[0];
t = new int[5];
t[0] = x+1;
}

public static void f5(Obj e)
{
e = new Obj();
e.y = 30;
}

public static void f6(Obj e)
{
e.y = 40;
}

public static void main(String[] args)
{
int[] t = new int[5];

int x = 1;
f1(x);
System.out.println(x);
x = 1;
System.out.println(f1(x));
x = f1(x);
System.out.println(x);

x = 10;
f2(x);
System.out.println(x);

t[0] = 20;
f3(t);
System.out.println(t[0]);

t[0] = 7;
f4(t);
System.out.println(t[0]);

Obj a = new Obj();
a.y = 100;
f5(a);
System.out.println(a.y);

f6(a);
System.out.println(a.y);

a.y = 300;
Obj b = a;
b.y = a.y*2;
System.out.println(a.y);
}
}

4 Listes chaînées

Soit une liste simplement chaînée définie par des noeuds du type suivant:
public class Noeud
{
double valeur;
Noeud suivant;
}
On suppose qu'on représente une liste chaînée simplement par une variable faisant référence à son premier noeud. Pour cet exercice vous pouvez utiliser des boucles.

a) Écrivez une fonction static appelée getNoeud qui prend en paramètre une liste l, et une position entière i et qui retourne une référence (de type Noeud) au ième noeud de la liste (ou null si il n'y a pas de ième élément). Les positions dans la liste sont numérotées à partir de 0 (tout comme pour les tableaux). Donc i=0 signifie le premier noeud.























b) Écrivez une fonction static appelée insereElement qui prend trois paramètres: une liste l, une position entière i, et une valeur réelle x. Cette fonction insèrera dans la liste l, juste après le ième noeud, un noeud portant la valeur x. Vous pouvez bien entendu vous servir de la fonction getNoeud...

























5 Récursivité


POUR CET EXERCICE VOUS N'AVEZ PAS LE DROIT D'UTILISER DE BOUCLES, NI DE DÉFINIR D'AUTRES FONCTIONS QUE CELLES DEMANDEES.



a) Écrivez une fonction palindrome récursive avec la signature suivante:
public static boolean palindrome(String s, int debut, int fin)

Cette fonction devra retourner true si et seulement si la sous-chaîne de caractère de s débutant au caractère à la position debut (inclue) et se terminant à la position fin (exclue) est un palindrome (voir la question b de l'exercice 1 pour la définition d'un palindrome). Ainsi palindrome("aKAYAKbcd",1,6) devrait retourner true.
Vous n'avez pas le droit d'utiliser aucune boucle, ni aucune autre fonction définie par vous (en particulier pas celles de l'exercice 1!), mais il vous est suggéré d'utiliser les méthodes charAt et substring. On rappelle l'utilisation de substring(int debut, int end) avec l'ex suivant: si s="aKAYAKbcd", alors s.substring(1,6) retournera la sous-chaîne "KAYAK". Note: vous pouvez supposer qu'au moment de l'appel debut et fin définissent un intervalle valide pour substring (pas besoin de vérification).



public static boolean palindrome(String s, int debut, int fin)
{


























}

b) On considère à présent des listes simplement chaînées de même type qu'à l'exercce précédent, représentées par une référence à leur premier Noeud.
Écrivez une fonction récursive somme qui retournera la somme des valeurs des éléments de la liste.
public static double somme(Noeud l)
{





















}
c) Écrivez une fonction récursive ordreCroissant qui retournera true si et seulement si les éléments de la liste sont en ordre croissant (et false sinon). Remarque: on considérera qu'une liste ne contenant aucun ou un seul élément est "en ordre croissant".