Chapitre 8 : Bases de numération

8.1 Les différentes systèmes de numération :

	1) Le système décimal : base dix

(328)dix = 8 + 2*10 + 3*10²

plus généralement
(an an-1 ...a1 a0)dix =  ai 10i

	2) Le système binaire : base deux

- chiffres : 0 et 1
- (an an-1 .... a1 a0)deux= ai 2i  	ai appartient à {0,1}
ex : (1101)deux 	= 1 + 0*2 +1*22 + 1*23
				= 1 + 4 + 8
				= 13
pour décomposer un entier en base 2
(35)dix 	= ( ? )deux
		= (100011)deux

35	/	2
1		17	/	2
		1		8	/	2
				0		4	/	2
						0		2	/	2
								0		1	/	2
										1		0
	3) Le système octal : base huit

- chiffres : 0, 1 , 2, 3, 4, 5, 6, 7
- (an an-1 ... a1 a0) =  ai 8i
exemple : (127)huit 	= 7 + 2*8 + 1*8²
					= 87

pour décomposer un entier en base huit
35 	/ 	8
3		4 	/ 	8
		4		0

(35)dix = (43)huit

	4) Système hexadécimal : base seize

- Chiffres : 0, ..., 9, A, B, C, D, E, F
- (an an-1 .... a1 a0)H =  ai 16i
- (1AB)H 	= 11 + 10*16 + 1*16²
			= 11 + 160 + 256
			= 427

pour décomposer un entir en base seize :

632	/	16
152		39	/	16
8		7		2	/	16
				2		0

(632)dix = (278)H

	5) Plus généralement : base b 	(b appartient à N, b >= 2)

- chiffres : b symboles qui représentent les entiers 0, ..., b-1 (en général, on prend les dix premiers : 0, ..., 9

- (an an-1 ... a1 a0)b =  ai bi

pour décomposer u entier N en base b
rappel : 	division euclidienne de a par b
		soit (a appartient à N) et (b appartient à N*)
		alors il existe 2 entiers uniques q et r tels que :
a = bq + r et 0 <= R < b

Remarque : notation :
	q = a div b
	r = a mod b

pour décomposer N en base b, on effectue les divisions euclidiennes par b
=> tout entier a une écriture unique en base b

Remarque :
dans toute base, (0)b = 0

faire la table représentant les 20 premiers entier naturels dans les base Dix, deux, huit, seize :

8.2 Propriétés de l'écriture en base b

	1) Multiplication par la base

N s'écrit (an... a1 a0)b 

b*N s'écrit (an....a0 0)b : on décale l'écriture de N de 1 rang vers la gauche

	1) Division par la base

N s'écrit (an ... a1 a0)b
N div b s'écrit (an ... a1)b on décale de 1 rang vers la droite
N mod b = a0

8.3 Transcodage

Passage d'une base à une autre
- passage d'une base b au décimal : vu
- passage du décimal à la base b : vu

algorithme ecrire_en_base_b
Déclaration n, b, chiffres des entiers
Début
	demander_une_valeur_pour N
	demander_une_valeur_pour b
	tant_que (N > 0) faire
		affecter_la_valeur de N mod b à chiffres
		affecter_la_valeur_de N div b à N
		montrer_la_valeur_de chiffres
	fintq
fin

passage d'une base à une autre : on passe par la base 10

sauf :
pour passer  du binaire à l'octal
M 	= (1101011)dix
	= 1 + 1*2 + 0*2² + 1*2³ + 0*24 + 1*25 + 1*26
	= app à [0,7]  + 2³ (1 + 0*2 + 1*2²) + (2³)² (...)
	= (153)huit
pratiquement : 
- on ajoute des z&ros à gauche de manière à obtenir un nombre de chiffres multiple de 3
- on groupe les chiffres binaires par 3 et on les remplace  par l'écriture qu'elles représentent

ex : M 	= (10011)deux
		= (010 011)deux
		= (2 3)huit

passage du binaire à l'héxadécimal
pareil mais les groupements se font par 4
N 	= (101011)deux
	= (0010 1011)deux
	= (2 B)H
l'hexadécimal est utilisé pour coder les octets (8 bits)
un octet = b7 b6 b5 b4 b3 b2 b1 b0
		= 2 chiffres hexadécimaux

8.4 Réprésentation des nombres fractionnaires an base b

Les nombres sont supposés positifs

	N un décimal

	Ent(N) désigne la partie entière de N
	Ent(N) < N < Ent(N)+1
	frac(N) est la partie fractionnaire de N
	frac(N)=N-Ent(N)
	ex : N = 3.72
		Ent(N)=3
		frac(N)=0.72
Exemple :
(13.72)dix  = 1*101 + 3*100 + 7*10-1 + 2*10-2

1) Ecriture des nombres fractionnaires en base b
N = (an an-1....a1a0, a-1...a-k)
représente le décimal :
 (i=-k à n) aibi		0<= ai <b
					an<>0
					a-k<>0

(23,71)huit 	= 2* 8 + 2 + 7*8-1 + 1*8-2
			= 19 + 7/8 + 1/0.8
			= 19, 890625

La précision est le nombre de chiffres de la partie fractionnaire

2) Multiplication et division par la base

N = (an an-1... a1a0,a-1...a-k)b
b×N = (an...a0 a-1, a-2...a-k)b on déplace la virgule de 1 rang à droite
N/b = (an....a1,a0...a-k)b on déplace la virgule de 1 rang à gauche

N*8 = (237,1)huit = (23,71)huit * (10)huit
N/8 = (2,371)huit

3) Passage du décimal au binaire

exemple : (0,101)deux = 1*2-1 + 0*2-2 + 1*2-3
					= 1/2 + 1/8
					= 0.5 + 0.125
					= 0.625

Problème inverse

N un décimal = (?)deux
N = (0,a1 a0....a-k)deux
N * 2 = (a-1,a-2,....a-k)deux
Ent(N*2) = a-1
N*2 - a-1 = (0,a-2....a-k)deux
on recommence
....

N=0.3

2*0.3 = 0.6 	=> a-1=0
2*0.6 = 1.2 	=> a-2=1
2*0.2 = 0.4	=> a-3=0
2*0.4 = 0.8	=> a-4=0
2*0.8 = 1.6	=> a-5=1
2*0.6 STOP

(0.3)dix = (0,010011001...1001...)deux

Récapitulatif :
Pour écrire un décimal N en base 2
1) on écrit la partie entière de N en base 2
2) on écrit la partie fractionnaire de N en base 2 en utilisant l'algorithme suivant

Algorithme décomposition d'un nombre fractionnaire en base 2
Déclaration 
	precision, b, chiffres des entiers
	N, aux des nombres fractionnaires
Début
	Demander_une_valeur_pour N
	Affecter_la_valeur_de N à aux
	Demander_une_valeur_pour b
	Demander_une_valeur_pour precision
	Tant que (aux>0)  ou (precision=0) faire
		Affecter_la_valeur_de b*aux à aux
		Affecter_la_valeur_de precision-1  precision
		Affecter_la_valeur_de Ent(aux) à chiffre
		Montrer_la_valeur_de chiffre
		Affecter_la_valeur_de aux-chiffre à aux
	Fintq
Fin