Discussion :

[johnny3]

Bonjour,

je suis en train de préparer un concours IRTF pour mai juin 2009 où l'on demande d'écrire en C ou en pseudolangage. Je connais java et j'apprends le C.

En attendant de bien manier le C, j'écris mes programmes en java, ce qui sera facilement transformable en pseudolangage.

Mais voilà, je me retrouve face à un exercice d'annales qui me pose de sacrés problèmes!

Voici l'énoncé:

En vue de transferer des images sur un reseau informatique a faible bande passante, il vous est demande de developper des algorithmes de compactage et decompactage.
L'algorithme de compactage envisage consiste a generer un nouveau fichier image B qui resulte du remplacement dans le fichier origine A de toutes les suites de symboles identiques par le nombre de fois ou le symbole a ete rencontre.

Exemple:
A : 0000==&&&&&8888*****
B : 402=5&5485*

En supposant que le fichier image origine A est un tableau de N elements et que les
symboles sont les nombres entiers O et 1
a) Ecrire l'algorithme de compactage
b) Ecrire l'algorithme de decompactage

Ca me paraissait simple, mais ça ne l'est finalement pas!

J'ai pour le moment écrit cela:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class character{
	int compteur;
	char binaire;
}
 
public class algoCompactage {
	static character [] tab = new character[0];
	static char [] tabSymbDecompacte;
	static char [] tabSymbCompacte;
	static String symb;
	static int compteur = 1;
 
	static char [] RentrerChaineSymb() throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		System.out.println("Tapez la chaine de symboles");
		symb = in.readLine();
		StringToChar();
		return tabSymbDecompacte;
	}
 
	static void StringToChar(){
		tabSymbDecompacte = symb.toCharArray();
	}
 
	// calcul de la taille du tableau compacté
	static int TailleTableauCompacte(){
		int taille = 1;
		for (int i = 0; i < tabSymbDecompacte.length - 1; i++){
			if (tabSymbDecompacte[i+1] != tabSymbDecompacte[i]) taille ++;
		}
		return taille;
	}
 
	// OK
	static void InitialiserTableauCompacte(){
		tab = new character [TailleTableauCompacte()];
	}
 
	// fonction permettant de compter des caractères identiques contigus
	static int compteurCharacter(){
		for (int i = 0; i < tabSymbDecompacte.length - 1; i++){
			if (tabSymbDecompacte[i+1] == tabSymbDecompacte[i]) compteur ++;
			else break;
		} 
		return compteur;
	}
 
	// fonction retournant le caractère étant suivi par un caractère différent
	static Character symbTabComptacte(){
		int i;
		for (i = 0; i < tabSymbDecompacte.length - 1; i++){
			if (tabSymbDecompacte[i+1] != tabSymbDecompacte[i]) return tabSymbDecompacte[i];
		}
		return null;
	}

J'ai plusieurs idées pour résoudre l'exercice mais je sollicite vos neurones.

1) Parcourir le tableau initial, compter le nombre de fois où l'on a un même char, retourner le compteur, stocker les deux infos dans le tableau d'objets ayant un char et un int
2) Copier le tableau initial dans un nouveau tableau plus petit, en démarrant à la dernière valeur lue (en reprenant la valeur du compteur trouvée)

Qu'en pensez-vous?

Des idées moins tordues que les miennes?

Merci par avance,
Johnny

P.S: je n'écris pas en objet pour plus facilement transcrire en C plus tard, même si je sais qu'il existe struct en C qui ressemble à class en java.

[Braillane]

Je ne suis pas sur d'avoir bien saisi mais je pense pas qu'un tableau d'objet soit nécessaires... Un simple String me semble suffisant, String étant facilement convertible en tableau de char....

[johnny3]

oui, mais comment faire pour compter chaque occurrence de 0 ou de 1 et l'afficher dans une nouvelle String au fur et à mesure ?

[Braillane]

soit machaine la chaine de départ :
fait un truc du genre :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
String chaineArrivé = "";
char enCours = '!'; //caractere bidon
int compteur=0;
for(int i=0;i<maChaine.length;i++)
{
    if(maChaine[i]==enCours||compteur==0)
           compteur++;
    else
     {
         chaineArrivé+=String.valueOf(compteur)+String.valueOf(enCours );
         compteur=0;
     }
     enCours = maChaine[i];
}

Voila un truc du genre. Ca m'étonnerait que sa compile, c'est juste pour l'idée

[johnny3]

Merci, je vais retenter ce week-end.

[nouknouk]

limite off-topic, mais bon pour la culture générale: ce genre d'algo est de type RLE (pour Run Length Encoding).

[Braillane]

Pas du tout off-topic, la culture générale a sa place partout
Nan mais en plus dans ton lien, il y a un exemple en java qui est en plus doit être bien plus pertinent que le mien... J'ai envie de dire "problem solved" du coup
GG

[johnny3]

J'ai réussi!

Eh bien ce n'était pas si simple, franchement!

J'ai tenté un autre sujet d'annale et je me suis rendu compte que c'était le même exo, sauf qu'on nous demandait de mettre le résultat dans 2 tableaux, un avec le nombre d'occurrences et un avec la valeur.

J'ai réussi mais il fallait prendre en compte plusieurs choses, notamment, le fait de repartir du tableau du bon endroit à chaque fois.

Voici une réponse possible, qui fonctionne. Peut-être en trouverez-vous une plus simple que la mienne.

Amicalement, et merci pour l'aide apportée,
Johnny3

P.S: bon, c'est pas tout ça, mais dans la seconde partie du problème, il est demandé de faire l'inverse: à partir d'un tableau compacté, je dois retrouver le tableau décompacté, mais je ne pense pas que ça soit trop compliqué, une fois la première partie faite.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class plateau {
	int vecteur[];
	int valeurs[];
	int longueurs[];
 
	int getNbCases() throws NumberFormatException, IOException
	{
		int nb;
		do
		{
			System.out.println("Donnez le nombre de cases (entre 1 et 10):");
			BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
			nb = Integer.parseInt(in.readLine());
			if (nb < 0 || nb > 10) System.out.println("Veuillez entrer un nombre non nul non supérieur à 10.");
		} while (nb < 0 || nb > 10);
		return nb;
	}
 
	int TailleValeursLongueurs()
	{
		int taille = 1;
		for (int i = 0; i < this.vecteur.length - 1; i++)
		{
			if (this.vecteur[i + 1] != this.vecteur[i]) taille++;
		}
		return taille;
	}
 
	int [] initialisationVecteur(int nb) throws NumberFormatException, IOException
	{
		this.vecteur = new int[nb];
		return vecteur;
	}
 
	int [] initialisationValeurs() throws NumberFormatException, IOException
	{
		this.valeurs = new int[this.TailleValeursLongueurs()];
		return valeurs;
	}
 
	int [] initialisationLongueurs() throws NumberFormatException, IOException
	{
		this.longueurs = new int[this.TailleValeursLongueurs()];
		return longueurs;
	}
 
	int [] remplirVecteur() throws NumberFormatException, IOException
	{
		this.vecteur = this.initialisationVecteur(this.getNbCases());
		System.out.println("Donnez les valeurs (nb entiers) du vecteur (valeurs positifs et/ou négatives): ");
		for (int i = 0; i < vecteur.length; i++)
		{
			System.out.println("Case " + (i + 1) + ":");
			BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
			vecteur[i] = Integer.parseInt(in.readLine());
		}
		return vecteur;
	}
 
	int addCumTabLongueur()
	{
		int somme = 0;
		for (int i = 0; i < this.longueurs.length; i++)
		{
			if (longueurs[i] == 0) break;
			somme += longueurs[i];
		}
		return somme;
	}
 
	int addCumTabLongueur2(int longueur)
	{
		int somme = 0;
		for (int i = 0; i < longueur; i++)
		{
			somme += longueurs[i];
		}
		return somme;
	}
 
	void remplirLongueurs()
	{
		int compteurValeur = 0;
		int compteurVecteur = 0;
		for (int i = 0; i < this.longueurs.length; i++)
		{
			for (int j = compteurVecteur; j < this.vecteur.length - 1; j++)
			{
				if (this.vecteur[j] == this.vecteur[j + 1])
				{
					compteurValeur++;
					compteurVecteur++;
				}
				if (this.vecteur[j] != this.vecteur[j + 1]) break;
			}
			this.longueurs[i] = (compteurValeur + 1);
			compteurVecteur = addCumTabLongueur();
			compteurValeur = 0;
		}
	}
 
	void affichageVecteur()
	{
		for (int i = 0; i < this.vecteur.length; i++)
		{
			System.out.print(vecteur[i] + " ");
		}
	}
 
	void affichageValeurs()
	{
		for (int i = 0; i < this.valeurs.length; i++)
		{
			System.out.print(valeurs[i] + " ");
		}
	}
 
	void affichageLongueurs()
	{
		for (int i = 0; i < this.longueurs.length; i++)
		{
			System.out.print(longueurs[i] + " ");
		}
		System.out.println();
	}
 
	void affichageLineaire(){
		System.out.print("Résultat compacté: ");
		for (int i = 0; i < this.longueurs.length; i++){
			 System.out.print(this.longueurs[i] + " " + this.valeurs[i] + " | ");
		}
	}
 
	void remplirValeurs()
	{
		int compteurVecteur = 0;
		for (int i = 0; i < this.valeurs.length; i++)
		{
			if (compteurVecteur == (this.vecteur.length - 1))
			{
				this.valeurs[this.valeurs.length - 1] = this.vecteur[compteurVecteur];
				break;
			}
			for (int j = compteurVecteur; j < this.vecteur.length - 1; j++)
			{
				if (this.vecteur[j] != this.vecteur[j + 1])
				{
					this.valeurs[i] = this.vecteur[j];
					break;
				}
			}
			compteurVecteur = this.addCumTabLongueur2(i + 1);
		}
	}
 
	public static void main(String [] args) throws NumberFormatException, IOException
	{
		plateau p = new plateau();
		p.remplirVecteur();
		p.initialisationValeurs();
		p.initialisationLongueurs();
		p.remplirLongueurs();
		p.remplirValeurs();
		System.out.println();
		System.out.print("Vecteur: ");
		p.affichageVecteur();
		System.out.println();
		System.out.print("Tableau Valeurs: ");
		p.affichageValeurs();
		System.out.println();
		System.out.print("Tableau Longueurs: ");
		p.affichageLongueurs();
		p.affichageLineaire();
	}
}

[johnny3]

je viens de voir la solution proposée, mais le concours est en C (ou en pseudolangage) et je ne connais pas bien du tout les regex en java (mais j'apprendrai avec le temps).

Bon, je mets en place l'algorithme de décompactage, puis je travaille sur les cas particuliers des 00 01 10 et 11 et je clique sur résolu!

[johnny3]

Voici un algorithme de décompactage. Eh bien pas si évident car il faut gérer la mauvaise double saisie de la même valeur binaire, le fait de bien rentrer un nombre binaire, le fait de ne pas rentrer un nombre d'occurrences négatif ou nul.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class AlgoDecompactage {
	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	int valeurs[];
	int longueurs[];
 
	int initialiserLongueurTabValeurs() throws NumberFormatException, IOException
	{
		return this.longueurs.length;
	}
 
	int initialiserLongueurTabLongueurs() throws NumberFormatException, IOException
	{
		int nbOccurrences;
		nbOccurrences = Integer.parseInt(in.readLine());
		return nbOccurrences;
	}
 
	void remplirTableauLongueurs() throws NumberFormatException, IOException
	{
		System.out.println("Rentrez le nombre d'occurrences de chaque valeur binaire (jamais négatif): ");
		int nbOccurrences;
		do
		{
			nbOccurrences = initialiserLongueurTabLongueurs();
			if (nbOccurrences <= 0) System.out.println("Vous ne pouvez rentrer un nombre négatif ou nul. Veuillez recommencer:");
		} while (nbOccurrences <= 0);
		longueurs = new int[nbOccurrences];
		for (int i = 0; i < nbOccurrences; i++)
		{
			System.out.println("Valeur " + (i + 1) + ": ");
			do
			{
				this.longueurs[i] = Integer.parseInt(in.readLine());
				if (this.longueurs[i] <= 0) System.out.println("Vous ne pouvez rentrer un nombre négatif ou nul. Veuillez recommencer:");
			} while (this.longueurs[i] <= 0);
		}
	}
 
	void remplirTableauValeurs() throws NumberFormatException, IOException
	{
		this.valeurs = new int[this.initialiserLongueurTabValeurs()];
		int valeur = 0;
		System.out.println("Rentrez les valeurs binaires correspondantes au nombre d'occurrences correspondant: ");
		for (int i = 0; i < this.valeurs.length; i++)
		{
			do
			{
				System.out.println("Valeur " + (i + 1) + ": ");
				valeur = Integer.parseInt(in.readLine());
				if (valeur != 0 && valeur != 1)
				{
					System.out.println("Vous devez rentrer une valeur binaire. Recommencez:");
				} else this.valeurs[i] = valeur;
			} while ((valeur != 0 && valeur != 1) || MemeNbBinaire(i + 1));
		}
	}
 
	boolean MemeNbBinaire(int valeur)
	{
		for (int i = 1; i < valeur; i++)
		{
			if (this.valeurs[i] == this.valeurs[i - 1])
			{
				System.out.println("Meme valeur rentrée. Recommencez:");
				return true;
			}
		}
		return false;
	}
 
	void affichageValeurs()
	{
		System.out.println("Tableau de valeurs binaires:");
		for (int i = 0; i < this.valeurs.length; i++)
		{
			System.out.print(valeurs[i] + " ");
		}
		System.out.println();
	}
 
	void affichageLongueurs()
	{
		System.out.println("Tableau de longueurs:");
		for (int i = 0; i < this.longueurs.length; i++)
		{
			System.out.print(longueurs[i] + " ");
		}
		System.out.println();
	}
 
	void affichageTabDecompacte()
	{
		System.out.println("Tableau décompacté:");
		for (int i = 0; i < this.longueurs.length; i++)
		{
			System.out.print(this.longueurs[i] + "" + this.valeurs[i]);
		}
	}
 
	public static void main(String [] args) throws NumberFormatException, IOException
	{
		AlgoDecompactage ad = new AlgoDecompactage();
		ad.remplirTableauLongueurs();
		ad.remplirTableauValeurs();
		ad.affichageLongueurs();
		ad.affichageValeurs();
		ad.affichageTabDecompacte();
	}
}

Bon, je suppose que pour un concours, on ne nous en demande pas tant, mais en fait, je ne sais pas. Je n'espère pas.

Je pense pouvoir me débrouiller seul pour 00, 01, 10 et 11 à présent.

Je vais pouvoir cocher "résolu."

Merci encore pour l'aide apportée.

Quand je pense qu'il m'a fallu 2 semaines pour trouver tout ça!

Bon, il ne me reste plus qu'à le code en C, ce qui ne va pas être une mince affaire.