Modifier l’exercice précédent de façon à ce que l’arbre ait une structure de maximier : contrairement à l’arbre binaire de recherche, le maximier est un arbre dans lequel la valeur de la racine (ici un entier) est supérieure celle de n’importe laquelle de ses sous arbres.
Archives de Catégorie: M1103
M1103-TP5 Exercice 5 – Space Invaders
On souhaite ajouter un peu plus de souplesse à structure du fichier config.yalm de façon à pouvoir y ajouter des commentaires, permuter des lignes, … Seules les clés autorisées nous intéressent donc.
Ajouter le code suivant :
| struct AuthorizedKey { /* List of authorized key for the type char in a struct CMyParam*/ const vector<string> VParamChar {“KeyLeft”, “KeyRight”, “VesselToken”, “InvaderToken”, “KShoot”}; /* List of authorized key for the type string in a struct CMyParam*/ const vector<string> VParamString {“VesselColor”, “InvaderColor”}; /* List of authorized key for the type unsigned in a struct CMyParam*/ const vector<string> VParamUnsigned {“GridSize”}; }; |
Modifier la fonction LoadParams () comme cela : après avoir fait une extraction d’une clé fichier config.yalm, vérifier qu’elle appartient à la structure AuthorizedKey avant de l’insérer dans la structure CMyParam.
R1.01 – Prog#7 – Corrigé
#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;
void Flux_cin()
{
string Ligne;
while (true)
{
getline (cin, Ligne);
if (cin.eof()) break;
cout << Ligne << endl;
}
}
void AffichFich()
{
ifstream ifs ("LaFontaine.txt");
string Ligne;
while (true)
{
getline (ifs, Ligne);
if (ifs.eof()) break;
cout << Ligne << endl;
}
}
void NomFichAuClavier()
{
ifstream ifs;
ofstream ofs;
string FichierSource, FichierDestination;
getline (cin, FichierSource);
ifs.open(FichierSource);
getline (cin, FichierDestination);
ofs.open(FichierDestination);
string Ligne;
unsigned Cpt (1);
while (true)
{
getline (ifs, Ligne);
if (ifs.eof()) break;
ofs << Cpt++ << " " << Ligne << endl;
}
}
void ValidFichier()
{
ifstream ifs;
ofstream ofs;
string FichierSource, FichierDestination;
unsigned NbVies (0);
while (true)
{
getline (cin, FichierSource);
ifs.open(FichierSource);
if (ifs.is_open()) break;
++NbVies;
cout << "Gros boulet" << endl;
if (3 == NbVies)
{
cout << "3 echecs d'ouverture de fichier en lecture" << endl;
return;
}
}
NbVies = 0;
while (true)
{
getline (cin, FichierDestination);
ofs.open(FichierDestination);
if (ofs.is_open()) break;
++NbVies;
cout << "Gros boulet" << endl;
if (3 == NbVies)
{
cout << "3 echecs d'ouverture de fichier en ecriture" << endl;
return;
}
}
string Ligne;
unsigned Cpt (1);
while (true)
{
getline (ifs, Ligne);
if (ifs.eof()) break;
ofs << Cpt++ << " " << Ligne << endl;
}
}
void FonctionGet()
{
ifstream ifs;
string FichierSource;
getline (cin, FichierSource);
ifs.open(FichierSource);
char car;
while (true)
{
car = char (ifs.get());
if (ifs.eof()) break;
cout << car /*<< endl*/;
}
}
void ExtractionsMots()
{
string mot;
while (cin >> mot)
cout << mot << endl;
}
void ExtractionsCars()
{
char Car;
while (cin >> Car)
cout << Car /*<< endl*/;
}
void ExtractionsEntiers()
{
int Entier;
while (cin >> Entier)
cout << Entier << endl;
}
void ExtractionsReels()
{
float Reel;
while (cin >> Reel)
cout << Reel << endl;
}
int main()
{
//cout << "Hello World!" << endl;
//Flux_cin();
//AffichFich();
//NomFichAuClavier();
ValidFichier();
//FonctionGet ();
//ExtractionsMots ();
//ExtractionsCars();
//ExtractionsEntiers ();
//ExtractionsReels ();
return 0;
}
M1103 – TD2 – Exercice 1
Rappel : un palindrome est “un mot, un vers, une phrase que l’on peut lire dans les deux sens” (dictionnaire Larousse).
Ecrire la fonction IsPalindrome() qui renvoie vrai si la chaîne qui lui est passée en paramètre est un palindrome de façon itérative.
On peut aussi en donner la définition récursive suivante :
- un mot est un palindrome si sa première et sa dernière lettre sont identiques et si le reste du mot est lui-même un mot palindrome,
- un mot d’une seule lettre est un palindrome,
- une chaîne vide sera considérée, par extension, comme un palindrome.
Ecrire la fonction IsPalindrome() qui renvoie vrai si la chaîne qui lui est passée en paramètre est un palindrome de façon récursive.
M1103 – TD2 – Exercice 2
On peut donner la définition du calcul d’une puissance d’un nombre de façon récursive comme suit :
Soit x un nombre réel et n un entier relatif. Alors :
xn = 1 si n = 0xn = 0 si x = 0 (et n ≠ 0)xn = 1 / (x-n) si n < 0xn = x * xn-1 sinonEn vous inspirant de la fonction
Factorielle ()montrée en cours, écrire la fonction récursivePuissEntRecurs ()qui renvoie le résultatxn,xetnétant passés en paramètres.
M1103 – TD2 – Exercice 3
Les nombres romains sont constitués de suites des caractères M, D, C, L, X, V et I, représentant respectivement 1000, 500, 100, 50, 10, 5 et 1. Le calcul de la valeur décimale est très simple lorsque les symboles se présentent dans l’ordre décroissant : il suffit de faire la somme des valeurs des symboles rencontrés. Par exemple, la chaine de caractères MMCVI représente la valeur 2106 (1000 + 1000 + 100 + 5 + 1.
En revanche, lorsque certains symboles sont inversés, il faut les soustraire au symbole suivant. Par exemple, la chaine de caractères CM représente 900 (1000 – 100), et IV représente 4 (5 – 1).
La récursivité offre une élégante solution à ce problème :
- si un nombre romain est constitué d’un seul caractère, sa valeur est égale à celle de ce caractère.
- la valeur d’un nombre romain est égale à la valeur du premier caractère + la valeur du nombre romain restant, si la valeur de ce premier caractère est supérieure ou égale à celle de son suivant (le deuxième, donc). Par exemple :
MMXI = M + (MXI) = MXI = M + (XI) XI = X + (I) I = 1 10 + 1 = 11 1000 + 11 = 1011 1000 + 1011 = 2011 2011 - la valeur d’un nombre romain est égale à la valeur du nombre romain restant après le premier caractère – la valeur du premier caractère, si la valeur de ce caractère est inférieure à celle de son suivant, Par exemple :
MCMIX = M + (CMIX) = CMIX = (MIX) - C MIX = M + (IX) IX = (X) - I 10 (10 - 1) = 9 1000 + 9 = 1009 1009 - 100 = 909 1000 + 909 = 1909 1909
On suppose qu’existe la fonction ValChRomain() qui renvoie la valeur numérique correspondant au caractère romain qui lui est passé en paramètre.
Ecrire la fonction ValNbRomain() qui renvoie la valeur numérique correspondant à un nombre romain qui lui est passé en paramètre sous forme d’un string. On supposera qu’une chaîne vide a pour valeur 0 et que la chaîne passée en paramètre est valide.
M1103 – TD2 – Exercice 4
Faites la trace de l’algorithme suivant en considérant l’appel LS ("","abc");
Algorithm Ls
Input: X and Y two string
Output:
if (Y.size() == 0) then {
cout << X;
return;
}
char tmp =Y.last ();
Y .pop_back ();
LS(X,Y);
string Z = X + tmp;
LS(Z,Y);
Déduisez la sortie.
M1103 – TD2 – Exercice 5
Les représentations binaires de tous les entiers codés sur 3 bits sont les suivantes :
000 001 010 011 100 101 110 111
On remarque que les 8 chaînes générées se répartissent en deux groupes : toutes les chaînes commençant par ‘0’ puis toutes celles commençant par ‘1’. Dans chacun de ces groupes, et abstraction faite de ce premier caractère, les chaînes de caractères restantes sont les représentations binaires de tous les entiers codés sur 2 bits :
0 00 0 01 0 10 0 11
Dans chacun des deux sous-groupes, et abstraction faite des deux premiers caractères, les chaînes de caractères restantes sont les représentations binaires de tous les entiers codés sur 1 bit :
00 0 00 1
L’algorithme de construction est évidemment doublement récursif. La génération de toutes les représentations binaires de N bits, consiste à :
- placer ‘0’ en position 0 de la chaîne, puis générer toutes les représentations binaires des N – 1 bits restants,
- placer ‘1’ en position 0 de la chaîne, puis générer à nouveau toutes les représentations binaires des N – 1 bits restants.
La construction se fait dans une chaîne, de longueur N, qui est remplie au fur et à mesure et affichée seulement lorsqu’elle est pleine.
L’exécution de votre algorithme devra est similaire à la trace suivante (le caractère 'X' désigne une lettre inconnue) :
XXX
/ \
0XX 1XX
/ \ / \
00X 01X 10X 11X
/ \ / \ / \ / \
000 001 010 011 100 101 110 111
Ecrire la procédure doublement récursive RepresentBin (), qui génère dans une chaîne de taille N toutes les représentations binaires à partir de la position i, et les affiche à chaque fois que la chaîne est pleine. La chaîne ainsi que le rang i sont passés en paramètres.
M1103 – TD2 – Exercice 6
Le problème dit des “Tours de Hanoi” peut être vu comme un exercice récréatif, un casse-tête, un jeu mathématique, … Il fait l’objet d’une abondante littérature sur Internet, présentant à la fois la légende d’où il serait issu, de nombreuses animations illustrant sa résolution, des variantes et de savants développements mathématiques … Sa résolution est une très simple et intéressante application récursive de parcours infixé d’arbre !
- Le problème
Le jeu est constitué de 3 pieux (ou pivots), et de N anneaux de diamètres strictement décroissants enfilés initialement sur l’un des pieux et constituant une “tour”. Il s’agit de faire passer les N anneaux du pieu initial sur l’un des deux autres pieux, en respectant les règles suivantes :
- les anneaux ne peuvent être déplacés qu’un seul à la fois,
- seul l’anneau du dessus d’une tour peut être déplacé,
- un anneau peut être prélevé de n’importe quelle tour et enfilé sur n’importe quel autre pieu à condition qu’il ne soit jamais posé sur un anneau de diamètre inférieur.
Le jeu consiste à effectuer le moins de déplacements possible !
Ecrire la procédure récursive Hanoi() qui décrit les mouvements élémentaires des disques. Elle reçoit en paramètres-données :
- le nombre d’anneaux de la tour à déplacer,
- les identifiants (un simple caractère) des pieux respectivement initial, final et intermédiaire.
Construire l’arbre des appels.
M1103 – TD1 – Exercice 1
Ecrire la procédure TriSelection () de signature
[Algo]
procedure TriSelection (TabInt : in_out tableau de entier);
[/Algo]
Ce sous-programme doit trié le tableau TabInt selon la méthode du tri par sélection / échange.
Ecrire dans un second temps un autre sous-programme qui vérifie que le tableau qui lui est passé en paramètre est trié.