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

Delphi Discussion :

Comment faire un algorithme recursif


Sujet :

Delphi

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre averti
    Profil pro
    Inscrit en
    Octobre 2006
    Messages
    22
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2006
    Messages : 22
    Par défaut Comment faire un algorithme recursif
    Bonjour

    Je voudrais transformer mon code pour le rendre plus propre, et je pense que je dois faire une truc recursif. Mais voilà, j'y arrive pas. Je sais pas comment m'y prendre.
    J'ai fait mon code pour cas avec nb = 8 (et donc je me tape du i, j, k, l, m, o, p) mais je voudrais pouvoir le faire fonctionner avec nb = 10 ou nb = n'importe quel chiffre paire.
    Donc ma question, c'est comment on s'y prend pour faire du recursif à part appeller LA fonction dans LA fonction.

    Merci d'avance

    Voilà mon code
    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
    30
    31
     
    for i:=0 to nb-1 do begin
      for j:=0 to nb-1 do begin
        for k:=0 to nb-1 do begin
          for l:=0 to nb-1 do begin
            for m:=0 to nb-1 do begin
              for n:=0 to nb-1 do begin
                for o:=0 to nb-1 do begin
                  for p:=0 to nb-1 do begin
                    if (   ((i <> j)and(i <> k)and(i <> l)and(i <> m)and(i <> n)and(i <> o)and(i <> p))
                      and((j <> k)and(j <> l)and(j <> m)and(j <> n)and(j <> o)and(j <> p))
                      and((k <> l)and(k <> m)and(k <> n)and(k <> o)and(k <> p))
                      and((l <> m)and(l <> n)and(l <> o)and(l <> p))
                      and((m <> n)and(m <> o)and(m <> p))
                      and((n <> o)and(n <> p))
                      and((o <> p))) then begin
                      inc(a);
                      setlength(tab, a);
                      tab[a-1] := tab_1[i] +tab_2[i,j] + tab_1[j];
                                                 tab[a-1] := tab[a-1] +tab_1[k] + tab_2[k,l] + tab_1[l];
                                                 tab[a-1] := tab[a-1] +tab_1[m] + tab_2[m,n] + tab_1[n];
                                                 tab[a-1] := tab[a-1] +tab_1[o] + tab_2[o,p] + tab_1[p];
                    end;
                  end;
                end;
              end;
            end;
          end;
        end;
      end;
    end;

  2. #2
    Membre averti
    Profil pro
    Inscrit en
    Octobre 2006
    Messages
    22
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2006
    Messages : 22
    Par défaut
    Oups je suis pas au bon endroit pour poser ma question

  3. #3
    Rédacteur
    Avatar de Pedro
    Profil pro
    Inscrit en
    Octobre 2003
    Messages
    5 411
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2003
    Messages : 5 411
    Par défaut
    Salut
    Citation Envoyé par maxclo
    Donc ma question, c'est comment on s'y prend pour faire du recursif à part appeller LA fonction dans LA fonction.
    Faire du récursif est appeler la fonction dans la fonction

    Je me demande d'ailleurs si la récursivité est la meilleure solution à ton problème
    Pedro
    Aucune réponse aux sollicitations techniques par MP

    Faut pas attendre d'en avoir besoin pour s'en servir... (Lucien Stéphane)

    Les pages Source C'est bon. Mangez-en!
    Le défi Delphi
    Règles du forum - FAQ Delphi - Pensez au chtit
    Aéroclub Bastia Saint-Exupéry

  4. #4
    Membre Expert Avatar de philnext
    Profil pro
    Inscrit en
    Octobre 2002
    Messages
    1 553
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2002
    Messages : 1 553
    Par défaut
    Ta fonction est censée faire quoi en fait ?

  5. #5
    Membre éprouvé Avatar de giltonic
    Profil pro
    Inscrit en
    Juillet 2002
    Messages
    109
    Détails du profil
    Informations personnelles :
    Âge : 51
    Localisation : France

    Informations forums :
    Inscription : Juillet 2002
    Messages : 109
    Par défaut
    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
    procedure TDataMod.RecusChaineArbre(Const ATable:string;Const AParentID:integer;Var AChaine:string);
    var Query:TZZMysqlQuery;
    begin
         Query:=TZZMysqlQuery.Create(Self);
         Query.DataBase:=DataMod.MySqlDatabase;
         Query.Close;
         Query.SQL.Clear;
         Query.SQL.Add('SELECT GAMID FROM '+ATable+' WHERE GAMPARENTID=' + IntToSTr(AParentID) );
         Query.Open;
         If Query.RecordCount=0 then exit;
         While not(Query.eof) do
              begin
                   AChaine := AChaine + Query.Fields[0].asstring;
                   AChaine := AChaine + ',';
                   RecusChaineArbre(ATable,Query.Fields[0].asinteger,AChaine);
                   Query.Next;
              end;
        Query.Close;
        Query.Free;
    end;
    Cette procedure me donne récursivement une chaine avec tout les enregistrements de la table gamme concernés par ma racine... c totalement hors sujet mais la récursivité est en gras rouge

  6. #6
    Membre averti
    Profil pro
    Inscrit en
    Octobre 2006
    Messages
    22
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2006
    Messages : 22
    Par défaut
    Bonjour

    Initialement je voulais faire 2 choses en une seule
    Cet à dire faire ma liste
    1234
    1243
    1324
    1342
    1423
    1432

    Et faire en meme temps mon petit calcul issu de 2 tableaux un simple et un a 2 dimensions.

    Bon maintenant je me dis que je vais dejà faire ma petite liste (parce que en fait je vais avoir plusieurs cas de figure) et que ensuite je la parcourerais pour faire mes petits calculs à partir de mes 2 tableaux

    Pour que vous compreniez bien, je vais expliquer le contexte. J'ai des auditeurs qui doivent faire x missions. Pour le moment ils en font 2 par semaine (mais ca pourrait etre 4 dans l'avenir). Et je dois optimiser les trajets qu'il vont faire sur par exemple les 2 mois à venir donc 2*8 missions. Sachant qu'il rentre chez eux tous les WE et qu'il vaut mieux qu'il se tape plein de route en debut de semaine que en fin de semaine. Donc mon idée etait de calculer comme une bourine tous les trajets possibles donc faire
    Tra Dom M1 + Tra M1 M2 + Tra M2 Dom + Tra Dom M3 + Tra M3M4 + Tra M4 Dom ..
    à comparer avec
    Tra Dom M1 + Tra M2 M3 + Tra M3 Dom + Tra Dom M2 + Tra M2M4 + Tra M4 Dom ..

    Et de prendre celui qui est le plus petit en terme de trajet et qui correspond au critere qui evolue un peu tous les jours. Voilà vous savez tout

  7. #7
    Membre averti
    Profil pro
    Inscrit en
    Octobre 2006
    Messages
    22
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2006
    Messages : 22
    Par défaut
    voilà ce que j'ai refais, meme si j'ai plus mes ijklm, ca ne resoud pas mon probleme car ca je n'arrive pas à faire une seule fonction pour n valeur, et là c'est que pour 4 valeurs

    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
    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
     
    procedure TF_principale.Button5Click(Sender: TObject);
     
    procedure affiche(nb : integer; tab : array of integer);
    begin
      if tab[0] < nb then begin
        if tab[0] <> tab[1] then begin
          if tab[0] <> tab[2] then begin
            if tab[0] <> tab[3] then begin
     
              if tab[1] < nb then begin
                if tab[1] <> tab[2] then begin
                  if tab[1] <> tab[3] then begin
     
                    if tab[2] < nb then begin
                      if tab[2] <> tab[3] then begin
     
                        if tab[3] < nb then begin
                          memo2.lines.add(inttostr(tab[0]) + ' - ' +inttostr(tab[1])+ ' - ' +inttostr(tab[2])+'- '+inttostr(tab[3]));
                          inc(tab[3]);
                          affiche(nb,tab );
                        end else begin
                          inc(tab[2]);
                          tab[3] := 0;
                          affiche(nb,tab);
                        end;
     
                      end else begin
                        inc( tab[3]);
                        affiche(nb,tab);
                      end;
                    end else begin
                      inc(tab[1]);
                      tab[2] := 0;
                      tab[3] := 0;
                      affiche(nb,tab);
                    end;
                  end else begin
                    inc( tab[3]);
                    affiche(nb,tab);
                  end;
                end else begin
                  inc( tab[2]);
                  affiche(nb,tab);
                end;
              end else begin
                inc(tab[0]);
                tab[1] := 0;
                tab[2] := 0;
                tab[3] := 0;
                affiche(nb,tab);
              end;
            end else begin
              inc(tab[3]);
              affiche(nb,tab);
            end;
          end else begin
              inc(tab[2]);
              affiche(nb,tab);
          end;
        end else begin
            inc(tab[1]);
            affiche(nb,tab);
        end;
      end;
    end;
    var
      tableau : array of integer;
    begin
      memo2.clear;
      setlength(tableau, 4);
      tableau[0] := 0;
      tableau[1] := 0;
      tableau[2] := 0;
      tableau[3] := 0;
      affiche(4,tableau);
    end;

  8. #8
    Expert confirmé
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Mai 2002
    Messages
    3 491
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : Mai 2002
    Messages : 3 491
    Par défaut
    salut

    pour une fonction recursive le principale et de determiner la condition de sortie
    apres il faut savoir exactement ce que tu veut faire

    par exemple si tu veut calculer la somme des celulle contenue dans ton tableau

    tu peut tre bien faire

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    function  somme(tab,index) : integer;
    begin
      if index < higth(Tab) Then
        Result := Result+tab[index]+somme(tab,index+1)
      else 
         Result := Result+tab[index]
    end;
    la fonction non recursif serait
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    function  somme(tab) : integer;
    var
     index : integer;
    begin
    index:=0
    while index < higth(Tab) do
    begin
      result := result+tab[index]
      inc(index);
    end
    end;
    @+ Phil

  9. #9
    Membre éprouvé Avatar de giltonic
    Profil pro
    Inscrit en
    Juillet 2002
    Messages
    109
    Détails du profil
    Informations personnelles :
    Âge : 51
    Localisation : France

    Informations forums :
    Inscription : Juillet 2002
    Messages : 109
    Par défaut
    Citation Envoyé par maxclo
    Pour que vous compreniez bien, je vais expliquer le contexte. J'ai des auditeurs qui doivent faire x missions. Pour le moment ils en font 2 par semaine (mais ca pourrait etre 4 dans l'avenir). Et je dois optimiser les trajets qu'il vont faire sur par exemple les 2 mois à venir donc 2*8 missions. Sachant qu'il rentre chez eux tous les WE et qu'il vaut mieux qu'il se tape plein de route en debut de semaine que en fin de semaine. Donc mon idée etait de calculer comme une bourine tous les trajets possibles donc faire
    Tra Dom M1 + Tra M1 M2 + Tra M2 Dom + Tra Dom M3 + Tra M3M4 + Tra M4 Dom ..
    à comparer avec
    Tra Dom M1 + Tra M2 M3 + Tra M3 Dom + Tra Dom M2 + Tra M2M4 + Tra M4 Dom ..

    Et de prendre celui qui est le plus petit en terme de trajet et qui correspond au critere qui evolue un peu tous les jours. Voilà vous savez tout
    Tres interessant, c'est de l'IA ton truc en fait.

    Pour ta liste c'est ce que mon prof de maths appelait un "arrangement". En gros il faut essayer toutes les possibilités. Mais a mon avis tu peux couper les "arbres" assez facilement. Tu n'as pas a parcourir tout de 0 à n-1, au fur et a mesure que tu avances dans ton arbre sa dimension limite diminue. donc tu n'auras pas a faire des tests pour savoir si c'est pris ou pas... est ce que je me suis fait comprendre ? Genre faire un tableau des valeurs, et un algo qui les melanges. Avant de faire quoi que ce soit, il faudra connaitre les dimensions des tableaux. Sachant qu'il y a n valeurs, il va y avoir n! (factoriel n) facons de le ranger...

    position 1 : n possibilités
    position 2 : n-1 possibilités
    ..etc.
    position n-1 : 2 possibilités
    postion n : plus qu'une seule possibilité
    d'ou le n! = n*(n-1)*...*2*1

    J'espere que j'ai fait progresser ta recherche.

    Va sur
    http://perso.orange.fr/jean-paul.dav...arr/index.html
    en prennant Arrangements de k = 4 éléments parmi n = 4 éléments.

    Salutations

  10. #10
    Membre éclairé
    Profil pro
    Inscrit en
    Novembre 2004
    Messages
    488
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2004
    Messages : 488
    Par défaut
    Salut,

    Juste une intervention pour faire remarquer que 16! = 2x10^13 (vingt mille milliards)... Les calculs risquent d'être longs, surtout en passant à 4 trajets par semaine (32! = 2x10^35).

    En fait ce problème est une variante d'un grand classique connu sous le nom de ... Problème du voyageur de commerce

    Par contre je pense qu'il est possible de ralentir l'explosion combinatoire si l'on ne tient pas compte de l'ordre des semaines (on divise par n/2!). et si on ne tient pas compte de l'ordre des villes lors d'une semaine (on gagne encore un facteur 2^n/2).

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Comment faire cet algorithme ?
    Par manatalenta dans le forum Algorithmes et structures de données
    Réponses: 6
    Dernier message: 03/12/2014, 19h56
  2. Makefile recursif, comment faire ?
    Par kamouminator dans le forum Linux
    Réponses: 2
    Dernier message: 29/04/2009, 18h22
  3. Comment faire un algorithme recursif
    Par maxclo dans le forum Algorithmes et structures de données
    Réponses: 15
    Dernier message: 08/03/2007, 16h57
  4. Comment faire pour mettre l'ecran en veille ?
    Par March' dans le forum MFC
    Réponses: 6
    Dernier message: 29/08/2002, 14h25
  5. Comment faire pour créer un bitmap
    Par GliGli dans le forum C++Builder
    Réponses: 2
    Dernier message: 24/04/2002, 15h41

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