Se connecter / S'enregistrer
Votre question

Travail sur les systèmes de Lindenmayer ou L-systèmes C++

Tags :
  • C++
  • Programmation
Dernière réponse : dans Programmation
27 Décembre 2011 13:22:40

Bonjour et Bonnes Fêtes à tous!

J'ai un travail de programmation à réaliser en C sur les systèmes de Lindenmayer ou L-systèmes et j'ai bien du mal à débuter! Étant aussi débutant en programmation...

Voici une petite explication du sujet:



J'ai un soucis avec la fonction (nouveau_symbole) décrite ci-après:



En effet, je ne sais pas faire une fonction qui change de valeur de sortie quand on l’exécute... Si vous pouviez me mettre sur la piste, je vous en remercierais fortement!

Bonne après-midi!

Guillaume.

Autres pages sur : travail systemes lindenmayer systemes

a c 232 L Programmation
27 Décembre 2011 14:33:28

Salut,

Si j'ai bien compris, tu devrais avoir une liste de tous les symboles possibles.
Il te faut faire une boucle sur les symboles, regarder si le symbole est déjà utilisé, et s'il n'est pas utilisé, le retourner.
27 Décembre 2011 15:23:03

Bonjour et merci pour ta réponse!

OmaR a dit :
tu devrais avoir une liste de tous les symboles possibles.


Je dois créer cette liste? Sachant que le type "symbole" représente les symboles de l’alphabet V et que dans l'exemple, on prend a et b, il faudrait que je crée une liste avec les lettres de l'alphabet?

OmaR a dit :
Il te faut faire une boucle sur les symboles, regarder si le symbole est déjà utilisé, et s'il n'est pas utilisé, le retourner.


Je suis d'accord sur ce point. Je l'avais compris. :) 

Contenus similaires
a c 232 L Programmation
27 Décembre 2011 17:05:37

J'aurais tendance en effet à dire que oui tu dois créer ton alphabet au départ.

Pour moi, tu dois avoir toutes les propriétés de ton L-système au départ.
28 Décembre 2011 16:26:07

Bonjour!

OmaR a dit :
J'aurais tendance en effet à dire que oui tu dois créer ton alphabet au départ.
Pour moi, tu dois avoir toutes les propriétés de ton L-système au départ.

Il y a en fait 4 types à définir:

Citation :
Le listing suivant indique les types à définir et les fonctions à réaliser.
  1. struct symbole;
  2. struct mot;
  3. struct regle;
  4. struct lsysteme;

Sachant que:

Citation :
Le type symbole représente les symboles de l’alphabet V . Le type mot représente une séquence (potentiellement vide) de symboles. Le type regle associe un mot à un symbole. Le type lsysteme représente un système complet, incluant un axiome et un ensemble de règles.

Avec beaucou d'aide, j'ai écrit la définition de la fonction nouveau_symbole:

  1. symbole* nouveau_symbole(void)
  2. {
  3. static symbole symbole_courant = 'a'; // Initialisation du symbole
  4. symbole* nouveau = malloc(sizeof(symbole)); // On crée le symbole (réservation de l'espace mémoire)
  5. *nouveau = symbole_courant++; // On affecte le symbole
  6. return nouveau; // Incrémentation du symbole puis retour
  7. }


Cette fonction créée les symboles en partant de 'a' et chaque exécution donne la lettre suivante.
Seulement, maintenant, j'ai un doute dans ma définition du type "struct symbole":

  1. typedef struct symbole { char sym; };


Il faut que mon "sym" corresponde avec l'élément que renvoie ma fonction nouveau_symbole donc "nouveau" dans la définition, non?

Merci de votre aide!



a c 232 L Programmation
29 Décembre 2011 12:06:24

La classe nouveau_symbole me parait bizarre.
Parce que si je comprends bien le L-système, au départ, tu as juste un symbole (ou un axiome plus précisément), et c'est en effectuant les transformations de P que tu obtiens de nouveaux symboles.
Dans ton exemple, on 2 règles de réécritures de P: a est transformé en ab et b est transformé en a.

Au départ, tu as juste ton axiome "a"
En effectuant les règles de P, le "a" est transformé en "ab" en étape 2
en étape 3, le "a" est transformé en "ab" et le "b" en "a", ce qui te donne "aba"
en étape 4, le 1er "a" de "aba" est transformé en "ab", le "b" est transformé en "a" et le 2ème "a" en "ab", ce qui te donne "abaab"
etc...

Donc je vois pas pourquoi tu aurais besoin d'un nouveau symbole en fait...
29 Décembre 2011 17:47:37

OmaR a dit :
La classe nouveau_symbole me parait bizarre.
Parce que si je comprends bien le L-système, au départ, tu as juste un symbole (ou un axiome plus précisément), et c'est en effectuant les transformations de P que tu obtiens de nouveaux symboles.
Dans ton exemple, on 2 règles de réécritures de P: a est transformé en ab et b est transformé en a.

Au départ, tu as juste ton axiome "a"
En effectuant les règles de P, le "a" est transformé en "ab" en étape 2
en étape 3, le "a" est transformé en "ab" et le "b" en "a", ce qui te donne "aba"
en étape 4, le 1er "a" de "aba" est transformé en "ab", le "b" est transformé en "a" et le 2ème "a" en "ab", ce qui te donne "abaab"
etc...

Donc je vois pas pourquoi tu aurais besoin d'un nouveau symbole en fait...


Bonjour,

Merci pour tes réponses! :) 

Dans mon énoncé, je dois créer cette fonction... Dans l'exemple, il y a seulement 2 symboles mais on peut avoir besoin de plus de symboles d'où la fonction...

a c 232 L Programmation
30 Décembre 2011 00:11:59

Oui je sais que tu dois créer cette fonction, mais je vois pas trop pourquoi alors, m'enfin, si tu comprends =)
a b L Programmation
30 Décembre 2011 12:11:01

Pour l'implémentation, tu peux faire 2 fonctions:
- une fonction qui calcule la taille du buffer dont tu as besoin (le buffer étant le tableau dynamique de symboles du mot à générer) à partir d'un mot (contenant le tableau dynamique de symboles).
- une fonction qui remplit ce buffer en appliquant l'algo
C'est un classique : on prévoit la taille de l'ensemble des données, puis on les remplit.

Et je rejoins OmaR, ta fonction nouveau_symbole ne sert à rien. A la limite pour faire de l'orienté objet, dans un constructeur, pourquoi pas, mais là en C, tu compliques trop pour faire quelque chose de simple. Et je ne parle même pas de l'utilisation d'une variable statique. :) 
Si tu veux faire ta séquence dans un tableau dynamique (c'est le plus simple), il ne te faut pas allouer les symboles un par un, mais allouer tout le tableau d'un coup (d'où ma proposition des 2 fonctions).
a b L Programmation
30 Décembre 2011 12:24:06

Bon, je viens de lire l'énoncé. :D 

C'est fait par quelqu'un qui sait programmer en orienté objet, mais pas trop en C. :) 
L'auteur de l'énoncé a dans l'idée de faire une liste chainée et pas un tableau dynamique, ce qui est absurde et ne permet pas de faire comprendre l'intérêt réel de la liste chainée.
Du coup, oublie les 2 fonctions, et fait de l'insertion en liste chainée (tout se fait en une seule passe).

Je vois que la fonction nouveau_symbole() ne prend pas de paramètre et oblige donc l'utilisation de variables globales. Tu dois réinitialiser ton symbole à chaque nouveau remplacement de symbole dans le mot, ce qui rend le code encore plus foireux... Bref, tu ne peux pas utiliser de variable statique car tu ne peux pas la réinitialiser à 'a'.

L'auteur devrait revoir sa conception...
30 Décembre 2011 12:27:53

OmaR a dit :
Oui je sais que tu dois créer cette fonction, mais je vois pas trop pourquoi alors, m'enfin, si tu comprends =)


CRicky a dit :
Pour l'implémentation, tu peux faire 2 fonctions:
- une fonction qui calcule la taille du buffer dont tu as besoin (le buffer étant le tableau dynamique de symboles du mot à générer) à partir d'un mot (contenant le tableau dynamique de symboles).
- une fonction qui remplit ce buffer en appliquant l'algo
C'est un classique : on prévoit la taille de l'ensemble des données, puis on les remplit.

Et je rejoins OmaR, ta fonction nouveau_symbole ne sert à rien. A la limite pour faire de l'orienté objet, dans un constructeur, pourquoi pas, mais là en C, tu compliques trop pour faire quelque chose de simple. Et je ne parle même pas de l'utilisation d'une variable statique. :) 
Si tu veux faire ta séquence dans un tableau dynamique (c'est le plus simple), il ne te faut pas allouer les symboles un par un, mais allouer tout le tableau d'un coup (d'où ma proposition des 2 fonctions).


Bonjour, merci pour vos réponses!

Le problème, c'est que je n'ai pas le choix... L'énoncé demande que cette fonction, nouveau_symbole, soit créée... En plus, ma travail sera corrigé par un test qui alloue les points en fonction de ce que j'ai fait et donc il faut que je suive scrupuleusement l'énoncé...

30 Décembre 2011 12:31:29

CRicky a dit :
Bon, je viens de lire l'énoncé. :D 

C'est fait par quelqu'un qui sait programmer en orienté objet, mais pas trop en C. :) 
L'auteur de l'énoncé a dans l'idée de faire une liste chainée et pas un tableau dynamique, ce qui est absurde et ne permet pas de faire comprendre l'intérêt réel de la liste chainée.
Du coup, oublie les 2 fonctions, et fait de l'insertion en liste chainée (tout se fait en une seule passe).

Je vois que la fonction nouveau_symbole() ne prend pas de paramètre et oblige donc l'utilisation de variables globales. Tu dois réinitialiser ton symbole à chaque nouveau remplacement de symbole dans le mot, ce qui rend le code encore plus foireux... Bref, tu ne peux pas utiliser de variable statique car tu ne peux pas la réinitialiser à 'a'.

L'auteur devrait revoir sa conception...


Salut!

Je viens de voir ta réponse au moment où je finissais la mienne...
Pour être foireux c'est foireux... Donc je rame! ^^ :D 
30 Décembre 2011 14:28:33

Bon... Pour vous la meilleure solution serait de faire une liste chainée, c'est ça? Je viens d'aller voir ce que c'est, j'ai plus ou moins bien compris, du moins j'ai compris le principe.

Ma déclaration de la structure "symbole" change du coup:
  1. typedef struct symbole symbole;
  2. struct symbole
  3. {
  4. char sym;
  5. struct symbole *nouveau;
  6. };
  7. typedef symbole* llist;


En fait, je crée le type symbole qui est une structure contenant un charactère (sym) et
un pointeur sur symbole (nouveau), qui contiendra l'adresse de l'élément suivant.
Ensuite, je crée le type llist qui est un pointeur sur le type structure. Ou pas besoin?
Correct ou pas? :D 

Merci!
a b L Programmation
30 Décembre 2011 17:20:20

La liste chainée n'est pas la meilleure solution, mais c'est ce que l'auteur de l'exercice semble vouloir définir. :D 

Les types, tu peux les créer ou pas, c'est juste une facilité d'écriture pour toi. Du coup, dans le nom que tu donnes, identifie bien le type. C'est juste un conseil pour s'y retrouver plus tard.
Par exemple pour des nouveaux type ajout un t devant, pour les pointeurs, un p ou ptr, etc. Bref, comme tu veux, mais juste pour bien identifier ce que c'est sans avoir à regarder le code de la déclaration.
par exemple:

typedef struct _symbole
{
char sym;
struct _symbole* pSuivant;
} tSymbole;

typedef tSymbole* tPtrSymbole;

tSymbole symEntete = { 0, NULL };


Après, il te faut faire les fonctions d'insertions, suppression, affichage de liste, etc.
3 Janvier 2012 17:26:20

Je dois programmer en C++ en fait, d'où le fait que je rame un peu plus...
a b L Programmation
3 Janvier 2012 20:39:49

Ah là je comprend mieux si c'est de l'orienté objet, même si la méthode est un peu lourde.

Commence par faire un diagramme UML.
3 Janvier 2012 20:43:57

Bonsoir! :) 

Un diagramme UML? :ouch: 

En tout cas, j'ai réussi à faire toutes les fonctions demandées. Je me heurte à un nouveau problème, on a: "Le type mot représente une séquence (potentiellement vide) de symboles." Et il faut définir "la fonction mot_vide(void) crée un nouveau mot vide, qui ne contient aucun symbole."
J'ai écrit:
  1. struct mot{ symbole* mo; };

mais la fonction mot_vide me pose problème...
  1. mot* mot_vide(void)
  2. {
  3.  
  4. mot* movid = new(mot);
  5. // Qu'écrire pour que le "mot soit vide"? Et donc que le tableau soit vide...
  6. return movid;
  7.  
  8. }


Merci!
a b L Programmation
3 Janvier 2012 20:55:22

Un diagramme UML permet de représenter les classes graphiquement (diagramme de classes).

Quelle est ta définition de ta classe/structure mot?
3 Janvier 2012 20:58:06

CRicky a dit :
Un diagramme UML permet de représenter les classes graphiquement (diagramme de classes).

Quelle est ta définition de ta classe/structure mot?


J'ai complété mon message précédent que j'avais envoyé par mégarde...

a b L Programmation
3 Janvier 2012 23:33:49

Si tu utilises une liste chainée, il te suffit de faire movid.mo = NULL;
Et pour connaitre la fin d'une liste, il te suffit de voir, pour un élément, si le mo est égal à NULL. Et si tu as NULL dès le premier élément, c'est que la liste est vide.
4 Janvier 2012 06:09:01

CRicky a dit :
Si tu utilises une liste chainée, il te suffit de faire movid.mo = NULL;
Et pour connaitre la fin d'une liste, il te suffit de voir, pour un élément, si le mo est égal à NULL. Et si tu as NULL dès le premier élément, c'est que la liste est vide.


Il est possible de ne pas utiliser une liste chaînée mais un tableau de symbole comme je l'ai fait? Il me suffirait de renvoyer un tableau vide... C'est possible?

Merci.

4 Janvier 2012 20:18:22

J'y suis arrivé! :) 

Merci.
4 Janvier 2012 23:31:19

Bonsoir!

Merci d'avoir déplacer mon sujet.

Je m'en sors mieux en C++ et j'ai bien avancé.

Voici la partie suivante où je bloque:





La création de la fonction mot* mot_vide(void) ne m'a pas posé problème, en effet j'ai déclaré la structure mot de la manière suivante:

  1. struct mot{const symbole* symboles[ ];};


et ai écrit:

  1. mot* mot_vide(void)
  2. {
  3. mot* movid = new(mot);
  4. movid->symboles[0] = 0L ;
  5. return movid;
  6. }


le problème réside dans les fonctions suivantes:

  1. mot* singleton(symbole const* a)
  2. {
  3. mot* sing = new(mot);
  4.  
  5. /* sing->symbole[??] = ??? ; je ne parviens pas à écrire correctement le fait que la fonction renvoie un singleton... j'ai écrit: sing->mo = a; mais ce n'est pas correcte de 'const symbole*' à juste 'symbole*'... */
  6.  
  7. return sing;
  8. }


Merci!
a b L Programmation
5 Janvier 2012 20:26:31

Si je comprends bien, tu fais un tableau, et pour reconnaitre la fin du tableau, tu mets un symbole NULL (comme pour les chaines de caractère).
Tu as déjà créé ta fonction qui instancie un nouveau symbole et retourne un pointeur sur ce symbole.
sing.symbole est un tableau de pointeurs sur des symboles (chaque élément du tableau n'est qu'une adresse sur un symbole qui a été créé).
Donc, ok tu as tout.

Maintenant, lorsque tu utilises l'opérateur ->, il y a la lecture d'un pointeur car sing->symbole est équivalent à *(sing.symbole).
De même lorsque tu fais variable[0], il y a aussi la lecture d'un pointeur, car c'est équivalent à *(variable + 0) : l'adresse du tableau (qui n'est qu'un pointeur sur le premier élément) que tu décales avec l'indice, et tu prends le contenu.
Quand tu écris ceci : movid->symboles[0]
l'opérateur -> étant exécuté avant l'opérateur [], c'est équivalent à (movid->symboles)[0], donc (*(movid.symboles))[0] et donc *( (*(movid.symboles)) + 0 )

movid.symboles est l'adresse du premier élément de ton tableau (puisque c'est un tableau).
*(movid.symboles) est donc le contenu du premier élément (puisque tu ne fais pas de décalage) du tableau. Cet élément est une adresse (puisque c'est un pointeur sur un symbole)
*( (*(movid.symboles)) + 0 ) est donc, par chance (car tu as mis un décalage de 0, donc pas de décalage) le symbole.

Si tu avais mis un décalage de + 1, alors tu aurais ajouté +1 à l'adresse de symbole que tu récupères dans le premier élément du tableau. Or le symbole est quelque part tout seul en mémoire, donc tu vas pointer vers de la mémoire non allouée, c'est du buffer overflow qui ne génère pas forcément d'erreur.

Bref tout ça pour dire que tu as inversé les notions de tableau et de pointeur : il faut d'abord récupérer l'élément, ensuite prendre le contenu de la mémoire à l'adresse indiquée par l'élément du tableau.

Pour comprendre ce que j'explique, le mieux est de faire un dessin:
- un gros carré représentant la structure mot
- ce gros carré contient un petit carré représentant un pointeur (puisqu'un tableau n'est qu'un pointeur). Ce carré est mot.symbole
- de ce petit carré, tu fais une flèche vers N petits carrés (ailleurs en mémoire) qui se suivent, et ce sont les éléments du tableau (mot.symbole[0], mot.symbole[1], ...), équivalent à ( *(mot.symbole), *(mot.symbole + 1), ...)
- chacune de ces case est un pointeur de type symbole*, donc tu y dessines des flèches sortantes du tableau pour chaque élément du tableau. Chacune de ces flèches pointent vers des gros carrés disposés n'importe où et isolés les uns des autres.
- le dernier élément de ton tableau étant NULL donc c'est une adresse égale à 0 (pas de flèche, ou alors une flèche qui va dans le coin supérieur gauche de la feuille :)  )

Voilà, je me suis trop fatigué à faire ce post alors je te laisse te corriger. :D 
Et commence par corriger movid->symboles[0] qui est faux mais correct pour le cas 0.

Si tu n'as pas bien compris quelque chose, demande.
Tom's guide dans le monde
  • Allemagne
  • Italie
  • Irlande
  • Royaume Uni
  • Etats Unis
Suivre Tom's Guide
Inscrivez-vous à la Newsletter
  • ajouter à twitter
  • ajouter à facebook
  • ajouter un flux RSS