Discussion :

[maxclo]

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;

[maxclo]

Oups je suis pas au bon endroit pour poser ma question

[Pedro]

Salut

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

[philnext]

Ta fonction est censée faire quoi en fait ?

[giltonic]

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

[maxclo]

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

[maxclo]

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;

[giltonic]

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

[anapurna]

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

[Rayek]

De ce que j'ai compris (et au vu de ton dernier code)
J'aurais fait comme ca

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
procedure affiche(nb : integer; tab array of integer);
var
  i,j : integer;
  bModif : Boolean;
begin
  bModif := False;
  for i := 0 to High(Tab) -1 do
    if Tab[i] < nb then
      for j := i + 1 to High(Tab) - 2 do
        if Tab[i] = Tab[j] then
        begin
          inc(Tab[j]);
          Affiche(nb,tab);
          bModif := True;
        end;
  if not bModif then
    memo2.lines.add(inttostr(tab[0]) + ' - ' +
                    inttostr(tab[1])+ ' - ' +
                    inttostr(tab[2])+'- '+
                    inttostr(tab[3]));
end;

Code à tester, je ne suis pas sur vraiment du fonctionnement, mais je pense que tu dois avoir un jeu d'essai pour le faire ^^

[sovitec]

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).

[Gaadek]

Une solution serait de regarder du coté de l'algorithme de Dijkstra.

Pour info: http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra

[maxclo]

Oui en effet c'est une variante et c'est vrai aussi que l'ordre des semaines n'a pas d'importance.
Mais mon probleme par rapport aux alogoritme des voyageurs de commerce c'est que moi je rentre à la maison tous les WE. Et que du coup j'arrive pas à l'adapter.
mais c'est vrai que ma liste
12 34 56 c'est pareil pour moi que 21 43 65 ou me que 65 12 43 parce que une fois que j'ai 'le' trajet qui coute le moins cher en terme de distance apres je reordonne les couples en fonction des autres criteres de confort. (eh oui les petetes passent avant le confort)

[Gaadek]

Bah, c'est uniquement réussir à développer l'algorithme semaine par semaine, et pas les 2 ou 3 d'un coup

[LadyWasky]

Peut-être une piste, tu pourrais peut-être adapter plus facilement l'algorithme si tu raisonnais en terme de temps de parcours et non plus en terme de distance, celà devient donc jouable de sortir des combinaisons de 8h maxi par exemple avec comme contrainte de point terminaux, ta maison.

[Super_françois]

Salut,

Alors déjà si j'ai bien compris, si tu as n points, le nombre de solutions est (n-1)*(n-3)*(n-5)... ce qui est largement inférieur à n! et informatiquement raisonnable à calculer.
Pour ensuite la solution à ton pb, voici ma solution :

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
procedure TForm1.Remplissage(elements : string ; n_tot,n_tmp : integer) ;
var
  element1,element2,liste : string ;
  i,j,k : integer ;
  resu : string ;
  n_loc : integer ;
  index : integer ;
begin
if NbElementsListePointVirgule(elements)>2 then begin
  for i:=0 to NbElementsListePointVirgule(elements)-2 do begin
    liste := '' ;
    element1 := RecupererElementListePointVirgule(elements,1) ;
    element2 := RecupererElementListePointVirgule(elements,i+2) ;
    for j:= 2 to NbElementsListePointVirgule(elements) do begin
      if j<>(i+2) then begin
        liste := liste + RecupererElementListePointVirgule(elements,j) + ';' ;
      end ;
    end ;
    system.Delete(liste, length(liste), 1);
    n_loc := NbElementsListePointVirgule(liste) ;
    index := donne_rang(n_loc) ;
    if i<>0 then begin
      n_tmp := n_tmp + index ;
    end ;
    Remplissage(liste,n_tot,n_tmp) ;
    for k:= 1 to index do begin
      tableau[n_tmp+k-1] := element1+';'+ element2 + ';' + tableau[n_tmp+k-1] ;
    end ;
    indic2 := indic2 + 1 ;
  end ;
end else begin
  tableau[indic] := elements ;
  indic := indic + 1 ;
end ;
end ;
 
function TForm1.donne_rang(n_loc : integer) : integer ;
var
  i,j : integer ;
begin
result:=1 ;
i:=1 ;
while (n_loc-i)>0 do begin
  result := result * (n_loc-i) ;
  i := i+2 ;
end ;
end ;

qui donne, par exemple pour 6 éléments :
1;2;3;4;5;6
1;2;3;5;4;6
1;2;3;6;4;5
1;3;2;4;5;6
1;3;2;5;4;6
1;3;2;6;4;5
1;4;2;3;5;6
1;4;2;5;3;6
1;4;2;6;3;5
1;5;2;3;4;6
1;5;2;4;3;6
1;5;2;6;3;4
1;6;2;3;4;5
1;6;2;4;3;5
1;6;2;5;3;4

ou bien pour 8 élements :
1;2;3;4;5;6;7;8
1;2;3;4;5;7;6;8
1;2;3;4;5;8;6;7
1;2;3;5;4;6;7;8
1;2;3;5;4;7;6;8
1;2;3;5;4;8;6;7
1;2;3;6;4;5;7;8
1;2;3;6;4;7;5;8
1;2;3;6;4;8;5;7
1;2;3;7;4;5;6;8
1;2;3;7;4;6;5;8
1;2;3;7;4;8;5;6
1;2;3;8;4;5;6;7
1;2;3;8;4;6;5;7
1;2;3;8;4;7;5;6
1;3;2;4;5;6;7;8
1;3;2;4;5;7;6;8
1;3;2;4;5;8;6;7
1;3;2;5;4;6;7;8
1;3;2;5;4;7;6;8
1;3;2;5;4;8;6;7
1;3;2;6;4;5;7;8
1;3;2;6;4;7;5;8
1;3;2;6;4;8;5;7
1;3;2;7;4;5;6;8
1;3;2;7;4;6;5;8
1;3;2;7;4;8;5;6
1;3;2;8;4;5;6;7
1;3;2;8;4;6;5;7
1;3;2;8;4;7;5;6
1;4;2;3;5;6;7;8
1;4;2;3;5;7;6;8
1;4;2;3;5;8;6;7
1;4;2;5;3;6;7;8
1;4;2;5;3;7;6;8
1;4;2;5;3;8;6;7
1;4;2;6;3;5;7;8
1;4;2;6;3;7;5;8
1;4;2;6;3;8;5;7
1;4;2;7;3;5;6;8
1;4;2;7;3;6;5;8
1;4;2;7;3;8;5;6
1;4;2;8;3;5;6;7
1;4;2;8;3;6;5;7
1;4;2;8;3;7;5;6
1;5;2;3;4;6;7;8
1;5;2;3;4;7;6;8
1;5;2;3;4;8;6;7
1;5;2;4;3;6;7;8
1;5;2;4;3;7;6;8
1;5;2;4;3;8;6;7
1;5;2;6;3;4;7;8
1;5;2;6;3;7;4;8
1;5;2;6;3;8;4;7
1;5;2;7;3;4;6;8
1;5;2;7;3;6;4;8
1;5;2;7;3;8;4;6
1;5;2;8;3;4;6;7
1;5;2;8;3;6;4;7
1;5;2;8;3;7;4;6
1;6;2;3;4;5;7;8
1;6;2;3;4;7;5;8
1;6;2;3;4;8;5;7
1;6;2;4;3;5;7;8
1;6;2;4;3;7;5;8
1;6;2;4;3;8;5;7
1;6;2;5;3;4;7;8
1;6;2;5;3;7;4;8
1;6;2;5;3;8;4;7
1;6;2;7;3;4;5;8
1;6;2;7;3;5;4;8
1;6;2;7;3;8;4;5
1;6;2;8;3;4;5;7
1;6;2;8;3;5;4;7
1;6;2;8;3;7;4;5
1;7;2;3;4;5;6;8
1;7;2;3;4;6;5;8
1;7;2;3;4;8;5;6
1;7;2;4;3;5;6;8
1;7;2;4;3;6;5;8
1;7;2;4;3;8;5;6
1;7;2;5;3;4;6;8
1;7;2;5;3;6;4;8
1;7;2;5;3;8;4;6
1;7;2;6;3;4;5;8
1;7;2;6;3;5;4;8
1;7;2;6;3;8;4;5
1;7;2;8;3;4;5;6
1;7;2;8;3;5;4;6
1;7;2;8;3;6;4;5
1;8;2;3;4;5;6;7
1;8;2;3;4;6;5;7
1;8;2;3;4;7;5;6
1;8;2;4;3;5;6;7
1;8;2;4;3;6;5;7
1;8;2;4;3;7;5;6
1;8;2;5;3;4;6;7
1;8;2;5;3;6;4;7
1;8;2;5;3;7;4;6
1;8;2;6;3;4;5;7
1;8;2;6;3;5;4;7
1;8;2;6;3;7;4;5
1;8;2;7;3;4;5;6
1;8;2;7;3;5;4;6
1;8;2;7;3;6;4;5

[maxclo]

C'est exactement ca. Merci beaucoup super francois

[anapurna]

salut

en fait ca revient a chercher les "anagramme" ou permutation possible

c'etait pourtant pas si compliqué a explique

@+ Phil