Discussion :

[azziz2005]

Bonjour,
Comment je peux decomposer un nb QQ a une sommation des nbs qui appartienent a un ensembre definie.

par exemple

E={1,2,4,8,16,...}puissance a 2
decompose(3)
3=1+2;
decompose(5)
5=1+4;
decompose(6)
6=4+2;
decompose(7)
7=4+2+1;
decompose(9)
9=8+1;
decompose(10)
10=8+2;
....
Merci

[j.p.mignot]

un code de ce type par exemple

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
 
 
function p2(n : integer) : string;
var s : string; a : integer;
   begin
   s:='';
   if n <0 then s:='?' else if n=0 then s:='0' else
      begin
      s:='';
      a:=1;
      while n <> 0 do
         begin
         if ((n and 1)=1) then s:= IntToStr(a) + ' + ' + s;
         n:= n shr 1;
         a:=a shl 1;
         end;
      delete(s,length(s)-2,3);
      end;
   p2:=s;
   end;

[Jean-Marc.Bourguet]

Comment je peux decomposer un nb QQ a une sommation des nbs qui appartienent a un ensembre definie.

Le probleme est NP complet en general, mais certains ensembles (comme les puissances de deux) permettent une decomposition facile.

Vu que le probleme est NP complet, il est difficile de faire beaucoup mieux que d'essayer toutes les possibilites. Le tout est de les visiter dans le bon ordre pour avoir la meilleure chance de trouver rapidement la bonne. La technique gloutonne (essayer d'abord a chaque etape le nombre le plus grand possible) est l'heuristique la plus evidente.

Une recheche sur sac a dos, knapsack devrait fournir plus d'info.

[random]

tu écris tes nombres en base 2
0000000000000000001 1
0000000000000000010 2
0000000000000000100 4
0000000000000001000 8
0000000000000010000 16
0000000000000100000 32

tu observes ton nombre cible par exemple 9=1001 la réponse est inscrite
dans le nombre 1000=8 + 1=1

[ToTo13]

Bonjour,

je ne suis pas certain que ce soit un problème NP complet...

Pour ce qui est du problème à résoudre :
puisque tu connais déjà ton ensemble de nombre qui doivent servir à la décomposition, il te suffit de faire comme pour un décomposition en base 2, mais avec ton ensemble...

[FrancisSourd]

Si, il est NP-complet. On peut très facilement réduire le problème de partition à ce problème.

[azziz2005]

Bonjour,
la decomposition d'un nombre en binaire resoud le probléme.
j'ai une autre question a propos du codage de hamming
une autre question SVP

Le taux d'erreur est calculé a partir du nombre de bits recus erronnés
/ le nombre total des bits recus .
Comment je peux analyser pour plusieurs transfers de données le taux d'erreurs entre 1% et 10%?

[ToTo13]

Si tu veux des réponses, fais un nouveau forum...

[azziz2005]

OK
Merci