Discussion :

[moi659]

Bonjour,
Alors voila je debute en c et je bloque sur un exo : je dois créer un array de int positifs et negatifs avec une taille donnée par l'utilisateur et des valeurs données aussi par l'utilisateur (jusque là tout va bien!) et je dois ensuite trouver la somme des chiffres consécutifs la plus élevée et là rien ne va plus : c'est a dire pour un array {2,-8,3,-2,4,-10} je renvoie 5 (pour les valeurs {3,-2,4}) j'ai voulu essayer avec une boucle qui compare les sommes mais avant même d'arriver à ca je ne vois pas comment garder mes sommes cad j'ai tenté un

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
for (int i=0; i<arraySize; i++){
 
sum = ourArray[i]+ourArray[i+1];
 
…
}

mais le probleme c'est que la valeur change en fonction de l'avancement de la boucle . Donc je suis bloquée si quelqu'un pourrait m'aider ce serait top!

Merci !!!

[foetus]

Si on parle d'un algo classique (*) et non pas d'un algo génétique (si c'est possible), il faut avoir une structure avec comme champs/ attributs valeur, position min, position max [et éventuellement la longueur mais c'est la soustraction des 2 positions + 1]
Cette structure garde la plus grande valeur. Ensuite, si dans ton tableau, plusieurs séquences ont la valeur maximale, il faut utiliser une liste chaînée.

* : l'algo classique consiste à tester toutes les séquences de toutes les longueurs

En pseudo-code non testé

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
max_value.val     <- array[0];
max_value.min_pos <- 0;
max_value.max_pos <- 0;
 
Pour length : 1 to nb_elements Faire
    Pour index : 0 to (nb_elements - length) Faire
        tmp_sum <- sum(index, length);
 
        if (tmp_sum > /*or >=*/ max_value.val) { /* change max_value or save this sequence */ }
    Fin Pour
Fin Pour

[Sve@r]

et je dois ensuite trouver la somme des chiffres consécutifs la plus élevée et là rien ne va plus : c'est a dire pour un array {2,-8,3,-2,4,-10} je renvoie 5 (pour les valeurs {3,-2,4})

Bonjour

Je ne vois pas en quoi la suite 3, -2 et 4 désigne des entiers consécutifs. Ou alors je n'ai pas la même définition que toi de la consécutivité...

[Matt_Houston]

De rangs consécutifs au sein de la séquence, j'imagine. On aurait aussi pu écrire contigüs en mémoire.


Considérons pour l'instant seulement le problème de la sommation, puisqu'il ne paraît pas maîtrisé. Mettons que l'appelant te fournisse en entrée :

• une séquence de valeurs numériques ;
• un rang initial au sein de cette séquence ;
• le nombre d'éléments à additionner.

Comment écrirais-tu l'algorithme qui calcule la somme des valeurs de la sous-séquence ainsi définie ?

[moi659]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
for (int i = 0; i < arraySize; i++) {
			sum = ourArray[i];
			if (sum > maxSum) {
				maxSum = sum;
			}
			for (int j = i + 1; j < arraySize; j++) {
				sum += ourArray[j];
				if (sum > maxSum) {
					maxSum = sum;
				}
			}
		}

j'ai pas trop compris ton pseudo code (oui je dois aussi travailler ça lol) mais voilà aussi le code qu'on m'a expliqué je pense que je dois le paufiner pour qu'il limite mieux ses bornes mais je vois plus ou moins ce que tu veux dire ne tout cas merci beaucoup !
Sinon quand je parle de consecutivité c'est au niveau de leur place dans le tableau

merci a tous

De rangs consécutifs au sein de la séquence, j'imagine. On aurait aussi pu écrire contigüs en mémoire.


Considérons pour l'instant seulement le problème de la sommation, puisqu'il ne paraît pas maîtrisé. Mettons que l'appelant te fournisse en entrée :

• une séquence de valeurs numériques ;
• un rang initial au sein de cette séquence ;
• le nombre d'éléments à additionner.

Comment écrirais-tu l'algorithme qui calcule la somme des valeurs de la sous-séquence ainsi définie ?

je pense que j'aurais fais ainsi:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
for(int i=rangInitialAuSeinSequence; i<nbElementsAdditionner+1; i++){
sum += tableau[i];
}

[Matt_Houston]

Il te manque toujours une information capitale : combien d'éléments sont à prendre en compte pour le calcul de cette somme ! Ou est-ce qu'il s'agit de toutes les sommes possibles, de 1 au nombre total d'éléments de la séquence ?!

EDIT en rapport avec le message au-dessus : c'est un début, il y a une erreur que je te laisse retrouver. L'étape suivante consistera à placer cette solution à une partie du problème dans un module : une fonction en C.

[moi659]

De mon enoncé, ce n'est pas precisé (je pensais justement à ca quand je parlais des bornes ) mais du coup imaginons que je cherche à faire comme tu aurais dis , (en limitant le nombres d'elements) est ce que la boucle que j'ai écris est bonne ? (je vais la tester dans tous les cas mais je voulais d'abord repondre

je connais pas encore edit mais je vais checker ca ! Merci

[Sve@r]

De rangs consécutifs au sein de la séquence, j'imagine. On aurait aussi pu écrire contigüs en mémoire.

Ok. Effectivement vu ainsi ces 3 entiers de rang 2, 3 et 4 forment bien la plus grande somme qu'on puisse trouver.

Moi je sérialiserais les problèmes et commencerais par écrire une fonction qui part d'une position "p" et qui calcule la somme des "n" nombres qui suivent cette position (p et n paramètres de la fonction)
Ensuite je balaye le tableau et

• pour l'entier de rang 0 je calcule (via cette fameuse fonction) la somme des 0, 1, 2, 3, 4, 5, 6 entiers qui le suivent
• pour l'entier de rang 1 je calcule la somme des 0, 1, 2, 3, 4, 5 entiers qui le suivent
• pour l'entier de rang 2 je calcule la somme des 0, 1, 2, 3, 4 entiers qui le suivent

et etc etc en mémorisant à chaque fois la plus grande somme trouvée.

Pas le plus économique des algorithmes (complexité O²) mais 100% efficace.

[foetus]

j'ai pas trop compris ton pseudo code (oui je dois aussi travailler ça lol)

Et tu fais du C

Donc je me répète : Si on parle d'un algo classique (*) et non pas d'un algo génétique (si c'est possible), il faut avoir une structure avec comme champs/ attributs valeur, position min, position max [et éventuellement la longueur mais c'est la soustraction des 2 positions + 1]
Cette structure garde la plus grande valeur. Ensuite, si dans ton tableau, plusieurs séquences ont la valeur maximale, il faut utiliser une liste chaînée.

* : l'algo classique consiste à tester toutes les séquences de toutes les longueurs


Non testé, peut-être des fuites de mémoires et des +1/-1 à ajouter :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
 
 
/********************************* Structures ********************************/
 
typedef struct s_One_Value {
    unsigned int max_pos;
    unsigned int min_pos;
 
    struct s_One_Value* next;
} t_One_Value;
 
 
typedef struct s_List_Sequences {
    int max_value;
 
    t_One_Value* list;
} t_List_Sequences;
 
 
/**************************** Forward Declarations ***************************/
 
void list_sequences_add_first_sequence(t_List_Sequences*, /*const*/ t_One_Value*, int /*max*/);
 
void list_sequences_add_sequence(t_List_Sequences*, /*const*/ t_One_Value*);
 
void list_sequences_delete(t_List_Sequences*);
 
void list_sequences_display(/*const*/ t_List_Sequences*, int* /*array*/);
 
unsigned char list_sequences_if_equal(/*const*/ t_List_Sequences*, int /*value*/);
 
unsigned char list_sequences_if_sup(/*const*/ t_List_Sequences*, int /*value*/);
 
void list_sequences_init(t_List_Sequences*);
 
void list_sequences_reset(t_List_Sequences*);
 
void one_value_copy(/*const*/ t_One_Value* /*from*/, t_One_Value* /*to*/);
 
void one_value_init(t_One_Value*, unsigned int /*min_pos*/, unsigned int /*max_pos*/);
 
 
/********************************* Inferface *********************************/
 
// XXX : should return an error if malloc failed
void list_sequences_add_first_sequence(t_List_Sequences* list, /*const*/ t_One_Value* one_value, int max) {
    if (list != NULL) {
        t_One_Value* new_value;
 
        list_sequences_delete(list);
 
        list->max_value = max;
 
        new_value = malloc( sizeof(t_One_Value) );
 
        if (new_value != NULL) {
            one_value_copy(one_value, new_value);
 
            new_value->next = NULL;
            list->list      = new_value;
        } else {
            list->list      = NULL;
        }
    }
}
 
 
// XXX : should return an error if malloc failed
void list_sequences_add_sequence(t_List_Sequences* list, /*const*/ t_One_Value* one_value) {
    if (list != NULL) {
        t_One_Value* new_value;
 
        new_value = malloc( sizeof(t_One_Value) );
 
        if (new_value != NULL) {
            one_value_copy(one_value, new_value);
 
            new_value->next = list->list;
            list->list      = new_value;
        }
    }
}
 
 
void list_sequences_delete(t_List_Sequences* list) {
    if ((list != NULL) && (list->list != NULL)) {
        t_One_Value* sequence;
        t_One_Value* next;
 
        sequence = list->list;
 
        while (sequence != NULL) {
            next = sequence->next;
 
            free(sequence);
 
            sequence = next;
        }
 
        list->list = NULL;
    }
}
 
 
// XXX Warning : no bounds checking
void list_sequences_display(/*const*/ t_List_Sequences* list, int* array) {
    if ((list != NULL) && (array != NULL)) {
        t_One_Value* value;
        unsigned int index;
 
        printf("Max value : %d\n\n", list->max_value);
 
        value = list->list;
 
        while (value != NULL) {
            index = value->min_pos;
 
            printf("Sequence  : [%d, %d]\n%d", index, value->max_pos, array[index]);
 
            for(++index; index <= value->max_pos; ++index) {
                printf(" %d", array[index]);
            }
            printf("\n");
 
            value = value->next;
        }
    }
}
 
 
unsigned char list_sequences_if_equal(/*const*/ t_List_Sequences* list, int value) {
    unsigned char result;
 
    if (list != NULL) {
        result = (list->max_value == value);
    } else {
        result = 0;
    }
 
    return result;
}
 
 
unsigned char list_sequences_if_sup(/*const*/ t_List_Sequences* list, int value) {
    unsigned char result;
 
    if (list != NULL) {
        result = (list->max_value < value);
    } else {
        result = 0;
    }
 
    return result;
}
 
 
void list_sequences_init(t_List_Sequences* list) {
    if (list != NULL) {
        list->max_value = INT_MIN;
        list->list      = NULL;
    }
}
 
 
void list_sequences_reset(t_List_Sequences* list) {
    if (list != NULL) {
        list_sequences_delete(list);
 
        list->max_value = INT_MIN;
    }
}
 
 
void one_value_copy(/*const*/ t_One_Value* from, t_One_Value* to) {
    if ((from != NULL) && (to != NULL)) {
        to->max_pos = from->max_pos;
        to->min_pos = from->min_pos;
//      to->next    = NULL;
    }
}
 
 
void one_value_init(t_One_Value* value, unsigned int min_pos, unsigned int max_pos) {
    if (value != NULL) {
        value->max_pos = max_pos;
        value->min_pos = min_pos;
        value->next    = NULL;
    }
}
 
 
/************************************ Main ***********************************/
 
// XXX Warning : no bounds checking
void sum_values(int* array, unsigned int first_index, unsigned int length, int* sum) {
    if ((array != NULL) && (sum != NULL)) {
        unsigned int pos;
 
        (*sum) = array[first_index];
 
        for(pos=1; pos < length; ++pos) {
            (*sum) += array[first_index + pos];
        }
    }
}
 
 
int main(int argc, char** argv)
{
    t_List_Sequences list;
    t_One_Value value;
    int array[] = {2, -8, 3, -2, 4, -10, 5};
    int tmp_sum ;
    unsigned int index, nb_elements, length;
 
    nb_elements = 6; // hardcode
 
    list_sequences_init(&list);
 
    for(length=1; length <= nb_elements; ++length) {
        for(index=0; index <= (nb_elements - length); ++index) {
            sum_values(array, index, length, &tmp_sum);
 
            printf("sequence [%0u, %0u] with length %02d, sum = %d", index, (index + length - 1), length, tmp_sum);
 
            if ( list_sequences_if_sup(&list, tmp_sum) ) {
                printf(" -> new max value\n");
 
                one_value_init(&value, index, (index + length - 1));
 
                list_sequences_add_first_sequence(&list, &value, tmp_sum);
            } else if ( list_sequences_if_equal(&list, tmp_sum) ) {
                printf(" -> add this sequence\n");
 
                one_value_init(&value, index, (index + length - 1));
 
                list_sequences_add_sequence(&list, &value);
            } else {
                printf("\n");
            }
        }
    }
 
    printf("\n\nResult:\n");
    list_sequences_display(&list, array);
 
    list_sequences_delete(&list);
 
    return 0;
}

Mise à jour : une procédure reset pour réutiliser la liste.

[moi659]

haha oui je sais je dois m'occuper de ca ! Bon finalement j'ai laissé avec l'algo que je vous ai posté en dernier, en fait c'était sensé etre un exo d'intro donc résolu en quelques lignes. Je verrai quelle correction ils nous donne et je vous la posterai.
Merci encore

[Sve@r]

Non testé, peut-être des fuites de mémoires et des +1/-1 à ajouter :

Un bel exercice de style de 242 lignes. Et il fonctionne au poil (sauf que je ne me suis pas amusé à l'examiner pour détecter une fuite éventuelle). Mais des listes chainées pour ça c'est riche non ?

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

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
#include <stdio.h>
 
int cumul(int *array, size_t n) {
	int r;
	int *pt;
	size_t i;
	r=0;
	for (i=0, pt=array; i <= n; i++, pt++)
		r+=(*pt);
	return r;
}
 
typedef struct {
	int calc;
	int sum;
	size_t ghe;
	size_t dte;
} t_find;
 
int main(int argc, char** argv) {
	int array[] = {2, -8, 3, -2, 4, -10};
	int *pt;
	t_find find;
	size_t i, j, nb_elements;
 
	nb_elements = 6; // hardcode
	find.sum=array[0];
	find.dte=0;
	find.ghe=0;
 
	for (i=0, pt=array; i < nb_elements; i++, pt++) {
		for (j=0; (j+i) < nb_elements; j++) {
			find.calc=cumul(pt, j);
			if (find.calc > find.sum) {
				find.sum=find.calc;
				find.ghe=i;
				find.dte=i+j;
			}
		}
	}
 
	printf("somme=%d, bornes=%lu, %lu\n", find.sum, find.ghe, find.dte);
}

[foetus]

Mais des listes chainées pour ça c'est riche non ?

Non, et je vois le professeur arriver

Si tu prends ce tableau {2, -8, 3, -2, 4, -10, 5} (c'est le même tableau mais avec un 5 en plus à la fin), la plus grande valeur est toujours 5, mais il y a 2 séquences [2, 4] - {3, -2, 4} et [6, 6] - {5}
(Si je ne me trompe pas )

Ensuite , c'est une séquence de longueur de 1 - peut-être que ce n'est pas valide. Alors il faudrait tester, mais au lieu de rajouter un 5 à la fin, on peut rajouter des nombres dont la somme fait 5 ({1, 4} par exemple)

[Sve@r]

et je dois ensuite trouver la somme des chiffres consécutifs la plus élevée

Ensuite , c'est une séquence de longueur de 1 - peut-être que ce n'est pas valide. Alors il faudrait tester, mais au lieu de rajouter un 5 à la fin, on peut rajouter des nombres dont la somme fait 5 ({1, 4} par exemple)

Une séquence de longueur 1 ne semble pas interdite (ça reste toujours une séquence). Mais le vrai débat c'est que l'énoncé demande juste la somme la plus élevée, pas la séquence la plus longue

Ceci dit, rajouter dans mon code un indicateur permettant de flagguer aussi la longueur de la séquence en plus de la somme n'est pas franchement très compliqué puisque la longueur de la séquence en cours correspond à ma variable "j" et la plus grande séquence trouvée sera "dte - ghe"...