Blog ENI : Toute la veille numérique !
Accès illimité 24h/24 à tous nos livres & vidéos ! 
Découvrez la Bibliothèque Numérique ENI. Cliquez ici
Accès illimité 24h/24 à tous nos livres & vidéos ! 
Découvrez la Bibliothèque Numérique ENI. Cliquez ici
  1. Livres et vidéos
  2. Algorithmique
  3. Édition d'un nombre
Extrait - Algorithmique Raisonner pour concevoir (3e édition)
Extraits du livre
Algorithmique Raisonner pour concevoir (3e édition) Revenir à la page d'achat du livre

Édition d'un nombre

Introduction

Le problème de l’édition d’un entier a déjà été abordé au chapitre « Récursivité ». Ce court chapitre présente des exercices qui utilisent les techniques d’édition d’un entier pour résoudre quelques problèmes simples. La section « Édition d’un entier dans une base quelconque » commence par résoudre complètement un exercice posé au chapitre « Itération ». La section « Conversion des adresses Internet » traite du même problème, mais compliqué par la nature des nombres à convertir. La section « Conversion d’un nombre entier en chiffres romains » pose un exercice non résolu dans le livre, mais dont la solution complète est donnée dans les éléments en téléchargement, associés à cet ouvrage, disponibles depuis la page Informations générales. La section « Vérification des identifiants d’entreprises » présente les algorithmes qui permettent de vérifier la validité des identifiants d’entreprises et de leurs établissements. De même, la section « Vérification des identifiants de livres »...

Édition d’un entier dans une base quelconque

Ce problème a déjà été posé au chapitre « Récursivité » dans lequel la section « Nombres et chaînes de caractères : édition d’un entier » présentait le problème et un exercice en demandait une première solution. Dans cette section, l’exercice est résolu complètement. La section « Nombre de chiffres d’un entier » calcule le nombre de chiffres d’un entier exprimé dans une base B quelconque. La section « Résolution du problème d’édition » résout le problème proprement dit et la section « Résolution du problème réciproque » en fait autant pour la conversion d’un nombre exprimé dans une base B vers la base dix.

1. Nombre de chiffres d’un entier

On donne un entier n. Calculer le nombre de chiffres de la représentation de n en base B = dix. Remarquer d’abord que nous pouvons nous restreindre aux entiers positifs. Le nombre de chiffres d’un entier négatif est le nombre de chiffres de sa valeur absolue.

Obtenir les chiffres d’un entier est un problème qui sera résolu à la section suivante. Cependant, nous pouvons déjà voir qu’ils peuvent être successivement obtenus par une suite de divisions par B = dix. Le nombre n est divisé puis, successivement, tous les quotients obtenus, jusqu’à un quotient nul. Le nombre de chiffres est le nombre de divisions. Voyons cela sur un exemple.

Exemple

Calculer le nombre de chiffres de 325 exprimé en base dix.

Il suffit de diviser 325 par 10 :

  • la première division donne 32 et il reste 5 ;

  • la seconde division donne 3 et il reste 2 ;

  • la troisième division donne 0 et il reste 3.

Trois divisions ont permis d’atteindre un quotient nul. Le nombre de chiffres cherché est 3.

Remarquez aussi qu’il est possible d’arrêter l’itération dès que le quotient d’une division devient strictement inférieur au diviseur.

Écrire cet algorithme est facile et nous pouvons passer directement à la solution définitive. Il faudra cependant rester attentif...

Conversion des adresses Internet

1. Conversion d’un entier en adresse « Internet Protocol »

Les sections précédentes ont montré comment convertir un entier dans sa représentation dans une base B < 37. Cette limite s’imposait parce que nous ne disposons pas d’un ensemble de symboles facile à mémoriser pour représenter tous les chiffres d’une base B ≥ 37. Cette section montre comment résoudre cette difficulté sur un exemple courant en informatique.

a. Introduction

Chacun des composants actifs d’un réseau informatique (ordinateur, commutateur, routeur…) est identifié d’une façon unique par un entier positif de n octets, soit 8n bits, appelé son adresse du Protocole Internet (Internet Protocol ou IP). Pour la norme IPv4, une adresse IP est telle que n=4, soit 32 bits. Une adresse IPv4 est donc un nombre entier A tel que 0 ≤ A < 232 = 4 294 967 296. Ainsi, par exemple, tel ordinateur du réseau a pour adresse IP l’entier 2 886 342 405 en base dix.

Toute communication entre deux composants actifs d’un réseau utilise leurs adresses IP pour les identifier et distinguer ainsi sans ambiguïté l’émetteur et le récepteur du message parmi les autres composants. Il est évidemment difficile, pour un être humain, de retenir les adresses des composants d’un réseau dès que leur nombre dépasse quelques unités. On adopte alors une autre convention de représentation des adresses pour simplifier ces références.

Comme une adresse est constituée de quatre octets, on convient de représenter chaque adresse IPv4 par la valeur en base dix de chacun de ses quatre octets. Chaque octet est séparé du suivant par un point. Ainsi, l’adresse de l’exemple ci-dessus devient :

2 886 342 40510 ≡ 172.10.23.5 

La valeur en base dix d’un octet (8 bits) est un entier positif v qui vérifie :

0 ≤ v < 28 = 256 

Ainsi, les composantes de la représentation « humaine » d’une adresse IPv4 sont les chiffres, exprimés en base dix, de sa représentation en base B = 256. Autrement dit, pour cet exemple, 172, 10, 23 et 5 sont les chiffres, exprimés...

Conversion d’un nombre entier en chiffre romain

Exercice 4 : Conversions d’un nombre entier en chiffre romain

1. On donne un nombre entier positif. Définir un algorithme qui exprime ce nombre en chiffre romain.

2. Étudier la conversion réciproque.

Exemples

1912 = 'MCMXII'  
1999 = 'MCMXCIX' 

Comme souvent, ce problème n’est pas entièrement défini. L’analyse devra donc apporter les précisions nécessaires.

Solution

La solution de cet exercice n’est pas développée ici pour des raisons de place. Vous trouverez une solution complètement analysée et rédigée dans les éléments associés à cet ouvrage disponibles en téléchargement depuis la page Informations générales.

Vérification des identifiants d’entreprises

Chaque entreprise est identifiée par un numéro entier de 9 chiffres en base dix du Système Informatique pour le Répertoire des ENtreprises ou SIREN. Chaque établissement d’une entreprise est identifié, relativement à cette entreprise, par un numéro entier à 5 chiffres en base dix appelé le Numéro Interne de Classement ou NIC. Le nombre de 14 chiffres obtenu en regroupant, comme s’il s’agissait d’une concaténation, le numéro SIREN d’une entreprise et le NIC de l’un de ses établissements constitue le numéro du Système Informatique pour le Répertoire des ÉTablissements ou SIRET.

Exemple

La société PUBLITRONIC est identifiée par les nombres suivants :

SIREN : 319 937 454  
NIC   :             000 35  
SIRET : 319 937 454 000 35 

Les identifiants sont composés selon des règles dont l’étude dépasse le cadre de cette initiation. Cependant, une règle de cohérence peut être utilisée pour vérifier la validité d’un SIREN ou d’un SIRET. L’un de ces nombres est un numéro valide s’il satisfait à la règle de contrôle suivante :

Règle de contrôle d’un SIREN ou d’un SIRET...

Vérification des identifiants de livres

Un livre est identifié par un numéro appelé un International Standard Book Number ou ISBN. C’est un nombre de 10 chiffres qui repère la zone géographique ou linguistique d’édition, l’éditeur dans cette zone et, bien entendu, le livre chez cet éditeur. Depuis quelques années, l’introduction des codes-barres a fait évoluer cet identifiant en un nombre de 13 chiffres, le European Article Numbering ou EAN du système global d’identification univoque d’objets.

La structure d’un ISBN est donnée dans le tableau ci-dessous sur un exemple dont la valeur est 0-8436-1072-7.

Numéro de groupe

Préfixe d’éditeur

Numéro de titre

Contrôle

0

8436

1072

7

Le contrôle d’un ISBN consiste à réaliser des calculs basés sur la position, c’est-à-dire sur le rang du chiffre dans le nombre, et sa valeur. Les chiffres d’un ISBN sont numérotés de 1 à 10 en commençant par le chiffre des unités, c’est-à-dire le chiffre de contrôle. Chaque chiffre est multiplié par son rang et la somme des produits ainsi obtenus est divisée par 11. L’ISBN est valide lorsque le reste de cette division est nul.

Exemple

Vérifier la validité de 0-8436-1072-7.

Chiffres :  0  ...

Résumé

Ce chapitre a proposé des activités autour du problème de l’édition d’un nombre. Éditer un nombre, c’est déterminer sa représentation dans une base de numération donnée. Nous avons successivement étudié le calcul du nombre de chiffres d’un entier, son édition en chaîne de caractères et le problème réciproque. Nous avons ensuite résolu le problème de la représentation d’une adresse IP. Le problème de la représentation d’un entier en chiffres romains a été présenté et sa solution complète est disponible sur le site de l’éditeur. Les solutions au problème réciproque, qui consiste à transformer un nombre exprimé en chiffres romains en un entier, sont inspirées des solutions exposées dans [ARS80]. Les deux dernières sections ont étudié des algorithmes de vérifications, utilisés en informatique de gestion, pour contrôler la cohérence de la saisie des identifiants d’entreprises ou de livres.

Bibliographie

[ARS80] Jacques ARSAC : Premières leçons de programmation ; CEDIC/NATHAN, 1980.