Salut, j'ai pris mon temps pour donner une solution en scheme.
Ça fait un moment que je n'étais pas vraiment passé par là et je n'avais pas vu que vous aviez commencé.
Menfinbon.
Voici sans optimisation, avec un code simple.
C'est la technique de tous je crois.
Si vous vouliez des explications je me tiens à votre disposition.
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
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 (define (n-est-egale-a-m? m) (lambda (n) (= n m))) (define est-1? (n-est-egale-a-m? 1)) (define est-0? (n-est-egale-a-m? 0)) (define (1- n) (- n 1)) (define (creer-liste-de-1-a m) (define (creer-liste-de-1-a-it n l) (if (est-1? n) (cons 1 l) (creer-liste-de-1-a-it (1- n) (cons n l)) ) ) (creer-liste-de-1-a-it m '()) ) (define (union-des-listes-de l) (foldl append '() l) ) (define (decomposition_n_m n m) (if (est-0? n) '() (let* ((liste-1-min-n-m (creer-liste-de-1-a (min n m))) (creer-decomposition-partiel (lambda (x) (let ((decomposition_n-x_x (decomposition_n_m (- n x) x)) ) (if (null? decomposition_n-x_x) `((,x)) (map (lambda (l) (cons x l)) decomposition_n-x_x) ) ) ) ) ) (union-des-listes-de (map creer-decomposition-partiel liste-1-min-n-m)) ) ) ) (define (decomposition n) (decomposition_n_m n n) )
Dans les optimisations simples: les listes « infinies » pour conserver les valeurs des calculs temporaires et le retour de plusieurs paramètres pour éviter les constructions destructions de listes (je pense surtout au créateur union-des-listes-de). Mais j'ai pas essayé encore.
Partager