IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Défis langages fonctionnels Discussion :

Défi N°1 : Génération des ensembles de nombre dont la somme est identique


Sujet :

Défis langages fonctionnels

  1. #141
    Futur Membre du Club
    Profil pro
    Inscrit en
    Janvier 2008
    Messages
    14
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2008
    Messages : 14
    Points : 8
    Points
    8
    Par défaut
    Je suis content d'apprendre que je suis pas le seul à m'interesser aux partitions d'un entier...
    Pour commencer je ne crois pas qu'il soit possible d'avoir une formule simple pour compte les solutions (ramanujan et hardy ont une formule degueulasse et probablement indémontrable qui donne un O avec égalité jusqu'a n=200 si ma mémoire est bonne)
    Ensuite je suis impressionné par vos solutions et surtout par vos optimisations, ca prouve qu'il me reste beaucoup à apprendre...
    Bref pour ce qui est du code, j'ai fait une solution en Ada et je suis entrain d'en mettre au point une en perl (pas trop des langages fonctionnels je sais...)
    Au niveau Ada comme je l'ai expliqué sur mon post dans la section ada j''utilise un algorithme recursif qui génère l'abre des solutions...
    j'arrive à calculer jusqu'à N=77 sur une machine normale
    en temps j'ai
    part(50)=>0.444s 204226
    part(60)=>1.791s 966467
    part(70)=>7.427 4087968
    et plus de 50s pour n=77
    je pensais pas qu'il etait possible d'avoir des resultats pour n=120 et plus vu le nombre de listes possibles...
    enfin bon voila le code
    Code ada : 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
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
     
    with Ada.Command_Line,Ada.Text_IO,Ada.Unchecked_Deallocation;
    use Ada.Command_Line,Ada.Text_IO;
     
    procedure partition is
     
       type Cellule;
     
       type Liste is access Cellule;
     
       type BCellule;
     
       type Bliste is access BCellule;
     
       type BCellule is record
          Val:Liste;
          Suiv:BListe;
       end record;
     
       type Cellule is record
          Val:Natural;
          Suiv:Liste;
       end record;
     
       type Tab;
     
       type Ptab is access Tab;
     
       type Part is record
          Val:Natural;
          Rest:Natural;
          Suiv:PTab;
       end record;
     
       type Tab is array(Natural range<>) of Part;
     
       B:BListe;
     
    N:Natural:=0;
     
    procedure Free is new Ada.Unchecked_Deallocation(Cellule,Liste);
     
    procedure Libere(L:in out Liste) is
    Prec:Liste;
    begin
    while L/=null loop
    Prec:=L;
    L:=L.suiv;
    Free(Prec);
    end loop;
    end;
     
       function min(A:in Natural;B:in Natural) return Natural is
       begin
          if B=0 then return A; end if;
          if A<B then return A;
          else return B;
          end if;
       end;
     
       procedure Traite(P:in out Part) is
          Limite:Natural:=min(P.Rest,P.Val);
          Entree:Part;
       begin
          P.Suiv:=new Tab(1..Limite);
          for I in 1..Limite loop
             Entree:=(Val=>I,Rest=>(P.Rest-I),Suiv=>null);
             P.Suiv(I):=Entree;
          end loop;
       end;
     
             procedure Partit(Rac: Part) is
     
       begin
          if Rac.Rest=0 then N:=N+1; return;
          else
             for I in Rac.Suiv'Range loop
                Traite(Rac.Suiv(I));
                Partit(Rac.Suiv(I));
                end loop;
          end if;
       end;
     
       procedure Construit(Rac:in Part;L:Liste) is
     
          procedure AjoutB(A: in Liste) is
          begin
             B:=new BCellule'(Val=>A,Suiv=>B); return;
          end;
     
          function Copie(P: in Liste) return Liste is
             PCourant:Liste:=P;
             Debut:Liste:=new Cellule;
          begin
             Debut:=null;
             while PCourant/=null loop
    if PCourant.Val/=0 then
                Debut:=new Cellule'(Val=>PCourant.Val,Suiv=>Debut);
    end if;
                PCourant:=PCourant.Suiv;
             end loop;
             return Debut;
          end;
          Eff:Liste:=L;
       begin
          if Rac.Rest=0 then AjoutB(new Cellule'(Val=>Rac.Val,Suiv=>L)); return;
          else
             for I in Rac.Suiv'Range
             loop
                Construit(Rac.Suiv(I),Copie(new Cellule'(Val=>Rac.Val,Suiv=>L)));
     
             end loop;
                         Libere(Eff);
          end if;
       end;
     
       procedure AfficheB is
          Courant:BListe:=B;
          I:Natural:=1;
          procedure Affiche (L:in Liste) is
             Courant:Liste:=L;
          begin
             if (Courant=null) then Put_Line("La liste est vide"); return; end if;
             loop
                Put(Natural'Image(Courant.Val));
                Courant:=Courant.Suiv;
                exit when (Courant=null);
             end loop;
             New_Line;
          end;
       begin
          while Courant/=null loop
             New_Line;
             Put(Natural'Image(I)&": ");
             I:=I+1;
             Affiche(Courant.Val);
             Courant:=Courant.Suiv;
          end loop;
       end;
       Debut:Part;
       L:Liste:=null;
    begin
       Put_Line(Command_Name&" renvoie l'ensemble des partitions de "&Argument(1)) ;
       New_Line;
       Put_Line("Pour donner une idee on a les resultats suivants:");
       Put_Line("p(50) = 204226");
       Put_Line("le maximum atteint par l'algo utilisé ici est p(78)=12132164");
       Put_Line("p(100) = 190569292");
       Put_Line("p(200) = 3972999029388");
       Put_Line("p(1000) = 24061467864032622473692149727991");
       Debut:=(Val=>0,Rest=>Natural'Value(Argument(1)),Suiv=>null);
       Traite(Debut);
       Partit(Debut);
    Put_Line("Parti interessante de l'algo terminée"&Natural'Image(N));
       Construit(Debut,L);
       AfficheB;
    end;
    Je vais voir selon ce que vous avez pu dire comment je peux ameliorer mon algo...
    Deja je viens de penser qu'à partir du moment ou j'ai rajouté un 1 je sais que je n'aurais plus que ça...
    Je reviens bientot avec un meilleur programme

  2. #142
    Futur Membre du Club
    Profil pro
    Inscrit en
    Janvier 2008
    Messages
    14
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2008
    Messages : 14
    Points : 8
    Points
    8
    Par défaut
    Bon j'ai réussi à améliorer un peu en arretant les appels recursifs quand Val=1. J'arrive à N=88 en 20s et quelque ce qui est vraiment beaucoup mieux, après je ne vois pas à quoi pourrait me servir de memoriser mes resultats puisque chaque liste est genérée de manière unique, il me semble que je ne recalcule rien...
    Si certains d'entre vous voient des améliorations je vous en prie...
    Bonne nuit, j'ai cours demain l'air de rien

  3. #143
    Nouveau Candidat au Club
    Homme Profil pro
    Enseignant
    Inscrit en
    Novembre 2004
    Messages
    3
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : France, Aude (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Novembre 2004
    Messages : 3
    Points : 1
    Points
    1
    Par défaut
    Un beau déterrage de sujet, je mets le code en Python que je n'ai pas trouvé dans ce sujet (il y a dix ans, Python était peut-être moins démocratisé ?).

    Code python : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    def partitions(n):
        def somme(n,m):   
                if n==0:
                    return [[]]
                return [[x]+k for x in range(1,min(m,n)+1) for k in somme(n-x,x)]
        return somme(n,n)

  4. #144
    Membre confirmé
    Profil pro
    Inscrit en
    Mai 2007
    Messages
    340
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mai 2007
    Messages : 340
    Points : 528
    Points
    528
    Par défaut
    Bon ! Si c'est reparti, alors voici un code en Tcl :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    proc partition {n {m -1}} {
      if {$m < 0 || $m > $n } {set m $n}
      if {$n == 0} {return [list [list]]}
      set p {}
      for {set i $m} {$i > 0} {incr i -1} {
         foreach list [partition [expr {$n - $i}] $i] {lappend p [linsert $list 0 $i]}
      }
      return $p
    }
    Un test :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    % partition 10
    10 {9 1} {8 2} {8 1 1} {7 3} {7 2 1} {7 1 1 1} {6 4} {6 3 1} {6 2 2} {6 2 1 1} {6 1 1 1 1} {5 5} {5 4 1} {5 3 2} {5 3 1 1} {5 2 2 1} {5 2 1 1 1} {5 1 1 1 1 1} {4 4 2} {4 4 1 1} {4 3 3} {4 3 2 1} {4 3 1 1 1} {4 2 2 2} {4 2 2 1 1} {4 2 1 1 1 1} {4 1 1 1 1 1 1} {3 3 3 1} {3 3 2 2} {3 3 2 1 1} {3 3 1 1 1 1} {3 2 2 2 1} {3 2 2 1 1 1} {3 2 1 1 1 1 1} {3 1 1 1 1 1 1 1} {2 2 2 2 2} {2 2 2 2 1 1} {2 2 2 1 1 1 1} {2 2 1 1 1 1 1 1} {2 1 1 1 1 1 1 1 1} {1 1 1 1 1 1 1 1 1 1}

Discussions similaires

  1. Réponses: 3
    Dernier message: 23/07/2015, 08h26
  2. Réponses: 8
    Dernier message: 20/03/2015, 16h21
  3. Réponses: 9
    Dernier message: 03/11/2009, 17h39
  4. Rechercher les nombres dont la somme est donnée
    Par TMuet dans le forum Intelligence artificielle
    Réponses: 2
    Dernier message: 17/08/2009, 18h17
  5. Extraire lignes dont le debut est identique
    Par Raoul555 dans le forum Shell et commandes GNU
    Réponses: 3
    Dernier message: 19/05/2007, 12h01

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo