Problème de car

Version imprimable

Problème de car

Bonjour,
J'abuse de votre serviabilité mais depuis quelques temps je me prends sérieusement la tête.
Je n'arrive pas à comprendre pourquoi à la deuxième récursion je me plante sur (car L2). Je n'ai aucune hypothèse pour tester !!! Si vous pouviez me débloquer.Merci d'avance
Code:

1 2 3 4 5 6 7 8 (define (nb-intervalles L1 L2) (if (pair? (cdr L1)) (let ((k (nb-intervalles (cdr L1) (car L2))) (couple (car L1))) (cond ((and (>= (car L2) (car couple)) (<= (car L2) (cadr couple))) (list (car L1) (+ 1 (cadr k)))) (else k))) (list (car L1) 0))) (trace nb-intervalles) (nb-intervalles (list (list 1 3) (list 4 6) (list 7 13)) (list 1 2 3 10))

15/03/2011, 17h35
Trap D

Je veux bien chercher mais quelle est la finalité de cette fonction ?
Je ne comprends pas ce qu'elle fait ! :(
16/03/2011, 00h39
debmaths

Merci de prendre en compte mon problème. C'est un embryon de réponse du problème ci-dessous:
Écrire une définition complète de la fonction qui prend en entrée une liste d'intervalles disjoints LI supposée non vide, ainsi qu'une liste de valeurs L et rend une liste d'associations qui indique pour chaque intervalle de LI, le nombre des valeurs de L qui sont incluses dedans.

Merci d'avance

Mon gros problème est de balayer x fois une liste dans une fonction
16/03/2011, 09h09
Trap D

OK; N'oubliez pas que vous faites de la programmation fonctionnelle, vous ecrivez des fonctions qui sont réutilisables.
Réfléchissez à la signification de la fonction map2 qui applique une fonction fn à tous les éléments d'une liste, n'est-ce pas ce que vous cherchez à faire actuellement ?

Code:

Mon gros problème est de balayer x fois une liste dans une fonction

Problème de car

Je ne saisis pas très bien ce que vous voulez me faire comprendre mais voici sur quoi j'étais parti mais je ne m'en sortais pas
;

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
define (nb-intervalles L1 L2)
  (if  (pair? (cdr L2))
     ((nb-intervalles L1 (cdr L2))
     (balaie L1 (cdr L2)))
  (list)))
             
(define (balaie L1 L2)
  (if (pair? L1)
      (let ((n (balaie (cdr L1) L2)))
      (cond ((and (>= L2 (caar L1)) (<= L2 (cadar L1))) (cons (car L1) (list (+ 1 (cadr n)))))
      (else n)))
  (cons (car L1) (list 0))))
(trace nb-intervalles) (nb-intervalles (list (list 1 3))  (list 2 4 1 10))

16/03/2011, 11h23
Trap D

Je pense que vous devez définit une fonction qui prend en argument la liste L des valeurs à tester et un intervalle, cette fonction (appelons la teste-1-intervalle) va renvoyer le nombre de valeurs de L incluse dans cette intervalle.
Vous n'avez plus ensuite qu'à appliquer cette fonction à toute la liste des intervalle en utilisant map.
16/03/2011, 13h17
debmaths

Problème car

C'est donc bien ce que je voulais faire.
Fonction traitant un intervalle: "balaie"
Fonction traitant intervalle par intervalle: nb-intervalles

Ma logique était donc bonne c'est l'écriture qui foire. Je verrai cela ce soir.

Merci pour votre aide

Problème de car

Eh bien je craque, à force de simplifier il ne reste presque plus rien comme code. Mais ça ne tourne toujours pas.
Duux problèmes:
-- comment nommer L2 dans "balaie" alors que la liste est traitée par map
-- comment sortir les résultats ?
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ;;; traitement intervalle par intervalle, lecture de L1 (define (nb-intervalles L1 L2) ;; traitement intervalle, fonction de map (define (balaie L1) (if (and (>= e (caar L1)) (<= e (cadar L1))) (cons (car L1) (list (+ 1 (cadr (balaie L1))))) )) (if (pair? L1) (map (balaie (cdr L1)) L2))) ;;; lecture de L2 par map (trace nb-intervalles) (nb-intervalles (list (list 1 3)) (list 2 4 1 10))

Je donne la solution qui est "un peu" compliquée. On peut simplifier avec des fonctions qui facilite la solution de ce genre d'exercices.
Solution 1 :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
; L1 est la liste des intervalles
; L2 est la liste des valeurs à traiter
(define (nb-intervalles L1 L2) 
  ;; traitement intervalle, 
  ;; on passe en revue tous les éléments de L2 pour savoir s'ils sont dans l'intervalle défini par L1
  ;; renvoie une liste d'association (Nombre-presents Intervalle)
  (define (balaie-un-intervalle Intervalle)
    ;; on definit une nouvelle fontion qui teste un nombre de L2 pour savoir s'il est dans l'intervalle
    ;; renvoie le nombre d'occurences lorsque la liste est terminée
    (define (teste-valeur  L N)
      (cond ((null? L) N)
            ((and (>= (car L) (car Intervalle)) (<= (car L) (cadr Intervalle))) (teste-valeur (cdr L) (+ N 1)))
            (else (teste-valeur (cdr L) N))))
    (list (teste-valeur L2 0) Intervalle))
  
  ;; maintenant, on n'a plus qu'a appliquer la fonction balaie-un-intervalle à toute la liste des intervalles
  ;; à l'aide de map
  (map balaie-un-intervalle L1))

Résultat

Citation:

> (nb-intervalles (list (list 1 3)) (list 2 4 1 10))
((2 (1 3)))
> (nb-intervalles (list (list 1 3) (list 4 6) (list 7 13)) (list 1 2 3 10))
((3 (1 3)) (0 (4 6)) (1 (7 13)))

Une solution utilisant les fonctions prédéfinies de Scheme, en l'occurence foldl

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
;; avec l'utilisation de foldl qui sert à travailler sur les éléments d'une liste !
; L1 est la liste des intervalles
; L2 est la liste des valeurs à traiter
(define (nb-intervalles-2 L1 L2) 
  ;; x represente un intervalle
  (map (lambda (x)
         ;; y représente un nombre de la liste des valeurs à tester
         ;; acc est un accumulateur qui est mis à jour en fonction des valeurs de y
         (list (foldl (lambda (y acc)
                        (if (and (>= y (car x)) (<= y (cadr x)))
                            (+ 1 acc)
                            acc))
                      ; l'accumulateur est initialisé à 0
                      0
                      ; on balaie la liste de valeurs L2
                      L2)
               x))
       L1))

17/03/2011, 07h45
debmaths

Problème de car

Merci pour votre rapide réponse.
Je n'ai pas encore vu "fold" "lambda" et "accumulateur'. Je vais me pencher sur ces mots.
Pour l'instant je n'ai pas le temps de tester mais rien que de visu, quand vous lisez un intervalle x qui est une association est-nomal que vous la lisez avec (car x) et (cadr x) ? Ne serait-ce pas "caar" et "cadar" ?
17/03/2011, 09h06
Trap D

x n'est pas une association, x est un intervalle, l'association est renvouée en fin de fonction par (list (teste-valeur L2 0) Intervalle) c'est (teste_valeur L2 0) qui calcule le nombre d'éléments de la liste L2 dans l'intervalle, puis on renvoie l'association.
17/03/2011, 12h31
debmaths

Problème de car

Merci beaucoup. Je n'aurai jamais trouvé. Je préfère votre première solution:
-- traitement 1 élément de L2 avec l'intervalle x de L1
-- tous les éléments de L2 avec l'intervalle x de L1
-- Tous les intervalles de L1

Dans ma logique je zappais la première fonction.
Je reviens sur ma question d'association. Je ne saisis pas et il faudrait que je comprenne car ça doit être important. Par création, "intervalle" est une association de 2 chiffres or vous y accédez par car et cadr ET CA FONCTIONNE, pourquoi ?

C'est bien la première fois qu'un langage me pose un aussi gros problème. Il faut dire que sa philosophie est différente des langages que j'ai pratiqués: CAB500, FORTRAN IV, différents COBOL, Assembleur IBM, Assembleur CII, HTLM et autres dont je me rappelle plus les noms.
17/03/2011, 13h33
Trap D

L'intervalle est simplement une liste (debut fin) accessible par car et cadr.
Il faut bien comprendre que l'association n'est crée qu'après le comptage des nombres figurant dans l'intervalle.