Rapport dessiner des appelles de fonction avec Graphviz

Table des matières

1. Syracuse
2. Fonction f
3. Conclusion

1. Syracuse

1.1. Définition

La suite de Syracuse est un suite d’entier naturels definie de la manière suivante: On part d’un nombre entier strictement positif:

s’il est pair, on le divise par 2:
s’il est impair, on le multiplie par 3 et l’on ajoute 1.

En répétant l’opération, on obtient une suite d’entiers strictements positifs dont chacun ne dépend que de son prédécesseur.

Pour modéliser ces relations, on peut utiliser le logiciel Graphviz qui permet de dessiner des graphes.

Chaque noeud sera un nombre et il sera lié à son ou ses prédécesseurs et à son fils. Dans cette exemple, on part du nombre 1.

1.2. Code en C

#include <stdio.h>
#include <stdlib.h>

void syracuse(int n, int hauteur, int hauteur_max){

  if (hauteur == hauteur_max){
    printf("\n");
    return;
  }

  printf("%d -> %d\n", n, n*2);
  syracuse(n*2, hauteur + 1, hauteur_max);

  if ((n-1) % 3 == 0 && ((n-1)/3) % 2 == 1){
    printf("%d -> %d\n", n, (n-1)/3);
    syracuse((n-1)/3, hauteur + 1, hauteur_max);
  }
}

int main(){

  printf("strict digraph { \n");
  printf("rankdir=\"BT\"");

  syracuse(1, 1, 15);

  printf("}");
  return 0;
}

1.3. Explication du code

A commence par appeller la fonction syracuse en première fois, avec comme argument le nombre de départ ici 1, la hauteur du prochain noeud ici 1, et la hauteur max que l’on souhaite.

Ensuite, a chaque appelle de fonction on verifie si l’on a atteind la hauteur max. Si oui on quitte la fonction sans nouvel appelle, si non deux cas ce présentent. Si il existe (n-1)/3 un nombre entier impair alors (n-1)/3 est un antécedent. Dans tous les cas deuxieme antécedent sera toujours n*2. On rappelle ensuite la fonction pour chaque antécédents trouvés.

1.4. Résultat

2. Fonction f

2.1. Définition

La fonction f est définie comme suit:

fonction f(entier i, entier j):

si j==0, renvoyer 1
sinon si i < j, renvoyer f(i+1, j) + 1
sinon, revoyer la somme pour k dans [0..i-1] des f(k, j-1)

2.2. Code en C

#include <stdio.h>
#include <stdlib.h>

int f(int i, int j){
  if (j == 0){
    return 1;
  }else if(i < j){
    printf("\"(%d, %d)\"->\"(%d, %d)\"", i, j, i+1, j);
    return f(i+1, j) + 1;
  }else {
    int k;
    int somme = 0;
    for(k=0; k<=i-1; k++){
      printf("\"(%d, %d)\"->\"(%d, %d)\"", i, j, k, j-1);
      somme += f(k, j-1);
    }
    return somme;
  }
}


int main() {
  printf("digraph {\n");

  f(5, 3);

  printf("}\n");
  return 0;
}

2.3. Explication du code

On commence par appeller la fonction f avec les arguments 5 et 3. Puis pour chaque appelle de la focntion on verifie les trois cas possibles. Le premier cas permet de sortir de la récusion c’est le cas de base. Les deuxieme et troisieme conditions rappellent quand à elle la fonction f.

2.4. Résultat

3. Conclusion

Les commandes utilisées pour compiler puis transformer le résulat en svg sont les suivantes:

gcc -Wall -Wextra -o syracase syracuse.c
./syracuse > syracuse.gvz
dot -Tsvg syracuse.gvz > syracuse.svg

On peut condenser le tout en une ligne:

gcc -Wall -Wextra -g -o syracuse syracuse.c && ./syracuse > syracuse.gvz && dot -Tsvg syracuse.gvz > syracuse.svg

Pour ouvrir l’image on peut utiliser la commande suivante:

mimeopen syracuse.svg &

Pour en savoir plus sur la conjecture de Syracuse : Page Wikipédia

Lien de retour vers ma page web personnelle