Numeration positionnelle et conversion de base
12
pages
Français
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe en t'inscrivant gratuitement
Découvre YouScribe en t'inscrivant gratuitement
12
pages
Français
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
CHAPITRE IV Numeration positionnelle et conversion de base Algorithms + Data Structures = Programs Niklaus Wirth Objectifs ? Reviser la numeration en base b≥ 2 et l'algorithme de changement de base. ? Implementer une application surprenante : le calcul de e et de pi a une precision arbitraire. ? Preparer le terrain pour le calcul arrondi (chap. XV) et le calcul arrondi fiable (chap. XVI) Ce chapitre explique d'abord comment convertir la representation d'un nombre de la base 10 a la base 2, puis comment convertir entre deux bases quelconques. L'idee est simple, mais les applications sont etonnantes : avec tres peu d'analyse, cette methode permet de calculer quelques milliers de decimales de e = 2,71828 . . . Le projet traitera ensuite le calcul de pi = 3,14159 . . . Sommaire 1. Numeration positionnelle. 1.1. Un premier exemple : la conversion de la base 10 a la base 2. 1.2. Representation en base b. 1.3. Conversion de base. 2. Representation factorielle. 2.1. Calcul de e a 10000 decimales. 3. Quelques conseils pour une bonne programmation. 1. Numeration positionnelle 1.1. Un premier exemple : la conversion de la base 10 a la base 2. Rappelons d'abord la division euclidienne des entiers : pour tout a,b ? Z avec b 6= 0 il existe une unique paire (q,r) ? Z?Z telle que a = bq+ r et 0≤ r < |b|.
Voir
- representation factorielle
- representations au debut de la jeme iteration
- base factorielle
- application ?·?
CHAPITRE IV
Algorithms + Data Structures = Programs Niklaus Wirth
Num´erationpositionnelleetconversiondebase
Objectifs ◮ Reviser la nume´ration en base b ≥ 2 et l'algorithme de changement de base. ´ ◮ Imple´menter une application surprenante : le calcul de e et de ϑ a une pre´cision arbitraire. ◮ Pr´eparerleterrainpourlecalcularrondi(chap.XV)etlecalcularrondiable(chap.XVI) Ce chapitre explique d'abord comment convertir la repre´se ntation d'un nombre de la base 10 a la base2,puiscommentconvertirentredeuxbasesquelconques.L'id´eeestsimple,maislesapplicationssont ´etonnantes:avectr espeud'analyse,cettem´ethodepermetdecalculerquelquesmilliersded´ecimalesde e = 2 71828 Le projet traitera ensuite le calcul de ϑ = 3 14159 Sommaire 1.Num´erationpositionnelle. 1.1. Un premier exemple : la conversion de la base 10 a la base2. 1.2.Repr´esentationenbase b . 1.3. Conversion de base. 2. Repre´sentation factorielle. 2.1. Calcul de e a10000d´ecimales. 3. Quelques conseils pour une bonne programmation. 1. Nume´ration positionnelle 1.1. Un premier exemple : la conversion de la base 10 a labase 2 . Rappelons d'abord la division euclidienne des entiers : pour tout a b ∈ Z avec b 6 = 0 il existe une unique paire ( q r ) ∈ Z × Z telle que a = bq + r et 0 ≤ r < | b | . Dans la suite on utilisera la notation a div b : = q pour le quotient, et a mod b : = r pour le reste d'une telle division euclidienne. Exemple 1.1. Commenttrouverlarepr´esentationbinairedunombre11 6875 dec ? C'est facile pour la partie enti ere 1 d 1 ec = 1 2 3 + 0 2 2 + 1 2 1 + 1 2 0 = 1011 bin .Ced´eveloppements'obtientparunedivision euclidienneit´er´eeselonlesche´masuivant: 11 mod 2 = 1 et 11 div 2 = 5 5 mod 2 = 1 et 5 div 2 = 2 2 mod 2 = 0 et 2 div 2 = 1 1 mod 2 = 1 et 1 div 2 = 0 Pareil pour la partie fractionnaire 0 6875 dec = 1 2 − 1 + 0 2 − 2 + 1 2 − 3 + 1 2 − 4 = 0 1011 bin . Ici on multiplie par 2 au lieu de diviser, on extrait la partie enti ere et continue avec la partie fractionnaire : 0 6875 2 = 1 3750 0 3750 2 = 0 7500 0 7500 2 = 1 5000 0 5000 2 = 1 0000 Exercice/M 1.2. V´erierlaconversionde31 9 dec en binaire donne´e en chapitre I, page 12. Cette fois-ci onobtientunerepre´sentationbinairequiestp´eriodique.(Pourquoi?) 69
