SHARE
TWEET

Untitled

a guest Oct 12th, 2017 50 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <assert.h>
  4. #include <conio.h>
  5.  
  6. struct NoeudSt {
  7.     int masse;
  8.     float longueur_droite;
  9.     float longueur_gauche;
  10.     struct NoeudSt * fils_gauche;
  11.     struct NoeudSt * fils_droit;
  12. };
  13. typedef struct NoeudSt * Mobile;
  14.  
  15. Mobile creer_noeud(float longueur_gauche,float longueur_droite, Mobile fils_gauche, Mobile fils_droit) {
  16.  
  17.     Mobile resultat;
  18.  
  19.     resultat = (Mobile)malloc(sizeof(struct NoeudSt));
  20.     if (resultat == NULL) {
  21.         fprintf(stderr, "Erreur: impossible d'allouer un nouveau noeud.\n");
  22.         exit(-1);
  23.     }
  24.     resultat->masse = 0;
  25.     resultat->longueur_gauche = longueur_gauche;
  26.     resultat->longueur_droite = longueur_droite;
  27.     resultat->fils_gauche = fils_gauche;
  28.     resultat->fils_droit = fils_droit;
  29.  
  30.     return resultat;
  31. }
  32.  
  33. Mobile creer_feuille(int masse) {
  34.  
  35.     Mobile resultat;
  36.  
  37.     resultat = (Mobile)malloc(sizeof(struct NoeudSt));
  38.     if (resultat == NULL) {
  39.         fprintf(stderr, "Erreur: impossible d'allouer un nouveau noeud.\n");
  40.         exit(-1);
  41.     }
  42.     resultat->masse = masse;
  43.     resultat->longueur_gauche = 0;
  44.     resultat->longueur_droite = 0;
  45.     resultat->fils_gauche = NULL;
  46.     resultat->fils_droit = NULL;
  47.  
  48.     return resultat;
  49. }
  50. int est_barre(Mobile m) {
  51.     if ((m->masse == 0) && (m->longueur_gauche > 0.0f) && (m->longueur_droite > 0.0f)) return 1;
  52.     else return 0;
  53. }
  54.  
  55. int est_objet(Mobile m) {
  56.     if ((m->masse > 0) && (m->longueur_gauche == 0.0f) && (m->longueur_droite == 0.0f)) return 1;
  57.     else return 0;
  58. }
  59.  
  60. int masse_mobile(Mobile m) {
  61.     if (m == NULL) return 0;
  62.     else if (est_objet(m)) return m->masse;
  63.     else return (masse_mobile(m->fils_gauche) + masse_mobile(m->fils_droit));
  64. }
  65.  
  66. int barre_horizontale(Mobile m) {
  67.     if (m == NULL) return 1;
  68.     else if ((masse_mobile(m->fils_gauche)* m->longueur_gauche) == (masse_mobile(m->fils_droit) * m->longueur_droite)) return 1;
  69.     else return 0;
  70. }
  71.  
  72. int est_equilibre(Mobile m) {
  73.     if (m == NULL) return 1;
  74.     else if (barre_horizontale(m)) return barre_horizontale(m->fils_gauche) * barre_horizontale(m->fils_droit);
  75.     else return 0;
  76. }
  77.  
  78. int encombrement(Mobile m) {
  79.     if (m == NULL) return 0;
  80.     else {
  81.         float max_l = encombrement(m->fils_gauche) + m->longueur_gauche;
  82.         float max_r = encombrement(m->fils_droit) + m->longueur_droite;
  83.         return (int)((max_l > max_r) ? max_l : max_r);
  84.     }
  85. }
  86.  
  87. int barre_assez_large(Mobile m) {
  88.     if (m == NULL) return 1;
  89.     int enc_l = encombrement(m->fils_gauche);
  90.     int enc_r = encombrement(m->fils_droit);
  91.     if (m->longueur_droite < enc_r) return 0;
  92.     else if (m->longueur_gauche < enc_l) return 0;
  93.     else return 1;
  94. }
  95.  
  96. int mobile_libre(Mobile m) {
  97.     if (m == NULL) return 1;
  98.     else if (!est_equilibre(m)) return 0;
  99.     else if (barre_assez_large(m)) return mobile_libre(m->fils_gauche) * mobile_libre(m->fils_droit);
  100.     else return 0;
  101. }
  102.  
  103. Mobile libere(Mobile m) {
  104.     if (m == NULL) return NULL;
  105.     if (est_barre(m)) {
  106.         int ret_l_l = m->longueur_gauche;
  107.         int ret_l_r = m->longueur_droite;
  108.         if (barre_assez_large(m) == 0) {
  109.             int max_l = encombrement(m->fils_gauche);
  110.             int max_r = encombrement(m->fils_droit);
  111.             if (m->longueur_gauche < max_l) ret_l_l = max_l + 1;
  112.             if (m->longueur_droite < max_r) ret_l_r = max_r + 1;
  113.         }
  114.         return creer_noeud(ret_l_l, ret_l_r, libere(m->fils_gauche), libere(m->fils_droit));
  115.     }
  116.     else {
  117.         return creer_feuille(m->masse);
  118.     }
  119. }
  120.  
  121. int main() {
  122.     Mobile m1 = creer_noeud(5.0f, 5.0f,
  123.         creer_noeud(2.0f, 2.0f, creer_feuille(2), creer_noeud(3.0f, 6.0f, creer_feuille(4), creer_feuille(2))),
  124.         creer_noeud(3.0f, 3.0f, creer_feuille(4), creer_feuille(4)));
  125.     Mobile m2 = NULL;
  126.     Mobile m4 = creer_noeud(5.0f, 5.0f,
  127.         creer_noeud(6.0f, 7.0f, creer_feuille(1), creer_noeud(1.0f, 3.0f, creer_feuille(12), creer_feuille(22))),
  128.         creer_noeud(3.0f, 3.0f, creer_feuille(40), creer_feuille(46)));
  129.     Mobile m3 = creer_feuille(10);
  130.     Mobile m5 = creer_noeud(5.0f, 5.0f,
  131.         creer_noeud(2.0f, 2.0f, creer_feuille(2), creer_feuille(2)),
  132.         creer_feuille(4));
  133.     printf("Masse totale");
  134.     printf("\n%d", masse_mobile(m1));
  135.     printf("\n%d", masse_mobile(m2));
  136.     printf("\n%d", masse_mobile(m3));
  137.     printf("\n%d", masse_mobile(m4));
  138.     printf("\n%d", masse_mobile(m5));
  139.     printf("\n______________________________\nBarre Horizontale");
  140.     printf("\n%d", barre_horizontale(m1));
  141.     //printf("\n%d", barre_horizontale(m2));
  142.     printf("\n%d", barre_horizontale(m3));
  143.     printf("\n%d", barre_horizontale(m4));
  144.     printf("\n%d", barre_horizontale(m5));
  145.     printf("\n______________________________\nEst Equilibre");
  146.     printf("\n%d", est_equilibre(m1));
  147.     //printf("\n%d", est_equilibre(m2));
  148.     printf("\n%d", est_equilibre(m3));
  149.     printf("\n%d", est_equilibre(m4));
  150.     printf("\n%d", est_equilibre(m5));
  151.     printf("\n______________________________\nEncombrement");
  152.     printf("\nCercle de rayon : %d", encombrement(m1));
  153.     printf("\nCercle de rayon : %d", encombrement(m3));
  154.     printf("\nCercle de rayon : %d", encombrement(m4));
  155.     printf("\nCercle de rayon : %d", encombrement(m5));
  156.     printf("\n______________________________\nBarre assez large");
  157.     printf("\nAssez large : %d", barre_assez_large(m1));
  158.     printf("\nAssez large : %d", barre_assez_large(m1->fils_droit));
  159.     printf("\nAssez large : %d", barre_assez_large(m3));
  160.     printf("\nAssez large : %d", barre_assez_large(m4));
  161.     printf("\nAssez large : %d", barre_assez_large(m5));
  162.     printf("\n______________________________\nMobile Libre");
  163.     printf("\nLibre : %d", mobile_libre(m1));
  164.     printf("\nLibre : %d", mobile_libre(m1->fils_droit));
  165.     printf("\nLibre : %d", mobile_libre(m3));
  166.     printf("\nLibre : %d", mobile_libre(m4));
  167.     printf("\nLibre : %d", mobile_libre(m5));
  168.     _getch();
  169. }
RAW Paste Data
Top