Forum Programmation.autre Algo de recherche arborescente en largeur

Posté par (page perso) .
Tags : aucun
0
6
oct.
2004
Salut, j'ai un petit exercice à réaliser, mais mes lacunes en maths me coutent chers :

Soit x un entier, on a x = Somme( i=0; k) bi*2^i , où bi E {-1;0;1}

Mon problème consiste à trouver, pour x fixé, une suite la plus courte possible, constituée d'additions et de soustractions.

Je m'oriente vers une recherche arborescente en largeur, ou chaque niveau correspondera a un terme en plus dans la somme.

Existe t-il une meilleur solution, ou sinon, existe t-il des règles qui permettent de limiter la taille de l'arbre et donc le temps de calcul ?

Le but, est simplement de trouver un temps de calcul raisonnable ( de qq dizièmes de secondes à qq secondes) pour des nombres d'environ 32 ou 64 bits (ce que m'offrent la plupart des langages en fait).
  • # Demandes de précisions

    Posté par . Évalué à 3.

    Qu'appelles-tu "plus court" ?
    D'autre part, si c'est un exercice de cours ou de TD, quémander la solution n'est pas forcément une bonne idée. Alors, fake ?
    Sinon si "plus court" signifie que le dernier chiffre non-nul a le rang le plus faible : reste en binaire, le -1 ne sert à rien.
    Si par contre "plus court" signifie le moins grand nombre de chiffres non-nuls, ce qui présente plus d'intérêt, pas encore d'idée. Sorry.
    • [^] # Re: Demandes de précisions

      Posté par (page perso) . Évalué à 1.

      C'est très gentil de veiller à ce que je fasse mes devoirs moi-même.
      Non, c'est juste une question/un délire avec un copain.
      Je fé un bts d'info alors je m'ennuie, voilà...
      On s'occupe comme on peut hein !


      plus court signifie la somme la plus courte :

      60 = 4+8+16+32 = 64-4 (= 64 +(-4))

      La deuxième somme est plus courte que la première.

      « Il n’y a pas de choix démocratiques contre les Traités européens » - Jean-Claude Junker

  • # marrant, ton truc

    Posté par (page perso) . Évalué à 2.

    A titre personnel , je tenterais une approche par récurrence
    ou le calcul de la meilleure solution pour x appelerait
    le calcul de la meilleure solution pour 2^(n+1)-x et
    le calcul de la meilleure solution pour x-2^n, où
    2^n est la plus grande puissance de 2 inférieure ou égale à x.
    (Je ne considère ici que des x positifs).

    Mais c'est juste une intuit....
    Tu nous tiens au courant ? Ca pourrait plaire à mes étudiants...
    • [^] # Re: marrant, ton truc

      Posté par (page perso) . Évalué à 4.

      Bon, ça m'a titillé ton truc. J'ai codé mon algo en scilab.
      Ca a l'air de marcher.

      function [e,t]=ecriture(x)
      if (x>0) then
      p=1;
      while (p<x), p=2*p, end
      if (x==p) then
      e=[p];
      t=1;
      else
      [f,u]=ecriture(p-x);
      [g,v]=ecriture(x-p/2);
      if (u<v) then e=[p -f], t=u+1
      else e=[p/2 g], t=v+1, end

      end
      else
      e=[];
      t=0;
      end
      endfunction

      Par exemple, pour 121:
      [e,s]=ecriture(121)
      s= 3
      e=[ 128 -8 1]
      • [^] # Re: marrant, ton truc

        Posté par (page perso) . Évalué à 1.

        je comprendpas bien la syntaxe de ce langage : on a du mal à détérminer quand les blocks se terminent.

        Ce serait possible de clarifier un peu ?
        merci :)

        « Il n’y a pas de choix démocratiques contre les Traités européens » - Jean-Claude Junker

        • [^] # Re: marrant, ton truc

          Posté par (page perso) . Évalué à 2.

          Oui, effectivement, la syntaxe de if est un peu déroutante

          if condition then instruction1; instruction2; end
          quand il n'y a pas de "sinon" et

          if condition then instruction1; instruction2;
          else instruction3; instruction4; end
          quand il y en a un.
          (En fait le else ferme le bloc d'instruction précédent).

          Sinon, scilab est orienté liste, donc si tu fais
          a=[2];
          a=[ 1 a];
          a=[a -a 3];

          tu récupères a=[1 2 -1 -2 3]
  • # probleme semblable

    Posté par . Évalué à 1.

    je ne veux pas lancer un troll sur le remplacement de la question posee par une autre question a laquelle j'aurais la réponse ;-)

    Mais le probleme (qui n'a pas de rapport avec linux, non ?) s'apparente à la conversion décimal -> binaire

    A mon avis, il faut:
    1: déterminer le signe de x, si positif, on utilisera bi = 0|1 sinon bi=0|-1;
    2: y=abs(x)
    2: ensuite, tu regarde si y est pair (bi=0) ou impair (bi=1/-1, cf 1: ), ca te donne bi, pour i=0
    3: y=y/2; tu incrémente i et tu retourne au 2: (tant que y>0)
    • [^] # Re: probleme semblable

      Posté par (page perso) . Évalué à 1.

      merci, mais pas exactement.

      J'ai oublié de préciser x positif, et je cherche bien à déterminer x positif avec bi=-1|0|1

      Exemple : 63 = 1+2+4+8+16+32 = 64-1 ...

      « Il n’y a pas de choix démocratiques contre les Traités européens » - Jean-Claude Junker

      • [^] # Re: probleme semblable

        Posté par . Évalué à 2.

        si je comprends bien, tu veux avoir le moins de '0' possible en utilisant des soustractions ?

        Dans ce cas, bi = 1|-1 , non ?

        parce que si tu prends en compte bi=0, ton exemple n'est pas complet:
        63 = 1+2+4+8+16+32 = 1*64 + 0*32 + 0*16 + 0*8 + 0*4 + 0*2 + (-1)*1

        La solution que je te propose n'apporte pas la solution optimale.
        Peut-etre peux-tu essayer d'optimiser celle-ci. Les suites 111 (3 '1' consecutifs) peuvent etre optimisées en 1000-1 :
        exemple:
        1000111010 = 1001000010 - 1000
        du coup, a droite, tu a moins de '1'

        cela est valable pour les suites de 3 '1' ou plus
        cette transformation marche bien sur un cas, mais il faut sans doute
        faire un peu de recursivite (ca complique la chose, evidemment)

        Cela s'applique a quoi, ce type de pb ?

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.