somme d’éléments d'u tableau

Question

salut.

int segc=[253  249  245  241  237  233  229  225  221  217  213  209  205  201  197  193  189  185  181  177  173  169  
165  161  157  153  149  145  141  137  133  129  125  121  117  113  109  105  101  97  93  89  85  81  77  
73  69  65  61  57  53  49  45  41  37  33  29  25  21  17  13  9  5  1]; 

int div4= [252 248 244 240 236 232 228 224 220 216 212 208 204 200 196 192 188 184 180 176 172 168 164 160 156 152 148
 144 140 136 132 128 124 120 116 112 108 104 100 96 92 88 84 80 76 72 68 64 60 56 52 48 44 40 36 32 28 24 20 16 
 12 8 4];

long som;


Je veux écrire un code en langage C qui determine le premier element x de div4 qui verifie:
x*segc[i]+ x*segc[j]+ x*segc[k] + .... +...... = som;
tel que som a une valeur determinée et 0 <=i <= j<= k<= ..
Autrement je dois trouver un ensemble d'élements de segc dont la somme som/x  (NB: som % x0)
Comment trouver au moins une combinaison (si elle exsite) qui verifie cette condition ?
Je ai pu écrire juste la partie "banale" qui parcourt div4 et determiner son premier élément diviseur de som 
mais pour le reste je bloque :((

Exemple:
 si som =114688 je dois trouver x=224 et l'ensemble d'élements de segc ={253 253 5 1} 
 Concerant les éléments trouvés je peux les sauvegarder dans un 3ème tableau ou autre.

cptpingu · Answer

Bonjour.

Oh un copier-coller d'exercice...
http://www.codes-sources.com/forum/sujet-BAR-SUJET-PFE-TP-AUTRES-DEVOIRS-SCOLAIRES_1557761.aspx

Je rappelle qu'ici on corrige volontier des codes aboutis, mais qu'on ne fait en aucun cas le travail ou la réflexion à la place du demandeur.

________________________________________________________________________
Historique de mes créations, et quelques articles:
[ http://0217021.free.fr/portfolio http://0217021.free.fr/portfolio]
Merci d'utiliser Réponse acceptée si un post répond à votre question

alice90 · Answer

Bonjour!
Ce n'est pas un copier coller d'un exercice et je connais bien le règlement.
C'est une partie d'un code que je suis en train de développer et j'ai juste besoin qu'on me mette sur la bonne voie et non pas qu'on m'écrive le code en totalité.
Juste une petite indication pour commencer car je bloque vraiment:(

cptpingu · Answer

Il y a un nombre absolument énorme de demandeur faignant qui postent leurs énoncés pour avoir du code tout cuit, mais si tu prends la peine de répondre et de t'expliquer, ce que tu n'en fais pas partit (néanmoins la prochaine fois pense à poster ton code, afin d'éviter cette ambiguïté). Je vais donc te donner quelques indications.

Étant donné que segc est un tableau contenant des nombres premiers, il y a peut être une propriété à exploiter. Ne la connaissant pas, je te propose une solution naïve:

- On part du principe que tu as déjà x.
- Il te faut coder une pile gérant des entiers (avec "empiler",  "désempiler" et "récupérer haut de la pile").
- Tu parcours ton tableau, tu empiles la première valeur. Si la somme des éléments de la pile est égale à som, tu as ton résultat. Si la som est inférieur, tu insères de nouveau la valeur. Si la somme est supérieur, tu désempiles la valeur, et tu passes à la suivante. Tu recommences alors cette étape.

Il te faut, techniquement, que tu crées les éléments suivants:
- Coder une pile.
- Réaliser une fonction qui prend en argument une pile et un x, qui applique la formule x*segc[i]+ x*segc[j]+ x*segc[k] + .... +......

N'hésite pas à poster ton code et tes avancées.

________________________________________________________________________
Historique de mes créations, et quelques articles:
[ http://0217021.free.fr/portfolio http://0217021.free.fr/portfolio]
Merci d'utiliser Réponse acceptée si un post répond à votre question

cptpingu · Answer

À noter que tu peux remplacer l'utilisation d'une pile, par une fonction récursive (si tu es à l'aise avec la récursivité).

________________________________________________________________________
Historique de mes créations, et quelques articles:
[ http://0217021.free.fr/portfolio http://0217021.free.fr/portfolio]
Merci d'utiliser Réponse acceptée si un post répond à votre question

BunoCS · Answer

Yop,
Je n'ai jamais vraiment aimé les stat/proba (calcul de combinaison,...) mais voici ma modeste contribution à ton problème:
ne pourrais-tu pas t'inspirer du problème du sac à dos?


@+
Buno, Admin CS
L'urgent est fait, l'impossible est en cours. Pour les miracles, prévoir un délai...

cptpingu · Answer

Je n'ai jamais vraiment aimé les stat/proba (calcul de combinaison,...) Parce qu'il y a des gens qui aiment :p ? ne pourrais-tu pas t'inspirer du problème du sac à dos? C'est effectivement un problème de ce genre, en un peu plus complexe. L'algorithme proposé précedemment est celui dénommé "glouton" (que j'ai nommé naïf) dans le lien proposé par buno. ________________________________________________________________________ Historique de mes créations, et quelques articles: [ http://0217021.free.fr/portfolio http://0217021.free.fr/portfolio] Merci d'utiliser Réponse acceptée si un post répond à votre question

Somme d’éléments d'u tableau

6 réponses

Votre réponse

Discussions similaires