Détermination d'une somme

Version imprimable

Slt.
Code:

1 2 3 4 5 6 7 8 9 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 qui determine le premier element x de div4 qui verifie:

Code:

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 % x =0)
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 :((
Aidez moi SVP.

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.

L'algorithme est assez simple :

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
 
- tant qu'on a pas trouvé la solution :
       - prendre un élément de div4.
       - si som%element != 0
                    -> continue
      -  sinon :
                 - calculer Atrouver = som/element;
                 - somme = 0;
                 - i = 0;
                 - tant que somme != Atrouver et somme != -1
                         - ++i;
                         - ++x;
                         - si ??????
                                        - somme = -1
                         - sinon
                                        - somme = 0;
                         - fin si
                         - ibis = i;
                         - j =0;
                         - tant que ibis != 0 et somme != -1
                                  - si ibis%2
                                         - somme += segc[j];
                                  - ibis >>= 1;
                                  - ++j
                         - fin tant que
                - fin tant que
                //si somme = -1, pas de solutions possibles
       - fin si
-fin tant que

Par contre pour plus de facilité, j'ai préféré trié segc par ordre croissant.
Je te laisse quand même chercher un peu pour la condition avec les "????"

EDIT : 2ème possibilité

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
typedef struct
{
          int nombre;
          int i;
} SousSomme;
 
                 - somme = 0;
                 - i = 0;
                 - resultat;
                 - tant que somme != Atrouver et somme != -1
                         - si segc[i] > Atrouver
                                        - somme = -1
                         - sinon
                                        - si segc[i] == Atrouver
                                                 somme = Atrouver
                                                 resultat = 1 << i;
                                        - sinon 
                                                 pour chaque element de Z
                                                          - si Zi.nombre + segc[i] == Atrouver
                                                                     somme = Atrouver
                                                                      resultat = 1<<i | Zi.i
                                                           - sinon si Zi.nombre + segc[i] > Atrouver
                                                                       on supprimer Zi de Z
                                                           - sinon
                                                                       on ajoute Zy = {Zi.nombre + segc[i] , 1<<i | Zi.i} à Z
                         - fin si
                         - ++i;
                - fin tant que
                //si somme = -1, pas de solutions possibles

Avec Z une liste de SousSomme

13/08/2012, 21h45
kwariz

Bonjour,

Quelques questions/remarques :

* segc est l'ensemble des {4i+1} pour i de 0 à 63
* div4 est l'ensemble des {4(i+1)} pour i de 0 à 63
* Dans ton exemple tu donnes som=114688 et tu t'attends à la réponse {253,253,5,1} pour x=224 ; y a-t-il une raison particulière pour préférer cette réponse à {1 répété 512 fois} ? ou à x=4 et {1 répété 28672 fois} ? (tu remarqueras que les multiples de 4 ont tous une solution triviale, les non multiples de 4 n'ont aucunes solutions)

Edit: typo
14/08/2012, 03h06
nirvana_90

Pour div4 ça représente les diviseurs de 4 inférieurs à 255.
Pour segc c'est bien l'ensemble de 4n+1 inférieur à 255.
Pour la combinaison je doit trouver une combinaison avec le plus petit nombre d’éléments c'est pourquoi j'ai trié segc en ordre décroissant.

Citation:

Pour div4 ça représente les diviseurs de 4 inférieurs à 255.
Pour segc c'est bien l'ensemble de 4n+1 inférieur à 255.
Pour la combinaison je doit trouver une combinaison avec le plus petit nombre d’éléments c'est pourquoi j'ai trié segc en ordre décroissant.

Tu aurais dû nous dire cela dès ton premier post.
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 si nombre%4 - pas de solutions sinon - nombre >>= 2; - liste = listeDiviseurDeNombre(nombre); - pour chaque elementDeliste X: //lecture selon l'ordre décroissant - si X > ???? - continu; - sinon - break; - fin boucle - tmpNombre = nombre/X; - modulo = tmpNombre % 4; - n = tmpNombre / 4; - solution[modulo]; - i = 0; - tant que i != modulo - solution[i] = n - (1 + (modulo - 1 - i))/2 * (modulo - 1 - i); - si solution[i] > ??? solution[i] -= i; - n -= solution[i]; - solution[i] <<= 2; - ++solution[i]; - break; - fin tant que;
Et tu n'as plus besoin de tes deux tableaux.

On n'a effectivement pas besoin des tableaux.

I- Recherche de x et de somme
Pour trouver x, il suffit de diviser som par 4 et de rechercher le plus grand diviseur du résultat parmi 63, 62,...3,2,1.
Pas besoin de tableau.

II- Maintenant, reste à trouver la composition de somme avec les éléments du tableau segc (qui s'avérera inutile):

1- Les éléments de segc ont la forme 4*n+1 avec n = 0..63 . On doit donc avoir, si on utilise N termes,
      somme = (1+4*a0) + (1+4*a1) + (1+4*a(N-1)) avec les ai = 0..63
en posant pour simplifier S = (a0+a1+...+a(N-1))
[1]   somme = N + 4*S  
On pose (division euclidienne)
[2]   somme = 4*P+Q , Q<4  
[3]   N = 4*n+m , m<4
L'expression [1] devient
      4*P+Q = 4*n+m+4*S = m+4(n+S)
et on a (division euclidienne)
[4]   m = Q 
[5]   P = n+S 
2- Reste à trouver le plus petit n.
D'après [5] et comme les ai<=63 :
       P = n+S <= n+N*63 = n+(4*n+m)*63 = 253*n +63*m = 253*n +63*Q
Donc
       P-63*Q <= 253*n 
On prendra le plus petit n qui vérifie cette relation. On connait maintenant n et N (cf [3] et [4]) : N=4*n+Q 
3- Recherche des éléments de S :
On a (cf [5])  S = P-n et on pose
       P-n = 63*A + B  ,  B<63
Alors 
       S =  63*A + B = 63+63+...63 + B + 0+0...+0 
avec A termes 63, un terme B et N-A-1 termes à 0. On a donc
       ai = 63  ,  i=0..A-1
       ai = B   ,  i=A
       ai = 0   ,  i=A+1..N-1
D'où 
       somme = (253 +...+253) + (4*B+1) + (1 +...........+1) 
                ...A fois...               ...N-A-1 fois...
4- Le code doit donc faire :
- Calculer P = somme/4
- Calculer Q = somme%4
- Calculer n : en posant t = P-63*Q   
     - si t<= 0 :  n=0 
     - sinon si t est divisible par 253 n= t/253
     - sinon n= t/253+1
- le nombre total de termes est N = 4*n+Q
- il y a n253 = (P-n)/63 termes à 253 (=4*63+1)
- il y a un terme v = (P-n)%63*4+1;
- Il y a n1 = N-n253-1 termes à 1 (=4*0+1)
5- On peut stocker ces caractéristiques dans une structure qui suffit à décrire la décomposition. Par exemple :
Code:

1 2 3 4 5 6 7 struct Somme { int x; int n253; int v; int n1; };
L'ensemble du code effectuant ce travail est simple et s'écrit en une quinzaine de lignes :

14/08/2012, 14h20
kwariz

Citation:

Envoyé par nirvana_90

Pour div4 ça représente les diviseurs de 4 inférieurs à 255.
Pour segc c'est bien l'ensemble de 4n+1 inférieur à 255.
Pour la combinaison je doit trouver une combinaison avec le plus petit nombre d’éléments c'est pourquoi j'ai trié segc en ordre décroissant.

Bonjour,
Sans vouloir pinailler, les diviseurs de 4 (les nombres qui divisent 4) sont 1,2 et 4. Ton tableau div4 contient les multiples de 4 (les nombres que 4 divise) inférieurs à 255.
Pour débroussailler un peu :
- si som n'est pas un multiple de 4 : pas de solution
- si som est un multiple de 4 inférieur à 255 : une solution unique x=som et {1}
- si som est un multiple de 4 supérieur à 255 : c'est là que le problème devient un peu plus intéressant. Il est alors équivalent à résoudre le problème du rendu de monnaie sur som/(un multiple de 4) sur la base segc.
Tout va dépendre si une bonne solution (pas forcément prouvée optimale en terme de longueur) te convient et dans ce cas un algorithme glouton comme Neckara te donne convient à merveille.
Si tu as besoin d'une solution optimale alors il faut prouver que ta base segc est canonique (revient à vérifier que l'algorithme glouton donne le résultat optimal pour tous les nombres entre 253+1=254 et 253+249=502) entre autre ... un peu plus de boulot en l'occurence.

Au final, de quoi as-tu besoin exactement ?