Marc Chemillier - Cours de Scheme

Scheme

Université de Caen - UFR de Sciences
Deug MIAS-MASS
Marc Chemillier

Scheme - TD n° 9
2 mai 2001

Représentation des nombres en binaire et fichiers d'images BMP

Exercices : (1h1/2)

Pour tout nombre n, il existe un unique k, et des coefficients a₀, ... a_k valant 0 ou 1 tels que:
n = a₀ + a₁2 + ... + a_k2^k.
C'est la représentation binaire de n. Faire la fonction (decimal->binaire n) qui donne la liste des coefficients a_i de la décomposition binaire de n. Pour 13 = 1 + 2² + 2³, on a:
```
> (decimal->binaire 13) 
(1 0 1 1)
```
```
 (define (decimal->binaire n)
   (cond ((= n 0) '())
         (else (cons (remainder n 2)
                     (decimal->binaire (quotient n 2))))))
```

Faire une fonction (applatit l) qui enlève un niveau de parenthèses dans l:

> (applatit '((a b c) (d e) (f g h))) 
(a b c d e f g h)


(define (applatit l)
  (if (null? l) () (append (car l) (applatit (cdr l)))))

Faire une fonction (nthcar n l) qui donne la liste des n premiers éléments de l, supposée de longueur supérieure à n:
```
(define (nthcar n l)
  (cond ((= n 0) ())
        (else (cons (car l) (nthcar (- n 1) (cdr l))))))
```
Faire une fonction (nthcdr n l) qui donne la liste obtenue en supprimant les n premiers éléments de l, et () si la longueur de l est inférieure à n:
```
(define (nthcdr n l)
  (cond ((or (null? l) (= n 0)) l)
        (else (nthcdr (- n 1) (cdr l)))))
```

Avec machines : (1h1/2) Format des fichiers d'images bitmap BMP

une entête de 62 octets
des octets représentant une matrice de pixels (1 bit par pixel) stockée ligne après ligne en partant de la ligne du bas
2 octets nuls pour terminer

Exemple : le fichier 4pixels.bmp contient un dessin de 4 x 4 pixels dont les pixels noirs (*) et blancs (B) sont répartis comme suit :

B B B B 
B * * B 
B B B B 
B B B B

00001111 11111111 11111111 11111111 
01101111 11111111 11111111 11111111 
00001111 11111111 11111111 11111111 
00000101 01100110 00001010 01000000

Le fichier tintin87a.html contient une matrice de bits, chaque ligne contenant des sous-listes de 8 éléments 0 ou 1. En utilisant les fonctions applatit, nthcdr, nthcar vues en td, faire une fonction qui

applatit les lignes en supprimant les parenthèses internes qui délimitent les octets,
élimine les bits superflus en fin de ligne, qui ne sont pas des pixels, en ne retenant que les n premiers bits.

En utilisant la fonction (affiche l) du tp n°7, faire (dessine n fichier) qui trace la matrice de 0 et 1 obtenue, en fonction du nombre n de bits "utiles" par ligne (pixels).

tintin tintin87.bmp (matrice d'octets : tintin87.html, tintin87a.html, 87 pixels par ligne sur 12 octets = 3*4*8 = 96 bits, résultat de l'affichage : tintinaff.html)

Représentation en chiffres romains

> (romain->decimal '(m x l v i i)) 
1047

Le programme : romains.drs

Faire la fonction réciproque (dec->rom n) qui transforme un nombre en liste de chiffres romains (pour vérifier la conversion, on peut utiliser Excel en insérant une fonction "Math&Trigo" appelée "Romain", en mettant le nombre en 1er arg. et rien en 2ème pour le "type"). On obtient le tableau suivant :

1 I 11 XI 10 X 110 CX 210 CCX 100 C 1100 MC 1000 M

2 II 12 XII 20 XX 120 CXX 220 CCXX 200 CC 1200 MCC 2000 MM

3 III 13 XIII 30 XXX 130 CXXX 230 CCXXX 300 CCC 1300 MCCC 3000 MMM

4 IV 14 XIV 40 XL 140 CXL 240 CCXL 400 CD 1400 MCD 3100 MMMC

5 V 15 XV 50 L 150 CL 250 CCL 500 D 1500 MD 3200 MMMCC

6 VI 16 XVI 60 LX 160 CLX 260 CCLX 600 DC 1600 MDC 3300 MMMCCC

7 VII 17 XVII 70 LXX 170 CLXX 270 CCLXX 700 DCC 1700 MDCC 3400 MMMCD

8 VIII 18 XVIII 80 LXXX 180 CLXXX 280 CCLXXX 800 DCCC 1800 MDCCC 3500 MMMD

9 IX 19 XIX 90 XC 190 CXC 290 CCXC 900 CM 1900 MCM 3600 MMMDC

10 X 100 C 200 CC 300 CCC 1000 M 3700 MMMDCC

3800 MMMDCCC

3900 MMMCM

3999 MMMCMXCIX

4000 #VALEUR!

Scheme

1	I	11	XI	10	X	110	CX	210	CCX	100	C	1100	MC	1000	M
2	II	12	XII	20	XX	120	CXX	220	CCXX	200	CC	1200	MCC	2000	MM
3	III	13	XIII	30	XXX	130	CXXX	230	CCXXX	300	CCC	1300	MCCC	3000	MMM
4	IV	14	XIV	40	XL	140	CXL	240	CCXL	400	CD	1400	MCD	3100	MMMC
5	V	15	XV	50	L	150	CL	250	CCL	500	D	1500	MD	3200	MMMCC
6	VI	16	XVI	60	LX	160	CLX	260	CCLX	600	DC	1600	MDC	3300	MMMCCC
7	VII	17	XVII	70	LXX	170	CLXX	270	CCLXX	700	DCC	1700	MDCC	3400	MMMCD
8	VIII	18	XVIII	80	LXXX	180	CLXXX	280	CCLXXX	800	DCCC	1800	MDCCC	3500	MMMD
9	IX	19	XIX	90	XC	190	CXC	290	CCXC	900	CM	1900	MCM	3600	MMMDC
10	X			100	C	200	CC	300	CCC	1000	M			3700	MMMDCC
														3800	MMMDCCC
														3900	MMMCM
														3999	MMMCMXCIX
														4000	#VALEUR!