[Lisp][Débutant] Récursivité incomplète

Version imprimable

Bonjour,

Voici mon code :

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
 
(define (calcul p l lro )
  (cond ((null?( car l)) lro)
        (else calcul p (cdr l) (add p (car l) (cons(car (car l)) () ) (addr lro) lro) ) ) )
 
 
(define (add p ltc lto lrc lro)
  (cond ((or (null? (cdr ltc)) 
             (>  (+ (car (car ltc)) (car (car (cdr ltc)))) p))   
         (cond ((> (car (cdr (car ltc))) (car(cdr (car lrc)))) lto) 
               (else lro )))  
 
        (else (add p 
                   (append (cons (cons (+ ( car (car ltc) ) (car (car (cdr ltc))))
                                       (cons (+ (car (cdr (car ltc))) (car (cdr (car (cdr ltc))))) ()) 
                                       )()) 
                           (cdr (cdr ltc)))
                   (append (cons (car (cdr ltc)) () ) lto) lrc lro))))
 
 
( define (addr ltc) 
   (cond ( (null? (cdr ltc) )  ltc)
         (else 
          (addr (
                 append (            
                         cons            
                         (                        
                          cons                                      
                          ( + ( car (car ltc) ) (car (car (cdr ltc) ) ) )                                              
                          (cons (+ (car (cdr (car ltc) ) ) ( car (cdr (car (cdr ltc) ) ) ) ) ())                                                     
                          )                                            
                         ()                                       
                         )                                       
                        (cdr (cdr ltc) )                                  
                        ) 
                ) ) ) )

J'envoie une liste l à "calcul" de type ( ( (2 3) (3 5) (3 5) ) ( (3 6) (6 2) (3 5) ) ), un argument p = 6, et un lro = car(car l)

"Add" et "addr" font bien leur travail. Mais dès la premiere fois où le programme rentre dans addr, l'interpréteur me renvoie lro ou lto (suivant le cas) alors qu'elle doit normalement le renvoyer à la fonction calcul afin de continuer la récursivité. Comme d'habitude, je ne vois pas le problème...

Merci

30/11/2006, 21h34
Trap D
J'ai un peu tester et moi j'ai une erreur lorsque je fais :
Code:

1 2 3 (let* ((l '(((2 3) (3 5) (3 5)) ((3 6) (6 2) (3 5)) )) (lro (caar l))) (calcul 6 l lro))
Tu pourrais donner exactement la fonction de lancement de calcul ?

J ai modifié mon programme afin qu il soit plus lisible :

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
 
(define (sac-a-dos p l) 
  ( go p (constree l)  ) )
 
(define (go p l)
  (calcul p l (list (car(car l)) ) )
 
(define (calcul p l lro )
  (cond ((null?( car l)) lro)
        (else calcul p (cdr l) (add p (car l) (list (car (car l)) ) (addr lro) lro) ) ) )
 
(define (add p ltc lto lrc lro) 
  (cond ((or (null? (cdr ltc)) ( > (+ (poids1 ltc) (poids2 ltc) ) p ) )   
         (cond ( (> (valeur1 ltc) (valeur1 lrc) ) lto) 
               (else lro )))       
        (else (add p 
                   (append (list (cons (+ (poids1 ltc) (poids2 ltc) ) (list (+ (valeur1 ltc) (valeur2 ltc) ) ) ) )       
                           (cdr (cdr ltc) ) ) 
                   (append (list (car (cdr ltc)) ) lto) lrc lro))))
 
( define (addr ltc) 
   (cond ( (null? (cdr ltc) )  ltc)
         (else (addr (append (list (cons(+ (poids1 ltc) (poids2 ltc)) (list(+ (valeur1 ltc) ( valeur2 ltc) ) ) ) )                           
                             (cdr (cdr ltc) ) ) ) ) ) ) 
 
(define (constree l)
  (let* ((ll (reverse l))
         (tete (list(list (car ll))))
         (reste (cdr ll)))
    (let foo1 ((x reste) (y tete))
      (cond ((null? x) y)
            (else (foo1 (cdr x) 
                        (let foo2 ((xx (car x)) (yy y))
                          (cond ((null? yy) yy)
                                (else (append (list (cons xx (car yy)) (car yy)) (foo2 xx (cdr yy))))))))))))
 
 
(define (poids1 l )
  ( car(car l) ) )
 
(define (poids2 l)
  ( car(car(cdr l) ) ) )  
 
(define (valeur1 l) 
  ( car(cdr(car l) ) ) )
 
(define (valeur2 l)
  ( car(cdr(car(cdr l) ) ) ) )

Pour une liste de type '( (1 2)(3 4)(5 6) )
poids1 = 1
poids2 = 3
valeur1 = 2
valeur2 = 4

Le tout se lance avec : (sac-a-dos '15 '( (1 2)(3 4)(15 6) )
Les a list designent les objets et 15 le poids maximal
Constree construit un arbre et l envoie a calcul (indirectement...)

Calcul prends la tete de cette liste (donc une combinaison d'objets)
Il les additonne entre eux jusqu a ce qu il depasse ou egale le poids max ou que la liste soit terminée
Il compare ensuite la valeur de cette nouvelle combinaison et la valeur de la combinaison reponse (qui a la plus grande valeur a cet instant)

Voila j ai teste ca hier, pas de probleme sauf cette recursivité incomplète

03/12/2006, 15h38
Treuze

Pas de réponse ?

est ce que le programme fonctionne chez vous ?
04/12/2006, 17h58
Trap D

Salut

je n'ai pas regardé tout le code mais j'ai un problème avec ce calcul

Code:

(list (cons (+ (poids1 ltc) (poids2 ltc) ) (list (+ (valeur1 ltc) (valeur2 ltc)

Tu additionnes les poids des objets ensemble et les nombre d'objets ensemble ?
J'aurais cru qu'il fallait faire des multiplications entre les poids et le nombre d'objets de chaque liste ? C'est ça ou j'ai rien compris à ce que tu veux faire ?

Ça me coince un peu avant de continuer.
05/12/2006, 13h16
Trap D
Pour t'aider, j'ai besoin de savoir
- ce que tu donnes en entrée
- ce que tu espères obtenir en sortie
C'est le meilleur moyen pour moi.
06/12/2006, 13h26
Treuze

J aditionne les poids entre eux et les valeurs entre elles, le resultat est pose en debut de liste et concatene avec le reste de la liste moins les deux premiers objets. Si le poids calculé depasse p, j arrete

Tu lances avec sac-a-dos p (poids max) et la liste des objets disponibles : (sac-a-dos '15 '( (15 2)(3 4)(1 6) )

Constree te construit une liste avec ttes les combinaisons (merci a toi)

Et en sortit on devrait obtenir la meilleure combinaison donc ( (3 4)(1 6)) car 3 + 1 = 4 la meilleure valeur possible sans depasser le poids

Voila !

Bon, maintenant que je sais où il faut aller, je crois avoir trouvé :

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
(define (sac-a-dos p l) 
  ( go p (constree l)  ) )
 
(define (go p l)
  (calcul p l (list (car(car l))))) 
 
 
(define (calcul p l lro )
 
;  (cond ((null?( car l)) lro)   <== ici erreur, il faut tester simplement l et par car l
 
  (cond ((null? l) lro) 
        (else (calcul p (cdr l) (add p (car l) (list (car (car l))) (addr lro) lro)))))
; ici oubli de la parenthèse devant calcul, celà donnait un peu n'importe quoi !
 
 
(define (add p ltc lto lrc lro) 
  (cond ((or (null? (cdr ltc)) ( > (+ (poids1 ltc) (poids2 ltc) ) p ))   
         (cond ((> (valeur1 ltc) (valeur1 lrc)) lto) 
               (else lro )))        
        (else (add p 
                   (append (list (cons (+ (poids1 ltc) (poids2 ltc) ) (list (+ (valeur1 ltc) (valeur2 ltc) ) ) ) )       
                           (cdr (cdr ltc) ) ) 
                   (append (list (car (cdr ltc)) ) lto) lrc lro))))
 
(define (addr ltc) 
   (cond ((null? (cdr ltc) ) ltc)
         (else (addr (append (list (cons(+ (poids1 ltc) (poids2 ltc)) (list(+ (valeur1 ltc) (valeur2 ltc)))))                           
                             (cdr (cdr ltc) ) ) ) ) ) ) 
 
(define (constree l)
  (let* ((ll (reverse l))
         (tete (list(list (car ll))))
         (reste (cdr ll)))
    (let foo1 ((x reste) (y tete))
      (cond ((null? x) y)
            (else (foo1 (cdr x) 
                        (let foo2 ((xx (car x)) (yy y))
                          (cond ((null? yy) yy)
                                (else (append (list (cons xx (car yy)) (car yy)) (foo2 xx (cdr yy))))))))))))
 
 
(define (poids1 l )
  (car(car l) ) )
 
(define (poids2 l)
  ( car(car(cdr l) ) ) )  
 
(define (valeur1 l) 
  (car(cdr(car l) ) ) )
 
(define (valeur2 l)
  (car(cdr(car(cdr l) ) ) ) )

Avec (sac-a-dos '15 '( (15 2)(3 4)(1 6))), j'obtiens ((1 6) (3 4)) :lol:

07/12/2006, 20h21
Gnux
Citation:
Envoyé par Trap D

Pour t'aider, j'ai besoin de savoir

ce que tu donnes en entrée
ce que tu espères obtenir en sortie
C'est le meilleur moyen pour moi.
Ce serait bien aussi d'avoir une spécification et des commentaires dans le code parce que là franchement ça fait potion magique...
Ecrivez du code lisible pour vous (au moment de le relire 6 mois après l'écriture) et pour les autres (qui devront le maintenir après vous). Par exemple tu pourrais expliciter ton problème comme tu l'as fait à trap des le début que tout le monde comprenne
Merci
11/12/2006, 16h12
Treuze

Gnux : Je vais faire ca oui... c est vrai que le lisp n est pas vraiment lisible en plus

TrapD : Merci encore une fois !