Partage

zArray1D

Réponses

1 2 3 4 5 >>

1 février 2010 à 11:14:35

Bonjour,

Postez vos réponses à l'exercice actuel (zArray1D)ici, ça sera plus simple.
Merci.
On va réserver le topic des exercices aux énoncés, corrections, et questions concernant les exercices.

Dorénavant, à chaque nouvel exercice, j'ouvrirai un nouveau sujet portant le nom de l'exercice.

Je vais commencer par copier/coller toutes les solutions déjà proposées ici.
Moustick1991

int indexMin(int tableau[], int tailleTableau)
{
  int min = tableau[0] ,Imin = 0, i;     
    
  for(i = 0 ;i < tailleTableau ;i ++) 
  {
        if(tableau[i]<min)
        {min = tableau[i] , Imin = i;}
  }  
  
return Imin ;    
}


int indexMax(int tableau[], int tailleTableau)
{
  int max = tableau[0] ,Imax = 0, i;     
    
  for(i = 0 ;i < tailleTableau ;i ++) 
  {
        if(tableau[i]>=max)
        {max = tableau[i] , Imax = i;}
  }  
  
return Imax ;    
}

void afficherEltCommuns(int tableau1[], int tableau2[], int tailleTableau1, int tailleTableau2)
{
     int i , j ;
     
     printf("elements en commun : [");
     
     for(i = 0 ; i < tailleTableau1 ; i++)
     {
           for(j = 0 ; j < tailleTableau2 ; j++)
           {
                 if(tableau1[i] == tableau2[j])
                 {printf(" %d",tableau1[i]);j = tailleTableau2;} 
           
           }
     }  
     
     printf(" ]\n");    
}

void triCroissant(int tableau[], int tailleTableau)
{
     int i , buff;
     
     for(i = 0 ; i < tailleTableau ; i++)
     {
           buff = tableau[indexMax(tableau,tailleTableau-i)]; 
           tableau[indexMax(tableau,tailleTableau-i)] = tableau[tailleTableau-1-i];
           tableau[tailleTableau-1-i] = buff ; 
     }
}

void triDecroissant(int tableau[], int tailleTableau)
{
     int i , buff;
     
     for(i = 0 ; i < tailleTableau ; i++)
     {
           buff = *(tableau+indexMax(tableau+i,tailleTableau-i)+i); 
           *(tableau+indexMax(tableau+i,tailleTableau-i)+i) = tableau[i];
           tableau[i] = buff ; 
     }              
}

void zeroADroite(int tableau[], int tailleTableau)
{
     int i , j;
     
     for(i = tailleTableau - 1; i > -1 ; i --)
     {
           if(tableau[i] == 0)
           {
               for(j = i; i < tailleTableau - 1 && tableau[i+1] != 0; i++) 
               {tableau[j] = tableau[j+1];}
               tableau[j+1] = 0;
           }
     }
}

Adronéus

#include <stdio.h>


int       indexMin(int *, int);
int       indexMax(int *, int);
void      afficherEltCommuns(int *, int *, int, int);
void      xchang(int *, int, int);
void      triCroissant(int *, int);
void      triDecroissant(int *, int);
int       indexNul(int *, int);
void      zeroADroite(int *, int);

typedef unsigned int u_int;

int     indexMin(int *grid, int SizeGrid)
{
 int     iter;
 int     posit;

 iter = -1;
 posit = 0;
 while ( ++iter < SizeGrid )
	if ( *(grid + iter) < *(grid + posit) )
		posit = iter;
 return (posit);
}

int indexMax(int *grid, int SizeGrid)
{
 int     iter;
 int     posit;

 iter = -1;
 posit = 0;
 while ( ++iter < SizeGrid )
 	{
		if ( *(grid + iter) >= *(grid + posit) )
			posit = iter;
	}
 return (posit);
}

void    afficherEltCommuns(int *grid1, int *grid2, int Sz1, int Sz2)
{
 int     i;
 int     j;

 i = -1;
 while ( ++i < Sz1 )
	{
		j = 0;
		while ( (j < Sz2) && ((*(grid1 + i)) != (*(grid2 + j))) )
			j++;
		if ( (*(grid1 + i)) == (*(grid2 + j)) && (j != Sz2 ))
			printf("%d\n", *(grid1 + i));
	}
}

void      xchang(int *Grid, int pos1, int pos2)
{
 int     temp;

 temp = *(Grid + pos1);
 *(Grid + pos1) = *(Grid + pos2);
 *(Grid + pos2) = temp;
}

void      triCroissant(int *Grid, int SzGrid)
{
 int     min;
 int     iter;

 iter = -1;
 while ( ++iter < SzGrid )
	{
		min = indexMin(Grid + iter, SzGrid - iter);
		xchang(Grid + iter, min, 0);
	}
}

void     triDecroissant(int *Grid, int SzGrid)
{
 int     min;
 int     iter;

 iter = -1;
 while ( ++iter < SzGrid )
	{
		min = indexMax(Grid + iter, SzGrid - iter);
		xchang(Grid + iter, min, 0);
	}
}

int       indexNul(int *Grid, int SzGrid)
{
 int     iter;

 iter = -1;
 while ( ++iter < SzGrid )
	{
		if ( Grid[iter] == 0 )
			return (iter);
	}
 return (-1);
}

void      zeroADroite(int *Grid, int SzGrid)
{
 int     index;

 while ( SzGrid >= 0 )
	{
		index = indexNul(Grid, SzGrid);
		if ( index != -1 )
			{
				while ( index < SzGrid - 1 )
					{
						xchang(Grid, index, index + 1);
						index++;
					}
			}
		SzGrid--;
	}
}

Lithrein

#include <stdio.h>
#include <stdlib.h>

void aff(int *, size_t);
/* Exo 1 -- Prototypes */
size_t indexMin (int *, size_t );
size_t indexMax (int *, size_t );
/* Exo 2 -- Prototypes */
int cmpCroissant (const void *, const void *);
int cmpDecoissant (const void *, const void *);
void afficherEltCommuns (int *, size_t, int *, size_t );
/* Exo 3 -- Prototypes */
void triCroissant(int *, size_t);
void triDecroissant(int *, size_t);
/* Exo 4 -- Prototype */
void zeroADroite(int *, size_t);
/* Exo 5 -- Prototype */
void trianglePascal(int);

void
aff(int * tab, size_t size) {
    size_t i;
    for (i = 0 ; i < size; ++i)
        printf("%s%d", (0 == i)?"[":" ", tab[i]);
    printf("]\n");
}

/* Exo 1 -- Implementation */
size_t
indexMin (int * tab, size_t size) {
    size_t min;
    size_t i;

    min = 0;
    for (i = 0 ; i < size ; ++i) {
        min = (tab[min] > tab[i])? i : min;
    }
    return min;
}

size_t
indexMax (int * tab, size_t size) {
    size_t max;
    size_t i;

    max = 0;
    for (i = 0 ; i < size ; ++i) {
        max = (tab[max] < tab[i])? i : max;
    }
    return max;
}

/* Exo 2 -- Implementation */
int
cmpCroissant (const void * elem1, const void * elem2) {
    int const *p_elem1 = elem1;
    int const *p_elem2 = elem2;

    return *p_elem1 - *p_elem2;
}

int
cmpDecroissant (const void * elem1, const void * elem2) {
    int const *p_elem1 = elem1;
    int const *p_elem2 = elem2;

    return *p_elem2 - *p_elem1;
}

void
afficherEltCommuns (int * tab1, size_t size1, int * tab2, size_t size2) {
    int * inter = NULL;
    size_t i, j, k;
    /* Pas plus d'elemments communs que la taille du plus petit tableau  */
    size_t sizeInter = (size1 > size2)? size2 : size1;
    inter = malloc(sizeInter * sizeof(int));
    if (NULL == inter) {
        return;
    }

    /* On trie les tableaux  */
    qsort(tab1, size1, sizeof *tab1, cmpCroissant);
    qsort(tab2, size2, sizeof *tab2, cmpCroissant);

    i = j = k = 0;
    while (i < size1 && j < size2) {
        if (tab1[i] == tab2[j]) {
            inter[k] = tab1[i];
            ++k, ++i, ++j;
        } else if (tab1[i] > tab2[j]) {
            ++j;
        } else {
            ++i;
        }
    }

    for (i = 0 ; i < k ; ++i) {
        printf("%s%d", (0 == i)?"[":" ", inter[i]);
    }
    printf("]\n");
    free(inter);
}

/* exo 3 -- Implementation */
void
triCroissant(int *v, size_t size) {
    qsort(v, size, sizeof *v, cmpCroissant);
}

void
triDecroissant(int *v, size_t size) {
    qsort(v, size, sizeof *v, cmpDecroissant);
}

/*Exo 4 -- Implementation*/
void
zeroADroite(int * tab, size_t size) {
    int last = size-1;
    size_t i;

    for (i = 0 ; i < size ; ++i) {
        if (0 == tab[i]) {
            tab[i] = tab[i]+tab[last];
            tab[last] = tab[i]-tab[last];
            tab[i] = tab[i]-tab[last];
            --last, --size;
        }
    }
}

/* Exo 5 -- Implementation*/
void
trianglePascal(int nbLignes) {
    int triangle[100] = {1};
    size_t i, j;
    int ligne = 1;

    for (i = 0; i < nbLignes; ++i, ++ligne) {
        triangle[ligne] = 1;
        for (j = ligne-1; j >= 1; --j) {
            printf("%d ", triangle[j]);
            triangle[j] += triangle[j-1];
        }
        printf("%d\n", triangle[j]);
    }
}

int
main (void) {
    int tab1[] = {0, 0, 0, 1, 11, 2, 3, 4, 5, 256, 254, 268, 4, 3, 8, 10};
    int tab2[] = {3, 4, 5, 6,  0, 7, 0, 256, 268, 1, 3, 8, 10, 11};
    size_t size1 = sizeof tab1 / sizeof *tab1;
    size_t size2 = sizeof tab2 / sizeof *tab2;

    printf("tab1 = ");
    aff(tab1, size1);
    printf("tab2 = ");
    aff(tab2, size2);
    
    printf("\nIndice maximal de tab1 : %3lu.\n", (unsigned long int)indexMax(tab1, size1));
    printf("Indice minimal de tab1 : %3lu.\n", (unsigned long int)indexMin(tab1, size1));

    printf("\nIndice maximal de tab2 : %3lu.\n", (unsigned long int)indexMax(tab2, size2));
    printf("Indice minimal de tab2 : %3lu.\n", (unsigned long int)indexMin(tab2, size2));
    
    printf("Intersection de tab1 et tab2 :\n");
    afficherEltCommuns(tab1, size1, tab2, size2);

    printf("\nZero a droite :\n");
    zeroADroite(tab1, size1);
    zeroADroite(tab2, size2);
    printf("tab1 = ");
    aff(tab1, size1);
    printf("tab2 = ");
    aff(tab2, size2);

    printf("\nTri Croissant :\n");
    triCroissant(tab1, size1);
    triCroissant(tab2, size2);
    printf("tab1 = ");
    aff(tab1, size1);
    printf("tab2 = ");
    aff(tab2, size2);

    printf("\nTri Deroissant :\n");
    triDecroissant(tab1, size1);
    triDecroissant(tab2, size2);
    printf("tab1 = ");
    aff(tab1, size1);
    printf("tab2 = ");
    aff(tab2, size2);

    printf("\nTriangle de Pascal (17 premieres lignes) :\n");
    trianglePascal(17);

    return 0;
}

Pouet-forever

#include <stdio.h>
#include <stdlib.h>

int index(int * tab, int sz, char compar) {
	int ind = 0;
	int i;
	
	for (i = 0; i < sz; i++)
		switch (compar) {
			case '<':
				if (tab[i] < tab[ind])
					ind = i;
				break;
			case '>':
				if (tab[i] > tab[ind])
					ind = i;
				break;
			default:
				break;
		}
	
	return ind;
}

int indexMin(int * tab, int sz) {
	return index(tab, sz, '<');
}

int indexMax(int * tab, int sz) {
	return index(tab, sz, '>');
}

void afficherEltCommuns(int * tab1, int * tab2, 
                        int sz1, int sz2) {
	int i, j;
	
	for (i = 0; i < sz1; i++)
		for (j = 0; j < sz2; j++)
			if (tab1[i] == tab2[j])
				printf("%d ", tab1[i]);
	puts("");
}

void swap(int * tab, int x, int y) {
	int tmp = tab[x];
	tab[x] = tab[y];
	tab[y] = tmp;
}

void tri(int * tab, int sz, int (*ind)(int *, int)) {
	int i, id;
	
	for (i = 0; i < sz-1; i++) {
		id = ind(tab+i, sz-i);
		swap(tab, i, id+i);
	}
}

void triCroissant(int * tab, int sz) {
	tri(tab, sz, indexMin);
}

void triDecroissant(int * tab, int sz) {
	tri(tab, sz, indexMax);
}

void zeroADroite(int * tab, int sz) {
	int * fin = tab + sz;
	int * tmp = tab;
	
	for ( ; tab < fin; tab++) {
		*tmp = *tab;
		if (*tab != 0)
			tmp++;
	}
	
	for ( ; tmp < fin; tmp++)
		*tmp = 0;
}

void triangle_de_pascal(int nb_lignes) {
	int tab[100] = { 1 };
	int i, j;
	int indice = 0;
	
	for (i = 0; i < nb_lignes; i++) {
		indice++;
		tab[indice] = 1;
		for (j = indice-1; j >= 1; j--) {
			printf("%d ", tab[j]);
			tab[j] += tab[j-1];
		}
		printf("%d", tab[j]);
		puts("");
	}
}


void affiche_tab(int * tab, int sz) {
	int i;
	
	for (i = 0; i < sz; i++)
		printf("%d ", tab[i]);
	puts("");
}

#define SZ_TAB0 6
#define SZ_TAB1 5
#define SZ_TAB2 7

int main(void) {
	int tab1[SZ_TAB1] = { 3, 4, 5, 1, 2 };
	int tab2[SZ_TAB2] = { 1, 2, 3, 4, 5, 6, 7 };
	int tab0[SZ_TAB0] = { 1, 0, 4, 0, 0, -7 };
	
	printf("ind max: %d\n", indexMax(tab1, SZ_TAB1));
	printf("ind min: %d\n", indexMin(tab1, SZ_TAB1));
	printf("Elt com: ");
	afficherEltCommuns(tab1, tab2, SZ_TAB1, SZ_TAB2);
	
	printf("Tri cro: ");
	triCroissant(tab1, SZ_TAB1);
	affiche_tab(tab1, SZ_TAB1);
	
	printf("Tri dec: ");
	triDecroissant(tab1, SZ_TAB1);
	affiche_tab(tab1, SZ_TAB1);
	
	printf("Zer a d: ");
	zeroADroite(tab0, SZ_TAB0);
	affiche_tab(tab0, SZ_TAB0);
	
	printf("Tri pas:\n");
	triangle_de_pascal(10);
	return EXIT_SUCCESS;
}

TerreMinees

/*
SOLUCES D'EXOS DU SdZ par terresMinees
chuis pas un boss basez-vous pas sur mes sources 
*/

#include <stdio.h>
#include <stdlib.h>
int kEmeElt(int tableau[], int tailleTableau, const int K);
int indexMin(int tableau[], int tailleTableau);
int indexMax(int tableau[], int tailleTableau);
void afficherEltCommuns(int tableau1[], int tableau2[],
                        int tailleTableau1, int tailleTableau2);
void copie(int tableauOriginal[], int tableauCopie[], int tailleTableau);


int main(int argc, char *argv[])
{
    int tab[10] = {9, 50, 9, 17, 150, 641, 25, 874, 945, 156};
    int tab_2[10] = {8, 25, 65, 98, 12, 24, 39, 85, 75, 26};
    const int K = 6;
    int result = 0, i;

    result = kEmeElt(tab, 10, K);
    printf("[%d PLUS GRAND INDEX DU TAB : %d]\n\n", K, result);

    printf("CONTENU DU TAB\n========\n");
    for (i = 0 ; i < 10 ; i++)
    {
        printf("%d\n", tab[i]);
    }
    printf("========\n");
    int index_min_tab = indexMin( tab, 10);
    printf("[INDEX MIN DU TAB == %d ==]", index_min_tab);

    printf("[LISTE ELEMENTS COMMUNS\n");

    afficherEltCommuns(tab, tab_2,
                        10, 10);
    printf("]\n");

    return 0;
}

// ====================== FUNCTIONS =======================

// EXO 1
int indexMin(int tableau[], int tailleTableau)
{
    int index_min = tableau[0], i;
    for (i = 0 ; i < tailleTableau ; i++)
    {
        if(tableau[i] < index_min)
        {
            index_min = tableau[i];
        }
    }
    return index_min;
}


int indexMax(int tableau[], int tailleTableau)
{
    int index_max = tableau[0], i;
    for (i = 0 ; i < tailleTableau ; i++)
    {
        if(tableau[i] < index_max)
        {
            index_max = tableau[i];
        }
    }
    return index_max;
}

//=======================================
//EXO 2
//AFFICHE LES éLéMENTS COMMUNS
void afficherEltCommuns(int tableau1[], int tableau2[],
                        int tailleTableau1, int tailleTableau2)
{
    int i, j, taillePlusGrandTab, tab_grand[], tab_petit[];
    if(tailleTableau1 < tailleTableau2)
    {
        taillePlusGrandTab = tailleTableau2;
        copie(tab_grand, tableau2, tailleTableau2)
        copie(tab_petit, tableau1, tailleTableau1)
    }
    else
    {
        taillePlusGrandTab = tailleTableau1;
        copie(tab_grand, tableau1, tailleTableau1)
        copie(tab_petit, tableau2, tailleTableau2)
    }


    for(j= 0;j < taillePlusGrandTab;j++)
    {
        for(i= 0;i < taillePlusGrandTab;i++)
        {
            if(tab_grand[j] == tab_petit[i])
            {
                printf("%d\n", tab_grand[j]);
            }
        }
    }
}


//==========================================
// EXO 7
//RETOURNE LE Kieme PLUS GRAND INDICE DU TAB

int kEmeElt(int tableau[], int tailleTableau, const int K)
{
    int i, j;


    for(j= 0;j < tailleTableau;j++)
    {
        for(i= 0;i < tailleTableau;i++)
        {
            if(tableau[j] > tableau[i])
            {
                int sauvegarde = tableau[j];
                tableau[j] = tableau[i];
                tableau[i] = sauvegarde;
            }
        }
    }


    return tableau[K-1];
}
void copie(int tableauOriginal[], int tableauCopie[], int tailleTableau)
{
    int i;
    for (i = 0 ; i < tailleTableau ; i++)
    {
        tableauOriginal[i] = tableauCopie[i];
    }
}

Je pense n'avoir oublié personne.

Zeste de Savoir, le site qui en a dans le citron !

Adroneus

1 février 2010 à 12:21:19

Je tiens a dire quand même (bon je l'ai pas fait pour respecter les protos mais j'ai eu l'idée, d'où le u_int) que pour les index, on aurait pu utiliser des unsigned

candide

1 février 2010 à 12:42:47

Citation : Adroneus

Je tiens a dire quand même (bon je l'ai pas fait pour respecter les protos mais j'ai eu l'idée, d'où le u_int) que pour les index, on aurait pu utiliser des unsigned

C'est pour moi une complication car le mélange signé/non signé est source de nombreux problèmes à cause de conversions implicites. Disons que la question est controversée. Déjà, pour une meilleure portabilité, utiliser plutôt le type standard (non signé) size_t.

moustick1991

1 février 2010 à 14:18:49

Suite aux conseils donnés par mob, je modifie mon exercice 3 :

void triCroissant(int tableau[], int tailleTableau)
{
     int i , buff , index;
     
     for(i = 0 ; i < tailleTableau ; i++)
     {
           index = indexMax(tableau,tailleTableau-i);
           buff = tableau[index]; 
           tableau[index] = tableau[tailleTableau-1-i];
           tableau[tailleTableau-1-i] = buff ; 
     }
}

void triDecroissant(int tableau[], int tailleTableau)
{
     int i , buff , index ;
     
     for(i = 0 ; i < tailleTableau ; i++)
     {
           index = indexMax(tableau+i,tailleTableau-i)+i ;
           buff = *(tableau+index); 
           *(tableau+index) = tableau[i];
           tableau[i] = buff ; 
     }              
}

Tosh

1 février 2010 à 14:52:45

Voilà mon premier jet pour cet exercice (Pas commenté, désolé) :

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

void afficherTableau (int tableau[], int taille)
{
   int i;

   puts ("");
   for (i = 0; i < taille; i++)
   {
      printf ("%d ", tableau[i]);
   }
   puts ("");
}

int indexMin (int tableau[], int tailleTableau)
{
   int min = 0;
   int i;
   for (i = 0; i < tailleTableau; i++)
   {
      if (tableau[min] > tableau[i])
         min = i;
   }

   return min;
}

int indexMax (int tableau[], int tailleTableau)
{
   int max = tailleTableau - 1;
   int i;
   for (i = tailleTableau - 1; i >= 0; i--)
   {
      if (tableau[max] < tableau[i])
         max = i;
   }
   return max;
}

void afficherEltCommuns (int tableau1[], int tableau2[], int tailleTableau1,
                         int tailleTableau2)
{
   int i, j;
   int max_taille =
      (tailleTableau1 > tailleTableau2) ? tailleTableau2 : tailleTableau1;

   for (i = 0; i < max_taille; i++)
   {
      for (j = 0; j < max_taille; j++)
      {
         if (tableau1[i] == tableau2[j])
         {
            printf ("%d ", tableau1[i]);
         }
      }
   }
   puts ("");
}

void triCroissant (int tableau[], int tailleTableau)
{
   int i, indice = tailleTableau - 1, max, tmp;
   for (i = 0; i < tailleTableau; i++, indice--)
   {
      max = indexMax (tableau, indice + 1);
      tmp = tableau[indice];
      tableau[indice] = tableau[max];
      tableau[max] = tmp;
   }
}

void triDecroissant (int tableau[], int tailleTableau)
{
   int i, min, tmp, indice = tailleTableau-1;
   for (i = 0; i < tailleTableau; i++, indice--)
   {
      min = indexMin (tableau, indice+1);
      tmp = tableau[indice];
      tableau[indice] = tableau[min];
      tableau[min] = tmp;
   }
}

void zeroADroite (int tableau[], int tailleTableau)
{
   int i, j;
   for (i = 0; i < tailleTableau - 1; i++)
   {
      for (j = 0; j < tailleTableau - 1; j++)
      {
         if (!tableau[j])
         {
            tableau[j] = tableau[j + 1];
            tableau[j + 1] = 0;
         }
      }
   }
}

void TrianglePascal (int n)
{
   int i, j, indice = 1, k;
   int *tab_lect = malloc (n * sizeof (int));
   int *tab_ecr = malloc (n * sizeof (int));
   if (tab_ecr == NULL || tab_lect == NULL)
      exit (1);

   for (i = 0; i < n; i++)
   {
      for (j = 0; j < indice; j++)
      {
         if (j == 0 || j == indice - 1)
         {
            printf ("%5d", 1);
            tab_ecr[j] = 1;
         }
         else
         {
            printf ("%5d", tab_lect[j - 1] + tab_lect[j]);
            tab_ecr[j] = tab_lect[j - 1] + tab_lect[j];
         }
      }
      for (k = 0; k < indice; k++)
      {
         tab_lect[k] = tab_ecr[k];
      }
      puts ("");
      indice++;
   }
   free (tab_lect);
   free (tab_ecr);
}

int mode (int tableau[], int tailleTableau)
{
   int mode;
   return mode;
}

int kEmeElt (int tableau[], int tailleTableau, int k)
{
   int *tableau_tmp = malloc (tailleTableau * sizeof (int));
   if (tableau_tmp == NULL)
      exit (1);
   memcpy (tableau_tmp, tableau, tailleTableau * sizeof (int));
   triCroissant (tableau_tmp, tailleTableau);
   free (tableau_tmp);
   return tableau_tmp[k];
}

int main (void)
{
   int tableau1[] = { 5, 15, -25, 0, 15, -25 };
   int tableau2[] = { 0, 1, 10, 1, 3, 5 };
   int tableau3[] = { 10, 1, 11, 7, 98, 8, 7, 8 };

   printf ("**********MIN/MAX***************\n");
   printf ("MIN : %d\n", indexMin (tableau1, 6));
   printf ("MAX : %d\n", indexMax (tableau1, 6));

   printf ("**********EltCommuns************\n");
   afficherEltCommuns (tableau2, tableau3, 6, 8);

   printf ("**********Decroissant***********\n");
   triDecroissant (tableau1, 6);
   afficherTableau (tableau1, 6);

   printf ("**********Croissant*************\n");
   triCroissant (tableau1, 6);
   afficherTableau (tableau1, 6);

   printf ("**********0 a droite************\n");
   zeroADroite (tableau1, 6);
   afficherTableau (tableau1, 6);

   printf ("**********kEmeElt***************\n");
   int i;
   for (i = 0; i < 6; i++)
   {
      printf ("avec k = %d -> %d\n", i, kEmeElt (tableau2, 6, i));
   }
   printf ("**********Triangle Pascal*******\n");
   TrianglePascal(15);
   return 0;
}

Bon, ce n'est pas très optimisé, et je ne suis pas satisfait de ma fonction afficherEltCommuns(), je ferais la suite des exercices si j'ai un peu de temps

Arthurus

1 février 2010 à 16:37:51

Ma version pour l'exo 6 en utilisant une table de hashage.
(petite différence avec le sujet, si 2 éléments ont le même nombre d'occurrence, c'est le premier qui atteint le max d'occurrence qui est renvoyé).

#include <stdio.h>
#include <stdlib.h>

#define MAX_HASH 10

typedef struct liste {
	int val;
	int occ;
	struct liste *next;
} liste;

int hash_code(int i, int t) 
{
	return i%t;
}

int maj_table(liste* hash_a[], int taille_hash, int val) 
{
	int occ;
	liste *cour = hash_a[hash_code(val,taille_hash)];
	liste *tmp = hash_a[hash_code(val,taille_hash)];
	for (; cour && cour->val != val;cour = cour->next);
	if (cour) {
		occ = ++(cour->occ);
	} else {
		cour = malloc(sizeof(liste));
		cour->val = val;
		cour->occ = 1;
		cour->next = tmp;
		hash_a[hash_code(val,taille_hash)] = cour;
		occ = 1;
	}
	return occ;
}

int mode (int tab[], int t)
{
	liste *hash_table[MAX_HASH] = {NULL};
	int val = -1;
	int occ = 0;
	int tmp;
	int i;
	for (i=0; i<t; i++) {
		tmp = maj_table(hash_table,MAX_HASH,tab[i]);
		if (tmp > occ) {
			val = tab[i];
			occ = tmp;
		}
	}
	return val;
}

int main (void) 
{
	int tab[] = {0,3,5,4,6,3,5,5,2,5,4};
	printf("%d\n",mode(tab,11));
	return 0;
}

TerresMinees

1 février 2010 à 17:13:51

A préciser au-dessus de mon code qu'il est incomplet.
(j'ai pas terminé le 2 par exemple, d'autres n'ont pas été MàJé etc.)

GurneyH

1 février 2010 à 17:31:02

@moustick1991 et Tosh: vous devriez vous servir de la fonction indexMin pour le tri décroissant. C'est demandé de faire les 2 tris avec la fonction indexMax dans l'énoncé, mais le code est moins naturel... J'edite l'énoncé.

@TerreMinees: Pour ton code, même s'il n'est pas terminé, ce n'est pas grave, au final j'éditerais le premier post avec les derniers.

@Arthurus, quelle taille doit on attribuer à la table de hashage en fonction de la taille du tableau. Avec un tableau de taille 10¨8 éléments, par exemple?

J'ai édité l'énoncé, pour le cas ou plusieurs éléments on le même nombre d'occurrence.
Retourner l'élément le plus petit, est trop dirigiste sur l'algo à utiliser. Je laisse le choix, finalement.

Zeste de Savoir, le site qui en a dans le citron !

Tosh

1 février 2010 à 17:37:26

J'ai édité mon premier post. J'ai aussi rajouté la fonction du triangle de Pascal, mais je n'ai pas réussis à n'utiliser qu'un seul tableau...Je vais tenter d'y remédier

GurneyH

1 février 2010 à 17:50:46

Citation : Tosh

J'ai édité mon premier post. J'ai aussi rajouté la fonction du triangle de Pascal, mais je n'ai pas réussis à n'utiliser qu'un seul tableau...Je vais tenter d'y remédier

Il n'est pas demandé de n'utiliser qu'un seul tableau

Citation : Gurneyh

Rappelez vous que l'exercice porte sur les tableaux à 1 dimension.
Le but est ici, d'arriver à construire la ligne courante à partir de la précédente sans copie d'éléments, simplement par échange...

Ce qu'il faut éviter c'est pour n lignes, d'utiliser une matrice de n * n.

Zeste de Savoir, le site qui en a dans le citron !

Arthurus

1 février 2010 à 20:19:16

Citation : GurneyH

@Arthurus, quelle taille doit on attribuer à la table de hashage en fonction de la taille du tableau. Avec un tableau de taille 10¨8 éléments, par exemple?

y a aucun rapport entre la taille du tableau et la taille de la table

Avec une taille quelconque de la table de hashage, ça devrait marcher (si ça marche pas chez toi, c'est bug)

BZH76

1 février 2010 à 21:21:01

Bonsoir , voici mes réponses pour les exercices de 1 à 4 , en mode tableau, le formalisme pointeur viendra et j'éditerais si besoin. Certains de mes algos me semblent bancals mais réalisent leurs fonctions (les élements communs en particulier ).

J'avoue bloqué sur le triangle de pascal, il me résiste et je dois manquer d'imagination pour réussir à l'implémenter facilement.

Je profite de ce post , pour remercier GurneyH pour le temps qu'il prend à créer ces sujets et les corrections plus que complètes.

Chapeau aussi aux " avancés " qui fournissent des codes qui donnent mal à la tête à la première lecture mais qui permettent de bien mieux voir l'étendu du C.

int indexMax(int tab[], int tailleTab)
{
    int i=0,max,indexmax;
    max=tab[i];
    indexmax=i;
    for (i=0;i<tailleTab;i++)
    {
        if (max<tab[i])
        {
            max=tab[i];
            indexmax=i;
        }
    }
    return indexmax;
}
int indexMin(int tab[], int tailleTab)
{
    int i=0,min,indexmin;
    min=tab[i];
    indexmin=i;
    for (i=0;i<tailleTab;i++)
    {
        if (min>tab[i])
        {
            min=tab[i];
            indexmin=i;
        }
    }
    return indexmin;
}

void afficherEltCommuns(int tab1[], int tab2[],int tailleTab1, int tailleTab2)
{
    int i,j,k=0,max;

    if (tailleTab1>tailleTab2)
    {
        max=tailleTab1;
    }
    else
    {
        max=tailleTab2;
    }

    int tabElemComm[max];

    for (i=0;i<tailleTab1;i++)
    {
        for (j=0;j<tailleTab2;j++)
        {
            if (tab1[i]==tab2[j])
            {
                tabElemComm[k]=tab1[i];
                k++;
            }
        }
    }
    printf("\nil y a %d elements communs [ ",k);
    for (i=0;i<k;i++)
    {
        printf("%d ",tabElemComm[i]);
    }
    printf("]\n");

}
void triCroissant(int tab[], int tailleTab)
{
    int idmax;
    int tmp;
    int i=0;
    for (i=0;i<tailleTab ;i++)
    {
        idmax=indexMax(tab,tailleTab-i);
        tmp=tab[tailleTab-i-1];
        tab[tailleTab-i-1]=tab[idmax];
        tab[idmax]=tmp;
    }
}

void triDecroissant(int tab[], int tailleTab)
{
    int idmin;
    int tmp;
    int i=0;
    for (i=0;i<tailleTab ;i++)
    {
        idmin=indexMin(tab,tailleTab-i);
        tmp=tab[tailleTab-i-1];
        tab[tailleTab-i-1]=tab[idmin];
        tab[idmin]=tmp;
    }
}

void zeroADroite(int tab[], int tailleTab)
{
    int i,j,k=0;
    for (i=0;i<tailleTab-k ;i++)
    {
        if (tab[i]==0)
        {
            for (j=i;j<tailleTab-k;j++)
            {
                tab[j]=tab[j+1];
            }
            tab[tailleTab-k-1]=0;
            k++;i--;
        }
    }
}

moustick1991

1 février 2010 à 22:47:18

@BZH76 : Un post à été créé sur le forum pour mettre les réponses .

Citation : GurneyH

@moustick1991 et Tosh: vous devriez vous servir de la fonction indexMin pour le tri décroissant. C'est demandé de faire les 2 tris avec la fonction indexMax dans l'énoncé, mais le code est moins naturel... J'edite l'énoncé.

Je me disait aussi ... Je me suis plus creusé la tête :lol:

.Mais , c'était pas mal non plus comme exercice

. Avec la fonction indexMin , c'est beaucoup plus simple ...

Merci , j'éditerais si j'ai le temps (j'essaye d'écrire un tuto en ce moment).

Pouet_forever

1 février 2010 à 22:54:45

Citation : moustick1991

@BZH76 : Un post à été créé sur le forum pour mettre les réponses .

Oui et c'est celui-là :lol:

Arthurus

1 février 2010 à 22:57:24

Citation : Pouet_forever

Citation : moustick1991

@BZH76 : Un post à été créé sur le forum pour mettre les réponses .

Oui et c'est celui-là

moustick1991

1 février 2010 à 23:00:46

Citation : Athurus

Citation : Pouet_forever

Citation : moustick1991

@BZH76 : Un post à été créé sur le forum pour mettre les réponses .

Oui et c'est celui-là

Désolé , la fatigue

GurneyH

2 février 2010 à 4:02:44

Citation : Arthurus

Citation : GurneyH

@Arthurus, quelle taille doit on attribuer à la table de hashage en fonction de la taille du tableau. Avec un tableau de taille 10¨8 éléments, par exemple?

y a aucun rapport entre la taille du tableau et la taille de la table
Avec une taille quelconque de la table de hashage, ça devrait marcher (si ça marche pas chez toi, c'est bug)

J'avoue que j'ai du mal à comprendre... Si tu restes, avec une valeur de 10, pour la taille de hashage, tu vas avoir pas mal de collisions, donc pas mal d'ajout dans la liste chaînée.

Il doit bien y avoir des tailles plus favorables que d'autres.

Je vais faire des tests.

Je confirme, pour de très grand tableaux, le choix du nombre d'entrées dans la table est primordial, sinon tu passes ton temps à parcourir les listes...
Avec un nombre d'entrée suffisant, par contre, les performances sont très bonne.)

Zeste de Savoir, le site qui en a dans le citron !

Arthurus

2 février 2010 à 9:04:46

Pour des perf optimales, il faut prendre MAX_HASH égal au max des éléments du tableau.

mob

2 février 2010 à 9:18:04

Salut.
Je n'avais jamais essayé de calculer et stocker le triangle de pascal dans un tableau 1D, c'est pour ça que j'ai décidé de faire l'exercice 5 :

Première méthode : Le code ne me plait pas beaucoup, j'espère que les commentaires aident à la compréhension :

#include <stdio.h>

void print_tab(int t[], int);

int
main(void)
{
#define DIM 17
        
        /*
         * On utilise un tableau à une dimension pour calculer
         * et afficher le triangle de pascal. On peut y penser 
         * comme un tableau à deux dimensions où la case (lig, col)
         * est à l'index [lig*NB_COL + col].
         */
        int t[DIM * DIM] = {0};
        int lig, col;
        int cur_ind, above_ind;

        lig = col = 0;
        while (lig < DIM)
        {
                /* Indice de l'élément qu'on cherche à calculer */
                cur_ind = lig * DIM + col;
                /* Indice de l'élément juste au dessus dans le triangle */
                above_ind = (lig-1) * DIM + col;
                
                if (col == 0 || col == lig)
                        t[cur_ind] = 1;
                else if (col <= lig)
                        t[cur_ind] = t[above_ind - 1] + t[above_ind];

                /* Si on est en fin de ligne */
                if (col == lig)
                {
                        col = 0;
                        lig++;
                }
                else
                        col++;
        }
        
        print_tab(t, DIM);
        
        return 0;
}

void
print_tab(int t[], int dim)
{
        int col, lig;
        int cur_ind;

        lig = col = 0;
        while (lig < dim)
        {
                cur_ind = lig * dim + col;
                
                if (col <= lig)
                        printf("%d\t", t[cur_ind]);

                /* Fin de ligne */
                if (col == lig)
                {
                        printf("\n"); 
                        col = 0;
                        lig++;
                }
                else
                        col++;
        }
}

Après avoir fait l'exercice, je suis allé voir wikipédia et j'ai trouvé une méthode assez simple et peu couteuse, par ici : http://en.wikipedia.org/wiki/Pascal%27s_triangle#Calculating_an_individual_row. Implémentation :

#include <stdio.h>

void print_row(float *, int);

int
main(void)
{
#define DIM 17
        
        float t[DIM] = {0};
        int lig, col;
        float coeff;
        
        lig = col = 0;
        while (lig < DIM)
        {
                if (col == 0)
                        t[col] = 1;
                else
                {
                        coeff = ((lig + 1 - col) / (float)col);
                        t[col] = t[col - 1] * coeff;
                }

                if (col == lig)
                {
                        print_row(t, col);
                        col = 0;
                        lig++;
                }
                else
                        col++;
        }

        return 0;
}

void
print_row(float t[], int last)
{
        int i;

        for (i = 0; i <= last; i++)
                printf("%.0f\t", t[i]);
        printf("\n");
        
}

Pour l'exercice 7, j'ai essayé d'implémenter un algorithme auquel j'avais réfléchis, mais je n'ai toujours pas réussi à le débuguer. De toutes façons j'ai vu après qu'il était déjà connu et utilisé, et pas très performant. C'est une sorte de tri par selection partiel.

J'ai donc décidé d'implémenter un algorithme présenté sur wikipédia qui lui est plutôt une sorte de quicksort partiel. Par ici : http://en.wikipedia.org/wiki/Selection_algorithm#Partition-based_general_selection_algorithm. Le code :

#include <stdio.h>
#include <stdlib.h>

int partition(int *, int, int, int);
int kth_min(int *, int, int);
void swap(int *, int, int);

int
main(void)
{
#define N 6
#define M 100000000

        int k, res, i;
        int t[N] = {0, 1, 10, 1, 3, 5};
        int *p;

        if ((p = malloc(M * sizeof *p)) == NULL)
                return EXIT_FAILURE;

        for (k = 0; k <= 5; k++)
        {
                res = kth_min(t, k, N);
                printf("%d-th minimum of t : %d\n", k, res);
        }
        printf("\n");

        for (i = 0; i < M; i++)
                p[i] = i;

        k = 5;
        res = kth_min(p, k, M);
        printf("%d-th minimum of q : %d\n", k, res);

        free(p), p = NULL;
        
        return 0;

}

int
kth_min(int t[], int k, int size)
{
        int left, right, mid;
        int piv_ind;
        
        left = 0;
        right = size-1;
        while (left <= right)
        {
                mid = (left + right) / 2;
                piv_ind = partition(t, left, right, mid);
                if (k == piv_ind)
                        return t[k];
                else if (k < piv_ind)
                        right = piv_ind - 1;
                else
                        left = piv_ind + 1;
        }

        return -1;
}

/*
 * Partitionne le tableau en une partie dont les élements
 * sont plus petits que le pivot, une autre avec les élements
 * plus grand, et renvoie l'indice du nouveau pivot.
 */
int
partition(int t[], int left, int right, int pivot)
{
        int i, piv_new_ind;
        
        swap(t, right, pivot);
        piv_new_ind = left;
        for (i = left; i < right - 1; i++)
        {
                if (t[i] < t[pivot])
                {
                        swap(t, piv_new_ind, i);
                        piv_new_ind++;
                }
        }

        swap(t, piv_new_ind, right);

        return piv_new_ind;
}

void
swap(int t[], int i, int j)
{
        int temp;

        temp = t[i];
        t[i] = t[j];
        t[j] = temp;
}

Il y a un code de test pour l'entrée fournit par GurneyH, et un autre pour tester un tableau de 10^8 éléments, pour voir si ça tient la charge.

Pour mon tableau de test, le code est très rapide, mais ça semble être un cas particulier. En effet si je remplace p[i] = i par p[i] = INT_MAX - i à la ligne 29, le code devient très lent à mesure que k augmente. Pire encore, je commence à avoir des valeurs incorrectes en sorties, qui sont décalées de 5*(M/100) par rapport à la valeur qui devrait être renvoyée. Je ne sais pas d'où proviennent ces erreurs.

Tout commentaire sur le code est aussi le bienvenue.

EDIT : En essayant avec un remplissage plus aléatoire du tableau :

srand((unsigned) time(NULL));
for (i = 0; i < M; i++)
        p[i] = rand();

et avec k = 193284 et M = 10^8 c'est assez performant :

time ./out
0-th minimum of t : 0
1-th minimum of t : 1
2-th minimum of t : 1
3-th minimum of t : 1
4-th minimum of t : 5
5-th minimum of t : 10

193284-th minimum of q : 4161575

real    0m2.897s
user    0m2.556s
sys     0m0.324s

Par contre je ne suis absolument pas certain que la valeur retournée est juste...

darkipod

2 février 2010 à 11:47:44

bonjour,
j'ai fait les premiers exos du mois de fevrier avec une solution versus "tableaux" parce que je suis plus à l'aise que les pointeurs.

je m'engage, à fournir un peu plus tard la version pointeurs

Néanmoins je suis pas satisfait de deux exos :
-celui qui concerne de trouver deux elements identiques dans deux tableaux, j'ai une solution partielle!
et j'ai pas trouve comment faire differemment
- celui qui concerne le zero a droite, je pense avoir trouve une solution mais elle me parait......
enfin je vous laisse juger ici :

#include <stdio.h>
#include <stdlib.h>

int indexMin(int tableau[], int tailleTableau);
int indexMax(int tableau[], int tailleTableau);
void afficherEltCommuns(int t1[], int t2[],int tailleTableau1,int tailleTableau2);
void affiche(int tableau[], int tailleTableau);
void triCroissant(int tableau[], int tailleTableau);
void triDecroissant(int tableau[], int tailleTableau);
void zeroADroite(int tableau[], int tailleTableau);





int main(void)
{
    int tableau[] = {1, 0, 4, 0, 0, -7};
    int tableau1[] = {0, 1, -1, 3, 8};
    int tableau2[] = {10, 1, 11, 7, 98, 8, 7, 8};
    // taille du tableau / taille d'un element = nombre d elements
    int tailleTableau = sizeof (tableau) / sizeof (int);
    int tailleTableau1 = sizeof (tableau1) / sizeof (int);
    int tailleTableau2 = sizeof (tableau2) / sizeof (int);

    printf("n de l'index du chiffre le plus petit : %d\n",indexMin(tableau,tailleTableau));//exo1
    printf("n de l'index du chiffre le plus grand : %d\n",indexMax(tableau,tailleTableau));//exo2
    afficherEltCommuns(tableau1, tableau2,tailleTableau1,tailleTableau2);//exo3

    printf("\ntableau a trier :");//exo 4
    affiche (tableau1,tailleTableau1);
    triCroissant(tableau1,tailleTableau1);
    printf("\ndans l'ordre croissant :");
    affiche (tableau1,tailleTableau1);
    triDecroissant(tableau1,tailleTableau1);
    printf("\ndans l'ordre decroissant :");
    affiche (tableau1,tailleTableau1);

    printf("\n\n exo ZERO a droite :");
    affiche (tableau,tailleTableau);
    zeroADroite(tableau,tailleTableau);
    affiche (tableau,tailleTableau);


    return 0;
}

int indexMin(int tableau[], int tailleTableau)
{
    int resultat=0;
    int i,j;
    j= tableau[0];
    for (i=1;i<tailleTableau;i++)
    {
        if (j>tableau[i])
        {
            resultat = i ;
            j=tableau[i];
        }
    }
    return resultat;
}

int indexMax(int tableau[], int tailleTableau)
{
    int resultat=0;
    int i,j;
    j= tableau[0];
    for (i=1;i<tailleTableau;i++)
    {
        if (j<tableau[i])
        {
            resultat = i;
            j=tableau[i];
        }
    }
    return resultat;
}

void afficherEltCommuns(int t1[], int t2[],int tailleTableau1,int tailleTableau2)
// a ameliorer resultat pas conforme a ce qui est demande
{
    int i, j;
    printf("les elements identiques des deux tableaux sont : ");
    for (i=0;i<tailleTableau1;i++)
    {
        for (j=0;j<tailleTableau2;j++)
        {
            if (t1[i] == t2[j])
            {
                printf(" %d ",t1[i]);
            }
        }
    }
    printf("\n");
}

void affiche(int tableau[], int tailleTableau)
{
    int i;
    printf("\n");
    for (i=0;i<tailleTableau;i++)
    {
        printf (" %d ",tableau[i]);
    }
}
void triCroissant(int tableau[], int tailleTableau)
{
    /*
        1.On recherche l'index de la valeur maxi
        2.On insère l'élément max à la bonne position dans le tableau
        3.On répète les 2 premières opérations sur le reste du tableau tant que le tableau n'est pas entièrement trié
    */
    int index,echange,i;
    for (i=0;i<tailleTableau;i++)
    {
        index =indexMax(tableau, tailleTableau-i);
        echange = tableau[index];
        tableau[index]=tableau[tailleTableau -i-1];
        tableau[tailleTableau - i-1] = echange;
    }
}

void triDecroissant(int tableau[], int tailleTableau)
{
    /*
        1.On recherche l'index de la valeur mini
        2.On insère l'élément max à la bonne position dans le tableau
        3.On répète les 2 premières opérations sur le reste du tableau tant que le tableau n'est pas entièrement trié
    */
    int index,echange,i;
    for (i=0;i<tailleTableau;i++)
    {
        index =indexMin(tableau, tailleTableau-i);
        echange = tableau[index];
        tableau[index]=tableau[tailleTableau -i-1];
        tableau[tailleTableau - i-1] = echange;
    }
}

void zeroADroite(int tableau[], int tailleTableau)
{
    int i,j,k;
    i=0;
    k=0;//compteur de boucle secondaire
    while ((i<tailleTableau)&&(k<tailleTableau))//pas trouve autre chose pour eviter une boucle infinie i+k tour maximum
    {
        if (tableau[i]==0)
        {
            //alors on decale vers la droite
            for (j=i;j<(tailleTableau-1);j++)
            {
                tableau[j]=tableau[j+1];
            }
            k++;
            tableau[tailleTableau-1]=0;
        }
        else
        {
            i++;
        }
    }
}

Adroneus

2 février 2010 à 13:02:40

Voilà la suite de mes exos, (écrits a 3h du mat donc bon... je les réécrirai si besoin est)

int       mode(int *, int);
void      duplic(int *, int *, int);
int       kEmeElt(int *, int, int);

int     mode(int *Grid, int SzGrid)
{
 int     Test[2];
 int     iter;
 int     jter;
 int     value;

 *(Test + 1) = 1;
 iter = -1;
 value = 0;
 while ( (++iter) < SzGrid )
	{
 		(*Test) = 1;
 		jter = -1;
		while ( (++jter) < SzGrid )
			if ( *(Grid + iter) == *(Grid + jter) )
				(*Test)++;
		if ( *(Test + 1) < (*Test) )
			{
				*(Test + 1) = (*Test);
				value = *(Grid + iter);
			}
		else if ( *(Test + 1) == (*Test) )
			if ( value > *(Grid + iter) )
				value = *(Grid + iter);
	}
 return (value);
}

void     duplic(int *GridDes, int *GridSrc, int Sz)
{
 int     iter;

 iter = -1;
 while ( (++iter) < Sz )
	*(GridDes + iter) = *(GridSrc + iter);
}

int     kEmeElt(int *Grid, int SzGrid, int k)
{
 int     *temp;
 int     min;

 temp = malloc(SzGrid * sizeof(int));
 duplic(temp, Grid, SzGrid);
 triCroissant(temp, SzGrid);
 min = *(temp + k);
 free(temp);
 return (min);
}

Vala, je ferai le triangle de pascal plus tard il me reste pas mal de trucs a faire

EDIT erreur stupide...

Tosh

2 février 2010 à 13:08:39

EDIT : rien dit

Arthurus

2 février 2010 à 16:06:52

@Adroneus : Tu veux steplé réécrire ton code en utilisant la syntaxe des tableaux !! Franchement avec la syntaxe des pointeurs c'est pénible à lire (et ça sert à rien).

GurneyH

2 février 2010 à 16:27:42

@mob:

int t[DIM * DIM] = {0};

. Effectivement du utilises un tableau 1d, mais bon...

Pour ta seconde solution, ok, mais on peut faire sans flottant, sans divisions, et sans multiplications.

Pour l'exercice 7

Citation : mob

J'ai donc décidé d'implémenter un algorithme présenté sur wikipédia qui lui est plutôt une sorte de quicksort partiel. Par ici : http://en.wikipedia.org/wiki/Selection_algorithm#Partition-based_general_selection_algorithm. Le code :

C'est effectivement la meilleure solution. Par contre, il faut faire très attention à la fonction de partition.

Bien vu.

Pour la syntaxe des pointeurs, je ne pensais pas à la syntaxe qu'utilise Adronéus...
En fait, Adronéus, au lieu de faire
tab[i] tu fais *(tab + i) c'est strictement identique, et chacun à ses préférences sur ce style...
Quand je parlais de pointeurs, je pensais à la manière d'itérer sur un tableau, sans utiliser de variable i , par exemple.

Perso, je pense que c'est utile de se forcer à utiliser cette syntaxe, ça permet d'être moins perdu, lorsqu'on la rencontre.

Moi, ce qui me dérange plus dans le code d'Adronéus, c'est l'utisation systématique des boucles while , où une boucle for serait bien plus adaptée. Je sais également que c'est une affaire de gout. En C, on à déjà peu d'instructions, si en plus on se restreint encore, c'est compliqué d'avoir un code exprimant clairement un algorithme...

@Darkipod: effectivement, avec le second exemple de l'exercice, tu obtiens:

Elt com: 1 10 10 11 10 10 10 10

au lieu de

1, 10, 11, 10

Mais tu n'es pas le seul, il me semble que pour la plupart, le même problème existe.

Un indice, une fois que tu trouve un élément commun au 2 tableaux, il faut s'assurer de ne plus pouvoir utiliser cet élément.

Autre chose, tu as

int tailleTableau = sizeof (tableau) / sizeof (int);
int tailleTableau1 = sizeof (tableau1) / sizeof (int);
int tailleTableau2 = sizeof (tableau2) / sizeof (int);

Ca vaut le coup d'utiliser une macro bien connue

#define NELEM(a) (sizeof(a)/sizeof*(a))

que tu peux utiliser ainsi

indexMin(tableau, NELEM(tableau)

Zeste de Savoir, le site qui en a dans le citron !

Tosh

2 février 2010 à 17:41:55

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int indexMax (int tableau[], int tailleTableau)
{
   int max = tailleTableau - 1;
   int i;
   for (i = tailleTableau - 1; i >= 0; i--)
   {
      if (tableau[max] < tableau[i])
         max = i;
   }
   return max;
}

int mode(int tableau[], int tailleTableau)
{
    int i, j, mode;
    int *nb_elements = malloc(tailleTableau*sizeof(int));
    
    if(nb_elements == NULL)
       exit(1);
    
    memset(nb_elements, 0x00, tailleTableau*sizeof(int));
    for(i=0; i < tailleTableau; i++)
    {
       for(j=0; j < tailleTableau; j++)
       {
           if(tableau[j] == tableau[i])
           {
               nb_elements[j]++;
               break;
           }
           else if(j == tailleTableau-1)
           {
              nb_elements[i]++;
           }
       }
    }  
    mode = tableau[indexMax(nb_elements, tailleTableau)];
    free(nb_elements);
    
    return mode;
}

int main (int argc, char *argv[])
{
   int tab[] = {1,5,1,3,5,3,8,5,8,5};
   printf("%d\n", mode(tab, 10));
   return 0;
}

Voilà ma contribution pour la fonction mode (assez tordue, je l'avoue), le dernier exercice qu'il me restait à faire

Merci encore à GurneyH pour cette initiative.

Dîtes moi ce que vous en pensez.

Lithrein

2 février 2010 à 17:41:57

Juste une petite remarque, on s'aperçoit que beaucoup de monde utilise une variable temporaire pour faire leur fonction d'échange alors qu'elle n'est pas forcément utile quand on travaille sur des entiers.

Une autre méthode est :

void
swap (int * tab, int i, int j) {
    /* Par ex : tab[i] = 8 et tab[j] = 20 */
    tab[i] += tab[j]; /* tab[i] = 8 + 20 = 28 */
    tab[j] = tab[i] - tab[j]; /* tab[j] = 28 - 20 = 8 */
    tab[i] = tab[i] - tab[j]; /* tab[i] = 28 - 8 = 20 */
}

Bien entendu, cette méthode ne marche que pour les entiers. Et la méthode générique passe bien par une variable temporaire.

void
swap (void ** tab, int i, int j) {
    void * tmp;

    tmp = tab[i]; /* tmp = *(tab + i) */
    tab[i] = tab[j]; /* *(tab + i) = *(tab + j) */
    tab[j] = tmp; /* *(tab + j) = tmp */
}

Voilà, je postais juste pour montrer une autre méthode que certains connaissent peut-être déjà ...

Adroneus

2 février 2010 à 17:50:01

@GurneyH

C'est plus une histoire de norme que de préférence pour le while

sinon, des critiques? pour mon écriture des tableaux je les referai..

EDIT : quand je dis norme : c'est la norme EPITECH

Lithrein

2 février 2010 à 18:01:06

Citation : Adroneus

@GurneyH

C'est plus une histoire de norme que de préférence pour le while sinon, des critiques? pour mon écriture des tableaux je les referai..

EDIT : quand je dis norme : c'est la norme EPITECH

La norme EPITECH ne demande pas de faire des tabulations de 8 espaces (il me semble) car ça fait vraiment illisible à cause de la largeur imposé qui nous oblige à "scroller".

Arthurus

2 février 2010 à 18:03:50

Citation : Tosh

Dîtes moi ce que vous en pensez.

OK.

Remarques sur la forme :
* Ligne 27 : Tu utilises l'écriture hexa de 0 (pouquoi ???).
* En fait on peut complètement virer le memset, en faisant un calloc() au lieu de malloc().
* Ligne 23 : L'utilisation de perror() est très recommandée dans ce genre de situation.
* Ligne 33 : Ce break est inutile.

Remarques sur le fond :
Bon, ton algo est globalement quadratique, mais on peut très facilement l'améliorer (ça restera du quadratique, mais on enlèvera une passe).
Ce que tu fais, c'est que tu remplis ton tableau, puis tu le parcours pour trouver le max !
Tu peux t'inspirer de ce que j'ai fait pour repérer directement le max pendant le remplissant du tableau (ça t'évitera de le re-parcourir).

mob

2 février 2010 à 18:21:27

J'ai trouvé l'erreur dans mon code pour l'exercice 7, elle était dans la fonction de partition (merci pour l'indication GurneyH). Je n'ai pas modifié celui que j'ai posté avant, voilà :

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <time.h>

int partition(int *, int, int, int);
int kth_min(int *, int, int);
void swap(int *, int, int);

int
main(void)
{
#define N 6
#define M 100000000

        int k, res, i;
        int t[N] = {0, 1, 10, 1, 3, 5};
        int *p;

        if ((p = malloc(M * sizeof *p)) == NULL)
                return EXIT_FAILURE;

        for (k = 0; k <= 5; k++)
        {
                res = kth_min(t, k, N);
                printf("%d-th minimum of t : %d\n", k, res);
        }
        printf("\n");

        srand((unsigned) time(NULL));
        for (i = 0; i < M; i++)
                p[i] = INT_MAX - rand();

        k = 193284;
        res = kth_min(p, k, M);
        printf("%d-th minimum of q : %d\n", k, res);

        free(p), p = NULL;
        
        return 0;
}

int
kth_min(int t[], int k, int size)
{
        int left, right, mid;
        int piv_ind;
        
        left = 0;
        right = size-1;
        while (left <= right)
        {
                mid = (left + right) / 2;
                piv_ind = partition(t, left, right, mid);
                if (k == piv_ind)
                        return t[k];
                else if (k < piv_ind)
                        right = piv_ind - 1;
                else
                        left = piv_ind + 1;
        }

        return -1;
}

/*
 * Partitionne le tableau en une partie dont les élements
 * sont plus petits que le pivot, une autre avec les élements
 * plus grand, et renvoie l'indice du nouveau pivot.
 */
int
partition(int t[], int left, int right, int pivot)
{
        int i, piv_new_ind;
        int piv_value;

        piv_value = t[pivot];
        swap(t, right, pivot);
        piv_new_ind = left;
        for (i = left; i < right; i++)
        {
                if (t[i] < piv_value)
                {
                        swap(t, piv_new_ind, i);
                        piv_new_ind++;
                }
        }

        swap(t, piv_new_ind, right);

        return piv_new_ind;
}

void
swap(int t[], int i, int j)
{
        int temp;

        temp = t[i];
        t[i] = t[j];
        t[j] = temp;
}

GurneyH: Pour la méthode avec multiplications etc. c'est simplement une méthode parmi d'autres

J'imagine que tu fais allusion à quelque chose comme ce qu'a fait Pouet_forever ? Je trouve que c'est bien pensé en effet.

Pour l'exercice 7, wikipédia semble dire que la méthode de la median of medians est en O(n) dans le pire des cas tandis que celle que j'ai implémenté peut "chuter" en O(n^2) suite à un mauvais choix de pivot (même problème que pour quicksort). J'aimerais bien voir les performances dans un cas pratique, je prendrais peut-être le temps de l'implémenter.

1 2 3 4 5 >>

zArray1D

× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.

× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.

zArray1D

Réponses

zArray1D

Supprimer

Modérer

Signaler le message aux modérateurs