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_3/algo/tp1-done/PROG_TP1/mainTP1.cpp | 65 +++++++++++ sem_3/algo/tp1-done/PROG_TP1/outilsTab.cpp | 131 ++++++++++++++++++++++ sem_3/algo/tp1-done/PROG_TP1/outilsTab.h | 74 ++++++++++++ sem_3/algo/tp1-done/PROG_TP1/sm1.dat | 10 ++ sem_3/algo/tp1-done/PROG_TP1/sm2.dat | 7 ++ sem_3/algo/tp1-done/PROG_TP1/sm3.dat | 10 ++ sem_3/algo/tp1-done/PROG_TP1/sm4.dat | 10 ++ sem_3/algo/tp1-done/PROG_TP1/tp1 | Bin 0 -> 19257 bytes sem_3/algo/tp1-done/PROG_TP1/trace1.gnu | 5 + sem_3/algo/tp1-done/PROG_TP1/trace2.gnu | 5 + sem_3/algo/tp1-done/PROG_TP1/trace3.gnu | 5 + "sem_3/algo/tp1-done/\303\251nonc\303\251TP1.pdf" | Bin 0 -> 99901 bytes 12 files changed, 322 insertions(+) create mode 100644 sem_3/algo/tp1-done/PROG_TP1/mainTP1.cpp create mode 100644 sem_3/algo/tp1-done/PROG_TP1/outilsTab.cpp create mode 100644 sem_3/algo/tp1-done/PROG_TP1/outilsTab.h create mode 100644 sem_3/algo/tp1-done/PROG_TP1/sm1.dat create mode 100644 sem_3/algo/tp1-done/PROG_TP1/sm2.dat create mode 100644 sem_3/algo/tp1-done/PROG_TP1/sm3.dat create mode 100644 sem_3/algo/tp1-done/PROG_TP1/sm4.dat create mode 100644 sem_3/algo/tp1-done/PROG_TP1/tp1 create mode 100644 sem_3/algo/tp1-done/PROG_TP1/trace1.gnu create mode 100644 sem_3/algo/tp1-done/PROG_TP1/trace2.gnu create mode 100644 sem_3/algo/tp1-done/PROG_TP1/trace3.gnu create mode 100644 "sem_3/algo/tp1-done/\303\251nonc\303\251TP1.pdf" (limited to 'sem_3/algo/tp1-done') diff --git a/sem_3/algo/tp1-done/PROG_TP1/mainTP1.cpp b/sem_3/algo/tp1-done/PROG_TP1/mainTP1.cpp new file mode 100644 index 0000000..18d30ab --- /dev/null +++ b/sem_3/algo/tp1-done/PROG_TP1/mainTP1.cpp @@ -0,0 +1,65 @@ +#include +#include +#include +#include +#include +#include +#include "outilsTab.h" + +using namespace std; + + +int main(int argc, char ** argv) +{ + int* Tab; + struct triplet res; + int sm, taille, q; + clock_t t1, t2; + + srand(time(NULL)); + printf("Numero de la question traitee (1/2/3/4) ? "); + scanf("%d",&q); + switch (q){ + case 1 : + taille=1000; + Tab=genTab(taille); + t1=clock(); sm=ssTabSomMax1(Tab,taille); t2=clock(); + cout << "\n Somme Max1 : " << sm << " tps : " << (double) (t2-t1)/ (double) CLOCKS_PER_SEC << endl; + t1=clock(); sm=ssTabSomMax2(Tab,taille); t2=clock(); + cout << "\n Somme Max2 : " << sm << " tps : " << (double) (t2-t1)/ (double) CLOCKS_PER_SEC << endl; + t1=clock(); sm=ssTabSomMax3(Tab,taille); t2=clock(); + cout << "\n Somme Max3 : " << sm << " tps : " << (double) (t2-t1)/ (double) CLOCKS_PER_SEC << endl; + t1=clock(); sm=ssTabSomMax4(Tab,taille); t2=clock(); + cout << "\n Somme Max4 : " << sm << " tps : " << (double) (t2-t1)/ (double) CLOCKS_PER_SEC << endl; + + break; + case 2 : + fichierTemps("sm1.dat", 1000, 100, ssTabSomMax1); + fichierTemps("sm2.dat", 1000, 100, ssTabSomMax2); + fichierTemps("sm3.dat", 1000, 100, ssTabSomMax3); + fichierTemps("sm4.dat", 1000, 100, ssTabSomMax4); + system("gnuplot trace1.gnu"); + fichierTemps("sm2.dat", 20000, 1000, ssTabSomMax2); + fichierTemps("sm3.dat", 20000, 1000, ssTabSomMax3); + fichierTemps("sm4.dat", 20000, 1000, ssTabSomMax4); + system("gnuplot trace2.gnu"); + fichierTemps("sm3.dat", 1000000, 100000, ssTabSomMax3); + fichierTemps("sm4.dat", 10000000, 1000000, ssTabSomMax4); + system("gnuplot trace3.gnu"); + break; + case 3 : + Tab=genTab(20); + afficheTab(Tab,20); + res=indSsTabSomMax(Tab,20); + cout << "\n somme Max : " << res.somMax << "\n debut souTab : " << res.deb << "\n fin SouTab : " << res.fin << endl; + break; + case 4 : + Tab=genTab(20); + afficheTab(Tab,20); + rangerElemNeg(Tab,20); + afficheTab(Tab,20); + break; + } + return 0; +} + diff --git a/sem_3/algo/tp1-done/PROG_TP1/outilsTab.cpp b/sem_3/algo/tp1-done/PROG_TP1/outilsTab.cpp new file mode 100644 index 0000000..6643b13 --- /dev/null +++ b/sem_3/algo/tp1-done/PROG_TP1/outilsTab.cpp @@ -0,0 +1,131 @@ +#include +#include + +#include // pour rand +#include +#include "outilsTab.h" +using namespace std; + +int* genTab(int n){ + int* t; int i; + t=new int[n]; + for (i=0;i somMax) somMax = som; + } + } + return somMax; +} + +int ssTabSomMax2(int* T, int taille){ + int somMax, som, i, j; + somMax=0; + for (i=0;i somMax) somMax = som; + } + } + return somMax; +} + +int sTSM3(int* T,int g,int d){ + int m, som, i, smgd, smdg, smm, smg, smd; + assert(g<=d); + if (g==d){ + if (T[g]>0) return T[g]; else return 0; + } + else { + m = (d+g)/2; + smg=sTSM3(T,g,m); + smd=sTSM3(T,m+1,d); + smgd=0; som=0; + for (i=m;i>=g;i--){ + som=som+T[i]; + if (som > smgd) smgd=som; + } + smdg=0; som=0; + for(i=m+1;i<=d;i++){ + som=som+T[i]; + if (som>smdg) smdg=som; + } + smm=smgd+smdg; + if ((smg>=smd) && (smg>=smm)) return smg; + else { + if (smd>=smm) return smd; + else return smm; + } + } +} + +int ssTabSomMax3(int* T, int taille){ + return sTSM3(T,0,taille-1); +} + +int ssTabSomMax4(int* T, int taille){ + int ancienplusgrand = 0; + int somme =0; + for (int i =0; i < taille; i ++) { + somme+=T[i]; + if (somme < 0 ){ + somme= 0; + } + ancienplusgrand= ancienplusgrand> somme ? ancienplusgrand : somme; + } + return ancienplusgrand; +} + +struct triplet indSsTabSomMax(int* T, int taille){ +/* A COMPLETER */ + struct triplet res; + res.somMax=0; res.deb=0; res.fin=0; + return res; +} + + +void rangerElemNeg(int* T,int taille){ +/* A COMPLETER */ + return; + +} diff --git a/sem_3/algo/tp1-done/PROG_TP1/outilsTab.h b/sem_3/algo/tp1-done/PROG_TP1/outilsTab.h new file mode 100644 index 0000000..9576c28 --- /dev/null +++ b/sem_3/algo/tp1-done/PROG_TP1/outilsTab.h @@ -0,0 +1,74 @@ +#ifndef OUTILSTAB_H_INCLUDED +#define OUTILSTAB_H_INCLUDED + +struct triplet { + int deb, fin, somMax;} ; + +int* genTab(int t); +// Renvoie un tableau de taille t, dont les éléments sont des entiers aléatoires compris entre -100 et 100 + + +void afficheTab(int* T, int t); +// Affiche les éléments de T, tableau d'entiers de taille t + + +void fichierTemps(const char* nomFic, int tMaxTab, int pasTaille, int (*fssTabSomMax)(int*, int)); +// Données nomFic une chaîne de caractères, tMaxTab et pasTaille 2 entiers positifs pasTaille < tMaxTab +// fssTabSomMax nom d'une fonction dont les données sont 1 tableau d'entiers et la taille de ce tableau et renvoyant 1 entier +// Resultat : crée un fichier de nom nomfic et pour chaque taille comprise entre pasTaille et tMaxTab (avec un pas de pasTaille), +// génère un tableau de cette taille +// execute la fonction ssTabSomMax sur ce tableau +// ajoute au fichier de nom nomfic la taille du tableau et le temps d'execution de ssTabSomMax + + +int ssTabSomMax1(int* Tab, int n); +/* + Données : Tab un tableau d'entiers de taille n + Resultat : renvoie la somme max des sous-tableaux de tab, algo de complexite O(n^3) +*/ + +int ssTabSomMax2(int*, int); + +/* + Données : Tab un tableau d'entiers de taille n + Resultat : renvoie la somme max des sous-tableaux de tab, algo de complexite O(n^2) +*/ + +int ssTabSomMax3(int* Tab, int n); +/* + Données : Tab un tableau d'entiers de taille n + Resultat : renvoie la somme max des sous-tableaux de tab, algo de complexite O(n log n) +*/ + +int ssTabSomMax4(int* Tab, int n); +/* + Données : Tab un tableau d'entiers de taille n + Resultat : renvoie la somme max des sous-tableaux de tab, algo de complexite O(n) + FONCTION A COMPLETER +*/ + +struct triplet indSsTabSomMax(int* Tab,int n); +/* + Données : Tab un tableau d'entiers de taille n + Resultat : renvoie une structure contenant + la somme max des sous-tableaux de tab, + l'indice de début d'un sous-tableau de somme max + l'indice de fin d'un sous-tableau de somme max + algo de complexite O(n) + FONCTION A COMPLETER + +*/ + + +void rangerElemNeg(int* Tab,int n); +/* + Données : Tab un tableau d'entiers de taille n + Resultat : modifie le tableau Tab de sorte que tous les éléments négatifs soient placés avant tous les éléments positifs + algo de complexite O(n) + FONCTION A COMPLETER + +*/ + + + +#endif /* OUTILSTAB_H_INCLUDED */ diff --git a/sem_3/algo/tp1-done/PROG_TP1/sm1.dat b/sem_3/algo/tp1-done/PROG_TP1/sm1.dat new file mode 100644 index 0000000..6fe54af --- /dev/null +++ b/sem_3/algo/tp1-done/PROG_TP1/sm1.dat @@ -0,0 +1,10 @@ +100 0 +200 0 +300 0.03125 +400 0.03125 +500 0.046875 +600 0.09375 +700 0.15625 +800 0.21875 +900 0.3125 +1000 0.4375 diff --git a/sem_3/algo/tp1-done/PROG_TP1/sm2.dat b/sem_3/algo/tp1-done/PROG_TP1/sm2.dat new file mode 100644 index 0000000..79cda5f --- /dev/null +++ b/sem_3/algo/tp1-done/PROG_TP1/sm2.dat @@ -0,0 +1,7 @@ +1000 0 +2000 0 +3000 0.015625 +4000 0.015625 +5000 0.03125 +6000 0.046875 +7000 0.0625 diff --git a/sem_3/algo/tp1-done/PROG_TP1/sm3.dat b/sem_3/algo/tp1-done/PROG_TP1/sm3.dat new file mode 100644 index 0000000..811f1f9 --- /dev/null +++ b/sem_3/algo/tp1-done/PROG_TP1/sm3.dat @@ -0,0 +1,10 @@ +100 0 +200 0 +300 0 +400 0 +500 0 +600 0 +700 0 +800 0 +900 0 +1000 0 diff --git a/sem_3/algo/tp1-done/PROG_TP1/sm4.dat b/sem_3/algo/tp1-done/PROG_TP1/sm4.dat new file mode 100644 index 0000000..811f1f9 --- /dev/null +++ b/sem_3/algo/tp1-done/PROG_TP1/sm4.dat @@ -0,0 +1,10 @@ +100 0 +200 0 +300 0 +400 0 +500 0 +600 0 +700 0 +800 0 +900 0 +1000 0 diff --git a/sem_3/algo/tp1-done/PROG_TP1/tp1 b/sem_3/algo/tp1-done/PROG_TP1/tp1 new file mode 100644 index 0000000..8cce618 Binary files /dev/null and b/sem_3/algo/tp1-done/PROG_TP1/tp1 differ diff --git a/sem_3/algo/tp1-done/PROG_TP1/trace1.gnu b/sem_3/algo/tp1-done/PROG_TP1/trace1.gnu new file mode 100644 index 0000000..a7f446a --- /dev/null +++ b/sem_3/algo/tp1-done/PROG_TP1/trace1.gnu @@ -0,0 +1,5 @@ +set ylabel "secondes" +plot "sm4.dat" with lines, "sm3.dat" with lines, "sm2.dat" with lines, "sm1.dat" with lines +pause -1 "Appuyez sur RETURN pour continuer" +exit + diff --git a/sem_3/algo/tp1-done/PROG_TP1/trace2.gnu b/sem_3/algo/tp1-done/PROG_TP1/trace2.gnu new file mode 100644 index 0000000..ba4de89 --- /dev/null +++ b/sem_3/algo/tp1-done/PROG_TP1/trace2.gnu @@ -0,0 +1,5 @@ +set ylabel "secondes" +plot "sm4.dat" with lines, "sm3.dat" with lines, "sm2.dat" with lines +pause -1 "Appuyez sur RETURN pour continuer" +exit + diff --git a/sem_3/algo/tp1-done/PROG_TP1/trace3.gnu b/sem_3/algo/tp1-done/PROG_TP1/trace3.gnu new file mode 100644 index 0000000..1907656 --- /dev/null +++ b/sem_3/algo/tp1-done/PROG_TP1/trace3.gnu @@ -0,0 +1,5 @@ +set ylabel "secondes" +plot "sm4.dat" with lines, "sm3.dat" with lines +pause -1 "Appuyez sur RETURN pour continuer" +exit + diff --git "a/sem_3/algo/tp1-done/\303\251nonc\303\251TP1.pdf" "b/sem_3/algo/tp1-done/\303\251nonc\303\251TP1.pdf" new file mode 100644 index 0000000..bdd788a Binary files /dev/null and "b/sem_3/algo/tp1-done/\303\251nonc\303\251TP1.pdf" differ -- cgit v1.2.3