[Ada] Mon implémentation du Jeu du Taquin ::=la file de priorités

Mon implémentation du Jeu du Taquin ::=la file de priorités [Ada] - Ada - Programmation

Marsh Posté le 11-05-2006 à 13:27:16    

;)  :heink:  :hello: Bonjour à tous et toutes,  
 
la premiere partie du topic relate des evenements survenuent l'hors du developpement des premieres versions (lire le debut du topic)
 
A ce jour le problème principal est d'implémenter une file de priorité, (lire les derniers messages)
la version courante exploite un algorithme A* ou A etoile avec des listes chaînées (voir les sources)
 
Merci à tous et toutes  :jap:  :sol:  
 
 
<<MESSAGE ORIGINAL>>
 
 
:hello:  
 
Je me propose de réaliser avec Ada un jeu du Taquin dont le solutionnement est une liste des permutations effectuée durant le mélange
 
mes sources sont disponibles ICI
 
n'esitez pas à participer à ce topic  ;)  
 
Ma spécification de P_Taquin
 

Code :
  1. with P_Les_Types_Taquin;
  2. use P_Les_Types_Taquin;
  3. generic
  4.    N : T_Borne_1;
  5.    M : T_Borne_1;
  6. package P_Taquin is
  7.    type T_Taquin is private;
  8.    subtype T_Borne_2 is natural range 0..(N*M)-1;
  9.    procedure Afficher(Dans : in T_Taquin);
  10.    procedure Initialiser_Un_jeton(Dans : in out T_Taquin);
  11.    procedure Melanger_Un_Jeton(Dans : in out T_Taquin);
  12.    procedure Ranger_Un_Jeton(Dans : in out T_Taquin);
  13.    function Sont_Egales(Gauche, Droit : T_taquin) return Boolean;
  14.    procedure Vider(Un : in out T_Taquin);
  15. private
  16.    subtype T_Count is Natural range 0..T_Borne_2'last+1;
  17.    type T_Place;
  18.    type T_Ptr_place is access T_Place;
  19.    type T_Place is
  20.       record
  21.          Suivant : T_Ptr_place;
  22.          Id : T_Borne_2 := 0;
  23.       end record;
  24.      type T_Tab_2d is array (Positive range <>,
  25.                               Positive range <> ) of T_Place;
  26.    type T_Matrice_Jeton(N : T_Borne_1;
  27.                         M : T_Borne_1) is
  28.      record
  29.         Matrice : T_Tab_2d(1..N,1..M);
  30.         K : T_Borne_1 := 1;
  31.         L : T_Borne_1 := 1;
  32.         Count : T_count := 0;
  33.      end record;
  34.    type T_Liste is
  35.       record
  36.          Longueur : Natural := 0;
  37.          Tete, Precedent, Courant : T_Ptr_place:= null;
  38.       end record;
  39.    type T_Taquin is
  40.       record
  41.          Etat : T_Matrice_Jeton(N,M);
  42.          Liste_Vide : T_Liste;
  43.          Liste_De_Permutation : T_Liste;
  44.       end record;
  45. end P_Taquin;


 
Cette implémentation du jeu du Taquin ne reflétant pas en réalité le vrai problème posé, j'envisage d'y remédier. Malheuresement mes connaissances en mathématique, algorithmie et structure de donnée sont aujourd'hui insufisantes. Je me lance donc à la recherche d'un spécificateur qui souhaiterait partager le plaisir d'ecrire ou de réecrire une implémentation du jeu du Taquin avec Ada :love:


Message édité par Profil supprimé le 11-06-2006 à 18:17:00
Reply

Marsh Posté le 11-05-2006 à 13:27:16   

Reply

Marsh Posté le 11-05-2006 à 17:44:02    

l'ultime operation, la construction de la liste des identifiants des voisins de l'élément vide dans une matrice
 
la specification

Code :
  1. procedure Construction_Liste_Vide(dans : in out T_taquin);
  2.       -- construire la liste des valeur des jetons voisins de l'element vide
  3.       -- de la matrice du taquin


Si vous avez des idées ....  :p  

Reply

Marsh Posté le 11-05-2006 à 20:36:19    

j'ai fait ça  

Code :
  1. procedure Construction_Liste_Vide(dans : in out T_taquin) is
  2.       -- construire la liste des valeur des jetons voisins de l'element vide
  3.       -- de la matrice du taquin
  4.       X_Vide : T_Borne_2;
  5.       Y_Vide : T_Borne_2;
  6.       Nouveau : T_Ptr_Place;
  7.    begin
  8.       X_Vide := Absisse(Dans,0);
  9.       Y_Vide := ordonnee(Dans,0);
  10.       Dans.Liste_Vide.Tete := null;
  11.       Dans.Liste_Vide.Courant := null;
  12.       Dans.Liste_Vide.Longueur := 0;
  13.      if not ((X_Vide + 1) > n ) then
  14.         nouveau := new T_Place ' (null,
  15.                                   Dans.Etat.Matrice(X_Vide+1,Y_Vide).id);
  16.         Dans.Liste_Vide.Tete := Nouveau;
  17.         Dans.Liste_Vide.courant := Dans.Liste_Vide.Tete;
  18.         Dans.Liste_Vide.Longueur := Dans.Liste_Vide.Longueur + 1;
  19.      end if;
  20.      if not ((X_Vide - 1) < 1 ) then
  21.         nouveau := new T_Place ' (null,
  22.                                   Dans.Etat.Matrice(X_Vide-1,Y_Vide).id);
  23.         if Dans.Liste_Vide.Tete = null then
  24.            Dans.Liste_Vide.Tete := nouveau;
  25.            Dans.Liste_Vide.Longueur := Dans.Liste_Vide.Longueur + 1;
  26.            Dans.Liste_Vide.courant := Dans.Liste_Vide.Tete;
  27.         else
  28.            Dans.Liste_Vide.Courant.suivant := nouveau;
  29.            Dans.Liste_Vide.Longueur := Dans.Liste_Vide.Longueur + 1;
  30.            Dans.Liste_Vide.courant := Dans.Liste_Vide.Tete.Suivant;
  31.         end if;
  32.      end if;
  33.      if not ((Y_Vide + 1) > m ) then
  34.         nouveau := new T_Place ' (null,
  35.                                   Dans.Etat.Matrice(x_Vide,Y_Vide+1).id);
  36.         if Dans.Liste_Vide.Tete = null then
  37.            Dans.Liste_Vide.Tete := nouveau;
  38.            Dans.Liste_Vide.Longueur := Dans.Liste_Vide.Longueur + 1;
  39.            Dans.Liste_Vide.courant := Dans.Liste_Vide.Tete;
  40.         else
  41.            Dans.Liste_Vide.Courant.suivant := Nouveau;
  42.            Dans.Liste_Vide.Courant := Dans.Liste_Vide.Courant.Suivant;
  43.            Dans.Liste_Vide.Longueur := Dans.Liste_Vide.Longueur + 1;
  44.         end if;
  45.      end if;
  46.      if not ((y_Vide - 1) < 1 ) then
  47.         nouveau := new T_Place ' (null,
  48.                                   Dans.Etat.Matrice(x_Vide,Y_Vide-1).id);
  49.         if Dans.Liste_Vide.Tete = null then
  50.            raise Program_Error;
  51.            Dans.Liste_Vide.Tete := nouveau;
  52.            Dans.Liste_Vide.Longueur := Dans.Liste_Vide.Longueur + 1;
  53.         else
  54.            Dans.Liste_Vide.Courant.suivant := Nouveau;
  55.            Dans.Liste_Vide.Longueur := Dans.Liste_Vide.Longueur + 1;
  56.         end if;
  57.      end if;
  58. end Construction_Liste_vide;


mais dans l'etat, ça marche pas  :lol: et je suis bien embété  ;)


Message édité par Profil supprimé le 12-05-2006 à 10:17:10
Reply

Marsh Posté le 12-05-2006 à 10:48:09    

j'ai fait ça  

Code :
  1. procedure Construction_Liste_Vide(dans : in out T_taquin) is
  2.       -- construire la liste des valeur des jetons voisins de l'element vide
  3.       -- de la matrice du taquin
  4.       X_Vide : T_Borne_2;
  5.       Y_Vide : T_Borne_2;
  6.       Nouveau : T_Ptr_Place;
  7.    begin
  8.       X_Vide := Absisse(Dans,0);
  9.       Y_Vide := ordonnee(Dans,0);
  10.       Dans.Liste_Vide.Tete := null;
  11.       Dans.Liste_Vide.Courant := null;
  12.       Dans.Liste_Vide.Longueur := 0;
  13.      if not ((X_Vide + 1) > n ) then
  14.         nouveau := new T_Place ' (null,
  15.                                   Dans.Etat.Matrice(X_Vide+1,Y_Vide).id);
  16.         Dans.Liste_Vide.Tete := Nouveau;
  17.         Dans.Liste_Vide.courant := Dans.Liste_Vide.Tete;
  18.         Dans.Liste_Vide.Longueur := Dans.Liste_Vide.Longueur + 1;
  19.      end if;
  20.      if not ((X_Vide - 1) < 1 ) then
  21.         nouveau := new T_Place ' (null,
  22.                                   Dans.Etat.Matrice(X_Vide-1,Y_Vide).id);
  23.         if Dans.Liste_Vide.Tete = null then
  24.            Dans.Liste_Vide.Tete := nouveau;
  25.            Dans.Liste_Vide.Longueur := Dans.Liste_Vide.Longueur + 1;
  26.            Dans.Liste_Vide.courant := Dans.Liste_Vide.Tete;
  27.         else
  28.            Dans.Liste_Vide.Courant.suivant := nouveau;
  29.            Dans.Liste_Vide.Longueur := Dans.Liste_Vide.Longueur + 1;
  30.            Dans.Liste_Vide.courant := Dans.Liste_Vide.Tete.Suivant;
  31.         end if;
  32.      end if;
  33.      if not ((Y_Vide + 1) > m ) then
  34.         nouveau := new T_Place ' (null,
  35.                                   Dans.Etat.Matrice(x_Vide,Y_Vide+1).id);
  36.         if Dans.Liste_Vide.Tete = null then
  37.            Dans.Liste_Vide.Tete := nouveau;
  38.            Dans.Liste_Vide.Longueur := Dans.Liste_Vide.Longueur + 1;
  39.            Dans.Liste_Vide.courant := Dans.Liste_Vide.Tete;
  40.         else
  41.            Dans.Liste_Vide.Courant.suivant := Nouveau;
  42.            Dans.Liste_Vide.Courant := Dans.Liste_Vide.Courant.Suivant;
  43.            Dans.Liste_Vide.Longueur := Dans.Liste_Vide.Longueur + 1;
  44.         end if;
  45.      end if;
  46.      if not ((y_Vide - 1) < 1 ) then
  47.         nouveau := new T_Place ' (null,
  48.                                   Dans.Etat.Matrice(x_Vide,Y_Vide-1).id);
  49.         if Dans.Liste_Vide.Tete = null then
  50.            raise Program_Error;
  51.            Dans.Liste_Vide.Tete := nouveau;
  52.            Dans.Liste_Vide.Longueur := Dans.Liste_Vide.Longueur + 1;
  53.         else
  54.            Dans.Liste_Vide.Courant.suivant := Nouveau;
  55.            Dans.Liste_Vide.Longueur := Dans.Liste_Vide.Longueur + 1;
  56.         end if;
  57.      end if;
  58. end Construction_Liste_vide;


 ;) ça ça marche presque
 
mais j'ai encore un petit probleme, apriori, avec le tirage aleatoire   [:atreyu]


Message édité par Profil supprimé le 12-05-2006 à 11:14:16
Reply

Marsh Posté le 12-05-2006 à 11:39:37    

Il manque 1 élément dans ma liste des jetons voisins du vide  [:kernel-panic]  
 

Reply

Marsh Posté le 12-05-2006 à 12:23:01    

Maintenant, j'ai bien tous mes voisins dans ma liste, mais ça marche toujours pas,
 
Il doit y avoir un problème avec le tirage aleatoire à moins que ce soit cette function L_element  (Dans : T_Liste;place : in Positive) return T_Borne_2;

Code :
  1. function L_Element (Dans : T_Liste;place : in Positive) return T_Borne_2 is
  2.       Courant : T_Ptr_place := Dans.Tete;
  3.    begin
  4.       if Place > 1 then
  5.          for I in 1..Place-1 loop
  6.             Courant := Courant.Suivant;
  7.          end loop;
  8.       end if;
  9.       if Courant = null then
  10.          raise Program_Error;
  11.       end if;
  12.       return Courant.Id;
  13.    end L_Element;


 
Si non c'est le tirage aleatoire qui marche pas bien puisqu'il me renvoie presque toujours les même valeurs  [:666rip666]
 
La  spécification de P_Random_Sans_Remise

Code :
  1. generic
  2.    Borne : Positive;
  3. package P_Random_Sans_Remise is
  4.    pragma Elaborate_body(P_Random_Sans_Remise);
  5.    function Random return Positive;
  6. end P_Random_Sans_Remise;


Le  corp de P_Random_Sans_Remise

Code :
  1. with Ada.Numerics.Discrete_Random;
  2. package body P_Random_Sans_Remise is
  3.    count : natural := 0;
  4.    subtype T_Borne is Positive range 1..Borne;
  5.    Package P_T_Borne_Random is new Ada.Numerics.Discrete_Random(T_Borne);
  6.    T_Borne_Gen : P_T_Borne_Random.Generator;
  7.    use P_T_Borne_Random;
  8.    type T_Tab is array (Positive range 1..Borne) of T_Borne;
  9.    Tab_Image : T_Tab := (others => T_Borne'first);
  10.  
  11.    procedure Permute(Tab : in out T_Tab;I,J : T_Borne) is
  12.       Tampon : positive := Tab(I);
  13.    begin
  14.       Tab(I) := Tab(J);
  15.       Tab(J) := Tampon;
  16.    end Permute;
  17.  
  18.    function Random return Positive is
  19.    begin
  20.       if Count = Borne then
  21.          raise Program_Error;
  22.       else
  23.          Count := Count + 1;
  24.       end if;
  25.       Return Tab_image(Count);
  26.    end Random;
  27. begin
  28.    for I in Tab_Image'Range loop
  29.       Tab_Image(I) := I;
  30.    end loop;
  31.    for I in 1..4 loop--Tab_Image'Length/2 loop
  32.       Permute(Tab_Image,
  33.               Random(T_Borne_Gen),
  34.               Random(T_Borne_Gen));
  35.    end loop;
  36. end P_Random_Sans_Remise;


 
JagStang spécifier dans son message à ce sujet de mélanger N/2 fois le tableau, mais en mélangant un peut plus, ça marche un peut mieu.
 
Ma procedure Melanger_Un_Jeton(Dans : in out T_Taquin);
 

Code :
  1. procedure Melanger_Un_Jeton(Dans : in out T_Taquin) is
  2.       subtype T_Borne_Random is Positive range 1..Dans.Liste_Vide.Longueur;
  3.       Package P_T_Borne_2_random is new Ada.Numerics.Discrete_Random(T_Borne_random);
  4.       --T_Borne_Gen : P_T_Borne_2_Random.Generator;
  5.       --use P_T_Borne_2_Random;
  6.       package P_Vide_Random is new P_Random_Sans_Remise(Dans.Liste_Vide.longueur);
  7.       use P_Vide_Random;
  8.       Elu : T_Borne_2;
  9.       Nouveau : T_Ptr_place;
  10.    begin
  11.       --      Elu := L_Element(Dans.Liste_Vide,P_Vide_Random.Random);
  12.       Elu := L_Element(Dans.Liste_Vide,Random);--(T_Borne_Gen));
  13.       Nouveau  := new T_Place ' (null,elu);
  14.       Permuter(Dans,elu);
  15.       Construction_Liste_Vide(Dans);
  16.       if Dans.Liste_De_Permutation.Longueur = 0 then
  17.          Dans.Liste_De_Permutation.Tete := Nouveau;
  18.          Dans.Liste_De_Permutation.Courant := Dans.Liste_De_Permutation.Tete;
  19.       else
  20.          Dans.Liste_De_Permutation.Courant.suivant := Nouveau;
  21.          Dans.Liste_De_permutation.Precedent := Dans.Liste_De_permutation.Courant;
  22.          Dans.Liste_De_Permutation.Courant := Dans.Liste_De_Permutation.Courant.Suivant;
  23.       end if;
  24.       Dans.Liste_De_Permutation.Longueur :=
  25.         Dans.Liste_De_Permutation.Longueur + 1;
  26.    end Melanger_Un_Jeton;


 
Ma procedure Ranger_Un_Jeton(Dans : in out T_Taquin);

Code :
  1. procedure Ranger_Un_Jeton(Dans : in out T_Taquin) is
  2.    begin
  3.       if Dans.Liste_De_Permutation.Longueur /= 0 then
  4.          Dans.Liste_De_permutation.Courant := Dans.Liste_De_permutation.Precedent;
  5.          Renverser(Dans.Liste_De_Permutation);
  6.          Dans.Liste_De_Permutation.Longueur := 0;
  7.          Permuter(Dans,Dans.Liste_De_permutation.tete.Id);
  8.          Dans.Liste_De_permutation.Courant := Dans.Liste_De_permutation.Tete.suivant;
  9.       else
  10.          Permuter(Dans,Dans.Liste_De_permutation.Courant.Id);
  11.          Dans.Liste_De_permutation.Courant :=
  12.            Dans.Liste_De_permutation.Courant.Suivant;
  13.       end if;
  14.    end Ranger_Un_Jeton;


 

Reply

Marsh Posté le 12-05-2006 à 14:12:11    

Et bien, on pourait se demander ce que fait Ada.Numerics.Discrete_Random, parce-que ça random pas beaucoup ...  
 
Alors voila, en plus maintenant random est vraiment sans remise
 

Code :
  1. function Random(Strategique : positive) return Positive is
  2.       Resultat : Positive;
  3.       Elu : Positive := 1;
  4.    begin
  5.       loop
  6.          Resultat := Tab_image(elu);
  7.          Elu := Elu+1;
  8.          exit when Resultat /= Strategique;
  9.       end loop;
  10.       Return resultat;
  11.    end Random;


 
Mais ça mélange toujours trés mal   :p


Message édité par Profil supprimé le 12-05-2006 à 16:50:13
Reply

Marsh Posté le 12-05-2006 à 17:05:21    

J'ai légèrement modifié ma procedure Initialiser_Un_jeton(Dans : in out T_Taquin); pour avoir 2 fois plus de possibilités au  premier coup

Code :
  1. procedure Initialiser_Un_jeton(Dans : in out T_Taquin) is
  2.    begin
  3.       if ((dans.Etat.K = N/2) and (dans.Etat.L = M/2)) then
  4.          null;  -- Jeton central non initialisé
  5.       else
  6.          dans.Etat.Matrice(dans.Etat.k,Dans.Etat.l).id := Dans.etat.Count+1;
  7.          Dans.etat.Count := Dans.etat.Count + 1;
  8.       end if;
  9.       if Dans.etat.k = N then
  10.             Dans.etat.L := Dans.etat.L + 1;
  11.             Dans.etat.K := 1;
  12.          else
  13.             Dans.etat.K := Dans.etat.K + 1;
  14.          end if;
  15.       if Dans.Etat.Count = T_Borne_2'Last then
  16.          Construction_Liste_vide(Dans);
  17.       end if;
  18.    end Initialiser_Un_Jeton;


Le probleme concernant le tirage aleatoire se pose toujours, (saletée de machine)  :heink:  
En effet, à chaque appel du programme le jeton vide prend le même chemin. Stupéfiant  :pt1cable:

Reply

Marsh Posté le 12-05-2006 à 18:19:33    

[:aganemnon]  Comment repousser les limites de Ada.Numerics.Disctrete_Random.Random ou de Srandom, la fonction C de génération de nombre aléatoire :??:   [:aganemnon]  
 
 [:atreyu]
 
 
D'un coup, j'ai un doute, en effet, ne demeure t-il pas un bug au sein de ce petit programme  :??:


Message édité par Profil supprimé le 12-05-2006 à 18:34:06
Reply

Marsh Posté le 12-05-2006 à 20:31:45    

j'ai retapé la construction de la liste des voisins de l'élément vide pour pallier au maigre résultat de Ada.Numerics.Discrete_Random en y intégrant une part d'aleatoire.

Code :
  1. procedure Construction_Liste_Vide(dans : in out T_taquin) is
  2.       -- construire la liste des valeur des jetons voisins de l'element vide
  3.       -- de la matrice du taquin
  4.  
  5.  
  6.       function down(X,Y : T_Borne_1) return T_Borne_2 is
  7.       begin
  8.          if not ((X + 1) > N) then
  9.             return Dans.Etat.Matrice(X+1,Y).Id;
  10.          else
  11.             return 0;
  12.          end if;
  13.       end down;
  14.  
  15.       function up(X,Y : T_Borne_1) return T_Borne_2 is
  16.       begin
  17.          if not ((X -1) < 1) then
  18.             return Dans.Etat.Matrice(X-1,Y).Id;
  19.          else
  20.             return 0;
  21.          end if;
  22.       end up;
  23.  
  24.       function right(X,Y : T_Borne_1) return T_Borne_2 is
  25.       begin
  26.          if not ((Y + 1) > M) then
  27.             return Dans.Etat.Matrice(X,Y+1).Id;
  28.          else
  29.             return 0;
  30.          end if;
  31.       end right;
  32.  
  33.       function left(X,Y : T_Borne_1) return T_Borne_2 is
  34.       begin
  35.          if not ((Y - 1) < 1) then
  36.             return Dans.Etat.Matrice(X,Y-1).Id;
  37.          else
  38.             return 0;
  39.          end if;
  40.       end left;
  41.  
  42.       type Coordonnees_To_Id is access function(X,Y : T_Borne_1) return T_Borne_2;
  43.       subtype Methodes is Positive range 1..4;
  44.       type Tab_solution is array (Positive range 1..4) of Coordonnees_To_Id;
  45.       Solution : Tab_Solution :=
  46.         (1 => Up'Access,
  47.          2 => Down'Access,
  48.          3 => Right'Access,
  49.          4 => Left'Access);
  50.       Package P_Solution_random is new Ada.Numerics.Discrete_Random(methodes);
  51.       solution_Gen : P_Solution_random.Generator;
  52.       use P_Solution_Random;
  53.       procedure Permute(Tab : in out Tab_solution;I,J : methodes) is
  54.          Tampon : Coordonnees_To_Id := Tab(I);
  55.       begin
  56.          Tab(I) := Tab(J);
  57.          Tab(J) := Tampon;
  58.       end Permute;
  59.       X_Vide : T_Borne_2;
  60.       Y_Vide : T_Borne_2;
  61.       Nouveau : T_Ptr_Place;
  62.    begin
  63.     X_Vide := Absisse(Dans,0);
  64.       Y_Vide := ordonnee(Dans,0);
  65.       Dans.Liste_Vide.Tete := null;
  66.       Dans.Liste_Vide.Courant := null;
  67.       Dans.Liste_Vide.Longueur := 0;
  68.       for I in 1..128 loop
  69.          Permute(Solution,Random(Solution_Gen),Random(Solution_Gen));
  70.       end loop;
  71.       for I in 1..4 loop
  72.          if Solution(I)(x_Vide,y_Vide) /= 0 then
  73.             Nouveau := new T_Place ' (null,Solution(I)(x_Vide,y_Vide));
  74.             if Dans.Liste_Vide.Tete = null then
  75.                Dans.Liste_Vide.Tete := Nouveau;
  76.                Dans.Liste_Vide.courant := Dans.Liste_Vide.Tete;
  77.                Dans.Liste_Vide.Longueur := Dans.Liste_Vide.Longueur + 1;
  78.             else
  79.                Dans.Liste_Vide.Courant.suivant := Nouveau;
  80.                Dans.Liste_Vide.Courant := Dans.Liste_Vide.Courant.Suivant;
  81.                Dans.Liste_Vide.Longueur := Dans.Liste_Vide.Longueur + 1;
  82.             end if;
  83.          end if;
  84.       end loop;
  85.    end Construction_Liste_vide;


 
Mais ça marche pas encore  :cry:


Message édité par Profil supprimé le 13-05-2006 à 10:06:57
Reply

Marsh Posté le 12-05-2006 à 20:31:45   

Reply

Marsh Posté le 13-05-2006 à 11:06:13    

Voila, ça tourne, les sources sont disponibles ICI  :jap:

Reply

Marsh Posté le 13-05-2006 à 17:03:07    

Cette implémentation du jeu du Taquin ne reflétant pas en réalité le vrai problème posé, j'envisage d'y remédier. Malheuresement mes connaissances en mathématique, algorithmie et structure de donnée sont aujourd'hui insufisantes. Je me lance donc à la recherche d'un spécificateur qui souhaiterait partager le plaisir d'ecrire ou de réecrire une implémentation du jeu du Taquin avec Ada :love:

Reply

Marsh Posté le 14-05-2006 à 04:35:26    

En attendant l'affluance sur ce topic, :lol:  
je m'amuse un peut  :heink:  
 

Code :
  1. put("Positionner une matrice lines x columns > 1 avec un element vide en k,l, l'afficher, la melanger aleatoirement, l'ordonner" );
  2. put("durant les deux derniere phases, la matrice doit être affiché à chaque deplacement de tuile." );


 :pt1cable:  
procedure Ranger_Une_Tuile(Dans : in out T_Jeu_Du_Taquin) is
      Un_Char : Character;
      Vide_Passe : Boolean := False;
   begin
      if Dans.Liste_Initiale.tete = null then
         Dans.Matrice_Ordonnee := Dans.Matrice_melangee;
      end if;
      if Dans.Liste_Initiale.Courant = null then
         Construire_Liste(Dans.Liste_Initiale, Dans.Matrice_ordonnee);
         if not Vide_Passe then
            Tronquer_queu_Liste(Dans.Liste_Initiale,0);
         else
            Tronquer_tete_Liste(Dans.Liste_Initiale,0);
         end if;
         Dans.Liste_Initiale.Courant := null;--Dans.Liste_Initiale.Tete;
--         while Dans.Liste_Initiale.Courant.Suivant /= null loop
--            Dans.Liste_Initiale.Courant := Dans.Liste_Initiale.Courant.Suivant;
--         end loop;
         Renverser(Dans.Liste_Initiale);
         Dans.Liste_Initiale.Courant := Dans.Liste_Initiale.Tete;
      else
         Permuter(Dans.Matrice_Ordonnee,Dans.Liste_Initiale.Courant.Id);
         Dans.Liste_Initiale.Courant := Dans.Liste_Initiale.Courant.Suivant;
         if Dans.Liste_Initiale.Courant.Id = 0 then
            Vide_Passe := True;
            Dans.Liste_Initiale.Courant := Dans.Liste_Initiale.Courant.Suivant;
         end if;
      end if;
 
      Afficher(Dans.Liste_Initiale);
      Get_Immediate(Un_Char);
      ------------------------------------------------------------
   end Ranger_Une_tuile;


Message édité par Profil supprimé le 15-05-2006 à 14:36:52
Reply

Marsh Posté le 15-05-2006 à 14:55:34    

:hello:  J'ai un gros problème URGENT, please HELP ME  [:kernel-panic]  
 
En effet, je suis bloqué par mon incapacité à comprendre pourquoi dans le ma procedure ranger_une_tuile, à la ligne 58, ma liste_initiale n'est pas renversée lors de son affichage.
 
En fait je ne comprend pas le role de courant dans renverser, j'ai du mal à analiser ce probleme, vue que je suis dans l'algo du taquin, je fatigue.
 
  :??: ?? Courant doit prendre quel valeur pour renverser la totalité de la liste ?? :??:  
 
 
J'ai déjas utilisé les procedures renverser(sans l'avoir analisé) et afficher dans d'autres circonstances, elles fonctionnent tres bien.
 

Code :
  1. procedure Renverser(La_Liste: in out T_Liste) is
  2.       P : T_Ptr_Place := null;             -- la liste l', initialement vide
  3.       Q : T_Ptr_Place;                                                        -- variable locale
  4.    begin
  5.       if La_Liste.Longueur = 0 then return; end if;
  6.       while La_Liste.Tete /= null loop
  7.          Q := La_Liste.Tete;
  8.          La_Liste.Tete := La_Liste.Tete.Suivant;-- passer à fin (l)
  9.          Q.Suivant := P;
  10.          P := Q;                                                -- l' := premier(l) :: l'
  11.          if Q = La_Liste.Courant then
  12.             La_Liste.Precedent := La_Liste.Tete;
  13.          end if;                                                         -- nouveau précédant
  14.       end loop;
  15.       La_Liste.Tete := P;                                                  -- le résultat
  16.    end Renverser;
  17.    procedure Tronquer_Queu_Liste(Dans : in out T_Liste; Id : T_Borne_2) is
  18.    begin
  19.       Dans.Courant := Dans.Tete;
  20.       while Dans.Courant /= null and then
  21.         Dans.Courant.Id /= Id loop
  22.          Dans.Precedent := Dans.Courant;
  23.          Dans.Courant := Dans.Courant.Suivant;
  24.       end loop;
  25.       Dans.Precedent.Suivant := null;
  26.    end Tronquer_Queu_Liste;
  27.  
  28.    procedure Tronquer_tete_Liste(Dans : in out T_Liste; Id : T_Borne_2) is
  29.    begin
  30.       Dans.Courant := Dans.Tete;
  31.       while Dans.Courant /= null and then
  32.         Dans.Courant.Id /= Id loop
  33.          Dans.Precedent := Dans.Courant;
  34.          Dans.Courant := Dans.Courant.Suivant;
  35.       end loop;
  36.       Dans.Tete := Dans.Precedent.Suivant;
  37.    end Tronquer_tete_Liste;
  38.  
  39.  
  40.    procedure Ranger_Une_Tuile(Dans : in out T_Jeu_Du_Taquin) is
  41.       Un_Char : Character;
  42.       Vide_Passe : Boolean := False;
  43.    begin
  44.       if Dans.Liste_Initiale.tete = null then
  45.          Dans.Matrice_Ordonnee := Dans.Matrice_melangee;
  46.       end if;
  47.       if Dans.Liste_Initiale.Courant = null then
  48.          Construire_Liste(Dans.Liste_Initiale, Dans.Matrice_ordonnee);
  49.          if not Vide_Passe then
  50.             Tronquer_queu_Liste(Dans.Liste_Initiale,0);
  51.          else
  52.             Tronquer_tete_Liste(Dans.Liste_Initiale,0);
  53.          end if;
  54.          Dans.Liste_Initiale.Courant := null;--Dans.Liste_Initiale.Tete;
  55. --         while Dans.Liste_Initiale.Courant.Suivant /= null loop
  56. --            Dans.Liste_Initiale.Courant := Dans.Liste_Initiale.Courant.Suivant;
  57. --         end loop;
  58.          Renverser(Dans.Liste_Initiale);
  59.          Dans.Liste_Initiale.Courant := Dans.Liste_Initiale.Tete;
  60.       else
  61.          raise Program_Error;
  62.          Permuter(Dans.Matrice_Ordonnee,Dans.Liste_Initiale.Courant.Id);
  63.          Dans.Liste_Initiale.Courant := Dans.Liste_Initiale.Courant.Suivant;
  64.          if Dans.Liste_Initiale.Courant.Id = 0 then
  65.             Vide_Passe := True;
  66.             Dans.Liste_Initiale.Courant := Dans.Liste_Initiale.Courant.Suivant;
  67.          end if;
  68.       end if;
  69.  
  70.       Afficher(Dans.Liste_Initiale);
  71.       Get_Immediate(Un_Char);
  72.    ------------------------------------------------------------
  73.    end Ranger_Une_tuile;


 
La totalité des sources de Taquin_9 est disponible ICI


Message édité par Profil supprimé le 15-05-2006 à 15:23:32
Reply

Marsh Posté le 15-05-2006 à 15:51:25    

C'est bon, merci, j'ai trouvé que, comme je n'est pas incrémenté longueur durant la creation de la liste le premier test de renverser terminait le procedure prématurément.  [:dawa_neowen]

Reply

Marsh Posté le 15-05-2006 à 16:03:38    

heureusement que t'as trouvé :p bj ;)
De rien pour notre aide :P

Reply

Marsh Posté le 15-05-2006 à 21:47:24    

cet algorithme est-il applicable dans mon cas ?
 
Soit C le chemin (liste d'états) menant d'un état E à l'état initial. Une fonction heuristique possible est : h(C) = longueur(C) + d(E).
 
Soit I l'état initial. F une file d'attente de chemins avec priorité h, et D un dictionnaire des états déjà visités. On suppose que I est différent de l'état final.
 
   1. Rentrer le chemin réduit à I dans F (avec h(I)) et dans D
   2. Fini := faux
   3. Tant que (non Fini) et (F non vide) faire
        1. Sortir un chemin C de F de priorité minimale; soit E le premier élément de C
         2. Pour tous les successeurs S de E et tant que (non Fini) faire
               1. Si S est l'état final alors Fini := Vrai et Solution := inverse(S.C)
               2. Sinon, si S n'est pas dans D alors rentrer S.C dans F (avec h(S)) et S dans D

 
référence : Dijkstra
 
Autre ressources
 
METHODOLOGIE ET STRUCTURES DE DONNEES avec un exemple d'application au jeu du taquin (3x3)
Résolution de problèmes en Intelligence Artificielle
L'algorithme A*
 
Répartition de la charge dans les algorithmes parallèles irréguliers
 
Ce problème, la resolution du jeu du/de taquin est considéré comme difficile, moi qui ai eu du mal à parvenir a la 4eme ....  [:666rip666]  
 
Je ne cherche pas la meilleur solution, d'ailleur son calcule est assé lourd ; Je ne rejéterais quans même pas cette ultime algorithme ideal ; Bien que je ne soi pas préssé, je me contenterai, dans un premier temps, d'un algorithme qui trouve une solution, Et ce serait déjàs pas mal
 
L'orsque les problèmes de resolution seront résoluts, j'envisagerai une version graphique avec GtkAda,
 
Je rappel que je ne suis ni étudiant, bien que (autodidacte en formation continue), ni salarié, ça c'est sure !
je rappel aussi que j'ai du champagne pour ceux qui m'aide a atteindre mes objectifs
 
 
j'ai faî ecrire un truc pas mal cet après midi mais j'ai eu un problème avec une inversion de liste et j'ai oublié ce que j'étais en train de faire ; Dommage
 
Avec un peut de travail et un peut de patience, je pense y arriver. Un peut d'aide ne serait pas de refus, tout de même.


Message édité par Profil supprimé le 16-05-2006 à 02:07:11
Reply

Marsh Posté le 16-05-2006 à 10:33:26    

Trève de plaisenterie,
 
Je suis en train de lire Christian Carrez dans Structures de données en Java,C++ et Ada 95.pour implémenter mon Jeu du Taquin
 
Ce qui m'interresse, ce sont les arbres généraux. Pour la resolution du taquin j'opte pour les arbres généraux avec aîné et frère droit
 
l'implementation du type presenté dans le livre, est en Java
 

Code :
  1. public class noeud [
  2.     object contenu ;
  3.     boolean frere_null  true ;
  4.     noeud aine = null ;
  5.     noeu suivant = null ;
  6.     noeud (object val) { contenue val ; } ; // je ne comprend pas la derniere ligne  ! //
  7. }


j'ai besoin d'un peut d'aide pour traduire cette déclaration du Java à l'Ada

Code :
  1. type T_Arbre ;
  2. type T_Ptr_Arbre is access T_Arbre ;
  3. type T_Arbre is
  4.     record
  5.          Contenue : T_Item ;
  6.          Frere_null  : boolean ;
  7.          aine           : T_Ptr_Arbre := null;
  8.          suivant      : T_Ptr_Arbre := null;
  9.     -- je ne comprend pas la derniere ligne ! --
  10.     en record;


 
Merci  :jap:


Message édité par Profil supprimé le 16-05-2006 à 10:44:57
Reply

Marsh Posté le 16-05-2006 à 11:09:24    

Pour le code java
 
  La dernière ligne est le constructeur de la classe java. On passe en paramètre la variable val de type Object et on l'affecte à contenu.
 
en Ada, tu fait quelquechose dans ce style :  
 
procedure Create( N : out Noeud; Val : in T_Item) is
begin
   N.Contenue := Val;
end Create;
 
Ca répond à ta question?
 

Message cité 1 fois
Reply

Marsh Posté le 16-05-2006 à 11:12:48    

Erreur de ma part, un arbre p-aire sera suffisant. En effet on connait le nombre maximum de fils de chaque noeud, en l'occurence : 4
Et la coup de bole j'ai la declaration en Ada  [:666rip666]

Message cité 1 fois
Reply

Marsh Posté le 16-05-2006 à 11:13:59    

Hum, toutes mes excuse Loki du placard

Reply

Marsh Posté le 16-05-2006 à 11:16:38    

Loki du placard a écrit :

Pour le code java
 
  La dernière ligne est le constructeur de la classe java. On passe en paramètre la variable val de type Object et on l'affecte à contenu.
 
en Ada, tu fait quelquechose dans ce style :  
 
procedure Create( N : out Noeud; Val : in T_Item) is
begin
   N.Contenue := Val;
end Create;
 
Ca répond à ta question?


 
Euh, je comprend pas trop en fait,
Ce serait pas un truc du genre
 
type Noeud(val : item) is
  record
     --
     --
     --
   end record;

Reply

Marsh Posté le 16-05-2006 à 11:23:54    

Donc, en fait, mon type est complet ?
 

Code :
  1. type T_Arbre ;
  2.     type T_Ptr_Arbre is access T_Arbre ;
  3.     type T_Arbre is
  4.        record
  5.             Contenue : T_Item ;
  6.             Frere_null  : boolean ;
  7.             aine           : T_Ptr_Arbre := null;
  8.             suivant      : T_Ptr_Arbre := null;
  9.        -- je ne comprend pas la derniere ligne ! --
  10.        en record;

Reply

Marsh Posté le 16-05-2006 à 11:47:44    


 
C'est pas ça encore, bref je sais pas comment ça s'appel, c'est un arbre général, oui. une repérsentation contiguë par niveau.
 
Ce qui doit donner :
 
 
 

Code :
  1. type T_Arbre;
  2. type T_Ptr_Arbre is access T_Arbre;
  3. type T_Foret is array (positive range 1..4) of T_Ptr_Arbre;
  4. type T_Arbre is
  5.     record
  6.         Contenu : T_Item;
  7.         Foret       : T_Foret
  8.     end record;


 
Corrigez moi si je me trompe !  :heink:  

Reply

Marsh Posté le 16-05-2006 à 14:49:35    

Citation :

Euh, je comprend pas trop en fait,
Ce serait pas un truc du genre
 
type Noeud(val : item) is
  record
     --
     --
     --
   end record;


 
Non, pas du tout. En java, il ne faut pas oublier que les déclarations et le code proprement dit sont dans le même source. La ligne 6 de ton exemple en java est une méthode, plus exactement un constructeur. C'est codé sur une ligne, et on peut faire plus lisible, mais ça correspond parfaitement à la méthode create que j'ai envoyé.
 

Message cité 1 fois
Reply

Marsh Posté le 16-05-2006 à 15:38:02    

Loki du placard a écrit :

Citation :

Euh, je comprend pas trop en fait,
Ce serait pas un truc du genre
 
type Noeud(val : item) is
  record
     --
     --
     --
   end record;


 
Non, pas du tout. En java, il ne faut pas oublier que les déclarations et le code proprement dit sont dans le même source. La ligne 6 de ton exemple en java est une méthode, plus exactement un constructeur. C'est codé sur une ligne, et on peut faire plus lisible, mais ça correspond parfaitement à la méthode create que j'ai envoyé.


 
Ok, merci Loki du placard
 
 
 
je reprend mon type T_Arbre que j'ai définit ainsi

Code :
  1. type T_Noeud;
  2.    type T_Ptr_Noeud is access T_Noeud;
  3.    type T_foret is array (Positive range 1..4) of T_Ptr_Noeud;
  4.    type T_Noeud is
  5.       record
  6.          Sous_Arbre : T_Foret;
  7.          Matrice : T_Matrice(N,M);
  8.       end record;
  9.  
  10.    type T_Arbre is
  11.       record
  12.          Taille : Natural := 0;
  13.          Profondeur : Natural := 0;
  14.          Racine : T_Noeud;
  15.          Courant : T_Noeud;
  16.          Parent  : T_Noeud;
  17.       end record;


 
Integré à mon type T_Jeu_Du_Taquin

Code :
  1. type T_Jeu_Du_Taquin is limited
  2.       record
  3.          Count : T_Borne_2 := 0; -- nombre d'elements dans la matrice initiale;
  4.          Matrice_Initiale : T_Matrice(N,M);
  5.          Matrice_Melangee : T_Matrice(N,M);
  6.          Matrice_Ordonnee : T_Matrice(N,M);
  7.          Liste_Des_Voisins_De_Vide : T_Liste;
  8.          Arbre_De_Resolution : T_Arbre;
  9.       end record;


 
 
Dans le code suivant,  
absisse et ordonnee sont deux fonctions renvoyants une valeur correspondant à leur nom,
solution est un tableau de pointeur sur les fonctions up, down, left et right renvoyants 0 si aucun element ne correspond a la position correspondante à leur nom par rapport à une position donnée, l'id de l'element correspondant si non.  
 
dans la boucle while, certainement innadaptée, j'initialise le premier noeud de l'arbre de resolution du Jeu du Taquin
 

Code :
  1. procedure Ranger_Une_Tuile(Dans : in out T_Jeu_Du_Taquin) is
  2.  
  3.    begin
  4.       ------------------------------------------------------------
  5.       if Dans.Arbre_De_Resolution.taille = 0 then
  6.          Dans.Matrice_Ordonnee := Dans.Matrice_Melangee;
  7.          Dans.Arbre_De_Resolution.Racine.Matrice := Dans.Matrice_Ordonnee;
  8.          Dans.Arbre_De_Resolution.Taille :=
  9.            Dans.Arbre_De_Resolution.Taille + 1;
  10.          Dans.Arbre_De_Resolution.Courant := Dans.Arbre_De_Resolution.Racine;
  11.          while not Sont_Egales(Dans.Arbre_De_Resolution.Courant.Matrice,
  12.                                Dans.Matrice_Initiale) loop
  13.             for I in Methodes loop
  14.                if Solution(I)(Absisse(Dans.Arbre_De_Resolution.Courant.Matrice,0),
  15.                               Ordonnee(Dans.Arbre_De_Resolution.Courant.Matrice,0),
  16.                               Dans.Arbre_De_Resolution.Courant.Matrice) /= 0 then
  17.                   Dans.Arbre_De_Resolution.Courant.Sous_Arbre(I) :=
  18.                     new T_Noeud ' ((others => null),Dans.Arbre_De_Resolution.Courant.Matrice);
  19.                   Permuter(Dans.Arbre_De_Resolution.Courant.Sous_Arbre(I).Matrice,
  20.                            Solution(I)
  21.                            (Absisse(Dans.Arbre_De_Resolution.Courant.Matrice,0),
  22.                             ordonnee(Dans.Arbre_De_Resolution.Courant.Matrice,0),
  23.                             Dans.Arbre_De_Resolution.Courant.Matrice));
  24.  
  25.                
  26.  
  27.                end if;
  28.             end loop;
  29.          end loop;
  30.       else
  31.          null;
  32.       end if;
  33.  
  34.       ------------------------------------------------------------
  35.    end Ranger_Une_tuile;


 
Mon probleme  :heink:  : construire l'arbre j'usqu'a trouver la solution  :pt1cable:
 
Une question que je me pose aussi : comment vais-je retrouver le chemin de la solution pour resoudre mon Jeu du Taquin ?
 
 
Avis aux arboriculteurs
 
 
 
 

Reply

Marsh Posté le 16-05-2006 à 17:08:45    

Pour m'echauffer un peut, j'ai fait un truc de ouf, qui marche pas évidemment  :pt1cable:, un truc recursif, mais je suis vraiment pas fort en la matière. d'ailleur c'est pas une fonction mais une procedure  :??: n'y prété pas trop d'attention, je l'ai faite au pif  :pfff: il manque certainement quelque chose.  
 

Code :
  1. procedure Construire_Arbre_De_Resolution(courant : in out T_Noeud;
  2.                                             Matrice_initiale : in T_matrice) is
  3.    begin
  4.       New_Line;
  5.       for I in Methodes loop
  6.          if Solution(I)(Absisse(Courant.Matrice,0),
  7.                         Ordonnee(Courant.Matrice,0),
  8.                         Courant.Matrice) /= 0 then
  9.             Courant.Sous_Arbre(I) :=
  10.               new T_Noeud ' ((others => null),Courant.Matrice);
  11.             Permuter(Courant.Sous_Arbre(I).Matrice,
  12.                      Solution(I)
  13.                      (Absisse(Courant.Sous_Arbre(I).Matrice,0),
  14.                       ordonnee(Courant.Sous_Arbre(I).Matrice,0),
  15.                       Courant.Sous_Arbre(I).Matrice));
  16.             if Courant.Sous_Arbre(I) /= null then
  17.             Afficher(Courant.Sous_Arbre(I).Matrice);
  18.             end if;
  19.          end if;
  20.       end loop;
  21.       if not Sont_Egales(Courant.Matrice,Matrice_initiale) then
  22.          for I in T_Foret'Range loop
  23.             if Courant.Sous_Arbre(I) /= null then
  24.  
  25.                Construire_Arbre_De_Resolution(Courant.Sous_Arbre(I).all,
  26.                                               Matrice_initiale);
  27.             end if;
  28.          end loop;
  29.       end if;
  30.       delay 1.0;
  31.    end Construire_Arbre_De_Resolution;
  32.  
  33.    Procedure Ranger_Une_Tuile(Dans : in out T_Jeu_Du_Taquin) is
  34.    begin
  35.       ------------------------------------------------------------
  36.       if (Dans.Arbre_De_Resolution.Racine.Sous_Arbre(1) = null and
  37.         Dans.Arbre_De_Resolution.Racine.Sous_Arbre(2) = null and
  38.         Dans.Arbre_De_Resolution.Racine.Sous_Arbre(3) = null and
  39.         Dans.Arbre_De_Resolution.Racine.Sous_Arbre(4) = null) then
  40.          Dans.Matrice_Ordonnee := Dans.Matrice_Melangee;
  41.          Dans.Arbre_De_Resolution.Racine.Matrice := Dans.Matrice_Ordonnee;
  42.          Dans.Arbre_De_Resolution.Courant := Dans.Arbre_De_Resolution.Racine;
  43.          Construire_Arbre_De_Resolution(Dans.Arbre_De_Resolution.Courant,
  44.                                         Dans.Matrice_initiale);
  45.          Dans.Arbre_De_Resolution.racine := Dans.Arbre_De_Resolution.courant;
  46.       else
  47.          null;
  48.       end if;
  49.  
  50.       ------------------------------------------------------------
  51.    end Ranger_Une_tuile;


 
si qu'elqu'un pouvait me confirmer qu'un procedure recursive c'est forcement une function, ça m'arrangerait


Message édité par Profil supprimé le 16-05-2006 à 18:02:07
Reply

Marsh Posté le 16-05-2006 à 18:13:01    

Erreur de segmentation :cry:  
(je suis sous Linux)  
 
Avec une matrice 2x2 mon petit programme génère une erreur de segmentation.
 
Il y a qu'elque chose qui cloche ? [:666rip666]  
 

Message cité 1 fois
Reply

Marsh Posté le 16-05-2006 à 20:17:10    

[:trotter88]  [:atreyu]  
 
je comprend pas pourquoi cette procedure ne trouve pas la solution
 
Un chti coup pouce, svp ici --> message prec, ou ici sources html


Message édité par Profil supprimé le 17-05-2006 à 00:47:14
Reply

Marsh Posté le 17-05-2006 à 01:09:06    

Citation :


Pour m'echauffer un peut, j'ai fait un truc de ouf, qui marche pas évidemment  :pt1cable:, un truc recursif, mais je suis vraiment pas fort en la matière. d'ailleur c'est pas une fonction mais une procedure  :??: n'y prété pas trop d'attention, je l'ai faite au pif  :pfff: il manque certainement quelque chose.  


 
Bien qu'avoir implémenté la procedure contruire_arbre_de_resolution au pif, elle devrait tourner,
 
j'ai fait une version sous forme de fonction qui est maintenant ma version de developpement courante.

cette fonction est sensé construire un arbre de toute les combinaisons possibles à partir de la matrice melangée du jeu du taquin jusqu'a trouver une solution.
 
Merci à ceux qui planchent ou qui vont plancher  
   
 

Reply

Marsh Posté le 17-05-2006 à 16:59:31    


 
Rassures-moi : t'as interfacé avec du C ?
 
Parceque normalement, pas de ça en Ada ....

Message cité 1 fois
Reply

Marsh Posté le 17-05-2006 à 17:32:39    

apprentitux a écrit :

Rassures-moi : t'as interfacé avec du C ?
 
Parceque normalement, pas de ça en Ada ....


A la, moi je suis sure d'avoir généré des Erreur de segmentation toute l'après midi, falait voir le code aussi
 
 
 
Enfin bref, je me ratrape un peut, j'ai réussi à généré une solution avec ma petite function construire arbre ... ,  
c'est pas finit mais ça vien, Il ne me reste plus qu'a retrouver le chemin de resolution (a l'envers) est ça roule

Reply

Marsh Posté le 17-05-2006 à 18:30:26    

il marche toujours pas en fait,
 
Trop surpris, j'ai fait un erreur de vaiable et du coup ben c'est toujours n'importe quoi en fait  :o


Message édité par Profil supprimé le 17-05-2006 à 18:30:57
Reply

Marsh Posté le 18-05-2006 à 11:09:54    

quelqun aurais le code d'un arbre general p-aire ou avec aîné et frere droit ça m'avancerai, Ada bien sur
 
j'en suis la, faire un paquetage generique d'un arbre general p-aire ou avec aîné et frere droit, je sais pas le quel choisir  [:666rip666]

Message cité 1 fois
Reply

Marsh Posté le 18-05-2006 à 17:26:05    

:hello:  :heink:  
 
j'placarde mon code, encore au cas ou !!
 
dans la procedrue suivante, je trouve plus le resultat, c'est à dire
que j'arrive pas a sortir quant je trouve le resultat, pourtant j'ai mis des exit Main_Loop par tout
 
c'es dans un n-arbre "à la jovalise"
 

Code :
  1. procedure Construire_arbre_De_Solution(Dans : in out T_Arbre;Matrice_Melangee,Matrice_Initiale : T_matrice) is
  2.  
  3.       Nouvelle_Matrice : T_Matrice;
  4.  
  5.  
  6.  
  7.       procedure Init_Racine(Dans : in out T_Arbre;Matrice_initiale : T_Matrice) is
  8.       begin
  9.          Dans.racine :=
  10.            new T_Noeud ' (null,null,null,Matrice_initiale,Dans.Courant);
  11.          Dans.Courant := Dans.Racine;
  12.       end;
  13.  
  14.  
  15.  
  16.       function L_Element_Courant(Dans : T_Arbre) return T_Matrice is
  17.       begin
  18.          return Dans.Courant.Matrice;
  19.       end;
  20.       function A_Un_Fils(Dans : T_Arbre) return Boolean is
  21.       begin
  22.          if Dans.Courant.suivant /= null then
  23.             return True;
  24.          else
  25.             Return False;
  26.          end if;
  27.       end ;
  28.       function A_Un_frere(Dans : T_Arbre) return Boolean is
  29.       begin
  30.          if Dans.Courant.Frere_courant /= null then
  31.             return True;
  32.          else
  33.             Return False;
  34.          end if;
  35.       end ;
  36.  
  37.       procedure Passer_Au_Suivant(Dans : in out T_Arbre) is
  38.       begin
  39.          Dans.Courant := Dans.Courant.Suivant;
  40.       end;
  41.  
  42.       procedure Passer_Au_Parent(Dans : in out T_Arbre) is
  43.       begin
  44.          Dans.courant := Dans.Courant.Parent;
  45.       end ;
  46.  
  47.  
  48.  
  49.       ------------------------------------------------------------------
  50.  
  51.    begin
  52.  
  53.       Init_Racine(Dans,Matrice_Melangee);
  54.  
  55.  
  56.   Main_Loop :
  57.       loop
  58.          Put_line("TATA" );
  59.          if Sont_Egales(Dans.Courant.Matrice,Matrice_Initiale) then
  60.             exit;
  61.          end if;
  62.          while A_Un_fils(dans) loop
  63.             Passer_Au_Suivant(Dans);
  64.          end loop;
  65.          for I in Methodes'range loop                              -- pour up, right, down, left
  66.             if Solution(i)(Absisse(L_Element_courant(Dans),0),       -- si solution(i) /= 0
  67.                            Ordonnee(L_Element_courant(Dans),0),
  68.                            L_Element_courant(Dans)) /= 0 then
  69.  
  70.  
  71.                Nouvelle_Matrice := L_Element_courant(dans);
  72.  
  73.                Permuter(Nouvelle_matrice,
  74.                         Solution(i)
  75.                         (Absisse(Nouvelle_Matrice,0),
  76.                          ordonnee(Nouvelle_Matrice,0),
  77.                          Nouvelle_Matrice));-- permute dans noeud suivant avec solution(I)
  78.  
  79.                Afficher(Nouvelle_Matrice);
  80.                if not A_Un_Frere(Dans) then
  81.                   Put_line("TOTO" );
  82.                   delay 1.0;
  83.                   Dans.Courant.Suivant :=
  84.                     new T_Noeud ' (null,
  85.                                    null,
  86.                                    null,
  87.                                    Nouvelle_Matrice,Dans.Courant);
  88.  
  89.  
  90.                elsif Dans.Courant.Suivant.Frere_aine = null then
  91.                   Dans.Courant.Suivant.Frere_aine :=
  92.                     new T_Noeud ' (null,
  93.                                    Dans.Courant.Frere_Aine,
  94.                                    Dans.Courant.Suivant,
  95.                                    Nouvelle_Matrice,Dans.Courant);
  96.                   Dans.Courant.Suivant.Frere_Courant := Dans.Courant.suivant.Frere_aine;
  97.  
  98.                else
  99.                  Dans.Courant.Suivant.Frere_Courant.suivant :=
  100.                     new T_Noeud ' (null,
  101.                                    Dans.Courant.Frere_Aine,
  102.                                    Dans.Courant.Suivant,
  103.                                    Nouvelle_Matrice,Dans.Courant);
  104.                   Dans.Courant.Suivant.Frere_Courant := Dans.Courant.Suivant.Frere_Courant.Suivant;
  105.  
  106.                end if;
  107.  
  108.             end if;
  109.          end loop;
  110.          Dans.Courant.Suivant.Frere_Courant := Dans.Courant.Suivant.Frere_Aine;
  111.          if Dans.Courant /= Dans.Racine then
  112.             Passer_Au_Parent(Dans);
  113.          end if;
  114.          Dans.Courant := Dans.Courant.Suivant;
  115.          if Sont_Egales(Dans.Courant.Matrice,Matrice_Initiale) then
  116.             exit;
  117.          end if;
  118.          if Dans.Courant.Frere_Courant /=null then
  119.             Dans.Courant := Dans.Courant.Frere_Courant;
  120.             Dans.Courant.Frere_Courant := Dans.Courant.Frere_Courant.Suivant;
  121.             for I in Methodes'range loop                              -- pour up, right, down, left
  122.             if Solution(i)(Absisse(L_Element_courant(Dans),0),       -- si solution(i) /= 0
  123.                            Ordonnee(L_Element_courant(Dans),0),
  124.                            L_Element_courant(Dans)) /= 0 then
  125.  
  126.  
  127.                Nouvelle_Matrice := L_Element_courant(dans);
  128.  
  129.                Permuter(Nouvelle_matrice,
  130.                         Solution(i)
  131.                         (Absisse(Nouvelle_Matrice,0),
  132.                          ordonnee(Nouvelle_Matrice,0),
  133.                          Nouvelle_Matrice));-- permute dans noeud suivant avec solution(I)
  134.  
  135.                Afficher(Nouvelle_Matrice);
  136.                if not A_Un_Frere(Dans) then
  137.                   Put("TOTO" );
  138.                   delay 1.0;
  139.                   Dans.Courant.Suivant :=
  140.                     new T_Noeud ' (null,
  141.                                    null,
  142.                                    null,
  143.                                    Nouvelle_Matrice,Dans.Courant);
  144.                   if Sont_Egales(Dans.Courant.Suivant.Matrice,Matrice_Initiale) then
  145.                      exit Main_loop;
  146.                   end if;
  147.  
  148.                elsif Dans.Courant.Suivant.Frere_aine = null then
  149.                   Dans.Courant.Suivant.Frere_aine :=
  150.                     new T_Noeud ' (null,
  151.                                    Dans.Courant.Frere_Aine,
  152.                                    Dans.Courant.Suivant,
  153.                                    Nouvelle_Matrice,Dans.Courant);
  154.                   Dans.Courant.Suivant.Frere_Courant := Dans.Courant.suivant.Frere_aine;
  155.                   if Sont_Egales(Dans.Courant.Suivant.Frere_Aine.matrice,Matrice_Initiale) then
  156.                      exit Main_loop;
  157.                   end if;
  158.                else
  159.                   Dans.Courant.Suivant.Frere_Courant.suivant :=
  160.                     new T_Noeud ' (null,
  161.                                    Dans.Courant.Frere_Aine,
  162.                                    Dans.Courant.Suivant,
  163.                                    Nouvelle_Matrice,Dans.Courant);
  164.                   Dans.Courant.Suivant.Frere_Courant := Dans.Courant.Suivant.Frere_Courant.Suivant;
  165.                   if Sont_Egales(Dans.Courant.Suivant.Frere_Courant.matrice,Matrice_Initiale) then
  166.                      exit Main_loop;
  167.                   end if;
  168.                end if;
  169.  
  170.             end if;
  171.             end loop;
  172.             Dans.Courant.Suivant.Frere_Courant := Dans.Courant.Suivant.Frere_Aine;
  173.          else
  174.             Passer_Au_Parent(Dans);
  175.          end if;
  176.       end loop Main_Loop;
  177.    end Construire_Arbre_De_Solution

Reply

Marsh Posté le 19-05-2006 à 13:15:28    


 
 :hello:  
 
Oa, la spec, ça me suffira  [:666rip666]

Reply

Marsh Posté le 19-05-2006 à 13:48:01    

Je fait des tentatives par deduction mais si je suis partie avec une mauvaise abstraction du type je m'en sortirai pas  :??:  
 
svp, jetez un coup d'oeuil a mon T_Arbre  :heink:  
 

Code :
  1. type T_Noeud;
  2.    type T_Ptr_Noeud is access T_Noeud;
  3.  
  4.      type T_Noeud is
  5.         record
  6.            Suivant : T_Ptr_Noeud;    --pointeur sur suivant
  7.            Frere_aine : T_Ptr_Noeud;      -- pointeur file frere
  8.            Frere_Courant : T_Ptr_Noeud;  -- pointeur frere courant
  9.            Matrice : T_Matrice;                   -- element de l'abre
  10.            Parent : T_Ptr_Noeud;                -- pointeur sur le noeud parent
  11.         end record;
  12.  
  13.    type T_Arbre is
  14.       record
  15.          Racine : T_Ptr_Noeud;  -- pointeur sur la racine de l'arbre
  16.          Courant : T_Ptr_Noeud;  -- pointeur sur le noeud courant de l'arbre
  17. --         Frere_Courant : T_Ptr_Noeud; -- non utilisé
  18.       end record;


 
Merci    :jap:

Reply

Marsh Posté le 19-05-2006 à 22:11:03    

:heink:  J'ai un problème avec la procedruee construire_arbre_de_solution lignes 298 à 582 concernent le passage au frere_courant qui est en faite le frere suivant à visiter;
 
apres une iteration de passer_frere_suivant, courant.frere_courant doit prendre la valeur de courant.frere_courant.frere_courant, le frere suivant frere_courant
c'est ce que je fait ligne 434 a l'aide du tampon
 
ainsi en passant alternativement d'un courant a un frere_courant au courant, ainsi de suite, grace a passer_frere_suivant et passer_au_parent, je passe au frere suivant;
 
 
le probleme est que c'a n'itere pas, le frere_courant ne passe pas au frere suivant frere_courant.frere_courant;
 
les sources de Taquin_9 sont disponibles ICI  ;)  
 
construire_arbre_de_solution est dans p_taquin.adb
 

Reply

Marsh Posté le 20-05-2006 à 05:18:53    

[:cid]   [:666rip666]  
 
j'ai enfin réussi a itere mes frere_courant, a priorie ça tourne
 
c'est un peut long a calculer mais ça sort la solution (testé à chaud avec matrice 2x2 et 3x3)  
 
le reste, c'est de la rigolade, je vais essayer de suprimer les doublons direct,
 
je fait quelque test d'ici demain et je marque resolut dans le titre du topic  [:666rip666]

Reply

Marsh Posté le 20-05-2006 à 05:44:01    

Bon, ben fausse anonce, ça marche toujours pas,
pour une matrice 2x2 pas de probleme  [:666rip666]  
 
A+

Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed