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:
- un tableau à 2 dimensions de char appelé img
- une variable appelée nom de type String
Elle devra aussi avoir les méthodes suivantes:
- un constructeur qui prend en argument la hauteur (int) et la largeur
(int) d'une imagette ainsi que son nom (String), et qui initialise
les propriétés de l'objet en conséquence. En
particulier elle devra initialiser le tableau img à la hauteur
et largeur demandée et le remplir de catactères espace
blanc.
- une méthode non static nommée hauteur qui retourne la hauteur de l'imagette
- une méthode non static nommée largeur qui retourne la largeur de l'imagette
- une méthode non static nommée remplit qui prend en argument un char et ne retourne rien, mais remplit img avec le caractère passé en argument.
- une méthode non static nommée affiche qui imprime le nom de l'imagette à l'écran suivie de l'image.
- une fonction static appelée creeImagetteSimple prenant 3 arguments: une hauteur et une largeur ainsi qu'un nom
et qui retourne une Imagette. La fonction devra créer une imagette avec
les propriétés spécifiées en lui donnant le nom indiqué, et la remplir
avec le premier caractère du nom, avant de la retourner.
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):
- Sans faire appel à la fonction creeImagettesimple (mais en utilisant le constructeur): créer une imagette im1 de taille 3x3 avec le nom "im1" et la remplir de caractere #.
- A l'aide de la fonction creeImagetteSimple : créer une imagette im2 de taille 4x4 avec le nom "im2".
- Afficher ces deux imagettes.
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".