PROFDINFO.COM

Votre enseignant d'informatique en ligne

Chapitre 2 - Structures avancées

Exercice 2.1 - La cigale et les sets

Écrivez un programme qui permet de gérer un dictionnaire.

Dans un premier temps, votre programme doit demander le nom du fichier texte et doit vérifier s'il existe. Si le fichier texte existe, le programme lit les mots dans le fichier texte, un mot par ligne, et les place dans un arbre binaire de recherche. Les mots ne sont pas nécessairement classés en ordre lexicographique dans le fichier texte et le même mot peut y apparaitre plusieurs fois. Voici un exemple de fichier texte que vous pouvez utiliser: la cigale et la fourmi.

Deuxièmement, le programme doit parcourir l'arbre binaire de recherche de façon à afficher les mots en ordre lexicographique.

Vous devez faire deux versions de votre programme.

La première version doit utiliser un arbre binaire de recherche implémenté par la classe CABR telle que vue en classe.

La deuxième version doit utiliser un arbre binaire de recherche implémenté par la classe set de STL.

N.B.: Portez une attention particulière à la structure de votre programme et à la qualité de votre programmation!

Exercice 2.2 - Maître Corbeau et les maps

Écrivez un programme qui permet de traduire mot à mot un texte en français vers l'anglais. Le dictionnaire de traduction est sauvegardé dans un fichier texte où chaque ligne contient un mot en français suivi de sa traduction en anglais. Exemple:

 

arbre tree
bec beak
corbeau raven
en in
fromage cheese
maître master
perché perched
son his
sur on
tenait held
un a

Dans un premier temps, votre programme doit donc lire le dictionnaire et le sauvegarder dans un map.

Ensuite, votre programme doit lire un fichier texte comme par exemple:

 

Maître Corbeau, sur un arbre perché,
Tenait en son bec un fromage.

et afficher sa traduction en anglais à la console.

Exercice 2.3 - Combat entre le Set et le Vector

L'objectif de cet exercice est de déterminer lequel des structures de données est le plus rapide lorsque l'on insère des éléments de tailles différentes et que l'on recherche des éléments dans la structure.

Pour ce faire:

  1. Créez une structure de données dont la taille totale pourra être facilement modifiée dans votre code. Utilisez un tableau automatique?
  2. Calculez le temps nécessaire à l'insertion des valeurs uniques de 1 à 100 000 dans un set dans en ordre aléatoire.
  3. Calculez le temps nécessaire à la recherche de 100 000 valeurs aléatoires dans le set précédent.
  4. Calculez le temps nécessaire à l'insertion des valeurs uniques de 1 à 100 000 dans un vector dans en ordre aléatoire.
  5. Calculez le temps nécessaire à la recherche linéaire de de 100 000 valeurs aléatoires dans le vector précédent.

Répétez les étapes 2 à 5 pour des éléments de taille 4 octets, 8 octets, 16 octets, 32 octets, 64 octets, 128 octets, 256 octets, 512 octets, 1024 octets et 2048 octets.

Quelle conclusion tirez-vous de cette expérience?

Si l'on trie le vecteur et que l'on effectue une recherche dichotomique à la place d'une recherche linéaire, arrivez-vous aux mêmes conclusions?

Exercice 2.4 - Le plus court chemin

Écrivez un programme qui permet de trouver le plus court chemin entre deux noeuds d'un graphe avec l'algorithme de Dijkstra vu en classe. Votre programme doit implémenter la structure et la classe suivantes:

 

class CGraphe

{
public:
	CGraphe();
	vector<int> Dijkstra(int Debut, int Fin);

private:
	struct Noeud {
		int Distance_;
		int Prec_;
		bool Vu_;
		Noeud();
	};

	const int NbNoeuds = 6;
	const int Inf = numeric_limits<int>::max() / 2;

	vector<vector<int>> Distances_ =
	{
		{ 0,   3,   1,   Inf, Inf, Inf },
		{ 3,   0,   1,   3,   Inf, Inf },
		{ 1,   1,   0,   3,   5,   Inf },
		{ Inf, 3,   3,   0,   1,   3 },
		{ Inf, Inf, 5,   1,   0,   1 },
		{ Inf, Inf, Inf, 3,   1,   0 }
	};
	vector<Noeud> Noeuds_;
};

Testez le bon fonctionnement de votre classe avec l'exemple suivant:

int main()
{
	CGraphe Graphe;

	vector<int> Solution = 	Graphe.Dijkstra(0,5);

	for(auto i: Solution) cout << i << " "; 
}