Problème d'algorithmique

invite85cf360b · 05/04/2013, 16h09

Bonjour,

Je voudrais faire une fonction qui me calcule des numéros sosas sur des personnes et je ne sais pas comment m'y prendre, je m'explique.

Dans une table Mysql, j'ai des individus avec un id de référence et l'id de leur père et de leur mère.

Les numéros sosas se calculent de la manière suivante :

Le numéro sosa de départ est 1, le père est le 2 et la mère le 3, le grand père paternel est le 4, la grand mère paternelle est le 5, le grand père maternel est le 6, la grand mère maternelle est le 7.

Soit le sosa des parents est toujours 2*N pour le père et 2*N+1 pour la mère.

Donc partant de l'id de la première personne et lui attribuant le sosa 1, j'aimerais donner à chaque parent trouvé dans ma table Mysql son numéro sosa correspondant.

Je pense faire une fonction récursive mais je ne sais pas comment écrire cette fonction. Je voyais :

Code:

fonction Attrib_sosa (num_sosa, id_indi)
{
   lecture de la fiche de l'id_indi
      si le père est renseigné, on lit la fiche du père et on calcule son sosa 2*num_sosa et on mets à jour sa fiche
                                puis on rappelle la fonction Attrib_sosa avec le nouveau sosa calculé et l'id_indi du père
      si la mère est renseignée, on lit la fiche de la mère et on calcule son sosa 2*num_sosa+1 et on mets à jour sa fiche
                                 puis on rappelle la fonction Attrib_sosa avec le nouveau sosa calculé et l'id_indi de la mère
}

Voilà pour le principe que j'ai trouvé, mais en faisant des essais "à la main", je n'y arrive pas, il doit me manquer des sauvegardes de l'id quelque part, mais lequel et où ?

Quelqu'un ou quelqu'une pourrait il m'aider à construire cette fonction ?

Merci beaucoup de votre amabilité.

**kwariz** · 05/04/2013, 16h31

Bonjour,

Le calcul du sosa est correct. Quel est ton problème en faisant des essais à la main ?

La seule remarque que je pourrais faire est la manière dont tu as contruit Attrib_sosa. Tout comme toi je lui ferais prendre comme paramètre l'id de l'individu à mettre à jour, et la nouvelle valeur de sosa. Cela donne quelque chose comme :

Code:

procedure Attrib_sosa(new_sosa, id_indi)
debut
  mise à jour pour l'individu d'id id_indi du champs sosa avec la valeur new_sosa
  si le champs père de l'individu est renseigné alors
    Attrib_sosa(2*new_sosa, id_père)
  fin si
  si le champs mère de l'individu est renseigné alors
    Attrib_sosa(2*new_sosa+1, id_mère)
  fin si
fin

Du coup un appel à Attrib_sosa(1, id_depart) devrait faire l'affaire.

invite85cf360b · 05/04/2013, 17h04

Merci de cette réponse,

La fonction que tu donnes modifie la manière de mettre à jour l'individu, je mettais à jour sous condition, tu le mets à jour au départ et tu as raison.

Mon problème en essayant à la main est que je ne savais pas comment et où revenir sur quel individu quand j'atteignais l’enregistrement qui n'avait plus de père, et comment redémarrer sur la mère, puis sur quelle mère recommencer ? celle du départ, la 3 ou celle de la dernière fiche ? bref dans quelle branche repartir ?

Voilà tous ces problèmes qui me sortent à chaque fois que j'ai "tenté" de faire une fonction récursive, qui pour moi n'est pas du tout évidente à concevoir.

Si tu penses que ta fonction est la bonne, je vais la transcrire dans mon langage, et je vais bien voir, puis je reprends contact.
Merci beaucoup.

**kwariz** · 05/04/2013, 17h15

Ta structure est récursive et décrit un arbre binaire, la solution récursive me semble la meilleure approche. Quand tu effectues des appels récursifs tu n'as plus à te poser de questions où tu vas reprendre, tout est stocké sur un pile et c'est transparent pour toi. Souvent, suivant le langage et l'os la pile est un espace limité mais bon la profondeur d'un arbre généalogique n'est pas un problème si tu ne stocke pas trop de données.

A voir en vidéo sur Futura · Aujourd'hui

invite85cf360b · 05/04/2013, 17h29

Ok alors je ne pose plus de questions, je vais programmer et je lancerais mon jeu d'essai, puis on verra le résultat, correct ou pas, je reviens contact, sûrement demain.
Bonne soirée.

invite85cf360b · 06/04/2013, 08h57

Bonjour Kwariz,

Voilà la fonction écrite et qui marche, en dessous l'affichage du résultat (avant de faire un update dans ma base) et l'arbre représenté pour vérification.

Code:

function Attrib_sosa($new_sosa, $id_indi)
{
    $ret = mysql_query("select * from Test_pour_sosa where gedcom = '$id_indi'");
	$ligne = mysql_fetch_assoc($ret);
	$gedcom = $ligne['gedcom'];
	$sosa = $ligne['sosa'];
	$nom = $ligne['nom'];
	$prenom = $ligne['prenom'];
	$gedcom_pere = $ligne['gedcom_pere'];
	$gedcom_mere = $ligne['gedcom_mere'];

echo "Mise à jour de ".$prenom." ".$nom.", id = ".$gedcom.", sosa = ".$new_sosa.", pére : ".$gedcom_pere.", mère : ".$gedcom_mere;
    //$sqlmaj = "update Test_pour_sosa set sosa = $new_sosa where gedcom = '$id_indi'";  
    //mysql_query($sqlmaj) or  die('Erreur de base : '.mysql_error());

   if ($gedcom_pere != '') 
   {
      Attrib_sosa($new_sosa*2, $gedcom_pere);
   }  
   if ($gedcom_mere != '') 
   {
      Attrib_sosa(($new_sosa*2)+1, $gedcom_mere);
   }   
}

Mise à jour de Patrick DUPONT, id = 4173I, sosa = 1, pére : 4179I, mère : 4187I
Mise à jour de Gaston DUPONT, id = 4179I, sosa = 2, pére : 12923I, mère : 12928I
Mise à jour de Leopold DUPONT, id = 12923I, sosa = 4, pére : 1258I, mère : 2450I
Mise à jour de Francois DUPONT, id = 1258I, sosa = 8, pére : , mère : 
Mise à jour de Elisa TREDOULAT, id = 2450I, sosa = 9, pére : , mère : 
Mise à jour de Elise DOVAT, id = 12928I, sosa = 5, pére : 1587, mère : 
Mise à jour de , id = , sosa = 10, pére : , mère : 
Mise à jour de Rolande VINCENT, id = 4187I, sosa = 3, pére : 6527I, mère : 4484I
Mise à jour de Roger VINCENT, id = 6527I, sosa = 6, pére : 6571I, mère : 1682I
Mise à jour de , id = , sosa = 12, pére : , mère : 
Mise à jour de , id = , sosa = 13, pére : , mère : 
Mise à jour de Nellie MALIBAS, id = 4484I, sosa = 7, pére : , mère : 1477I
Mise à jour de , id = , sosa = 15, pére : , mère : 


1258I   2450I    1587I            6571I    1682I              1477I
 8        9       10      11        12       13       14       15

   12923I          12928I             6527I             4484I    
     4                5                 6                 7

           4179I                              4187I
             2                                  3
                          4173I
                            1

Je perds certains gedcom de la ligne 8 à 15, je ne sais pas pourquoi, car j'ai les sosas 8 et 9 et pas 10, 12, 13 et 15
Merci beaucoup de ta contribution.

invite85cf360b · 06/04/2013, 09h25

Au temps pour moi, c'est mon jeu d’essai dans ma base qui n'était pas complet, après complément on trouve bien toutes les attributions des sosas à tout ce petit monde :

Code:

Mise à jour de Patrick DUPONT, id = 4173I, sosa = 1, pére : 4179I, mère : 4187I
Mise à jour de Gaston DUPONT, id = 4179I, sosa = 2, pére : 12923I, mère : 12928I
Mise à jour de Leopold DUPONT, id = 12923I, sosa = 4, pére : 1258I, mère : 2450I
Mise à jour de Francois DUPONT, id = 1258I, sosa = 8, pére : , mère : 
Mise à jour de Elisa TREDOULAT, id = 2450I, sosa = 9, pére : , mère : 
Mise à jour de Elise DOVAT, id = 12928I, sosa = 5, pére : 1587I, mère : 
Mise à jour de Jean Marc DOVAT, id = 1587I, sosa = 10, pére : , mère : 
Mise à jour de Rolande VINCENT, id = 4187I, sosa = 3, pére : 6527I, mère : 4484I
Mise à jour de Roger VINCENT, id = 6527I, sosa = 6, pére : 6571I, mère : 1682I
Mise à jour de Pierre VINCENT, id = 6571I, sosa = 12, pére : , mère : 
Mise à jour de Marie CHOTARD, id = 1682I, sosa = 13, pére : , mère : 
Mise à jour de Nellie MALIBAS, id = 4484I, sosa = 7, pére : , mère : 1477I
Mise à jour de Marie CHEMINADE, id = 1477I, sosa = 15, pére : , mère :

Désolé d'avoir répondu avant d'avoir tout vérifié.
Maintenant tout marche parfaitement et je te remercie encore de ta contribution à m'avoir aider dans la conception de cette fonction.
Bonne journée

**kwariz** · 06/04/2013, 11h38

Hello,
Mais de rien, c'est très agréable (et rapide) d'orienter quelqu'un qui passe par un algo, un test à la main, une implémentation puis un test de l'implémentation avant ... tu as de bons réflexes et la bonne démarche.
Bravo et bonne continuation.

Dlzlogic · 06/04/2013, 12h32

Envoyé par kwariz

Hello,
Mais de rien, c'est très agréable (et rapide) d'orienter quelqu'un qui passe par un algo, un test à la main, une implémentation puis un test de l'implémentation avant ... tu as de bons réflexes et la bonne démarche.
Bravo et bonne continuation.

J'approuve.

D'ailleurs, je constate que ce sont les meilleurs qui font un algorithme, le testent etc.
Mais on constate aussi que ceux qui font un algorithme, le testent etc. sont les meilleurs.
Donc, gros dilemme pour les plus jeunes, par quoi faut-il commencer "être le meilleur" ou "faire un algorithme" ?

invite85cf360b · 06/04/2013, 13h21

C'est vrai que c'est en essayant et en testant que l'on apprends, que l'on se bonifie et que l'on devient meilleur qu'au départ, quand à être LE meilleur c'est une autre histoire.

Je débute, à 65 ans, dans ces nouveaux langages web, php, jquery, ajax, etc ... et certains algos que j'ai du mal à générer, alors des personnes comme vous me permettent d'avancer et de devenir un peu meilleur dans ce que j'entreprends.

Merci encore.

Problème d'algorithmique