gestion de tableaux

Version imprimable

10/06/2011, 16h20
sandball22

gestion de tableaux

bonjour,

j'aimerais utiliser un tableau de 100 données de type entier.
Je dois remplir ce tableau par des variables aléatoires qui arrivent au compte goute.
Je ne dois faire aucun traitement tant que je n'ai pas 100 valeurs dans mon tableau.
Une fois que j'ai 100 valeurs, je dois faire la moyenne de ces 100valeurs.
En même temps, je dois gérer l'arrivée de nouvelle valeur dans mon tableau en remplaçant la valeur la plus ancienne par une nouvelle valeur. et donc ensuite faire la moyenne de ces valeurs. et ainsi de suite.

Pouvez vous m'aider pour faire cela?
Merci
10/06/2011, 16h26
fregolo52

Bel exercice !!
Le genre qu'on trouve lors d'un entretien d'embauche ou à l'école.

Avant même de coder, il faut penser à l'algorithme. Ca ressemble à une "pile".
10/06/2011, 16h39
brachior

Dans ce que j'ai compris,
Vu que la taille est fixe,
J'utiliserai un tableau "circulaire" avec un index
Ainsi qu'une variable de somme pour éviter un calcul long à chaque fois

Eratosthène ?

Cela m'a fait penser au crible d'Eratosthène (ici), mais ce n'est pas cet algorithme que vous voulez

En fait, deux fonctions sont nécessaires:

l'une pump(élément)
Si la liste fait 100 éléments
remplacer le Xième élément dans la liste
Sinon
insérer
Si la liste fait 100 éléments alors calculer la moyenne

enfin un main()
boucler sur 500 éléments
Générer aléatoirement un élement
appeler la fonction pump(élément)
C:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 int *liste; int size; int position; void calcule_moyenne() { /* calculer la moyenne */ } void pump(int e) { if (size < 100) { liste[position] = e; position = position + 1; size = size + 1; } else { if (!(position % 100)) { position = 0; } liste[position] = e; position = position + 1; } if (size >= 100) { calcul_moyenne(); } } void main(char *argv[], int argc) { int ielement; size = 0; liste = (int*)malloc(100*sizeof(int)); position = 0; for(ielement = 0; ielement < 500; ielement = ielement + 1) { int r = (int)(random() * 1000); pump(r); } }

On peut suivre le schéma suivant :

- N  : une constante entière (#define N 100)
- tab : un tableau de N entier
- cpt : un compteur de données initialisé à 0
- somme : une variable initialisée à 0 stockant la somme des données stockées dans le tableau
---------------------------------------
- A chaque nouvelle valeur val
  - ajouter val à la somme : somme += val
  - Si cpt < N , stocker val dans tab[cpt] : tab[cpt] = val
  - Sinon il faut rechercher la position de la plus ancienne valeur. 
         Elle est située en ianc = (cpt-N) modulo N. 
         - retrancher cette valeur de somme  :  somme -= tab[ianc]
         - ranger la nouvelle valeur à la place de l'ancienne : tab[ianc] = val
  - incrémenter cpt : cpt++
  - Si cpt >= N calculer la moyenne : somme/(float)N

13/06/2011, 13h44
sandball22

Olivieram quelle la difference entre position et size?? Comment je sais quel est l element le plus ancien dans le tableau?
13/06/2011, 15h25
olivieram

position et size

Citation:

Envoyé par sandball22

Olivieram quelle la difference entre position et size?? Comment je sais quel est l element le plus ancien dans le tableau?

Bonjour sandball22,
'position' est la position courante dans la liste.
'size' est la taille de la liste.

Avant qu'il y ait 100 éléments dans la liste, 'size' et 'position' augmentent au fûr et à mesure.
Quand il y a 100 éléments dans la liste, on calcule la moyenne.
'position' est toujours la position courante, mais on revient toujours à 0 quand la position a atteint 100.

Pour moi, le plus ancien élément dans la liste, c'est l'élément qui se trouve dans l'index 0 de la liste. Mais, au fûr et à mesure que l'on écrase le plus ancien à ce moment là, le plus ancien élément se trouve à l'index 'position'.

je ne comprends pas trop la condition suivante :

Code:

1
2
3
4
5
 
      if (!(position % 100)) 
      {
         position = 0;
      }

ce n'est pas plutôt :

Code:

1
2
3
4
5
 
      if ((position % 100)) 
      {
         position = 0;
      }

???

14/06/2011, 10h44
fregolo52
Citation:
Envoyé par sandball22

je ne comprends pas trop la condition suivante :

Code:

1 2 3 4 5 if (!(position % 100)) { position = 0; }
Ca veut dire : si le modulo (le reste de la division) est égale à 0 alors position = 0; moins condensé ça donne ça :
Code:

1 2 3 4 5 6 int reste = position %100; if (reste == 0) { position = 0; }

La fonction pump() proposée par olivieram se résume en pratique à

Code:

1
2
3
4
5
6
7
8
9
#define N 100
void pump(int e)
{
   position %= N;
   liste[position] = e;
   position +=1 ;
   if(size < N)size +=1;
   if(size == N)calcul_moyenne();
}

Si on veut supprimer les variables globales qui sont à éviter absolument, cette fonction devient :

Code:

1
2
3
4
5
6
7
8
void pump(int * liste, int *position, int *size, int e)
{
   *position %= N;
   liste[*position] = e;
   *position +=1 ;
   if(*size < N)*size +=1;
   if(*size == N)calcul_moyenne(liste);  // à adapter selon ce qu'on veut faire de la moyenne
}

La fonction main()proposée par olivieram devient (avec quelques corrections, voir commentaires)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <time.h>
#include <stdlib.h>
int  main(void) // main renvoie toujours un int
{
  int ielement;
  int  * liste;
  int size = 0;
  int position = 0;
 
  srand(time(NULL)); // initialiser le générateur aléatoire
  liste = malloc(N*sizeof(int)); // le cast est inutile en C
  if(liste != NULL) // il faut toujours tester le succès de l'allocation
  {
    for(ielement = 0; ielement < 500; ielement = ielement + 1)
    {
     int r = rand ();  // random() n'est pas standard
     pump(liste,&position,&size, r);
    }
    free(liste); // et toujours libérer la mémoire allouée dynamiquement
  }
  return 0;
}

14/06/2011, 20h59
olivieram

En ce qui concerne le calcul de la moyenne
Bonjour,
Pour ce qui est du calcul de la moyenne, on pourrait le faire itérativement.
Pas de besoin de lancer un calcul de moyenne sur l'ensemble des éléments.
Imaginons un très grand nombre, par exemple, 2 milliards d'éléments ?
Eh bien, il ne faudrait pas calculer la somme sur les 2 milliards d'éléments...
Il faudrait les calculer au fur et à mesure que l'élément est ajouté ou qu'il est remplacé.

Et c'est pourquoi, j'ai écris précédemment un if:
Code:

1 2 3 4 5 6 7 8 9 double somme = 0; if (size < 100) { somme += e/100.0; } else { somme -= liste[position] / 100.0; somme += e/100.0; }
J'invite vivement diogene à modifier son code pour faire cela.
Bonne soirée
14/06/2011, 21h23
ZiGoM@r

J'aurais initialisé tout les éléments du tampon circulaire à zéro puis, à chaque insertion, il te suffit de retrancher la valeur supprimée à ta somme et d'y ajouter la nouvelle valeur.
Le calcul de ta moyenne ne nécessite plus qu'une division de ta somme.

C'est en effet un problème intéressant (sa solution peut s'avérer très pratique).

PS :
Je n'avais pas vu "Je ne dois faire aucun traitement tant que je n'ai pas 100 valeurs dans mon tableau.", tu peux donc éviter l'initialisation à zéro.

Concernant le code fournit plus haut, mieux vaut préférer un "int buffer[100];".
14/06/2011, 23h00
diogene

@olivieram

Citation:

J'invite vivement diogene à modifier son code pour faire cela.

ce n'est pas mon code.

@olivieram

Citation:

Pour ce qui est du calcul de la moyenne, on pourrait le faire itérativement.
Pas de besoin de lancer un calcul de moyenne sur l'ensemble des éléments.

@ZiGoM@r

Citation:

à chaque insertion, il te suffit de retrancher la valeur supprimée à ta somme et d'y ajouter la nouvelle valeur.

Si vous lisiez les posts précédents, c'est ce que fait l'algorithme que j'ai proposé il y a 3 jours.
14/06/2011, 23h44
ZiGoM@r

Citation:

Envoyé par diogene

Si vous lisiez les posts précédents, c'est ce que fait l'algorithme que j'ai proposé il y a 3 jours.

Au vu de l'utilité toute relative de ton message, je m'offre une défense.

Je postais mon idée (du coup inutile) d'initialiser les éléments du tampon à zéro et j'en ai profité pour souligner le fait qu'une seule division était nécessaire (par rapport au code d'olivieram).

En effet, la seconde moitié de ma première phrase n'est qu'une autre formulation de ta procédure mais j'ai estimé qu'une meilleure clarté compenserait une redondance.

Cordialement.

algo ou code ?

Citation:

Envoyé par diogene

Si vous lisiez les posts précédents, c'est ce que fait l'algorithme que j'ai proposé il y a 3 jours.

Ben, d'accord. Mais, c'était un algo dans un langage "pseudo-naturel" et moi j'ai écris le code en C en premier. Ce n'est pas pareil.

J'ai codé un petit test complet de la fonctionnalité.
Ce petit test utilise la librairie ncurses pour afficher le nombre ajouté et la moyenne toutes les secondes.
Ensuite, CTRL-C est la touche pour quitter le programme qui boucle à l'infini.
Un paramètre est à préciser dans la commande définissant la taille maximale du tableau.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
 
#include <stdio.h>
#include <stdlib.h>
#include <ncurses.h>
#include <signal.h>
 
/* ##############################################
   Initialisation librairie ncurses
   ############################################## */
void initNcurses()
{
	initscr();
	noecho();
}
 
typedef struct _Structure {
	int *liste;
	int sizeMax;
	int size;
	int position;
	double moyenne;
} Structure;
 
Structure list;
 
 
Structure constructorStructure(int sizeMax) {
	Structure s;
	s.sizeMax = sizeMax;
	s.liste = malloc(sizeof(int)*sizeMax);
	s.size = 0;
	s.position = 0;
	s.moyenne = 0;
	if (s.liste == NULL)
	{
		printf("Erreur allocation\n");
		endwin();
		exit(EXIT_FAILURE);
	}
	return s;
}
 
void push(Structure* ptr, int elem)
{
	if (ptr->size < ptr->sizeMax) {
		ptr->liste[ptr->position] = elem;
		ptr->position++;
		ptr->size++;
		ptr->moyenne += elem / (double)ptr->sizeMax;
	}
	else {
		ptr->position %= ptr->sizeMax;
		ptr->moyenne -= ptr->liste[ptr->position] / (double)ptr->sizeMax;
		ptr->moyenne += elem / (double)ptr->sizeMax;
		ptr->liste[ptr->position] = elem;
		ptr->position++;
	}
}
 
void loop(Structure* s)
{
	int newElement;
	int delindex;
	char str[256];
	while(1)
	{
		refresh();
		newElement = (int)(rand()/(float)RAND_MAX * 0x0A) + 1;
		move(1,0);
		sprintf(str,"Ajout d'un nombre:%02d", newElement);
		addstr(str);
		if (newElement >= 1 && newElement <= 10)
		{
			push(s, newElement);
			move(2,0);
			sprintf(str,"Moyenne obtenue:%02.2f", s->moyenne);
			addstr(str);
		}
		else
		{
			printf("Il y a un bug sur ce programme.\n\r");
			endwin();
			exit(EXIT_FAILURE);
		}
		refresh();
		sleep(1);
	}
}
 
void destructorStructure(Structure* s)
{
	free(s->liste);
}
 
void quit(int i)
{
	move(5,0);
	addstr("Fin du programme\n\r");
	refresh();
	endwin();
	destructorStructure(&list);
	exit(EXIT_SUCCESS);
}
 
int main(int argc, char **argv)
{
	int sizeMax;
printf("argc=%d\n",argc);
	if (argc < 2) {
		printf("USAGE : moyenne sizeMax\n\r");
		return EXIT_SUCCESS;
	} else {
		sizeMax = atoi(argv[1]);
		if (sizeMax > 0)
		{
			initNcurses();
			refresh();
			signal(SIGINT, quit);
			printf("Calcul de la moyenne sur une plage de valeurs de %d\n\r",sizeMax);
			printf("Appuyez sur CTRL+C pour terminer\n\r");
 
			list = constructorStructure(sizeMax);
			loop(&list);
			destructorStructure(&list);
		} else {
			printf("Erreur : sizeMax n'a pas la bonne valeur\n\r");
			return EXIT_FAILURE;
		}
	}
 
 
	return EXIT_SUCCESS;
}