Chaines PDF
Chaines PDF
Chaines PDF
Fabrice Rossi
8 janvier 2002
1 Analyse de programmes
1.1 Mémoire
Exercice 1.1 :
On considère le programme suivant :
Truc
1 public class Truc {
2 public static void a(String s) {
3 s+="DSQKJ";
4 }
5 public static String b(String s) {
6 s+="GHIJK";
7 return s;
8 }
9 public static void c(StringBuffer sb) {
10 sb.append("KNTOP");
11 }
12 public static StringBuffer d(StringBuffer sb) {
13 new StringBuffer("ERTBG");
sb=new
14 return sb;
15 }
16 public static void main(String[] args) {
17 String s="JNHGV";
18 a(s);
19 System.out.println(s);
20 s="GHIJK";
21 b(s);
22 System.out.println(s);
23 new StringBuffer("ABCDE");
StringBuffer sb=new
24 c(sb);
25 System.out.println(sb);
26 new StringBuffer("ERTBG");
sb=new
27 d(sb);
28 System.out.println(sb);
29 }
30 }
1.1 Mémoire
1. Dessiner l’état complet de la mémoire (en supposant que l’éboueur a fait son travail) juste
après l’exécution de la ligne 10 (et avant le retour dans la méthode main).
2. Donner l’affichage produit par le programme.
Exercice 1.2 :
Indiquer l’affichage produit par le programme suivant :
Analyse
1 public class Analyse {
2 public static void modif1(int int x) {
3 x+=2;
4 }
5 public static void modif2(int int x) {
6 x=5;
7 }
8 //
9 public static String ajoute1(String s) {
10 s+=" toto";
11 return s;
12 }
13 public static String ajoute2(String s) {
14 s="toto";
15 return "titi";
16 }
17 //
18 public static StringBuffer concat1(StringBuffer sb) {
19 sb.append(" +++");
20 return sb;
21 }
22 public static StringBuffer concat2(StringBuffer sb) {
23 sb= new StringBuffer("+++");
24 return sb;
25 }
26 public static void main(String[] args) {
27 int x=24;
28 modif1(x);
29 System.out.println(x);
30 x=24;
31 modif2(x);
32 System.out.println(x);
33 //
34 String s="titi";
35 System.out.println(ajoute1(s));
36 System.out.println(s);
37 s="titi";
38 System.out.println(ajoute2(s));
39 System.out.println(s);
40 //
41 StringBuffer sb=newnew StringBuffer("---");
42 System.out.println(concat1(sb));
43 System.out.println(sb);
44 new StringBuffer("---");
sb=new
45 System.out.println(concat2(sb));
46 System.out.println(sb);
47 }
48 }
1.2 Manipulations
Exercice 1.3 :
On considère la méthode suivante :
1 public static String e(String a) {
2 String r="";
3 for(int i=0;i<a.length();i++)
4 r=a.charAt(a.length()-i)+r;
5 return r;
6 }
1. Cette méthode :
(a) renvoie le miroir de la chaı̂ne paramètre (c’est-à-dire la chaı̂ne constituée des mêmes
caractères que la chaı̂ne paramètre mais dans le sens inverse)
(b) renvoie une chaı̂ne identique à la chaı̂ne paramètre
(c) plante quand la chaı̂ne paramètre contient au moins un caractère
(d) plante toujours
2. On remplace la ligne 3 par la ligne for(int i=1 ;i<=a.length() ;i++). La nouvelle
méthode :
(a) renvoie le miroir de la chaı̂ne paramètre (c’est-à-dire la chaı̂ne constituée des mêmes
caractères que la chaı̂ne paramètre mais dans le sens inverse)
(b) renvoie une chaı̂ne identique à la chaı̂ne paramètre
(c) plante quand la chaı̂ne paramètre contient au moins un caractère
(d) plante toujours
3. On remplace la ligne 3 par la ligne for(int i=a.length() ;i>0 ;i--). La nouvelle mé-
thode :
(a) renvoie le miroir de la chaı̂ne paramètre (c’est-à-dire la chaı̂ne constituée des mêmes
caractères que la chaı̂ne paramètre mais dans le sens inverse)
(b) renvoie une chaı̂ne identique à la chaı̂ne paramètre
(c) plante quand la chaı̂ne paramètre contient au moins un caractère
(d) plante toujours
4. Dans la méthode d’origine, on remplace la ligne 4 par :
r=a.charAt(a.length()-i-1)+r ;.
La nouvelle méthode :
(a) renvoie le miroir de la chaı̂ne paramètre (c’est-à-dire la chaı̂ne constituée des mêmes
caractères que la chaı̂ne paramètre mais dans le sens inverse)
(b) renvoie une chaı̂ne identique à la chaı̂ne paramètre
(c) plante quand la chaı̂ne paramètre contient au moins un caractère
(d) plante toujours
Exercice 1.4 :
On considère la méthode suivante :
1 public static int d(String a,String b) {
2 int k=Math.min(a.length(),b.length());
3 for(int i=0;i<k;i++) {
4 if(a.charAt(i)<b.charAt(i)) {
5 return -1;
6 } else {
7 if (a.charAt(i)>b.charAt(i)) {
8 return 1;
9 }
10 }
11 }
12 if(a.length()<b.length()) {
13 return -1;
14 } else {
15 if(a.length()>b.length()) {
16 return 1;
17 } else {
18 return 0;
19 }
20 }
21 }
Exercice 1.5 :
On considère la méthode :
1 public static String f(String s) {
2 StringBuffer sb=new StringBuffer(s);
3 int i;
4 for(i=0;i<sb.length();i++) {
5 char c=sb.charAt(i);
6 sb.setCharAt(i,sb.charAt(sb.length()-i-1));
7 sb.setCharAt(sb.length()-i-1,c);
8 }
9 return sb.toString();
10 }
Exercice 1.6 :
On considère la méthode suivante :
1 public static String buildString(String s) {
2 String r="";
3 for(int i=0;i<s.length();i++) {
4 if(keepChar(s.charAt(i),i)) {
5 r=r+s.charAt(i);
6 }
7 }
8 return r;
9 }
Exercice 2.1 :
Ecrire une méthode qui compare deux chaı̂nes de caractères au regard de l’ordre lexicographique
(l’ordre du dictionnaire pour les caractères non accentués). On n’utilisera pas la méthode
compareTo mais on cherchera à produire des résultats identiques à ceux de cette méthode.
Exercice 2.2 :
Ecrire une méthode qui à une chaı̂ne de caractères associe le nombre de caractères distincts
que celle-ci contient.
Exercice 2.3 :
Ecrire une méthode qui permet la saisie d’une chaı̂ne de caractères ne contenant que des chiffres.
Ecrire une méthode qui à une chaı̂ne de caractères ne contenant que des chiffres associe le
nombre correspondant (sous forme d’un int). Ecrire une méthode réalisant l’opération inverse.
Exercice 2.4 :
Écrire un programme qui demande à l’utilisateur un texte et un mot, puis affiche pour chaque
lettre du mot, le nombre d’occurrences de cette lettre dans le texte de départ.
Exercice 2.5 :
Ecrire une méthode qui à une chaı̂ne de caractères associe le nombre de mots que celle-ci
contient. Ecrire ensuite une méthode qui calcule la longueur moyenne des mots d’un texte.
Exercice 2.6 :
Ecrire une méthode qui à une chaı̂ne de caractères associe true si et seulement si la phrase
qu’elle contient vérifie les règles élémentaires de typographie : la phrase commence par une
majuscule et termine par un point. Les mots sont séparés par exactement un espace (sauf en
cas de symbole de ponctuation). La virgule et le point sont collés au mot qui les précède et
sont suivis par un espace. Le point-virgule et les deux points sont précédés et suivis par un
espace.
Exercice 2.7 :
Ecrire une méthode qui reçoit une chaı̂ne de caractères de longueur impaire et l’affiche sous la
forme d’un sablier et d’un noeud papillon. Par exemple :
bonjour b r
onjou bo ur
njo bon our
j bonjour
njo bon our
onjou bo ur
bonjour b r
Exercice 2.8 :
Ecrire une méthode qui à deux chaı̂nes de caractères s1 et s2 associe la chaı̂ne constituée des
caractères de s1 qui n’apparaissent pas dans s2 (dans le même ordre).
Exercice 2.10 :
On donne l’algorithme de cryptage élémentaire (et très inefficace) suivant :
Données :
– une chaı̂ne de caractères t : le texte à coder ;
– une chaı̂ne de caractères c : la clé (de longueur strictement inférieure à celle de t).
Résultat : une chaı̂ne de caractères cryptée.
1. créer une chaı̂ne vide s.
2. pour chaque caractère x de t (dans l’ordre) :
(a) extraire de c le caractère de position i définie comme suit : soit j la position de x
dans t. i est le reste de la division de j par la longueur de c.
(b) ajouter au code unicode de x celui de c.
(c) ajouter à la chaı̂ne s le caractère correspondant au code unicode qui vient d’être
obtenu.
3. Résultat : la chaı̂ne s.
Programmez une méthode de codage et une méthode de décodage utilisant cet algorithme.
Exercice 2.11 :
Etant donnés une chaı̂ne de caractères s et un caractère c, on peut découper s selon c de la
manière suivante : si s ne contient pas c, l’unique sous-chaı̂ne u0 est la chaı̂ne s entière. Sinon, s
est formée d’une première partie u0 ne contenant pas c, suivie de c, suivie d’une seconde partie
s1 . Si s1 n’est pas la chaı̂ne vide, on peut recommencer l’opération sur celle-ci, en cherchant c
dans s1 , ce qui permet de construire u1 et s2 , etc.
Ecrire une méthode qui à une chaı̂ne de caractères s, un caractère c et un entier n associe la
sous-chaı̂ne un (éventuellement vide).
3 Problèmes
Problème 3.1 :
Pour répondre aux questions de ce problème, on pourra en général donner deux solutions :
une avec les Strings, l’autre avec les StringBuffers. Les deux solutions sont intéressantes à
comparer, tant au niveau de l’efficacité que de la simplicité de l’écriture.
1. Écrire une méthode build prenant comme paramètres un caractère c et un entier positif
n, et renvoyant la chaı̂ne constituée de n fois le caractère c. Si le paramètre entier est
négatif ou nul, la méthode devra renvoyer la chaı̂ne de caractères vide.
Exemple : le résultat de build(’a’,3) est donc la chaı̂ne de caractères "aaa".
Problème 3.2 :
On souhaite étudier dans une chaı̂ne de caractères les séquences de caractères identiques,
c’est-à-dire les séquences de la forme "aaaa". Il faut bien sûr qu’une séquence de caractères
identiques comporte au moins deux caractères pour qu’elle soit prise en compte !
Problème 3.3 :
Dans ce problème, on programme un ensemble de méthodes qui permettent d’évaluer une
expression contenue dans une chaı̂ne de caractères :
1. écrire une méthode qui à une chaı̂ne de caractères associe true si et seulement si elle
ne contient que des chiffres, des lettres et des symboles mathématiques (+, /, *, - et les
parenthèses) ;
2. écrire une méthode qui à une chaı̂ne de caractères associe true si elle contient une expres-
sion correctement parenthèsée (à chaque parenthèse ouvrante correspond une parenthèse
fermante), et false sinon ;
3. écrire une méthode qui à une expression correctement parenthèsée associe la chaı̂ne de
caractères contenu dans la première paire de parenthèses ne contenant pas d’autre paire
de parenthèses. Si on a par exemple la chaı̂ne ((a+(b+c))+(a*b)), on obtient b+c ;
4. écrire une méthode qui calcule la valeur numérique d’une chaı̂ne de caractères contenant
un calcul élémentaire de la forme “opérande numérique 1 opérateur opérande numérique
2”, où les opérandes numériques sont des nombres entiers ;
5. écrire une méthode qui calcule la valeur numérique d’une chaı̂ne de caractères contenant
un calcul comportant éventuellement des parenthèses mais dans lequel chaque expression
sans parenthèse se réduit à un calcul de la forme élémentaire utilisé dans la question
précédente.
Problème 3.4 :
Dans ce problème, nous allons apprendre à transformer une String en un nombre entier ou
réel. S’il existe déjà une méthode Java qui réalise exactement (ou presque exactement) ce qui
est demandé dans l’énoncé, son utilisation est interdite dans le problème. Si on vous demandais
par exemple d’écrire une méthode qui calcule xn , vous n’auriez pas le droit d’utiliser la méthode
pow de la classe Math. Par contre, sauf si le contraire est précisé dans l’énoncé, vous pouvez
écrire une méthode en vous servant d’une méthode définie avant (même si vous n’avez pas su
répondre à la question). Vous pouvez aussi écrire d’autres méthodes si cela simplifie la solution.