From 9fe033ea88c2f705ec18c232873d056e0c229d72 Mon Sep 17 00:00:00 2001 From: Gaspard Coulet Date: Wed, 28 Apr 2021 23:05:53 +0200 Subject: Initial commit --- sem_4/Algo/TP1/Q1.cpp | 74 +++++++ sem_4/Algo/TP1/R1 | Bin 0 -> 13510 bytes sem_4/Algo/TP2/SolutionsFonctionMysterieuses.cpp | 47 +++++ sem_4/Algo/TP2/fonctionsMysterieuses.h | 14 ++ sem_4/Algo/TP2/fonctionsMysterieuses.o | Bin 0 -> 2600 bytes sem_4/Algo/TP2/sujet/TPReconnaissance2.pdf | Bin 0 -> 201180 bytes sem_4/Algo/TP2/test | Bin 0 -> 13979 bytes sem_4/Algo/TP3/TP3Tris.pdf | Bin 0 -> 104431 bytes sem_4/Algo/TP3/TriOutilsSimples.cpp | 27 +++ sem_4/Algo/TP4/AB.cpp | 72 +++++++ sem_4/Algo/TP4/AB.h | 44 +++++ sem_4/Algo/TP4/SortieLatex.cpp | 110 +++++++++++ sem_4/Algo/TP4/TPArborescencesBinaires.pdf | Bin 0 -> 278512 bytes sem_4/Algo/TP4/main.cpp | 24 +++ sem_4/Algo/TP4/prog | Bin 0 -> 14039 bytes sem_4/Algo/TP4/test | Bin 0 -> 14039 bytes sem_4/Algo/TP5/Arbo.cpp | 235 +++++++++++++++++++++++ sem_4/Algo/TP5/Arbo.h | 115 +++++++++++ sem_4/Algo/TP5/TPArbo.pdf | Bin 0 -> 61606 bytes sem_4/Algo/TP5/main.cpp | 6 + sem_4/Algo/TP5/prog | Bin 0 -> 14506 bytes sem_4/Algo/TP6/TPTas.pdf | Bin 0 -> 45585 bytes sem_4/Algo/TP6/Tas.h | 59 ++++++ sem_4/Algo/TP7/ArbreBinaireRecherche.cpp | 95 +++++++++ sem_4/Algo/TP7/ArbreBinaireRecherche.h | 57 ++++++ sem_4/Algo/TP7/SortieLatex.cpp | 101 ++++++++++ sem_4/Algo/TP7/TPABR.pdf | Bin 0 -> 191051 bytes sem_4/Algo/TP8/graphes.cpp | 108 +++++++++++ sem_4/Algo/TP8/graphes.h | 29 +++ sem_4/Algo/TP8/zbeb.exe | Bin 0 -> 14594 bytes 30 files changed, 1217 insertions(+) create mode 100644 sem_4/Algo/TP1/Q1.cpp create mode 100644 sem_4/Algo/TP1/R1 create mode 100644 sem_4/Algo/TP2/SolutionsFonctionMysterieuses.cpp create mode 100644 sem_4/Algo/TP2/fonctionsMysterieuses.h create mode 100644 sem_4/Algo/TP2/fonctionsMysterieuses.o create mode 100644 sem_4/Algo/TP2/sujet/TPReconnaissance2.pdf create mode 100644 sem_4/Algo/TP2/test create mode 100644 sem_4/Algo/TP3/TP3Tris.pdf create mode 100644 sem_4/Algo/TP3/TriOutilsSimples.cpp create mode 100644 sem_4/Algo/TP4/AB.cpp create mode 100644 sem_4/Algo/TP4/AB.h create mode 100644 sem_4/Algo/TP4/SortieLatex.cpp create mode 100644 sem_4/Algo/TP4/TPArborescencesBinaires.pdf create mode 100644 sem_4/Algo/TP4/main.cpp create mode 100644 sem_4/Algo/TP4/prog create mode 100644 sem_4/Algo/TP4/test create mode 100644 sem_4/Algo/TP5/Arbo.cpp create mode 100644 sem_4/Algo/TP5/Arbo.h create mode 100644 sem_4/Algo/TP5/TPArbo.pdf create mode 100644 sem_4/Algo/TP5/main.cpp create mode 100644 sem_4/Algo/TP5/prog create mode 100644 sem_4/Algo/TP6/TPTas.pdf create mode 100644 sem_4/Algo/TP6/Tas.h create mode 100644 sem_4/Algo/TP7/ArbreBinaireRecherche.cpp create mode 100644 sem_4/Algo/TP7/ArbreBinaireRecherche.h create mode 100644 sem_4/Algo/TP7/SortieLatex.cpp create mode 100644 sem_4/Algo/TP7/TPABR.pdf create mode 100644 sem_4/Algo/TP8/graphes.cpp create mode 100644 sem_4/Algo/TP8/graphes.h create mode 100644 sem_4/Algo/TP8/zbeb.exe (limited to 'sem_4/Algo') diff --git a/sem_4/Algo/TP1/Q1.cpp b/sem_4/Algo/TP1/Q1.cpp new file mode 100644 index 0000000..116cf84 --- /dev/null +++ b/sem_4/Algo/TP1/Q1.cpp @@ -0,0 +1,74 @@ +#include +#include +#include + +void f1 ( int n); +void f3 (int n); +void g2 (int n); + +void f1 (int n){ + for (int i = 1; i <=n; i ++){ + + } +} + +void f3 (int n ) { + for (int i = 1; i <=n; i ++){ + for (int i = 1; i <=n; i ++){ + for (int i = 1; i <=n; i ++){ + } + } + } +} + +void g2 (int n){ + if ( n != 1){ + g2(n-1); + g2(n-1); + } +} +void g3 (int n){ + if ( n != 1){ + g3(n-1); + g3(n-1); + g3(n-1); + } +} + +int main ( int argc, char ** argv){ + if ( argc != 2){ + std::cout<<"Syntaxe attendue : ./R1 n"< +#include +#include /* atoi */ + +#include "fonctionsMysterieuses.h" + +int apuissanceb(int a, int b) { +// renvoie a puissance b + if (b==0) return 1; + if (b % 2 == 0) return apuissanceb(a * a, b / 2); + return a * apuissanceb(a,b-1);} + +int main(int argv, char** argc){ + + int numeroFonction = atoi(argc[1]), + n = atoi(argc[2]), + v; + for (int i = 0; i < n; i+=1){ + + switch (numeroFonction) { + case 1 : v=f1(i); break; + case 2 : v=f2(i); break; + case 3 : v=f3(i); break; + case 4 : v=f4(i); break; + case 5 : v=f5(i); break; + case 6 : v=f6(i); break; + } + std::cout<<"f"< + + +/************************ +Generaux +****************************/ +int max(int a, int b) {if (a > b) return a; return b;} + +int moitieSuperieure(int n){ + if (n % 2 == 0) return n / 2; return (n+1) / 2;} + +void imprimer(int n, int T[]){ + for (int i=0; iSupprimerSAG(); + delete SAG; + } +} + + +void Sommet::SupprimerSAD(){ + if (!FeuilleP()){ + SAD->SupprimerSAD(); + delete SAD; + } +} + + +void Sommet::GrefferSAG(AB g){ + SupprimerSAG(); + SAG = g; + g->Pere = this; + g->FGP= true; + } + +void Sommet::GrefferSAD(AB d){ + SupprimerSAD(); + SAD=d; + d->Pere=this; + d->FGP=false; + } + + +void Sommet::RemplacerPourLePerePar(AB Ar){ + //le pere existe + if ( FGP ){ + Pere->GrefferSAG(Ar); +} +else { + Pere->GrefferSAD(Ar); +} +} + + +/*Question 1 : L'etiquette d'un sommet est dans "racine", on voit que l'arbo est binaire car chaque sommet ne peut avoir que 2 fils au maximum. +*/ diff --git a/sem_4/Algo/TP4/AB.h b/sem_4/Algo/TP4/AB.h new file mode 100644 index 0000000..436d639 --- /dev/null +++ b/sem_4/Algo/TP4/AB.h @@ -0,0 +1,44 @@ +//AB.h + +#ifndef AB_H +#define AB_H + +#include +#include + +typedef int Valeur; + +class Sommet; + +typedef Sommet* AB; +void SortieLatex(AB Ar, std::string filepath); + std::string* TikzRecursAB(int ligne,int gauche, int droite, int numeroPere, int typeFils, AB Ar); + +class Sommet { + public: + Valeur racine; + AB Pere,SAG, SAD; + bool FGP; + + int hauteur,balanceGmoinsD; + + + Sommet(Valeur v); + Sommet(Sommet& s); + + void GrefferSAG(AB g); + void GrefferSAD(AB d); + + void SupprimerSAG(); + void SupprimerSAD(); + + bool FeuilleP(); + + void RemplacerPourLePerePar(AB); + + std::string* TikzRecursAB(int ligne,int gauche, int droite, int numeroPere, int typeFils, AB Ar); +}; + + + +#endif diff --git a/sem_4/Algo/TP4/SortieLatex.cpp b/sem_4/Algo/TP4/SortieLatex.cpp new file mode 100644 index 0000000..b400d1a --- /dev/null +++ b/sem_4/Algo/TP4/SortieLatex.cpp @@ -0,0 +1,110 @@ +//SortieLatex.cpp + +#include +#include +#include +#include +#include + +typedef int Valeur; + +class Sommet; + +typedef Sommet* AB; + +void SortieLatex(AB Ar, std::string filepath); + +class Sommet { + protected: + Valeur racine; + AB Pere,SAG,SAD; + bool FGP; + + // Unused: + // int hauteur,balanceGmoinsD; + + public: + Sommet(Valeur v); + Sommet(Sommet& s); + + AB remonterToutEnHaut(); + + void GrefferSAG(AB g); + void GrefferSAD(AB d); + + void SupprimerSAG(); + void SupprimerSAD(); + + bool FeuilleP(); + + void RemplacerPourLePerePar(AB); + + friend std::string* TikzRecursAB(int ligne,int gauche, int droite, int numeroPere, int typeFils, AB Ar); + + +}; + +std::string* TikzRecursAB(int ligne,int gauche, int droite, int numeroPere, int typeFils, AB Ar); + + + +std::string * TikzRecursAB(int ligne,int gauche, int droite, int numeroPere, int typeFils, AB Ar){ + std::ostringstream ossnum, osslign,osscol,ossnumPere, ossbal, ossnum2Pere,ossnumRac; + + std::string stres(""); + + if (Ar) { + ossnumPere<racine << "})\\\\this=\\textcolor{red}{" <Pere << "} (FGP=\\textcolor{red}{" << (Ar->FGP?"Gauche":"Droit") <<"})"; + + if (Ar->Pere )ossnum2Pere<Pere->racine; else ossnum2Pere<<0; + + int numero; + if (typeFils==-1) { numero=1; } else { numero= 2*numeroPere + typeFils; } + ossnum<SAG) stres+=*TikzRecursAB(ligne-3,gauche,mil-13,numero,0,Ar->SAG); + if (Ar->SAD) stres+=*TikzRecursAB(ligne-3,mil+13,droite,numero,1,Ar->SAD); + } + return new std::string(stres); +} + +std::string * TikzAB(AB Ar){ + return TikzRecursAB(1,1,10,1,-1,Ar); +} + + void SortieLatex(AB Ar, std::string filepath){ //don't insert garbage in filepath, its std::system-ised. + std::ofstream fichier(filepath.c_str(), std::ios::out | std::ios::trunc); + std::string preamb ("\\documentclass{article} \n \\usepackage{tikz} \n \\begin{document} \n \\resizebox{300pt}{!}{\n \\begin{tikzpicture}\n"); + std::cout<&1 isnt enough to mute pdflatex... + system_CARE << "mkdir pdflatex_temp > /dev/null 2>&1;" + << "pdflatex -output-directory=\"./pdflatex_temp\" -interaction=nonstopmode \"" << filepath << "\" >/dev/null 2>&1;" + << "mv ./pdflatex_temp/*.pdf ./ > /dev/null 2>&1;"; + std::system(system_CARE.str().c_str()); + return; +} + + + +// g++ -c SortieLatex.cpp diff --git a/sem_4/Algo/TP4/TPArborescencesBinaires.pdf b/sem_4/Algo/TP4/TPArborescencesBinaires.pdf new file mode 100644 index 0000000..fdf4ff1 Binary files /dev/null and b/sem_4/Algo/TP4/TPArborescencesBinaires.pdf differ diff --git a/sem_4/Algo/TP4/main.cpp b/sem_4/Algo/TP4/main.cpp new file mode 100644 index 0000000..6afaf71 --- /dev/null +++ b/sem_4/Algo/TP4/main.cpp @@ -0,0 +1,24 @@ +#include +#include +#include +#include"AB.h" + +int main ( int argc, char ** argv){ + AB s1 = new Sommet(2); + AB s2 = new Sommet(4); + AB s3 = new Sommet(2); + AB s4 = new Sommet(4); + AB s5 = new Sommet(0); + AB s6 = new Sommet(0); + AB s7 = new Sommet(6); + + s5->GrefferSAG(s1); + s5->GrefferSAD(s2); + s6->GrefferSAG(s3); + s6->GrefferSAD(s4); + s7->GrefferSAG(s5); + s7->GrefferSAD(s6); + SortieLatex(s7, "test"); + return 0; +} +// La methode estFeuille est testé lors de la suppresion, donc lors des greffes. diff --git a/sem_4/Algo/TP4/prog b/sem_4/Algo/TP4/prog new file mode 100644 index 0000000..62c1884 Binary files /dev/null and b/sem_4/Algo/TP4/prog differ diff --git a/sem_4/Algo/TP4/test b/sem_4/Algo/TP4/test new file mode 100644 index 0000000..57bc262 Binary files /dev/null and b/sem_4/Algo/TP4/test differ diff --git a/sem_4/Algo/TP5/Arbo.cpp b/sem_4/Algo/TP5/Arbo.cpp new file mode 100644 index 0000000..18305d8 --- /dev/null +++ b/sem_4/Algo/TP5/Arbo.cpp @@ -0,0 +1,235 @@ +#include "Arbo.h" + +/******* Liste doublement chainee Début *******/ + +Cellule::Cellule (ContCellule A){ + fils=A; + Apres=NULL; +} + + + + +ListeCellules Cellule::EstDansListeP(ContCellule A){ + if (fils==A) return this; + if (Apres==NULL) return NULL; + return Apres->EstDansListeP(A); +} + + + +ListeCellules Cellule::AjouterSuccesseur(ContCellule A){ + if (!EstDansListeP(A)) { + ListeCellules ptCell=new Cellule(A); + ptCell->Apres=this; + return ptCell; + } + return this; +} + + + +ListeCellules Cellule::RetirerSuccesseur(ContCellule A){ + if (fils==A) return Apres; + if (!Apres) return this; + Apres=Apres->RetirerSuccesseur(A); return this; +} + + + + +/******* Liste doublement chainee Fin *******/ + + +/************Arborescence Debut*************/ + + +Sommet::Sommet(Valeur v){ + racine=v; + ListeSuccesseurs= NULL; +} + + +ListeCellules Sommet::EstSuccesseurP(Arbo A){ + if (ListeSuccesseurs){ + return (ListeSuccesseurs->EstDansListeP(A)); // à completer et decommenter + } + return NULL; +} + + + +void Sommet::AjouterSuccesseur(Arbo A){ + if ( ListeSuccesseurs && !(ListeSuccesseurs->EstDansListeP(A))){ + ListeSuccesseurs = ListeSuccesseurs->AjouterSuccesseur(A); + } + else { + ListeSuccesseurs = new Cellule (A); + } + return; +} + + + +void Sommet::RetirerSuccesseur(Arbo A){ + if (ListeSuccesseurs && ListeSuccesseurs->EstDansListeP(A)) { + ListeSuccesseurs= ListeSuccesseurs->RetirerSuccesseur(A); // à completer et decommenter + } + return; +} + +ostream& operator<<(ostream& os, Sommet& S){ + os<ListeSuccesseurs; L!=NULL;L=L->Apres){ + TraverseePrefixeRec(L->fils); + } ; // à completer et decommenter + return; +} + +/************Traversee recursive Fin*************/ + +/**********Pile Début*********/ + +Pile::Pile(){ + Sommet=NULL; +} + + +bool Pile::VideP(){ + return Sommet==NULL; +} + + +void Pile::Empiler(ContCellule A){ + Cellule* ptCellule=new Cellule(A); + ptCellule->Apres=Sommet; + Sommet=ptCellule; + return; +} + + +ContCellule Pile::Depiler(){ + Cellule* ptCellule=Sommet; + Sommet=Sommet->Apres; + return ptCellule->fils; +} + +/**********Pile Fin*********/ + +/************Traversee prefixe iterative Debut*************/ + +void TraverseePrefixeIt(Arbo A){ + Pile* P=new Pile; + P->Empiler(A); + while (!(P->VideP())){ + Arbo tmp = P->Depiler(); + cout<< *tmp; + for (ListeCellules L = tmp->ListeSuccesseurs; L!=NULL; L=L->Apres){ + P->Empiler(L->fils); + } + } + cout<Apres=ptCellule; + Entree=ptCellule; + if (! Sortie) Sortie=ptCellule; + return; +} + + +ContCellule File::Defiler(){ + Cellule* ptCellule=Sortie; + Sortie=Sortie->Apres; + return ptCellule->fils; +} + +/**********File Fin*********/ + +/************Traversee Largeur Debut*************/ + +void TraverseeLargeur(Arbo A){ + File * f= new File; + f->Enfiler(A); + while (!f->VideP()){ + A = f->Defiler(); + cout<<(*A); + for (ListeCellules tmp = A->ListeSuccesseurs; tmp != NULL; tmp=tmp->Apres){ + f->Enfiler(tmp->fils); + } + + } +} // à completer + +/************Traversee Largeur Fin*************/ + + +int main(){ + + Arbo A0 = new Sommet(0); + Arbo A1 = new Sommet(1); + Arbo A2 = new Sommet(2); + Arbo A3 = new Sommet(3); + Arbo A4 = new Sommet(4); + Arbo A5 = new Sommet(5); + Arbo A6 = new Sommet(6); + + A3->AjouterSuccesseur(A6); + A1->AjouterSuccesseur(A5); + A3->AjouterSuccesseur(A4); + A2->AjouterSuccesseur(A3); + A0->AjouterSuccesseur(A2); + A0->AjouterSuccesseur(A1); + + cout<<" rec A0 "; + TraverseePrefixeRec(A0); + cout<< endl; + cout<<" iter A0 "; + TraverseePrefixeIt(A0); + cout<< endl; + cout<<" largeur "; + TraverseeLargeur(A0); + cout<< endl; + + + A3->RetirerSuccesseur(A4); + A3->RetirerSuccesseur(A6); + //Alors, pourquoi ? pourquoi essaie t'on de retirer A5 et A2 (respectivement + //fils de A1 et de A0 ?) il y a comme un soucis... + cout<<"rec A0 apres retrait "; + TraverseePrefixeRec(A0); + cout<< endl; + cout<<" iter A0 "; + TraverseePrefixeIt(A0); + cout<< endl; + return 1; +} +//g++ -Wall Arbo.cpp -o prog diff --git a/sem_4/Algo/TP5/Arbo.h b/sem_4/Algo/TP5/Arbo.h new file mode 100644 index 0000000..4658710 --- /dev/null +++ b/sem_4/Algo/TP5/Arbo.h @@ -0,0 +1,115 @@ +#ifndef ARBO_H +#define ARBO_H + +#include +#include + +using namespace std; + +typedef int Valeur; + +struct Sommet; +typedef Sommet* Arbo; + + + +typedef Arbo ContCellule; + +/******* Liste chainee Début *******/ +struct Cellule; + +typedef Cellule* ListeCellules; + +struct Cellule{ + ContCellule fils; + ListeCellules Apres; + + Cellule (ContCellule A); + + ListeCellules EstDansListeP(ContCellule A); +// Si A apparait dans la liste, renvoie un pointeur sur la sous liste commençant par A; sinon renvoie NULL + + ListeCellules AjouterSuccesseur(ContCellule A); +// si A appartenait déjà à la liste renvoie la liste +// sinon rajoute A en tete et renvoie le nouvelle liste + + + ListeCellules RetirerSuccesseur(ContCellule A); +// renvoie la liste d'où a été retirée A s'il lui appartenait (sinon renvoie la liste initiale) +}; + +/******* Liste chainee Fin *******/ + +/************Arborescence Debut*************/ +struct Sommet { + Valeur racine; + ListeCellules ListeSuccesseurs; + + + Sommet(Valeur v); + + ListeCellules EstSuccesseurP(Arbo A); +// Si A apparait dans la liste ListeSuccesseurs, renvoie un pointeur sur la sous liste de ListeSuccesseurs commençant par A; sinon renvoie NULL + + void AjouterSuccesseur(Arbo A); +//rajoute A comme fils ainé + + void RetirerSuccesseur(Arbo A); +// si A était un fils, il cesse de l'être +}; + +ostream& operator<<(ostream& os, Sommet& S); + +/************Arborescence Fin*************/ + +/************Traversee recursive Debut*************/ + +void TraverseePrefixeRec(Arbo); + +/************Traversee recursive Fin*************/ + +/**********Pile Début*********/ +struct Pile { + ListeCellules Sommet; + + Pile(); + + bool VideP(); + void Empiler(ContCellule); + ContCellule Depiler(); // pas défini si la pile est vide +}; + +/**********Pile Fin*********/ + +/************Traversee prefixe iterative Debut*************/ + +void TraverseePrefixeIt(Arbo); + +/************Traversee prefixe iterative Fin*************/ + +/**********File Début*********/ +struct File { + ListeCellules Sortie; + ListeCellules Entree; + + File(); + + bool VideP(); + void Enfiler(ContCellule); + ContCellule Defiler(); // pas défini si la pile est vide +}; + +/**********File Fin*********/ + +/************Traversee Largeur Debut*************/ + +void TraverseeLargeur(Arbo); + +/************Traversee Largeur Fin*************/ + + + + + + +#endif diff --git a/sem_4/Algo/TP5/TPArbo.pdf b/sem_4/Algo/TP5/TPArbo.pdf new file mode 100644 index 0000000..c2b4758 Binary files /dev/null and b/sem_4/Algo/TP5/TPArbo.pdf differ diff --git a/sem_4/Algo/TP5/main.cpp b/sem_4/Algo/TP5/main.cpp new file mode 100644 index 0000000..494e997 --- /dev/null +++ b/sem_4/Algo/TP5/main.cpp @@ -0,0 +1,6 @@ +#include +#include"Arbo.h" + +int main (int argc, char ** argv){ + +} diff --git a/sem_4/Algo/TP5/prog b/sem_4/Algo/TP5/prog new file mode 100644 index 0000000..5e468bb Binary files /dev/null and b/sem_4/Algo/TP5/prog differ diff --git a/sem_4/Algo/TP6/TPTas.pdf b/sem_4/Algo/TP6/TPTas.pdf new file mode 100644 index 0000000..27bc5b7 Binary files /dev/null and b/sem_4/Algo/TP6/TPTas.pdf differ diff --git a/sem_4/Algo/TP6/Tas.h b/sem_4/Algo/TP6/Tas.h new file mode 100644 index 0000000..58dad9a --- /dev/null +++ b/sem_4/Algo/TP6/Tas.h @@ -0,0 +1,59 @@ +#ifndef TAS_H +#define TAS_H + +#include +#include + +#include "AB.h" + +typedef int indiceDansTableauSommet; + +class ArbreParfait +{ + public: + int IndicePremierSommetLibre; + int hauteur; + int* contenu; + void Echanger(indiceDansTableauSommet,indiceDansTableauSommet); + + public: + ArbreParfait(int); +// on passe la hauteur max de l'arbre, un arbre réduit à  sa racine étant de hauteur 0 + + + int AjouteSommetArbreParfait(int); +// renvoie -1 si l'ajout a échoué + +bool SommetValide(indiceDansTableauSommet); + +indiceDansTableauSommet Racine(); +bool FeuilleP(indiceDansTableauSommet); +indiceDansTableauSommet Pere(indiceDansTableauSommet); +indiceDansTableauSommet FilsGauche(indiceDansTableauSommet); +indiceDansTableauSommet FilsDroit(indiceDansTableauSommet); + +void SupprimerArbreParfait(indiceDansTableauSommet); + +}; + + +class Tas : public ArbreParfait { + public: + Tas(int); + + void Remonter(indiceDansTableauSommet); + void Descendre(indiceDansTableauSommet); + + void SupprimerTas(indiceDansTableauSommet); + + void AjouterTas(int); + + int Supmin(); + + void DescendreRecursive(indiceDansTableauSommet indiceDansTas, AB S); + + AB TasVersAB(); + +}; + +#endif diff --git a/sem_4/Algo/TP7/ArbreBinaireRecherche.cpp b/sem_4/Algo/TP7/ArbreBinaireRecherche.cpp new file mode 100644 index 0000000..ecd5af9 --- /dev/null +++ b/sem_4/Algo/TP7/ArbreBinaireRecherche.cpp @@ -0,0 +1,95 @@ +#include "ArbreBinaireRecherche.h" + +SommetABR::SommetABR(Valeur v){ + racine=v; SAG=NULL; SAD=NULL;Pere=NULL; +} + +SommetABR::SommetABR(SommetABR& s){ + racine=s.racine; SAG=NULL; SAD=NULL; + if (s.SAG) GrefferSAG(new SommetABR(*(s.SAG))); + if (s.SAD) GrefferSAD(new SommetABR(*(s.SAD))); +} + +ABR SommetABR::PlusPetit(){ + if (this->SAG==NULL){ + return this; + } + else { + return this->SAG->PlusPetit(); + } +} + +ABR SommetABR::RechercherValeur(Valeur v){ + if (this!= NULL){ + if( v < this->racine){ + this->SAG->RechercherValeur(v); + } + else if (v > this->racine){ + this->SAD->RechercherValeur(v); + } + else if ( v == this->racine){ + return this; + } + } + return NULL; +} + +void SommetABR::InsererValeur(Valeur v){ + if (v < racine){ + if (SAG!=NULL){ + SAG->InsererValeur(v); + } + else { + GrefferSAG(SommetABR(v)); + } + } + else { + if (SAD!=NULL){ + SAD->InsererValeur(v); + } + else { + GrefferSAD(SommetABR(v)); + } + } +} + +ABR SommetABR::SupMin(){ + SupprimerValeur(PlusPetit()->racine); + return this; +} + + +ABR SommetABR::SupprimerValeur(Valeur v){ + if ( this!=NULL){ + if (v < racine){ + SAG->SupprimerValeur(v); + } + else if ( v > racine){ + SAD->SupprimerValeur(v); + } + else { + this->racine = this->SAD->racine; + } + } + return NULL; +} + + + + + +int main() { + ABR A1=new SommetABR(11); + ABR A2=new SommetABR(9); + ABR A3=new SommetABR(14); + ABR A4=new SommetABR(3); + ABR A5=new SommetABR(20); + A1->GrefferSAG(A2); + A1->GrefferSAD(A3); + A2->GrefferSAG(A4); + A3->GrefferSAD(A5); + std::cout<RechercherValeur(11)< +#include + + +#include +#include + + +using namespace std; + + +typedef int Valeur; + +class SommetABR; + +typedef SommetABR* ABR; + +class SommetABR { + public: + Valeur racine; + ABR Pere,SAG, SAD; + bool FGP; + + void GrefferSAG(ABR g); + void GrefferSAD(ABR d); + + SommetABR(Valeur v); + SommetABR(SommetABR& s); + + + void SupprimerSAG(); + void SupprimerSAD(); + + bool FeuilleP(); + + void RemplacerPourLePerePar(ABR); + + std::string* TikzRecursABR(int ligne,int gauche, int droite, int numeroPere, int typeFils, ABR Ar); + +// ABR + + ABR PlusPetit(); + ABR RechercherValeur(Valeur v); + void InsererValeur(Valeur v); + ABR SupprimerValeur(Valeur v); // notez la dissym�trie + ABR SupMin(); +}; + + + //void SortieLatex(ABR, std::string filepath); + + + +#endif diff --git a/sem_4/Algo/TP7/SortieLatex.cpp b/sem_4/Algo/TP7/SortieLatex.cpp new file mode 100644 index 0000000..e5354e6 --- /dev/null +++ b/sem_4/Algo/TP7/SortieLatex.cpp @@ -0,0 +1,101 @@ +//SortieLatex.cpp + +#include +#include +#include + +typedef int Valeur; + +class SommetABR; + +typedef SommetABR* ABR; + +void SortieLatex(ABR Ar); + +class SommetABR { + protected: + Valeur racine; + ABR Pere,SAG, SAD; + + int hauteur,balanceGmoinsD; + + public: + SommetABR(Valeur v); + SommetABR(SommetABR& s); + + ABR remonterToutEnHaut(); + + void GrefferSAG(ABR g); + void GrefferSAD(ABR d); + + void SupprimerSAG(); + void SupprimerSAD(); + + bool FeuilleP(); + + void RemplacerPourLePerePar(ABR); + + friend std::string* TikzRecursABR(int ligne,int gauche, int droite, int numeroPere, int typeFils, ABR Ar); + + +}; + +std::string* TikzRecursABR(int ligne,int gauche, int droite, int numeroPere, int typeFils, ABR Ar); + + + +std::string * TikzRecursABR(int ligne,int gauche, int droite, int numeroPere, int typeFils, ABR Ar){ + std::ostringstream ossnum, osslign,osscol,ossnumPere, ossbal, ossnum2Pere,ossnumRac; + + std::string stres(""); + + if (Ar) { + ossnumPere<racine; + if (Ar->Pere )ossnum2Pere<Pere->racine; else ossnum2Pere<<0; + int numero; + if (typeFils==-1) numero=1; else numero= 2*numeroPere + typeFils; + ossnum<SAG) stres+=*TikzRecursABR(ligne -1 ,gauche,mil-1, numero,0,Ar->SAG); + if (Ar->SAD) stres+=*TikzRecursABR(ligne - 1,mil+1,droite, numero,1,Ar->SAD); + } + return new std::string(stres); +} + +std::string * TikzABR(ABR Ar){ + return TikzRecursABR(1,1,10,1, -1,Ar); +} + + + void SortieLatex(ABR Ar, std::string filepath){ //don't insert garbage in filepath, its std::system-ised. + std::ofstream fichier(filepath.c_str(), std::ios::out | std::ios::trunc); + std::string preamb ("\\documentclass{article} \n \\usepackage{tikz} \n \\begin{document} \n \\resizebox{300pt}{!}{\n \\begin{tikzpicture}\n"); + std::cout<&1 isnt enough to mute pdflatex... + system_CARE << "mkdir pdflatex_temp > /dev/null 2>&1;" + << "init_texlive;"<< "pdflatex -output-directory=\"./pdflatex_temp\" -interaction=nonstopmode \"" << filepath << "\" >/dev/null 2>&1;" + <<"mv ./pdflatex_temp/*.pdf ./ > /dev/null 2>&1;"; + std::system(system_CARE.str().c_str()); + return; +} + + + +// g++ -c SortieLatex.cpp diff --git a/sem_4/Algo/TP7/TPABR.pdf b/sem_4/Algo/TP7/TPABR.pdf new file mode 100644 index 0000000..beabb1b Binary files /dev/null and b/sem_4/Algo/TP7/TPABR.pdf differ diff --git a/sem_4/Algo/TP8/graphes.cpp b/sem_4/Algo/TP8/graphes.cpp new file mode 100644 index 0000000..fdd386a --- /dev/null +++ b/sem_4/Algo/TP8/graphes.cpp @@ -0,0 +1,108 @@ +#include +#include "./graphes.h" + + +Sommet::Sommet(){ + nbVoisins= 0; + Voisins = NULL; +} +Sommet::Sommet( int n,Sommet ** tab){ + nbVoisins = n; + Voisins = tab; +} +int Sommet::getNbVoisins(){ + return nbVoisins; +} +Sommet ** Sommet::getVoisins(){ + return Voisins; +} +void Sommet::setVoisins(Sommet ** t, int taille){ + nbVoisins = taille; + Voisins= t; +} +void Sommet::addVoisins(Sommet * s){ + nbVoisins ++; + Sommet ** tmp = new Sommet*[nbVoisins]; + for (int i = 0; i < nbVoisins-1; i ++){ + tmp[i]=Voisins[i]; + } + tmp[nbVoisins - 1 ]= s; + Voisins = tmp; +} + +void Sommet::removeSommet (Sommet * s){ + nbVoisins --; + Sommet ** tmp= new Sommet*[nbVoisins]; + int j = 0; + for (int i = 0; i < nbVoisins+1;i++){ + if (!(Voisins[i]==s)){ + tmp[j]= Voisins[i]; + j ++; + } + } + Voisins = tmp; +} +bool Sommet::estVoisin(Sommet * s){ + int i = 0; + bool found= false; + while (!found && i < nbVoisins ){ + found = (Voisins[i]==s); + } + return found; +} + +Graphe::Graphe(int n){ + nbSum = n; + Sumtab = new Sommet*[nbSum]; + for (int i = 0 ; i < nbSum; i ++){ + Sumtab[i] = new Sommet(); + } +} +Graphe::Graphe(int n, Sommet ** tab){ + nbSum = n; + Sumtab = tab; +} + +int Graphe::getNbSum(){ + return nbSum; +} +Sommet ** Graphe::getSommets(){ + return Sumtab; +} +void Graphe::setSommet(Sommet ** sum){ + Sumtab= sum; +} +void Graphe::addSommet(Sommet * s){ + nbSum++; + Sommet ** tmp = new Sommet*[nbSum]; + for (int i = 0; i < nbSum-1; i ++){ + tmp[i]=Sumtab[i]; + } + tmp[nbSum - 1 ]= s; + Sumtab = tmp; +} + +void Graphe::removeSommet(Sommet * s){ + nbSum--; + Sommet ** tmp = new Sommet*[nbSum]; + int j = 0; + for (int i = 0; i < nbSum+1; i ++){ + if (!(Sumtab[i]==s)){ + tmp[j]= Sumtab[i]; + j ++; + } + } + tmp[nbSum - 1 ]= s; + Sumtab = tmp; +} + +bool Graphe::estdansgraphearc(Sommet * s1, Sommet * s2){ + return s1->estVoisin(s2)||s2->estVoisin(s1); +} + +int main ( int argc, char ** argv){ + std::cout<<"Creation d'un graphe de 12 sommets"<