decomposer un nombre entier

Version imprimable

03/04/2006, 18h46
azziz2005

decomposer un nombre entier

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

un code de ce type par exemple

Code:

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;

03/04/2006, 19h32
Jean-Marc.Bourguet

Re: decomposer un nombre entier

Citation:

Envoyé par azziz2005

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.
04/04/2006, 08h48
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
05/04/2006, 11h48
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...
05/04/2006, 11h56
FrancisSourd

Si, il est NP-complet. On peut très facilement réduire le problème de partition à ce problème.
05/04/2006, 18h54
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%?
05/04/2006, 20h13
ToTo13

Si tu veux des réponses, fais un nouveau forum...
06/04/2006, 18h47
azziz2005

OK
Merci