Comment faire un algorithme recursif

**maxclo** · 07/03/2007, 17h48

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
32
 
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;

**coyotte507** · 07/03/2007, 18h04

peux-tu expliquer qu'est ce que tu veux faire?

**maxclo** · 07/03/2007, 18h10

En fait je doit calculer des trajets, j'ai mes distances individuelles (avec 2 site par tournée) que je dois optimiser.
Le truc c'est que je voudrais avoir une meme fonction qui fonctionne pour 1, 2 3 4, 5 , ... tournée et ne pas avoir une fonction avec i, j quand j'ai 1 tounée, ijkl quand j'ai 2 tournée, ijklmn quand j'en ai 3, ....
Mon exemple fonctionne pour 4 tournée
Ouh là là c'est pas clair ce que je raconte

**coyotte507** · 07/03/2007, 19h20

Voilà ce que je pense

Par contre j'ai pas tout compris ce que tu voulais dire.

Je te montre juste comment exécuter certaines fonction avec un tableau d'entiers.

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
int w, x
booleen identique

//Le tableau des variables
int tabEnt[nb]

//le tableau commence à [0] et finit à [n-1]

toujours faire
{
  //On vérifie que aucun n'est identique (comme tu l'as fait)
  //On teste toutes les cases 2 à 2
  //Ca équivaut à ton gigantesque test
  identique <- faux
  pour w <- 0, tant que w < nb-1, w++
    pour x <- w+1, tant que x < nb, x++
      si tabEnt[w] == tabEnt [x]
           identique <- vrai
      finsi
    finpour
  finpour

  si identique == vrai
     //alors deux des cases sont égales, on ne fait rien
  sinon
    //Toutes les variables sont différentes
    Mettre ici ton code entre les if que j'ai pas compris
  finsi

  //Maintenant on augmente de 1 la dernière case du tableau possible
  //équivaut à toute ta série de for
  pour w <- nb-1, tant que tab[Ent] != nb-1, w--
  finpour

  //Maintenant w est la case du tableau qu'on peut augmenter
  //Si on a tout fait, on sort
  si w < 0
      sortir de la boucle
  finsi

  tabEnt[w] ++

  //On remet toutes les cases après à 0
  //Comme lorsqu'un for s'excéute tous ceux après sont à 0
  pour w <- w+1, tant que w < nb-1, faire w++
        tabEnt[w] <- 0
  finPour
}

Voilà, par contre j'ai carrément rien pigé à ce que tu fais dans le if

Par contre j'ai fait tous le reste.

Il y a une optimisation que je n'ai pas osé faire:
Si toutes les cases du tableaux doivent être différentes, et inférieures à nb, alors ca se présente comme ça:

Pour nb = 6
012345
102345
120345
123045
123405
123450
021345
...

Si on prend en compte ca alors on peut grandement réduire le nombre de boucles à éxecuter (énormément) ainsi que le test de ifs mais j'ai besoin d'une confirmation...

**maxclo** · 08/03/2007, 09h03

J'essaie des ce matin en essayant de tout bien comprendre et je te dis si ca correspond a ce que je voulais. Merci beaucoup de cette aide

**maxclo** · 08/03/2007, 12h02

Voilà ce que j'ai fait, mais j'ai franchement pas tout compris sur le code que tu m'as indiqué.
J'ai remplacé le bout qui etait pas tres comprehensible hors contexte et je l'ai remplacé par un mémo qui se remplit.
Ce que je crois comprendre mais qu'il faut que je fasse encore c'est de rendre mon 0, 1, 2, 3 et les transformer avec le x et le w

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;

**icer** · 08/03/2007, 14h25

Donc ma question, c'est comment on s'y prend pour faire du recursif à part appeller LA fonction dans LA fonction

Ben, tu peux pas

Par définition une fonction récursive est une fonction qui s'appelle elle-même.

Je n'ai pas regardé ton problème en détail, mais en général on peut remplacer une fonction récursif par des boucles, en empilant à chaque tour de boucles des variables dans des tableaux... pour ma part les fonctions récursifs sont toujours plus élégantes et elles simplifient la lecture de l'algorithme.

**maxclo** · 08/03/2007, 15h22

Bonjour

Ca je sais que du recursif c'est la fonction dans la fonction, ma question sous entendu est comment doit être Ma fonction qui commence a être recursive mais qui n'est pas evolutive comme elle le devrait.

**icer** · 08/03/2007, 15h33

... Ma fonction qui commence a être recursive mais qui n'est pas evolutive comme elle le devrait

Je ne comprend pas ta phrase

Je suppose que du veux un algorithme qui te permet de trouver le meilleur itinéraire entre deux points?

Si c'est ça, l'algorithme de Dijkstra pourra peut-être t'aider.

**maxclo** · 08/03/2007, 15h51

non c'est pas ca. Pour trouver l'itineraire entre 2 points j'utilise mappoint que j'ai integré dans delphi.
ce que je cherche c'est faire une liste comme telle
par exemple pour 6 ville

123456
123465
123546
123564
123645
123654
124356 ....

Sachant que comme je fonctionne par couple
ce serait encore mieux que j'arrive à
12 34 56 (parce que pour moi 56 ca va etre pareil que 65)
12 35 46
12 36 45
13 24 56
13 25 46
13 26 45
...

Et que ma fonction fonctionne pour 6 (soit 3 couples) ou 8 (soit 4 couples) ou n (soit n/2 couples)

Voilà j'espere que c'est plus clair comme ca

**icer** · 08/03/2007, 16h11

ahh ! Je crois que je commence à comprendre!

Tu veux, depuis une liste de ville, avoir toutes les combinaisons possibles de chemins pour traverser toutes les villes!

Mais, il y a un point qui n'est pas clair ; pourquoi tu veux regrouper les villes par couples?

Expliques nous ton application, parceque là, je suis dans le flou?

**maxclo** · 08/03/2007, 16h17

Oui t'as compris

ben le mes chiffres correspondent à des villes : ville1, ville2, ville3, ville4, ville5, ville6
il faut que j'organise au mieux les tournees de consultant sachant qu'il ne font que 2 villes par semaines (pour le moment) et qu'il rentre chez eux tous les WE. Et j'ai dans ma base de données toutes les distances ville1-Ville2, Ville1-Ville3 (distance dejà calculer avec mappoint).
Donc je cherche à savoir s'il vaut mieux faire une semaine ville 1 puis 2, puis une semaine 34 puis une semaine 56 ou alors faire une tournee en groupant 1 avec 3 et 2 avec 4 et 5 avec 6, ou alors....

**icer** · 08/03/2007, 16h28

S'ils doivent faire 2 villes par semaines et qu'ils doivent faire toutes les villes.
Tu choisis la première ville au hasard, ensuite tu cherche la ville la plus proche de la premiére.

Et la semaine d'aprés tu recommence. Et ainsi de suite jusqu'à ce que toutes les villes soit faites.

**maxclo** · 08/03/2007, 16h34

Ce qui me gene c'est que cette solution n'optimise pas le trajet global de l'ensemble des semaines. Enfin je crois...

**icer** · 08/03/2007, 16h47

Je ne vois pas comment l'optimiser plus.

Puisque un consultant doit faire toutes les villes 2 par deux, et pour aller dans chaque ville il y a deux cas :

1) Soit c'est la première ville : il doit partir de chez lui (il est rentré le WE avant).

2) Soit c'est la deuxième ville : il part de la première ville, et là le mieux c'est de choisir une ville pas trop loin de la premiére, comme ça il ne fera pas trop de route pour rentré chez lui le WE.

Vraiment je ne vois pas autre choses

**souviron34** · 08/03/2007, 16h57

problème de maths classique mais complexe :

algorithme du voyageur de commerce, ou "Traveliing salesman algorithm"

http://en.wikipedia.org/wiki/Travell...lesman_problem en anglais

ou

http://www.aromath.net/Page.php?IDP=668&IDD=0

en français...

Comment faire un algorithme recursif

Algorithmes et structures de données

Discussions similaires

Partager

Partager