Discussion :

[sam_93]

Bonjour tout le monde!alors voici l'énnoncé de mon exo:

on me demande de créer une fonction qui étant donnée une liste non vide de nombre rend le couple formé du maximum de la liste et de son nombre d'occurences:

ex:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
(fonction (list 1 3 3 2))->( 3 2)
(fonction (list 7))->( 7 1)

alors j'ai écrire le code suivant

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
(define (fonction L)
  (if (pair? L)
      (if (pair? (cdr L))
          (let ((res (fonction (cdr L))))
            (if (> (car L) (car res))
              (if (= (car L) (car couple))
                  (list (car L) (+ 1 (car couple)))
                  couple)))
          (list (car L) 1))
      (list 0 0)))

quand j'essaye sa marche pour le cas de base mais pour le reste nada!Je vois vraiment pas ou est le probléme donc si quelqun pouvait m'aider ce serait sympa!Merci à tous et bonne soirée!

[Trap D]

Je pense que tu dois envisager d'abord deux cas : soit la liste est vide soit elle ne l'est pas.
Ensuite si la liste n'est pas vide, elle possède donc au moins 1 élément qui est le premier maximum que tu rencontres.
Tu devrait donc utiliser une fonction secondaire qui parcourt la liste et étudie le premier élément en fonction du couple (max nb) qu'elle connait déjà.

[Jedai]

Je voudrais ajouter que le comportement correct si la liste est vide est probablement d'échouer violemment plutôt que de renvoyer '(0 0).
Par ailleurs ta fonction bien que non idéale (la proposition de TrapD est terminalement récursive puisqu'il s'agit d'un fold_left) devrait fonctionner, le seul problème est que tu changes de nom pour ta variable (res devient couple) sans raison, par ailleurs tu utilises (car couple) au lieu de (cadr couple)...

--
Jedaï

[sam_93]

bonsoir,tout d'abord je tiens à vous remercier de m'avoir répondu!Concernant le code de la fonction en effet j'ai fait une faute de frappe j'ai mis couple au lieu de res!le truc en faite c'est que j'ai essayé de dérouler cette fonction mais j'arrive pas voir quand est on obtient le couple est ce a partir de res?si quelqun pouvait me dérouler cette fonction ne serait ce qu'avec un cas simple juste que pour que je comprenne ça m'aiderait à comprendre!Merci à tous et bonne soirée!

[Nicolas_75]

Bonjour,

Ci-dessous ton code corrigé et commenté.

Il subsiste au moins deux soucis :
- le renvoi de '(0 0) si la liste est vide (cf. ci-dessus) ;
- la fonction ainsi définie n'est pas récursivement terminale.

Nicolas

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
(define (fonction L)
  (if (null? L) ; si L est une liste vide...
      '(0 0) ; ... on renvoie (0 0)
      ; à partir de cette ligne, on sait que L a au moins 1 élément
      (if (null? (cdr L)) ; si L ne contient qu'un élément...
          (list (car L) 1) ; ... on renvoie cet élément, avec 1 comme nombre d'occurence(s)
          ; à partir de cette ligne, on sait que L a au moins 2 éléments
          (let ((res (fonction (cdr L)))) ; res est donc le couple (maximum de cdrL, nb d'occurrences dans cdrL)
            (if (> (car L) (car res)) ; si (car L) est supérieur à (car res), ...
                (list (car L) 1) ; ... c'est en fait lui, (car L), le maximum de L, et de nb d'occurrence(s) 1
                (if (= (car L) (car res)) ; ... sinon, si (car L) est égal à égal à (car res)...
                    (list (car L) (+ 1 (cadr res))) ; ... (car res) est le bon maximum, il faut juste augmenter son nombre d'occurrences de 1 ...
                    res)))))) ; ... sinon on renvoie res, puisque carL est < que le maximum de cdr L

(fonction '()) ; -> (0 0)
(fonction '(7)) ; -> (7 1)
(fonction (list 1 3 3 2)) ; -> (3 2)
(fonction (list 1 2 4 3)) ; -> (4 1)

[Nicolas_75]

Une possible variante récursivement terminale...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
(define (fonction2-aux L maximum-courant nb-occurrences-courant)
  (if (null? L) 
      (list maximum-courant nb-occurrences-courant)
      (if (> (car L) maximum-courant)
          (fonction2-aux (cdr L) (car L) 1)
          (if (= (car L) maximum-courant)
              (fonction2-aux (cdr L) maximum-courant (+ nb-occurrences-courant 1))
              (fonction2-aux (cdr L) maximum-courant nb-occurrences-courant)))))
(define (fonction2 L)
  (if (null? (cdr L)) ; L n'a qu'un élément
      (list (car L) 1)
      (fonction2-aux (cdr L) (car L) 1)))
; (fonction2 '()) ; -> ERREUR
(fonction2 '(7)) ; -> (7 1)
(fonction2 (list 5 6)) ; -> (6 1)
(fonction2 (list 1 3 3 2)) ; -> (3 2)
(fonction2 (list 1 2 4 3)) ; -> (4 1)
(fonction2 (list 3 3 3 3)) ; -> (3 4)

[SpiceGuid]

si quelqun pouvait me dérouler cette fonction ne serait ce qu'avec un cas simple juste que pour que je comprenne ça m'aiderait à comprendre!

L'intérêt du style déclaratif c'est que justement tu n'as pas besoin de dérouler une fonction pour la comprendre. Tu la comprends à l'aide d'un principe d'induction, par exemple ici:

• quelle valeur est renvoyée pour une liste à 1 élément
• sinon quelle valeur est renvoyée pour une liste à n > 1 éléments

Ce sont les programmes impératifs qui doivent être déroulés pour constater que leur comportement est raisonnable.
Dérouler un programme déclaratif n'aide pas à le comprendre, ça n'aide à comprendre que la machine impérative qui l'implémente.