Niveau Licence Maths 1e ann

programmation impérative en C++

Posté par
jeprak34 17-05-17 à 16:54

Bonjour, je n'arrive pas bien un exercice de Programmation impérative en C++, pouvez-vous m'aider ?

Nous allons ici implémenter un tri original, le tri par panier. Celui-ci ne fonctionne que pour des tableaux d'entiers positifs. L'idée principale de ce tri est de calculer la valeur maximale x apparaissant dans un tableau T , et de générer un nouveau tableau R de x + 1 entiers. Ce tableau est construit tel que R[i] = y avec y le nombre d'occurrence de i dans le tableau T . Par exemple, pour trier le tableau T = [2; 8; 6; 4; 4; 12; 6; 4] on génère un tableau R de 13 cases tel que R = [0; 0; 1; 0; 3; 0; 2; 0; 1; 0; 1; 0; 1]. Pour cela, il suffit d'initialiser le tableau R avec que des zéros et pour chaque entier x = T [i] d'incrémenter R[x] de 1. Ensuite, en parcourant les valeurs de R[i] non nulles par indice i croissant nous obtenons les entiers triés du tableau T . Par exemple, la première valeur non nulle du tableau R est R[2] = 1, et elle indique que le plus petit élément de T est 2 et qu'il n'apparaît qu'une fois. Pareil, R[4] = 3 nous indique que le 2ème plus petit élément de T est 4 et qu'il apparaît 3 fois, etc.

1.Donner la signature d'une fonction permettant d'afficher à l'écran tous les éléments d'un tableau d'entiers positifs de taille quelconque.

2. Écrire une fonction construitTab qui, à partir d'un entier N , construit un tableau de taille N + 1 et dont toutes les cases sont initialisées à 0. Votre fonction devra renvoyer le nouveau tableau ainsi créé.

3. Écrire une fonction panier ( unsigned int T [], unsigned int N) qui renvoie le tableau R comme expli- qué précédemment.

4. Écrire la fonction triPanier (unsigned int T[], unsigned int N) qui modifie le tableau T pour le trier comme expliqué.

5. On suppose avoir à notre disposition une fonction unsigned int hasard () qui renvoie un entier positif quelconque. Écrire une fonction initT (unsigned int N, unsigned int max) qui renvoie un tableau de taille N rempli aléatoirement par des nombres compris entre 0 et max, ces deux valeurs, 0 et max, étant incluses.

6. Donner un programme principal permettant de valider l'ensemble des fonctions des questions précé- dentes. Il faudra donc demander une taille de tableau, une valeur maximale, générer un tableau avec des valeurs aléatoires, l'afficher, le trier et l'afficher à nouveau.

Voilà ce que j'ai fait :

1. void AfficheTab (unsigned x, unsigned int T[ ])

2. #include <iostream>

int construitTab (unisgned N){

int S[ ];

for (int i=0; i<N+1; i++)

             S[i] = 0;

return S;
}

3. #include <iostream>
int Panier (unsigned int T[ ], unsigned int N){

unsigned int x;
unsigned int R[x+1];
int c=0;

for (int i=0; i-1<N, i++){

         if (T[i]<= T[i+1])

                   x=T[i+1];

         else

                  x=T[i];
}

for (int i=0; i<x+1; i++){
        for (int j=0; j<N; j++){
                if (T[j] = T[j+1]){

                      c = R[i];
                      R[i] = c+1;
}}}

return R;
}

voilà, je suis vraiment pas sûre, surtout pour le 3 je m'embrouille,
ça serait gentil un peu d'aide
Merci d'avance.

Posté par re : programmation impérative en C++ 17-05-17 à 17:52

Bonjour ,

Question 2 : une fonction ne peut pas retourner un tableau .
En plus int construitTab (unisgned N){ ...      retourne un entier mais pas un tableau
Moi je passerais par l'utilisation de pointeurs  int* construitTab (unsigned N){ ...

int S[ ];   on ne peut pas déclarer un tableau statique sans donner sa taille . Moi j'utiliserai les tableaux dynamiques et la fonction  malloc (taille)

Cordialement

Posté par re : programmation impérative en C++ 17-05-17 à 20:39

#include <iostream>
#include <cstdlib>

using namespace std ;

void print(unsigned int *ptr, unsigned int n)
{
   for (unsigned int i = 0 ; i < n ; i++)
      cout << ptr[i] << " " ;

   cout << endl ;
}

Posté par re : programmation impérative en C++ 17-05-17 à 20:41

Attention à unsigned int utilise pour être cohérent avec le reste


unsigned int *construitTab(unsigned int n)
{
   unsigned int *ptr = new unsigned int[n + 1]() ;

   return(ptr) ;
}

Posté par re : programmation impérative en C++ 17-05-17 à 20:43

unsigned int *initTab(unsigned int n, unsigned int Max)
{
   unsigned int i = 0 ;

   unsigned int Min = 0 ;

   unsigned int range = Max - Min + 1 ;

   unsigned int *ptr = new unsigned int[n]() ;

   for (i = 0 ; i < n ; i++)
      ptr[i++] = rand() / 100 % range + Min ;

   return(ptr) ;
}

Posté par re : programmation impérative en C++ 17-05-17 à 20:44

void detruitTab(unsigned int *ptr)
{
delete [] ptr ;
}

Posté par re : programmation impérative en C++ 17-05-17 à 22:03

Correction en gras :


unsigned int *initTab(unsigned int n, unsigned int Max)
{
   unsigned int i = 0 ;

   unsigned int Min = 0 ;

   unsigned int range = Max - Min + 1 ;

   unsigned int *ptr = new unsigned int[n]() ;

   for (i = 0 ; i < n ; i++)
      ptr[i] = rand() / 100 % range + Min ;

   return(ptr) ;
}

Posté par re : programmation impérative en C++ 18-05-17 à 07:50

Bonjour

Ma proposition :


#include <iostream>
#include <cstdlib>      // pour rand()

using namespace std ;

// Q1 :

// -- print -------------------------------------------------------------------
//
// Description  : affichage d'un tableau
//
// Parameters   : - ptr ~ pointeur sur tableau
//                - n ~ taille tableau
//
// Return       :
//
// Notes        :
//
void print(unsigned int *ptr, unsigned int n)
{
   for (unsigned int i = 0 ; i < n ; i++)
      cout << ptr[i] << " " ;

   cout << endl ;
}

// Q2 :

// -- construitTab ------------------------------------------------------------
//
// Description  : generation d'un tableau[N + 1] nul
//
// Parameters   : - n + 1 ~ taille tableau
//
// Return       : - pointeur sur tableau[N + 1] nul
//
// Notes        :
//
unsigned int *construitTab(unsigned int n)
{
   unsigned int *ptr = new unsigned int[n + 1]() ;

   return(ptr) ;
}

// Q3

// -- panier ------------------------------------------------------------------
//
// Description  : generation d'un tableau R
//
// Parameters   : - ptr ~ pointeur sur tableau T
//                - n ~ taille tableau T
//
// Return       : - ptr ~ pointeur sur tableau R
//
// Notes        : - il serait plus simple de passer Max en argument
//
unsigned int *panier(unsigned int *ptr, unsigned int n)
{
   unsigned int i = 0 ;

   unsigned int item_max = 0 ;

   unsigned int *ptr_R ;

   // recherche de la valeur maximale des items
   for (i = 0 ; i < n ; i++)
   {
      if (ptr[i] > item_max)
      {
         item_max = ptr[i] ;
      }
   }

//   cout << " item_max = " << item_max << endl ;

   // creation d'un tableau[n+1] nul
   ptr_R = construitTab(item_max + 1) ;

   // histogramme des items
   for (i = 0 ; i < n ; i++)
   {
      ptr_R[ptr[i]] += 1;
   }

   return(ptr_R) ;
}

// Q4

// -- triPanier ---------------------------------------------------------------
//
// Description  : tri d'un tableau T
//
// Parameters   : - ptr ~ pointeur sur tableau T a trier
//                - n ~ taille tableau T a trier
//
// Return       : - ptr ~ pointeur sur tableau T trie
//
// Notes        : - il serait plus simple de passer Max en argument
//
void triPanier(unsigned int *ptr, unsigned int n)
{
   unsigned int i = 0 ;

   unsigned int r = 0 ;

   unsigned int t = 0 ;

   unsigned int item_max = 0 ;

   // recherche de la valeur maximale des items
   for (i = 0 ; i < n ; i++)
   {
      if (ptr[i] > item_max)
      {
         item_max = ptr[i] ;
      }
   }

//   cout << " item_max = " << item_max << endl ;

   // generation du tableau R
   unsigned int *ptr_R = panier(ptr, n) ;

   // affichage du tableau R
   cout << "\n tableau R = " ;

   print(ptr_R, item_max) ;
   cout << endl ;

   // tri du tableau

   // balayage du tableau R
   for  (r = 0, t = 0 ; r <= item_max ; r++)
   {
      for (i = 0 ; i < ptr_R[r] ; i++)
      {
         ptr[t++] = r ;
      }
   }
}

// Q5 :

// -- initTab -----------------------------------------------------------------
//
// Description  : generation d'un tableau T a contenu aleatoire
//
// Parameters   : - n ~ nombre d'items a generer
//                - max ~ valeur maximale des items generes
//
// Return       : - ptr ~ pointeur sur tableau T
//
// Notes        : - fait appel à rand() pour generer des items
//                   entre 0 et max
//
unsigned int *initTab(unsigned int n, unsigned int max)
{
   unsigned int i = 0 ;

   // nombres generes compris entre min et max inclus
   unsigned int min = 0 ;

   unsigned int range = max - min + 1 ;

   unsigned int *ptr = new unsigned int[n]() ;

   for (i = 0 ; i < n ; i++)
      ptr[i] = rand() / 100 % range + min ;

   return(ptr) ;
}

// Q6 : validation

// -- detruitTab --------------------------------------------------------------
//
// Description  : deallocation d'un tableau
//
// Parameters   : - ptr ~ pointeur sur tableau
//
// Return       :
//
// Notes        :
//
void detruitTab(unsigned int *ptr)
{
   delete [] ptr ;
}

int main()
{
   // pointeurs non alloues
   unsigned int *tab_T ;

   // nombre d'items
   unsigned int N = 0 ;

   // valeur maximale des items
   unsigned int Max = 0 ;

   cout << "\n Entrez le nombre d'entiers a trier  : " ;
   cin >> N ;

   cout << "\n Entrez la valeur maximale des items : " ;
   cin >> Max ;

   // generation du tableau T au contenu aleatoire
   tab_T = initTab(N, Max) ;

   // affichage du tableau T avant tri
   cout << "\n tableau T avant tri = " ;

   print(tab_T, N) ;
   cout << endl ;

   // tri du tableau dynamique
   triPanier(tab_T, N) ;

   // affichage du tableau T apres tri
   cout << "\n tableau T apres tri = " ;

   print(tab_T, N) ;
   cout << endl ;

   // destruction des tableaux dynamiques
//   detruitTab(tab_T) ;

   return(0) ;
}