7 jours d'essai offerts
Cet ouvrage et des milliers d'autres sont disponibles en abonnement pour 8,99€/mois
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:avectrespeud'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 alabase 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 entiere 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 entiere 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