Publicité
+ Répondre à la discussion
Page 1 sur 3 123 DernièreDernière
Affichage des résultats 1 à 20 sur 41
  1. #1
    Invité régulier
    Homme Profil pro Rachid Ihadadene
    Étudiant
    Inscrit en
    décembre 2012
    Messages
    33
    Détails du profil
    Informations personnelles :
    Nom : Homme Rachid Ihadadene
    Localisation : France, Seine Saint Denis (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Matériel informatique

    Informations forums :
    Inscription : décembre 2012
    Messages : 33
    Points : 7
    Points
    7

    Par défaut Récusivité terminale ?

    Bonjour ,je suis un étudiant en informatique , et j'ai un projet en Lisp que je dois rendre dés la rentré prochaine.

    mon projet consiste a écrire un programme qui prend en argument une liste correspondant à une fonction et renvoie #t s'il s'agit d'une récursivité terminale et #f sinon.
    Attention.

    j'ai commencé à écrire des fonction récursivité et récursivité terminale (ou récursivité totale ) et j'ai pris ces fonction comme si c'était une liste , ensuite j'ai défini chaque parti de la liste c'est à dire : nom de la fonction , paramètre de la fonction et le corps de la fonction . A partir de sa j'ai sélectionner les différence qu'il y a entre les deux formes de récursivité :

    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    (define (corp df); vu en cours
      (if (unpair df)'()
          (caddr df)))
    
    (define (unpair l)
      (if (pair? l)#f #t))
    
    (define (nom df); vu en cour
      (if (unpair df)'()
          (caadr df)))
    
    (define (par df); vu en cour
      (if (unpair df)'()
          (cdadr df)))
    ; sauf que comme les fonction fonction sans toute differentes je n'arrive pas a ecrire un programme adapté a toute les fonction récursivé :
    
    (define (fonction df); elle renvoie le nom de la fonction dans la fonction elle même . exemple la fonction somraux " (somraux (- n 1) (+ n acc))" elle renvoie :> somraux
      
      (if (unpair df)'()
          (car(car(cdr(cdr( cdr(car (cdr( cdr df))))))))))
    
    
    
    
    (define (rterminale df); renvoie #t si c'est terminale et si non #f.
      (if (equal? (fonction df)(nom df))
          #t
          #f))
    
    ;( ce programme ne marche que sur certain fonction simple avec un seul IF) 
    ; j'ai fai une fonction qui vérifié si la fonction appel une fonction chapeau :
    (define (chap df); nom de la fonction chapeau
      (if (unpair df)'()
          (caar(cddar df ))))
    
    
    (define (fchap df); fonction chapeau
      (if (unpair df)'()
          (car(cadadr df ))))
    
    (define (rterm df)
      (if (equal? (chap df)(fchap df))
          #t
          #f))
    mais quand je teste avec une fonction recursive normal , elle renvoie error pck elle retrouve pas l'élèment choisi du coup j'essaye de supprimé cette erreur en lui disnat de renvoyé liste vide s'il trouve pas l'élement mais j'ai pas pu .


    si quelqu'un peu m'aider sur ce programme , Merci à l'avance[/SIZE][/SIZE][/SIZE]

  2. #2
    Membre Expert
    Inscrit en
    avril 2008
    Messages
    1 033
    Détails du profil
    Informations forums :
    Inscription : avril 2008
    Messages : 1 033
    Points : 2 464
    Points
    2 464

    Par défaut

    Bonjour.

    Citation Envoyé par kbprince Voir le message
    Code :
    1
    2
    3
    (define (corp df); vu en cours
      (if (unpair df)'()
          (caddr df)))
    Vous n'avez pas vu le 'not' ???

    Code :
    1
    2
    3
    (define (corps df); pas encore vu en cours ???
      (if (not (pair? df)) '()
          (caddr df)))
    Ce n'est peut-être pas la peine de définir une fonction 'unpair' juste pour inverser le sens de 'pair?' !!!

    Code :
    1
    2
    3
    4
    5
    6
    ; sauf que comme les fonction fonction sans toute differentes je n'arrive pas a ecrire un programme adapté a toute les fonction récursivé :
    
    (define (fonction df); elle renvoie le nom de la fonction dans la fonction elle même . exemple la fonction somraux " (somraux (- n 1) (+ n acc))" elle renvoie :> somraux
      
      (if (unpair df)'()
          (car(car(cdr(cdr( cdr(car (cdr( cdr df))))))))))
    Comment peux-tu espérer que cette fonction marche pour toutes les fonctions???
    Elle est beaucoup trop câblée sur la définition de 'somraux'!
    Comme tu le dis plus loin, ça ne marchera que sur certaines fonctions qui auront la même forme que 'somraux'!

    Je ne suis pas sûr que ton algorithme soit le bon:
    1) rechercher LA fonction dans le corps
    2) vérifier si cette fonction est la fonction

    Il me semble qu'il vaudrait mieux explorer (parser) le corps de la fonction et chercher s'il contient (en position fonctionnelle) une ou plusieurs occurrences de la fonction.

    En gros, écrire une fonction auxiliaire:
    Code :
    (define (nb-occurrences fct corps) ...)
    qui retourne le nombre d'occurrences de 'fct' dans la liste 'corps'.

    Il est clair que cette recherche est elle-même récursive!

  3. #3
    Invité régulier
    Homme Profil pro Rachid Ihadadene
    Étudiant
    Inscrit en
    décembre 2012
    Messages
    33
    Détails du profil
    Informations personnelles :
    Nom : Homme Rachid Ihadadene
    Localisation : France, Seine Saint Denis (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Matériel informatique

    Informations forums :
    Inscription : décembre 2012
    Messages : 33
    Points : 7
    Points
    7

    Par défaut occurence de quoi ?

    Bonjour
    Merci pour votre réponse.
    j
    J'ai essayer de refaire mon programme avec d'autres manières :

    La 1er c'est de cherche si la fonction contient une fonction chapeau , et elle marche pour toutes les fonction en récusivité terminale mais pas sur toute les fonctions en récusivité normal.

    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    (define (chap df); nom de la fonction chapeau
      (if (unpair df)'()
          (caar(cddar df )
               )))
    
    (define (fchap df); fonction chapeau 
      (if (unpair df)'()
          
          (car(cadadr  df )
           )))
    
     (fchap '((define (somrt n); somme de n jusqu'a n en Récursivité terminale 
      (somraux n 0))
    (define (somraux n acc); Fonction Chapeau
      (if (= n 0)
          acc
          (somraux (- n 1)(+ n acc))))))
    somraux
    > (chap '((define (somrt n); somme de n jusqu'a n en Récursivité terminale 
      (somraux n 0))
    (define (somraux n acc); Fonction Chapeau
      (if (= n 0)
          acc
          (somraux (- n 1)(+ n acc))))))
    somraux
    >
    j'ai testé plein de fonction en terminale sa marche mais quand il s'agit de la récusité normal sa renvoi un eerruer parceque l'endroit recehrché n'existe pas dans c'est certain fonction, le programme ne peut pas continué la vérification, j'ai essayé de faire quelque comme "si le nom de la fonction chapeau n'existe pas dans la liste renvoyé une liste vie " mais sa ne marche pas .



    du coup je me suis retourné sur une autre hypothese : l'accumulateur : on sait que dans une fonction en récusivité terminale l'accumulateur est repté au moin trois fois : dans les parametres , la boucle et la fonction vu que le résultat se renvoi toujour dans l'accumulateur .
    j'ai fai la fusionner la focntion aplatir2 avec compter le nombre de fois ou le mot accumulateur est repété dans la fonction, donc si il repeté plus de 2 fois ( 3 et plus ) #t (terminale ) si non #f . , je sais pas commen dire au programme ( if (< cla 3) #t #f) mais sa ne marche pas aussi .
    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    (define (aplatir2 e)
      (define (aplatir-interne e r)
        (if (pair? e)
            (aplatir-interne (car e) (aplatir-interne (cdr e) r))
            (if (null? e) r (cons e r)) ) )
      (aplatir-interne e '()) )
    
    
    define (compter mot phrase)
      (if (pair? phrase)
          (+ (if (equal? mot (car phrase)) 1 0) ; Notez l'alternative sous l'addition!
             (compter mot (cdr phrase)) )
          0 ) )
    
    
    (define ( cla mot df)
      (if (unpair df)0
          (compter mot (aplatir2 df))))
    Merci !

  4. #4
    Membre Expert
    Inscrit en
    avril 2008
    Messages
    1 033
    Détails du profil
    Informations forums :
    Inscription : avril 2008
    Messages : 1 033
    Points : 2 464
    Points
    2 464

    Par défaut



    Afin de faciliter la lecture de ton message, peux-tu l'éditer en ajoutant la balise CODE (le '#' dans la barre d'outils) et en corrigeant les erreurs de frappe?

  5. #5
    Invité régulier
    Homme Profil pro Rachid Ihadadene
    Étudiant
    Inscrit en
    décembre 2012
    Messages
    33
    Détails du profil
    Informations personnelles :
    Nom : Homme Rachid Ihadadene
    Localisation : France, Seine Saint Denis (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Matériel informatique

    Informations forums :
    Inscription : décembre 2012
    Messages : 33
    Points : 7
    Points
    7

    Par défaut bonjour

    Bonjour
    Quand je teste si la fonction possede une fonction chapeau sa donne sa pour les fonction non terminale :
    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    (rterm '(define (pcr n); Fibonacci " vu en cours "
        (if (< n 2)
            1
            (+ (pcr (- n 1))
               (pcr (- n 2))))))
    . . cddar: expects argument of type <cddarable value>; given (define (pcr n) (if (< n 2) 1 (+ (pcr (- n 1)) (pcr (- n 2)))))
    
    >  (rterm '(define (add a b) ; addition
      (if (= a 0)
          b
          (add (- a 1)(+ b 1)))))
    . . cddar: expects argument of type <cddarable value>; given (define (add a b) (if (= a 0) b (add (- a 1) (+ b 1))))
    mais quand il s'agit d'une fonction en recusivité terminale il répond directement #t .
    #t (vrais)
    #f (faux).

  6. #6
    Invité régulier
    Homme Profil pro Rachid Ihadadene
    Étudiant
    Inscrit en
    décembre 2012
    Messages
    33
    Détails du profil
    Informations personnelles :
    Nom : Homme Rachid Ihadadene
    Localisation : France, Seine Saint Denis (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Matériel informatique

    Informations forums :
    Inscription : décembre 2012
    Messages : 33
    Points : 7
    Points
    7

    Par défaut Re

    Re Bonjour.

    Comme je l'ai précisez dans mes messages précédents, j'ai fait une fonction qui aplatir une liste ( enleve les parenthèses) et une autre qui compte le nombre occurrence d'un mot dans une liste.

    j'ai fusionner ces deux fonction pour faire un fonction qui aplatit la liste puis calcule le nombre occurrence d'un mot.
    En ce qui me concerne je cherche a savoir combien il y'a le mot acc (accumulateur dans la fonction) , qui est un paramètre indispensable dans une fonction en récusivité terminale.

    Si ce paramêtre est cité 3 fois ou plus dans la fonction dans c'est de la récusivité terminale si non faux, j'ai fais sa en fonction aparament sa marche sur toute type de fonction puisque les fonction sont aplati elle deviennent des liste simple (un probleme ou pas ? )


    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    (terminacc 'acc '((define (multrt a b)
      (multraux a b 0))
    (define (multraux a b acc)
      (if ( = a 0)
          acc
          (multraux (- a 1)b (+ b acc))))))
    #t
    >
    
    > (terminacc 'acc '(define (rac2 n r) ; racine carré
     (if (> (carre r) n)
         (- r 1)        
         (rac2 n ( + r 1))))
    )
    #f
    
    > (terminacc 'acc '(define (mult a b); multiplication avec des ( + et -)
      (if (= a 0)
          0
          (+ b (mult (- a 1) b)))))
    #f
    
    >(terminacc 'acc '((define (prt p n); puissance p du nombre n
      (praux p n 1))
      
      (define (praux p n acc)
      (if (= p 0)
          acc
          (praux (- p 1) n (* n acc))))))
    #t
    Merci !

  7. #7
    Membre Expert
    Inscrit en
    avril 2008
    Messages
    1 033
    Détails du profil
    Informations forums :
    Inscription : avril 2008
    Messages : 1 033
    Points : 2 464
    Points
    2 464

    Par défaut

    C'est pas gagné!

    Pour améliorer la lisibilité des messages, pourrais-tu:
    - utiliser la balise CODE en cliquant sur le '#' dans la barre d'outils du message
    - mettre un point ou un return à la fin de chaque phrase

    Ce n'est pas de ta faute si le français n'est pas ta langue maternelle, mais il m'est difficile de comprendre une phrase comme:

    Si ce paramêtre est cité 3 fois ou plus dans la fonction dans c'est de la récusivité terminale si non faux, j'ai fais sa en fonction aparament sa marche sur toute type de fonction puisque les fonction sont aplati elle deviennent des liste simple (un probleme ou pas ? )

    Citation Envoyé par kbprince Voir le message
    Re Bonjour.

    Comme je l'ai précisez dans mes messages précédents, j'ai fait une fonction qui aplatir une liste ( enleve les parenthèses) et une autre qui compte le nombre occurrence d'un mot dans une liste.

    j'ai fusionner ces deux fonction pour faire un fonction qui aplatit la liste puis calcule le nombre occurrence d'un mot.
    J'imagine que ton prof aurait préféré que tu comptes en parcourant récursivement l'arbre, sans créer explicitement la liste aplatie, mais c'est mieux que rien!

    En ce qui me concerne je cherche a savoir combien il y'a le mot acc (accumulateur dans la fonction) , qui est un paramètre indispensable dans une fonction en récusivité terminale.
    Si ce paramêtre est cité 3 fois ou plus dans la fonction dans c'est de la récusivité terminale si non faux, j'ai fais sa en fonction aparament sa marche sur toute type de fonction puisque les fonction sont aplati elle deviennent des liste simple (un probleme ou pas ? )
    C'est beaucoup trop réducteur!

    Que se passe-t-il si quelqu'un écrit une fonction avec le mot 'accu' ou 'ac' plutôt que 'acc', ou écrit une fonction sans variable d'accumulation ou avec plusieurs variables d'accumulation?

    Peux-tu donner une définition précise de ce que tu (ou ton prof) appelles récursivité terminale et récursivité non terminale?
    EDIT: J'ai consulté Wikipedia (pour me rafraîchir la mémoire):
    Une fonction à récursivité terminale est une fonction où l'appel récursif est la dernière instruction à être évaluée.

    Pour moi, la fonction 'rac2' est bien récursive terminale:
    Code :
    1
    2
    3
    4
    (define (rac2 n r) ; racine carré
     (if (> (carre r) n)
         (- r 1)        
         (rac2 n ( + r 1))))
    Un bon compilateur peut la remplacer par une boucle qui ne consomme pas de ressource.

    La fonction 'mult' n'est pas récursive terminale, car elle empile un paquet de 'b' et de '+':
    Code :
    1
    2
    3
    4
    (define (mult a b); multiplication avec des ( + et -)
      (if (= a 0)
        0
        (+ b (mult (- a 1) b))))
    La fonction 'aplatir2' est clairement récursive non terminale:
    Code :
    1
    2
    3
    4
    5
    6
    (define (aplatir2 e)
      (define (aplatir-interne e r)
        (if (pair? e)
          (aplatir-interne (car e) (aplatir-interne (cdr e) r))
          (if (null? e) r (cons e r)) ) )
      (aplatir-interne e '()) )
    car elle possède une fonction 'aplatir-interne' qui s'appelle 2 fois (parcours d'arbre binaire).
    Il faut, à chaque appel, empiler tout un contexte à restaurer au retour de la fonction.

  8. #8
    Membre Expert
    Inscrit en
    avril 2008
    Messages
    1 033
    Détails du profil
    Informations forums :
    Inscription : avril 2008
    Messages : 1 033
    Points : 2 464
    Points
    2 464

    Par défaut

    Citation Envoyé par jack-ft Voir le message
    C'est pas gagné!
    Je confirme! Ce n'est pas un problème facile qu'il vous a donné!

    Petite précision: il me semble que 'define' est spécifique de scheme et non de lisp.
    Je n'ai jamais fait de scheme. En particulier, je ne connais pas bien les syntaxes spécifiques.
    Par exemple, il semble que la syntaxe de la fonction 'if' n'autorise pas un 'progn' implicite (ou un 'begin', semble-t-il, en scheme?), contrairement aux autres lisps.

    En repartant d'une définition précise de la récursivité terminale, comme celle de wikipedia, voilà ce que je ferais:

    WP: Une fonction à récursivité terminale est une fonction où l'appel récursif est la dernière instruction à être évaluée.

    Je commencerais par traiter le cas d'une fonction sans sous-fonction, ce qui n'est déjà pas si simple!

    1) (pour s'entraîner) déterminer si une fonction 'fct' (sans sous-fonction) est récursive:
    parcourir récursivement le corps de 'fct' à la recherche d'un appel à 'fct'
    (sans aplatir le corps de la fonction)

    2) déterminer si une fonction 'fct' (sans sous-fonction) est récursive terminale
    parcourir récursivement le corps de 'fct'
    en vérifiant si les appels à 'fct' sont à l'intérieur d'une fonction normale (comme 'cons' '+' etc.) ou d'une fonction ignorable (comme 'if' ou 'cond')
    et faisant attention au cas particulier du 'begin' (explicite ou implicite).

    Pour préciser ce dernier point:
    si un appel à 'fct' est la dernière instruction d'un 'begin' (explicite ou implicite), il ne remet pas en cause la récursivité terminale.
    si un appel à 'fct' est avant la dernière instruction d'un 'begin' (explicite ou implicite), la fonction n'est pas récursive terminale.
    si un appel à 'fct' est imbriqué dans une fonction normale, la fonction n'est pas récursive terminale.

    Rq: le parser (la fonction qui explore récursivement le corps de 'fct') doit être assez intelligent pour reconnaître le type et la structure de chaque noeud de l'arbre: il doit plonger avec un indicateur spécifique dépendant de la fonction (normale (comme '+') ou structure de contrôle (comme 'if')).
    Pour la fonction 'cond', il doit traiter différemment chaque tête de clause (condition) du reste de la clause ('begin' implicite).
    etc.

    3) déterminer si une fonction 'fct' (avec sous-fonctions) est récursive terminale
    déterminer si chacune des sous-fonctions est récursive terminale (cf. 2)
    vérifier la récursivité croisée (fct1 appelle fct2 qui appelle fct1)

    Voilà quelques pistes à développer!

    Y a du boulot!

    Bon courage!

  9. #9
    Invité régulier
    Homme Profil pro Rachid Ihadadene
    Étudiant
    Inscrit en
    décembre 2012
    Messages
    33
    Détails du profil
    Informations personnelles :
    Nom : Homme Rachid Ihadadene
    Localisation : France, Seine Saint Denis (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Matériel informatique

    Informations forums :
    Inscription : décembre 2012
    Messages : 33
    Points : 7
    Points
    7

    Par défaut difficle !

    Bonjour
    D'après ce que je viens de lire il y'a boucaup de travail sur sa sur tout qu'il me reste pas boucaup de temps pour développer tous sa mais je ne baisserai pas les bras ce projet ces 40% de ma note finale pour le module ( programmation fonctionnelle) .

    Pour la fonction que j'ai faites (define (compter mot phrase)) qui compte le nombre d'occurrence ne fonction que sur des liste vraiment simple qui ne contiennent aucune parenthèse c'est pour sa que j'ai rajouter la fonction (define (aplatir2 e)).

    il y a plein d'expression que je ne comprend pas dans votre vocabulaire, comme le ( begin )et le (implicite et explicite), pour le cond , j'aime pas l'utiliser parce que je sais pas comment classer les événements du traiment de la fonction, car d'aprés le mon prof , le cond remplace plusieur (if).

    Apparemment, je me retrouve au point de départ du projet , et le travail qui me reste à faire n'est pas du gâteau.
    c'est ce que j'essaye de reprendre depuis le début, ce programme contient beaucoup pièges, les fonction récursive sont toutes différentes.

    en vérifiant si les appels à 'fct' sont à l'intérieur d'une fonction normale (comme 'cons' '+' etc.) ou d'une fonction ignorable (comme 'if' ou 'cond') (j'ai pas compris ou vous voullez en venir ).

    3) déterminer si une fonction 'fct' (avec sous-fonctions) est récursive terminale
    déterminer si chacune des sous-fonctions est récursive terminale (cf. 2)
    vérifier la récursivité croisée (fct1 appelle fct2 qui appelle fct1)

    vérifier tout simplement si il y a une fonction chapeau .

    jJe connais une fonction qui marche sur les liste simplement , cette fonction detail toute les etape de construction d'un liste :

    Code :
    1
    2
    3
    4
    5
    (define (reconstruire exp)
      (if (pair? exp)
          (list 'cons (reconstruire (car exp))
                      (reconstruire (cdr exp)) )
          (list 'quote exp) ) )
    donner lui n'importe quelle liste et elle vous détaillera sa construction. Je veux savoir si y il as une fonction qui detail les appels récursives d'un fonctionn par exemple :
    la fonction qui calcule la somme de 4 donne le résultat 10 = 1 + 2 + 3 + 4
    en récursivité sa fait :
    Code :
    1
    2
    3
    4
    (+ 4 (som ( - 4 1))
    (+ 3 (som (- 3 1))
    (+ 2 (som (- 2 1))
    (+ 1 (som (- 1 1)) somme de 0 = 0
    ensuite elle fai un calcule pour remonter les résultat :
    + 1
    + 2 sa donne 3
    + 3 sa donne 6
    + 4 sa donne 10

    en récursivité terminale sa fait :
    Code :
    1
    2
    3
    4
    5
    (somrt (- 4 1) (+ 4 0)) " 0 zéro est un accumulateur "
    (somrt (- 3 1) (+ 3 4))
    (somrt (- 2 1) (+ 2 7))
    (somrt (- 1 1) (+ 1 9))
    (somrt (- 0 1) (+ 0 10)) n = 0 en renvoi l'acumulateur .
    Si j'arrive a trouve une fonction qui ses appels, et comme vous l'avez précisez , si l'appel récusive et la dernier chose a faire donc c'est terminale si non faux. Le probleme c'est comme dire à la fonction qui prend l'argument liste .

    En gros : determiner si la fonction est récursive implique deux chose : avoir une boucle , et vérifié qu'on se dérige vers la boucle.
    deerminer si elle es terminale : appel récursive dernier chose a faire.
    puis determiner si la terminale a une sous fonction.
    Je suis Perdu pour l'instant je vais essayé de travailler tous sa , si j'ai d'autre question je vous les transmettrez demain,.

    Merci

  10. #10
    Invité régulier
    Homme Profil pro Rachid Ihadadene
    Étudiant
    Inscrit en
    décembre 2012
    Messages
    33
    Détails du profil
    Informations personnelles :
    Nom : Homme Rachid Ihadadene
    Localisation : France, Seine Saint Denis (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Matériel informatique

    Informations forums :
    Inscription : décembre 2012
    Messages : 33
    Points : 7
    Points
    7

    Par défaut bonjour

    j'ai trouvé sa dans un site internet je sais même pas si sava m'aider , je vous le transmet comeme.


    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    #lang racket
    
    (require parser-tools/lex
    
    (prefix-in re- parser-tools/lex-sre)
    
    parser-tools/yacc)
    
    (provide (all-defined-out))
    
     
    
    (define-tokens a (NUM VAR))
    
    (define-empty-tokens b (+ - EOF LET IN))
    
    (define-lex-trans number
    
    (syntax-rules ()
    
    ((_ digit)
    
    (re-: (re-? (re-or "-" "+")) (uinteger digit)
    
    (re-? (re-: "." (re-? (uinteger digit))))))))
    
    (define-lex-trans uinteger
    
    (syntax-rules ()
    
    ((_ digit) (re-+ digit))))
    
    (define-lex-abbrevs
    
    (digit10 (char-range "0" "9"))
    
    (number10 (number digit10))
    
    (identifier-characters (re-or (char-range "A" "z")
    
    "?" "!" ":" "$" "%" "^" "&"))
    
    (identifier (re-+ identifier-characters)))
    
     
    
    (define simple-math-lexer
    
    (lexer
    
    ("-" (token--))
    
    ("+" (token-+))
    
    ("let" (token-LET))
    
    ("in" (token-IN))
    
    ((re-+ number10) (token-NUM (string->number lexeme)))
    
    (identifier (token-VAR lexeme))
    
    ;; recursively calls the lexer which effectively skips whitespace
    
    (whitespace (simple-math-lexer input-port))
    
    ((eof) (token-EOF))))
    
     
    
    (define-struct let-exp (var num exp))
    
    (define-struct arith-exp (op e1 e2))
    
    (define-struct num-exp (n))
    
    (define-struct var-exp (i))
    
     
    
    (define simple-math-parser
    
    (parser
    
    (start exp)
    
    (end EOF)
    
    (error void)
    
    (tokens a b)
    
    (precs (left - +))
    
    (grammar
    
    (exp ((LET VAR NUM IN exp)
    
    (make-let-exp $2 (num-exp $3) $5))
    
    ((NUM) (num-exp $1))
    
    ((VAR) (var-exp $1))
    
    ((exp + exp) (make-arith-exp + $1 $3))
    
    ((exp - exp) (make-arith-exp - $1 $3))))))
    
     
    
     
    
    (define (eval parsed-exp)
    
    (match parsed-exp
    
    ((let-exp var num exp)
    
    (eval (subst var num exp)))
    
    ((arith-exp op e1 e2)
    
    (op (eval e1)
    
    (eval e2)))
    
    ((num-exp n) n)
    
    ((var-exp i) (error 'eval "undefined identifier ~a" i))))
    
     
    
    (define (subst var num exp)
    
    (match exp
    
    ((let-exp var2 num2 exp2)
    
    (if (eq? var var2)
    
    exp
    
    (let-exp var2 num2
    
    (subst var num exp2))))
    
    ((arith-exp op e1 e2)
    
    (arith-exp op
    
    (subst var num e1)
    
    (subst var num e2)))
    
    ((var-exp id)
    
    (if (equal? id var)
    
    num
    
    exp))
    
    ((num-exp n) exp)))
    
     
    
    (define (lex-this lexer input) (lambda () (lexer input)))
    
     
    
    (let ((input (open-input-string "3 - 3.3 + 6")))
    
    (eval (simple-math-parser (lex-this simple-math-lexer input))))
    
     
    
    (let ((input (open-input-string "let foo 6 in 3 - 3.3 + foo")))
    
    (eval (simple-math-parser (lex-this simple-math-lexer input))))

  11. #11
    Membre Expert
    Inscrit en
    avril 2008
    Messages
    1 033
    Détails du profil
    Informations forums :
    Inscription : avril 2008
    Messages : 1 033
    Points : 2 464
    Points
    2 464

    Par défaut

    Désolé, comme tes messages n'utilisent pas les balises QUOTE et CODE, j'ai beaucoup de mal à les lire et je préfère faire un meilleur usage de mon temps et de mon énergie.
    Merci d'éditer tes messages et de mettre les balises pour les rendre plus faciles à lire.

  12. #12
    Invité régulier
    Homme Profil pro Rachid Ihadadene
    Étudiant
    Inscrit en
    décembre 2012
    Messages
    33
    Détails du profil
    Informations personnelles :
    Nom : Homme Rachid Ihadadene
    Localisation : France, Seine Saint Denis (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Matériel informatique

    Informations forums :
    Inscription : décembre 2012
    Messages : 33
    Points : 7
    Points
    7

    Par défaut fonction compter

    Bonjour
    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
       (define (corp df)
      (if (unpair df)'()
          (caddr df)))
    
    (define (unpair l)
      (if (pair? l)#f #t))
    
    (define (nom df)
      (if (unpair df)'()
          (caadr df)))
    
    (define (par df)
      (if (unpair df)'()
          (cdadr df)))

    Je cherche à améliorer ma fonction qui compte le nombre d'occurence dans une liste , pour l'instant je suis obligé d'aplatir ma liste pour que la fonction arrive a compter les elements.
    Je cherche à compter le nombre d'occurence du nom de la fonction , si il es repeté au moin une fois c'est qu'il y a appel récursive normalement .

    Pour l'accumulateur c'est un peu dificile , parceque le nom de la fonction es bien définit , mais le parametre pour etre n'importe tous , sauf si on suppose par exemple qu'il sois le dernier élement des paramêtres.

    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    (define (multraux a b acc)
      (if ( = a 0)
          acc
          (multraux (- a 1)b (+ b acc))))
    le 'acc ( accumulateur c'est le dernier elemeent des parametre.
    
    (define (der df)
      (if (unpair df)'()                            
          (car (reverse (cdr df)))))
    
    (define (ac df); 
      (if (unpair df)'()
          (der(cdadr df))))
    la je pourrai faire une une fonction qui compte l'accumulateur.

    ensuite il reste toujour le probleme de comment parcourir les diférentes fonctions pour savoir si c'est vraiment la récursivité est la dernier chose à faire.

    une fois toute ces etape franchi la 3eme et derniere etape qui vérifie si fct 1 appel fct 2 et fct 2 appel fct1.

    Merci

  13. #13
    Invité régulier
    Homme Profil pro Rachid Ihadadene
    Étudiant
    Inscrit en
    décembre 2012
    Messages
    33
    Détails du profil
    Informations personnelles :
    Nom : Homme Rachid Ihadadene
    Localisation : France, Seine Saint Denis (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Matériel informatique

    Informations forums :
    Inscription : décembre 2012
    Messages : 33
    Points : 7
    Points
    7

    Par défaut Bonjour

    Voici la fonction qui comptes le nombre d'occurence d'un element dans une liste aplati

    Code :
    1
    2
    3
    4
    5
    (define (compter mot phrase)
      (if (pair? phrase)
          (+ (if (equal? mot (car phrase)) 1 0) ; Notez l'alternative sous l'addition!
             (compter mot (cdr phrase)) )
          0 ))

  14. #14
    Membre Expert
    Inscrit en
    avril 2008
    Messages
    1 033
    Détails du profil
    Informations forums :
    Inscription : avril 2008
    Messages : 1 033
    Points : 2 464
    Points
    2 464

    Par défaut

    Merci beaucoup d'avoir fait l'effort d'utiliser la balise CODE!
    Du coup, ça me donne presque envie de répondre...

    Citation Envoyé par kbprince Voir le message
    Voici la fonction qui comptes le nombre d'occurence d'un element dans une liste aplati

    Code :
    1
    2
    3
    4
    5
    (define (compter mot phrase)
      (if (pair? phrase)
          (+ (if (equal? mot (car phrase)) 1 0) ; Notez l'alternative sous l'addition!
             (compter mot (cdr phrase)) )
          0 ))
    Exercice (transformer le pseudo-code en code):

    Code :
    1
    2
    3
    4
    5
    6
    Pour compter le nombre d'occurrences de 'x' dans un arbre 'A' (sans l'aplatir):
      si 'A' = 'x' c'est 1
      sinon si 'A' n'est pas un 'cons', c'est 0 (on ne traite pas les vecteurs ni les chaines de caractères)
      sinon c'est la somme
        entre le nombre d'occurrences de 'x' dans le sous-arbre (car 'A')
        et le nombre d'occurrences de 'x' dans le sous-arbre (cdr 'A')

  15. #15
    Invité régulier
    Homme Profil pro Rachid Ihadadene
    Étudiant
    Inscrit en
    décembre 2012
    Messages
    33
    Détails du profil
    Informations personnelles :
    Nom : Homme Rachid Ihadadene
    Localisation : France, Seine Saint Denis (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Matériel informatique

    Informations forums :
    Inscription : décembre 2012
    Messages : 33
    Points : 7
    Points
    7

    Par défaut Bonjour

    J'ai suivi vos instruction sa me donne toujour le résultat 3 , voici ma fonction plus les exemple

    Code :
    1
    2
    3
    4
    5
    (define (conte mot df)
      
      (if(equal? mot df)1
         (if (unpair df) 0
      (+ 1 (conte mot (cdr df))))))
    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    Welcome to DrScheme, version 4.2.4 [3m].
    Language: Module; memory limit: 4096 megabytes.
    > (conte 'v '(define (cherarb v a)
      (if (unpair a) #f
    	(if (= v (car a)) #t
    	  (if (< v (car a))
    		  (cherarb v (cadr a))
    		  (cherarb v (caddr a)))))))
    3
    > (conte 'chararb '(define (cherarb v a)
      (if (unpair a) #f
    	(if (= v (car a)) #t
    	  (if (< v (car a))
    		  (cherarb v (cadr a))
    		  (cherarb v (caddr a)))))))
    3
    > (conte 'a '(define (cherarb v a)
      (if (unpair a) #f
    	(if (= v (car a)) #t
    	  (if (< v (car a))
    		  (cherarb v (cadr a))
    		  (cherarb v (caddr a)))))))
    3
    >
    Merci

  16. #16
    Membre Expert
    Inscrit en
    avril 2008
    Messages
    1 033
    Détails du profil
    Informations forums :
    Inscription : avril 2008
    Messages : 1 033
    Points : 2 464
    Points
    2 464

    Par défaut

    Citation Envoyé par kbprince Voir le message
    il y a plein d'expression que je ne comprend pas dans votre vocabulaire, comme le ( begin )et le (implicite et explicite),
    est votre ami:

    http://www.cs.bham.ac.uk/research/pr...ex_scheme.html
    http://www.cs.bham.ac.uk/research/pr...re4.html#begin

    Actually, the begin statement is not necessary in the test function above, since Scheme allows one to have a sequence of expressions as the body of a function, although the begin may make the code clearer.
    Lorsque le code contient explicitement un appel à la fonction 'begin', on dit que c'est un 'begin' explicite.
    Lorsque le code contient une forme (comme 'define' ou le 'cdr' d'une clause de 'cond') qui autorise une séquence d'instructions et retourne le résultat de la dernière, on dit que c'est un 'begin' implicite.

    pour le cond , j'aime pas l'utiliser parce que je sais pas comment classer les événements du traiment de la fonction,
    Je ne comprends pas 'classer les événements du traiment de la fonction'

    car d'aprés le mon prof , le cond remplace plusieur (if).
    Oui. C'est une manière de voir les choses.
    Il y a plusieurs "écoles":
    - ceux qui considèrent que la "vraie" primitive est le 'cond' est que le 'if' n'est qu'un cas particulier dégénéré et programmable à partir du 'cond'
    - ceux qui considèrent que la "vraie" primitive est le 'if' est que le 'cond' n'est qu'un cas particulier dégénéré et programmable à partir du 'if'.
    - ceux qui considèrent que les 2 existent et que chacun a ses avantages et inconvénients.

    Dans tous les cas, si on te demande d'écrire un programme qui vérifie si la définition d'une fonction quelconque est récursive terminale, il faut bien traiter le cas où le corps de la fonction contient des trucs comme des 'cond', des 'let', etc.

    Apparemment, je me retrouve au point de départ du projet , et le travail qui me reste à faire n'est pas du gâteau.
    Je confirme!

    c'est ce que j'essaye de reprendre depuis le début, ce programme contient beaucoup pièges, les fonction récursive sont toutes différentes.
    Je confirme!

    en vérifiant si les appels à 'fct' sont à l'intérieur d'une fonction normale (comme 'cons' '+' etc.) ou d'une fonction ignorable (comme 'if' ou 'cond') (j'ai pas compris ou vous voullez en venir ).
    C'est le point crucial!!!

    Dans l'arbre du corps d'une fonction comme:
    Code :
    1
    2
    3
    4
    (define (fact1 a)
      (if (= a 0)
        1
        (* a (fact1 (- a 1)))))
    l'appel (récursif) de 'fact1' est encapsulé dans un appel à '*' (qui n'est pas ignorable) lequel est encapsulé dans un appel à 'if' (qui est ignorable).
    conclusion: à cause de la fonction non-ignorable '*', l'appel n'est pas récursif terminal.

    Dans l'arbre du corps d'une fonction comme:
    Code :
    1
    2
    3
    4
    5
    6
    (define (membre a l)
      (if (not (pair? l))
        #f
        (if (eq a (car l))
          #t
          (membre a (cdr l)))))
    l'appel (récursif) de 'membre ' est encapsulé dans un appel à 'if' (qui est ignorable) lequel est encapsulé dans un appel à un autre 'if' (qui est aussi ignorable).
    conclusion: l'appel n'est imbriqué sous aucune fonction non-ignorable, l'appel est donc récursif terminal.



    3) déterminer si une fonction 'fct' (avec sous-fonctions) est récursive terminale
    déterminer si chacune des sous-fonctions est récursive terminale (cf. 2)
    vérifier la récursivité croisée (fct1 appelle fct2 qui appelle fct1)
    vérifier tout simplement si il y a une fonction chapeau .
    ce n'est malheureusement pas si simple!...

  17. #17
    Membre Expert
    Inscrit en
    avril 2008
    Messages
    1 033
    Détails du profil
    Informations forums :
    Inscription : avril 2008
    Messages : 1 033
    Points : 2 464
    Points
    2 464

    Par défaut

    Citation Envoyé par kbprince Voir le message
    J'ai suivi vos instruction
    Presque...

    Dans:
    Code :
    1
    2
    3
    4
    5
    6
    Pour compter le nombre d'occurrences de 'x' dans un arbre 'A' (sans l'aplatir):
      si 'A' = 'x' c'est 1
      sinon si 'A' n'est pas un 'cons', c'est 0 (on ne traite pas les vecteurs ni les chaines de caractères)
      sinon c'est la somme
        entre le nombre d'occurrences de 'x' dans le sous-arbre (car 'A')
        et le nombre d'occurrences de 'x' dans le sous-arbre (cdr 'A')
    Tu as oublié la partie le nombre d'occurrences de 'x' dans le sous-arbre (car 'A'), mais tu y es presque!

  18. #18
    Membre Expert
    Inscrit en
    avril 2008
    Messages
    1 033
    Détails du profil
    Informations forums :
    Inscription : avril 2008
    Messages : 1 033
    Points : 2 464
    Points
    2 464

    Par défaut

    Citation Envoyé par kbprince Voir le message
    j'ai trouvé sa dans un site internet je sais même pas si sava m'aider , je vous le transmet comeme.
    Totalement inutile: après reformatage, c'est juste un parser d'expressions arithmétiques.

  19. #19
    Invité régulier
    Homme Profil pro Rachid Ihadadene
    Étudiant
    Inscrit en
    décembre 2012
    Messages
    33
    Détails du profil
    Informations personnelles :
    Nom : Homme Rachid Ihadadene
    Localisation : France, Seine Saint Denis (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Matériel informatique

    Informations forums :
    Inscription : décembre 2012
    Messages : 33
    Points : 7
    Points
    7

    Par défaut Bonjour

    Sa Marche enfin :

    Code :
    1
    2
    3
    4
    5
    6
    7
    (define (decompter mot arbre)
      (if (pair? arbre)
          (+ (decompter mot (car arbre))   ; récursion à gauche
             (decompter mot (cdr arbre)) ) ; récursion à droite
          (if (equal? mot arbre)
              1
              0 ) ) )
    Maintenant , je peut compter le nombre d'occurence du 'Nom' et de 'l'accumulateur' dans la fonction !
    est que cela m'aiderai a prouver que c'est une fonction récursive , pour un début ?!
    il me restera bien sure le probeleme de comment parcourir les differentes fonction récursives pour determiner si c'est terminale ou pas.

    pour la derniere etape : vérifier si elle a une fonction chapeau , on a pas besoin de faire le teste sur les fonction qui ne sont pas on Rterminal , Non ?!

    Merci!

  20. #20
    Membre Expert
    Inscrit en
    avril 2008
    Messages
    1 033
    Détails du profil
    Informations forums :
    Inscription : avril 2008
    Messages : 1 033
    Points : 2 464
    Points
    2 464

    Par défaut

    Quelle version de scheme utilises-tu?

    Concernant le 'begin' implicite, cette référence est bien meilleure: http://www.gnu.org/software/mit-sche...tml#Sequencing

    Elle donne la liste des fonctions à parser spécialement!

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •