Rapport sur GraphViz

La suite de Syracuse est une suite mathématiques définie de la manière suivante: U₀=n,

Une conjecture a été émise par rapports a cette suite selon le fait que n’importe quel nombre x ∈ \mathbb{N*} auquel on applique cette suite atteindra forcémment la valeur 1. La conjecture est pour l’instant démontré pour les entiers allant de 1 à 2⁶⁸, ce qui représente environ 295 147 905 179 352 825 856 nombres. Il nous est demander de construire le graphe représentant du bas vers le haut, un nombre et son/ses antécédent(s) possible(s), le voici avec une hauteur limité a 15:

Le code en C qui a permis de creer ce graph grace a graphviz est:

#include<stdio.h>

int syracuse(int n, int h){

  if(h!=0){
    printf("%d->%d\n",n*2,n);
    syracuse(n*2,h-1);


  if((n-1)%6==3 && n!=4){
    printf("%d->%d\n",(n-1)/3,n);
    syracuse((n-1)/3,h-1);
  }
  }
  return 0;
}




int main(){
  int h=15;
  printf("strict digraph{\n");
  syracuse(1,h);
  printf("}\n");
  return 0;
}

Ce code fonctionne de manière a creer l’arbre en partant de 1.

On définie d’abord la fonction syracuse, qui est une fonction récursive, on regarde si la hauteur n’est pas dépasser, si c’est le cas on affiche l’antécédent pair de n vers n dans la syntaxe demander pour compiler avec dot puis on renvoie la fonction avec n qui devient l’antécédent pair de n ainsi que la hauteur-1.

On regarde ensuite si l’antécédent impair de n existe et on affiche de la même manière qu’au dessus l’antécédent impair suivi de n, puis en renvoie la fonction avec n devient son antécédent impair et h diminué de 1.

Dans main on définie la hauteur, 15 dans ce cas la, puis on affiche la ligne qui permet de creer le graph , ensuite on laisse la fonctions syracuse faire le boulot pour après afficher ce qui permet de fermet le graph.

C’est une fonction récursive, qui renvoie un couple de valeur (i,j), voici le graph obtenue à partir des valeurs i=1 et j=4:

Le code en C utilisé pour obtenir ce graph est le suivant:

#include <stdio.h>

int fonction(int i,int j){

  int k;

  if(j==0){
    return 1;
  }
  else if (i<j) {
    printf("{\"%d, %d\"}->{\"%d, %d\"}",i,j,i+1,j);
    fonction(i+1,j);

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


int main(){

  int i=1;
  int j=4;
    printf("digraph{\n");
    printf("{\"%d, %d\"}",i,j);
    fonction(i,j);
    printf("}\n");

return 0;
}

Ce code fonctionne de la manière suivante: On définie la fonction “fonction”, avec comme paramètres i et j.

En premier on regarde si j=0, dans ce cas on renvoie 1. Sinon on regarde si i<j, dans ce cas on affiche le couple de valeur (i,j) direction le couple (i+1,j), puis on renvoie la fonction pour i=i+1 et j=j.

Enfin si aucun des deux cas n’est respecté, on démarre une boucle puis on renvoie la fonction avec en paramètre i qui est égal à l’élément qui itère dans la boucle et j=j-1 puis on affiche le couple (i,j) direction le couple (k,j-1).

Dans main on définie les premiers i et j, puis on affiche la structure du graph tout en appelant au milieu la fonction.