Partage

zArray1D

Réponses

5 février 2010 à 18:22:52

Voici une approche récursive de zeroADroite :

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

Par contre ça doit être moins rapide que vos fonctions

Arthurus

5 février 2010 à 18:30:26

??
Appels infinis ?

Merkil

5 février 2010 à 18:34:28

Oups pardon, j'ai fais des conneries avec mon code, j'édite

Arthurus

5 février 2010 à 18:38:17

C'est toujours pas bon.

#include <stdio.h>

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

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

arthurus@Arthurus-Laptop:~$ ./a.out 
3 2 1307461 0

Merkil

5 février 2010 à 18:40:31

Pourtant chez moi(Ubuntu 9.10, avec Codeblocks + GCC, j'ai essayé Release et Debug) ça marche...

EDIT : Navré... J'ai fait cet exercice en toute hâte, donc à l'arrache.
Voici le code fonctionnel :

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

Arthurus

5 février 2010 à 18:42:58

Je t'assure que ça marche pas.
Exécute toi moi même ton algo comme si t'étais un pc, et tu verras que c'est pas bon.

Merkil

5 février 2010 à 18:45:13

J'ai édité.
Désolé, >.<

colbseton

5 février 2010 à 18:46:22

Vous pourriez me donner quelques conseils pour l'exo sur le mode, car je vois pas du tout comment procéder

.
Merci,

Tosh

5 février 2010 à 18:49:56

Je doute que ça soit une bonne méthode, mais j'ai utilisé une copie du tableau d'origine, que j'ai ensuite triée. (Après, ça va tout seul)

Je pensais que l'on ne pouvait pas modifier le tableau passé en paramètre, d'où la copie.

colbseton

5 février 2010 à 18:55:21

En attendant d'autres réponses, je post mes solutions pour index min et max. C'était histoire de me chauffer

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

int index_max(int t[], int taille)
{
    int i, max=t[0];

    for(i=0; i<taille; i++)
        if(t[i] > max)
            max = t[i];
    return max;
}

int index_min(int t[], int taille)
{
    int i, min=t[0];

    for(i=0; i<taille; i++)
        if(t[i] < min)
            min = t[i];
    return min;
}

int main(void)
{
    int t[4]={1,2,3,4};
    printf("index _max = %d \nindex_min = %d\n", index_max(t,4), index_min(t,4));
    return 0;
}

GurneyH

5 février 2010 à 19:21:24

Citation : Tosh

Je sais bien que c'est pas un tri à bulle, puisqu'il n'y a pas de tri, mais ce n'est pas le même principe? On fait remonter les zéros (les bulles) vers le haut du tableau, à la place de faire remonter les éléments les plus grands (ou les plus petits).

Ah, ok... J'ai mal lu ta phrase, et je croyais que tu trouvais ton tri avec pointeur, plus performant que ta première version.

@ColbSeton: Dans un premier temps, si la plage de valeurs dans ton tableau n'est pas trop importante, tu peux stocker le nombre d'occurrences d'une valeur dans un autre tableau.

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

candide

6 février 2010 à 10:48:42

Citation : Colb-Seton

En attendant d'autres réponses, je post mes solutions pour index min et max.

On demandait pas plutôt de retourner les indices min ou max que les valeurs min ou max ?

Concernant le tableau de Pascal, on peut aussi ne pas utiliser de tableau grâce à la formule explicite du coefficent binomial et dont on déduit une relation de récurrence entre un élément d'une ligne donné et son suivant dans la ligne.

Le problème est qu'avec des int sur 32 bits, l'overflow arrive plus vite (n=31 au lieu de n=34) qu'en utilisant la méthode classique du tableau dont on ajoute les paires d'éléments contigus.

#include <stdio.h>

/* Selon que l'on veut travailler avec des int (INT) ou des unsigned long
   long (ULL) */
#define INT

#if defined(ULL)
#define TYPE unsigned long long
#define FORMAT "%ull "
#elif defined(INT)
#define TYPE int
#define FORMAT "%d "
#endif

/* Affiche la ligne n du tableau de Pascal */
void pascal(int n)
{
  int k = 0;
  TYPE r = 1;

  printf("1 ");
  for (k = 1; k <= n; k++)
    {
      r *= n - k + 1;
      printf(FORMAT, r /= k);
    }
  printf("\n");
}

int main(void)
{
  int lig, n = 20;

  for (lig = 0; lig < n; lig++)
    pascal(lig);

  return 0;
}

1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
1 5 10 10 5 1 
1 6 15 20 15 6 1 
1 7 21 35 35 21 7 1 
1 8 28 56 70 56 28 8 1 
1 9 36 84 126 126 84 36 9 1 
1 10 45 120 210 252 210 120 45 10 1 
1 11 55 165 330 462 462 330 165 55 11 1 
1 12 66 220 495 792 924 792 495 220 66 12 1 
1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1 
1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1 
1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1 
1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1 
1 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380 680 136 17 1 
1 18 153 816 3060 8568 18564 31824 43758 48620 43758 31824 18564 8568 3060 816 153 18 1 
1 19 171 969 3876 11628 27132 50388 75582 92378 92378 75582 50388 27132 11628 3876 969 171 19 1

Adroneus

6 février 2010 à 13:21:23

impressionant... je suis entrain de faire le mien de tableau, le code est plus long

realmagma

6 février 2010 à 13:35:40

Bonjour à tous, ça fait pas mal de temps que je n'ai plus programmé :'(

et je viens de voir cet exercice.

Voici mon code, je ne comprends pas pourquoi il ne marche pas.

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

int indexMin(int tableau[], int tailleTableau);
int indexMax(int tableau[], int tailleTableau);


int main()
{
    int tableau[10] = {3, 6, 7, 9, 8, 2, 1, 4, 5};
    int min = 0;

    min = indexMin(tableau, 10);
    printf("Le min vaut %d", min);
    return 0;
}

/* *****************************************************************************/

int indexMin(int tableau[], int tailleTableau)
{
    int i, valeurTemp = 0, j;

    for(i = 0; i < tailleTableau-1; i++)
    {
        for(j = 0; j < tailleTableau-1; j++)
        {
            if(tableau[j] > tableau[j+1])
            {
                valeurTemp = tableau[j+1];
                tableau[j] = tableau[j+1];
                tableau[j+1] =  valeurTemp ;
            }


        }

    }

    return tableau[0];
}

Pourriez-vous m'aider? Merci d'avance les zéros.

Tosh

6 février 2010 à 13:40:24

Un tris à bulle pour chercher l'index min me parait un peu lourd

Sinon, les lignes :

valeurTemp = tableau[j+1]; //tu sauve [j+1]
tableau[j] = tableau[j+1]; //tu écrase [j] (qui n'est pas sauvé)        
tableau[j+1] =valeurTemp ; //tu remets la valeur [j+1] dans [j+1]

Je te laisse chercher avec les commentaires que j'ai laissé

candide

6 février 2010 à 13:52:58

Citation : Adroneus

impressionant... je suis entrain de faire le mien de tableau, le code est plus long

Non rien d'impressionnant, c'est très clasique en maths cette propriété.

Ton code est plus long dis-tu ? J'en suis revenu de la concision du code, on y passe un temps fou pour un gain minime et le résultat est un code peu déchiffrable voire inintelligible.

Les bonnes questions que l'on doit se poser sont plutôt : mon code produit-il le résultat cherché, mon code est-il lisible ? la logique de l'algorithme transparait-elle ?

realmagma

6 février 2010 à 13:58:52

Re, j'ai refet mon code mais il ne amrche toujours pas lol.

int indexMin(int tableau[], int tailleTableau)
{
    int i, valeurTemp = 0, j;

    for(i = 0; i < tailleTableau-1; i++)
    {
        for(j = 0; j < tailleTableau-1; j++)
        {
            if(tableau[j] > tableau[j+1])
            {
                valeurTemp = tableau[j+1]; // Je sauve 'J+1'
                tableau[j+1] = tableau[j]; // J'écrase 'j+1' qui vaut j'
                tableau[j] =  valeurTemp; // J' vaut 'J+1'
            }


        }

    }

    return tableau[0];
}

Merci pour vos futures réponses.

Tosh

6 février 2010 à 14:06:10

Qu'est-ce qui ne marche pas? Car je viens d'essayer, et ça à l'air de fonctionner.

GurneyH

6 février 2010 à 14:10:42

Citation : candide

mon code est-il lisible ? la logique de l'algorithme transparait-elle ?

+Je ne sais pas combien!

En, premier lieu, c'est vraiment le but à avoir! Après quelques astuces permettent à partir d'un algo simple et clair, de booster!

Ne jamais partir, dans l'optique de produire un code performant!
On réfléchit à une solution, on la code, et on la teste.
Ensuite à partir de cette base, on peut(ou pas)produire quelque chose de performant!).

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

colbseton

6 février 2010 à 14:24:01

Citation : candide

Citation : Colb-Seton

En attendant d'autres réponses, je post mes solutions pour index min et max.

On demandait pas plutôt de retourner les indices min ou max que les valeurs min ou max ?

Oups oui

.
Je post ça, il se peut que ce soit bugué, mais je dois y aller alors autant poster un ptit truc .

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

int index_max(int t[], int taille)
{
    int i, max=t[0], i_max;

    for(i=0; i<taille; i++)
        if(t[i] > max){
            max = t[i];
            i_max=i;
        }

    return i_max;
}

int index_min(int t[], int taille)
{
    int i, min=t[0], i_min;

    for(i=0; i<taille; i++)
        if(t[i] < min){
            min = t[i];
            i_min= i;
        }

    return i_min;
}

int main(void)
{
    int t[]={10,30,54,21,100,10};
    printf("index _max = %d \nindex_min = %d\n", index_max(t,6), index_min(t,6));
    return 0;
}

Adroneus

6 février 2010 à 15:18:43

Citation

Non rien d'impressionnant, c'est très classique en maths cette propriété.

Ton code est plus long dis-tu ? J'en suis revenu de la concision du code, on y passe un temps fou pour un gain minime et le résultat est un code peu déchiffrable voire inintelligible.

Les bonnes questions que l'on doit se poser sont plutôt : mon code produit-il le résultat cherché, mon code est-il lisible ? la logique de l'algorithme transparait-elle ?

Moi ça m'impressionne j'ai pas le droit?

.Mon code produit (presque, mais j'ai pas le temps de le finir) le résultat recherché. Il est lisible. La logique de l'algo... je sais pas étant donné que je me complique souvent la vie pour rien.

Pour moi 2 + 2 != 4
2 + 2 == 1 + 1 + 1 +1

donc on verra pour la clarté et l'algo quand je posterai mon code

Pouet_forever

6 février 2010 à 15:27:52

Citation : Adroneus

Pour moi 2 + 2 != 4

Jean-Clade Van Damme sort de ce corps !!! !!!

Adroneus

6 février 2010 à 15:33:40

Tu fais perdre tout son sens a ma phrase

candide

6 février 2010 à 16:42:10

Citation : Colb-Seton

Je post ça, il se peut que ce soit bugué, mais je dois y aller alors autant poster un ptit truc .

J'ai pas testé mais à vue d'oeil, ça semble aller. Un petit détail :

Citation : Colb-Seton

int i, max=t[0], i_max;

Ici, max et i n'ont pas même sémantique : l'un est une valeur du tableau, l'autre un indice. Donc, je préfère les placer sur des lignes distinctes :

int i, i_max;
int max=t[0];

Si pas exemple tu changes le type du tableau (par exemple tableau de long long) alors tu as juste à changer le type.

Il y aurait un prolongement à l'exercice : écrire une version générique càd capable de retourner l'indice quelque soit le type d'élément du tableau (float, long long, chaînes de caractères, etc). Le prototype pourrait avoir la tête suivante :

int min(void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *));

Lithrein

6 février 2010 à 17:08:43

Citation : candide

Il y aurait un prolongement à l'exercice : écrire une version générique càd capable de retourner l'indice quelque soit le type d'élément du tableau (float, long long, chaînes de caractères, etc). Le prototype pourrait avoir la tête suivante :
int min(void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *));

J'aurais une question sur le paramètre `size_t nmenb` qui contient la taille en octet d'un élément du tableau.
Vu que l'on travaille sur un tableau de type `void *` , ce paramètre sert bien à passer d'un élément du tableau à l'autre, non ?

Pouet_forever

6 février 2010 à 17:10:14

J'ai fait ça

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

int min(void * base, size_t nmemb, size_t size,
		int (*compar)(const void *, const void *)) {
	int ind = 0;
	size_t i;
	
	for (i = 0; i < nmemb; i++) {
		void * tmp1 = ((char *) base) + (i*size);
		void * tmp2 = ((char *) base) + (ind*size);
		if (compar(tmp1, tmp2)) {
			ind = i;
		}
	}
	
	return ind;
}

int compar_int(const void * arg1, const void * arg2) {
	const int * a = arg1;
	const int * b = arg2;
	return *a < *b;
}

int compar_double(const void * arg1, const void * arg2) {
	const double * a = arg1;
	const double * b = arg2;
	return *a < *b;
}

int compar_str(const void * arg1, const void * arg2) {
	return (strcmp(*(char * const *) arg1, *(char * const *) arg2) < 0) ? 1 : 0;
}

#define N 5

int main(void) {
	int tab_i[N] = { 1, 8, 6, 0, 4 };
	double tab_d[N] = { 6.5, 94.1, 78.4, 1.1, 4.9 };
	char *tab_str[N] = {
		"salut", "oui", "pouet", "maison", "prog"
	};
	
	printf("int    : %d\n", min(tab_i, N, sizeof *tab_i, compar_int));
	printf("double : %d\n", min(tab_d, N, sizeof *tab_d, compar_double));
	printf("chaine : %d\n", min(tab_str, N, sizeof *tab_str, compar_str));
	return 0;
}

@Lithrein: Oui

candide

6 février 2010 à 17:44:46

@Pouet : Dis-donc t'a été rapide ! Désolé, j'ai pas le temps de regarder en détail ni de le coder moi-même. Je sais seulement qu'il faut être très attentif et tester, on écrit vite des bêtises et qui passent silencieusement à cause des divers casts inhérents à la programmation générique.

*) Ta fonction de comparaison est astucieuse.
*) Tu recalcules à chaque fois l'adresse de l'élément minimal, pourquoi ne pas la stoker ?
*) Perso, j'aurais ecrit une version pointeur qui évite de recalculer (comme avec ton produit i*size) l'offset.
*) J'aurais aussi placé (char*)base dans une variable plutôt que de refaire l'opération à chaque tour de boucle.
*) Aussi, ta fonction de comparaison des flottants n'est pas très académique.

Lithrein

6 février 2010 à 17:58:13

@Pouet : Merci pour la confirmation

Je suis donc arrivé à ça :

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

size_t
index_min (void * base, size_t nmenb, size_t size,
           int (*cmp)(const void *, const void*)) {

    size_t i, i_min = 0;
    void * val1 = (char *)base + i_min*nmenb;
    for (i = 0 ; i < size ; ++i) {
        void * val2 = (char *)base + i*nmenb;
        if (cmp(val2, val1)) {
            i_min = i;
            val1 = (char *)base + i_min*nmenb;
        }
    }
    return i_min;
}

int
cmpChar(const void * a, const void * b) {
    const char * pa = a;
    const char * pb = b;
    if ('\0' == *pa || '\0' == *pb )
        return *pa > *pb;
    else
        return *pa < *pb;
}


int
cmpInt(const void * a, const void * b) {
    const int * pa = a;
    const int * pb = b;
    return *pa < *pb;
}

int
main (void) {
    char tab[] ="abcd";
    printf("Indice mininmum = %d\n",
        (int)index_min(tab, sizeof(char), sizeof tab / sizeof *tab, cmpChar));
    return 0;
}

size_t
index_min (void * base, size_t nmenb, size_t size,
           int (*cmp)(const void *, const void*)) {

    size_t i, i_min = 0;
    void * val1 = (void *)base + i*nmenb;
    for (i = 0 ; i < size ; ++i) {
        void * val2 = (void *)base + i_min*nmenb;
        if (cmp(val1, val2)) {
            i_min = i;
            val1 = (void *)base + i*nmenb;
        }
    }
    return i_min;
}

Pouet_forever

6 février 2010 à 18:08:21

Pour les cast je ne pense pas avoir de problèmes

(je me suis déjà fait avoir, je fais attention maintenant :-°

).
J'ai refait la fonction sans recalculer tout à chaque tour de boucle :

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

int min(void * base, size_t nmemb, size_t size,
		int (*compar)(const void *, const void *)) {
	int ind = 0;
	size_t i;
	void * tmp_ind = base;
	void * tmp_courant = base;
	
	for (i = 1; i < nmemb; i++) {
		tmp_courant = ((char *) tmp_courant) + size;
		
		if (compar(tmp_courant, tmp_ind)) {
			ind = i;
			tmp_ind = tmp_courant;
		}
	}
	
	return ind;
}

int compar_int(const void * arg1, const void * arg2) {
	const int * a = arg1;
	const int * b = arg2;
	return *a < *b;
}

int compar_double(const void * arg1, const void * arg2) {
	const double * a = arg1;
	const double * b = arg2;
	return *a < *b;
}

int compar_str(const void * arg1, const void * arg2) {
	return (strcmp(*(char * const *) arg1,
				   *(char * const *) arg2) < 0) ? 1 : 0;
}

#define N 5

int main(void) {
	int tab_i[N] = { 1, 8, 6, 0, 4 };
	double tab_d[N] = { 6.5, 94.1, 78.4, 1.1, 4.9 };
	char *tab_str[N] = {
		"salut", "oui", "pouet", "maison", "prog"
	};
	
	printf("int    : %d\n", min(tab_i, N, sizeof *tab_i, compar_int));
	printf("double : %d\n", min(tab_d, N, sizeof *tab_d, compar_double));
	printf("chaine : %d\n", min(tab_str, N, sizeof *tab_str, compar_str));
	return 0;
}

Par contre pour la comparaison des nombres flottants, qu'est-ce que tu veux dire par là ? :euh:

Edit: Je crois savoir en fait, tu parles des approximations dues aux flottants ? Il faudrait que je fasse ma comparaison avec un Epsilon

Par contre là où j'ai un doute c'est au moment de l'appel de 'min' pour les chaînes de caractères. J'ai mis sizeof *tab_str mais je sais pas, ça me paraît bizarre. C'est pas sizeof tab_str qu'il faudrait mettre ? (ça me fait un segfault donc je suppose que non, mais est-ce qu'on pourrait m'expliquer

merci)

@Lithrein: Tu n'as pas le droit d'additionner des pointeurs génériques ((void *)base + i_min*nmenb; par ex).

Lithrein

6 février 2010 à 18:27:43

Citation : Pouet_forever

@Lithrein: Tu n'as pas le droit d'additionner des pointeurs génériques ((void *)base + i_min*nmenb; par ex).

Oui, je viens de m'en rendre compte, (je comprenais pas pourquoi l'indice minimum ne décollait pas de 0

) puis j'ai activé l'option -pedantic et ... j'ai su ... :lol:

<< 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