Discussion :

[nirvana_90]

Slt.

Code :

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

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 :

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

	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.

[Neckara]

L'algorithme est assez simple :

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

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

[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

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

[Neckara]

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 :

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

[diogene]

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 :

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

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 :

[kwariz]

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 ?