1) La classe Naturel utilisera un tableau de chiffres, du moins significatif au plus significatif. Un chiffre peut être représenté par un entier ou un caractère, mais le choix d'un entier est plus générale. La classe devrait avoir un certain nombre de constructeurs pour : - construir le Naturel 0 - construir un objet Naturel à partir d'un entier - construir un objet Naturel à partir d'une chaîne de caractères contenant la représentation décimale d'un nombre naturel - construir un objet Naturel à partir d'un autre objet Naturel (constructeur de copie) Des méthodes que la classe doit offrir sont : - les quatre opérations arithmétiques : Naturel addition(Naturel n), Naturel soustraction(Naturel n) [n doit être inférieur ou égal au naturel représenté par l'objet], Naturel multiplication(Naturel n), (Naturel, Naturel) division(Naturel n) [n ne doit pas être égal à zéro ; renvoie quotient et reste] - une opération de comparaison : entier compare(Naturel n) [0 si égal, <0 si inférieur, >0 si supérieur] - d'autres opérations : chaîne représentationDécimale() booléen premier() 2.1) Naturel addition(Naturel self, Naturel n) entier taille <- max(self.taille(), n.taille()) + 1; entier temp[taille] entier retenue <- 0 pour i de 1 à taille retenue <- retenue + self.chiffre[i] + n.chiffre[i] temp[i] <- retenue (mod BASE) retenue <- retenue/BASE tant que temp[taille] = 0 et taille>1 taille <- taille - 1; Naturel resultat <- Naturel() resultat.chiffre <- entier[taille] pour i de 1 à taille resultat.chiffre[i] <- temp[i] renvoyer resultat NOTE : la ligne retenue <- retenue + self.chiffre[i] + n.chiffre[i] ne pourrait pas être utilisée telle qu'elle est écrite dans un "vrai" programme, parce qu'elle pourrait lire au delà de la fin des tableaux et donnerait des erreurs. Tout de même, on l'a écrite comme-ça pour privilégier la clarté, parce que la manière "correcte" d'accomplir l'opération, c'est-à-dire si i <= self.taille retenue <- retenue + self.chiffre[i] si i <= n.taille retenue <- retenue + n.chiffre[i] aurait été aussi plus difficile à lire. Il faut aussi dire que l'on pourrait sauvegarder la lisibilité et la correction à la fois en déclarant une méthode entier chiffre(entier i) si i > 0 et i <= self.taille renvoyer self.chiffre[i] sinon renvoyer 0 et en modifiant la ligne incriminée en retenue <- retenue + self.chiffre(i) + n.chiffre(i) Quand on écrit du pseudocode, il est possible parfois de prendre ce type de licences, si on est sûrs de savoir ce qu'on est en train de faire... 2.2) Soient n et m les naturels sommés. Les tailles de leurs représentations sont O(log n) et O(log n) respectivement. Complexité en temps : O(max{log n, log m}). Complexité en espace : O(log n + log m + max{log n, log m}). 2.3) entier compare(Naturel self, Naturel n) si self.taille() < n.taille() renvoyer -1 si self.taille() > n.taille() renvoyer 1 pour i de taille à 1 entier diff <- chiffre[i] - n.chiffre[i] si diff!=0 renvoyer signe(diff) # si on est arrivés ici, les deux nombres sont identiques ! renvoyer 0 2.4) Pire cas : les deux nombres sont égaux ou ils diffèrent que pour la chiffre la moins significative : O(log n) Meilleur cas : nombres de taille différente : O(1) Cas moyen : (1 - epsilon)O(1) + epsilon O(log n). Puisque étant donnés deux naturels aléatoires la probabilité qu'ils soient égaux ou qu'ils diffèrents que pour le chiffre le moins significatif sera très petite (pour l'estimer il faudrait supposer une distribution de probabilité sur les naturels), pratiquement le cas moyen coïncide avec le meilleur cas ; l'incidence du pire cas serait donc négligeable et le meilleur cas serait le plus pertinent. 2.5) Il suffit d'adopter une représentation en base 1000 au lieu d'une en base 10. 3.1) On peut représenter un rationnel comme un signe (+ ou -), un numérateur naturel et un dénominateur naturel. 3.2) Pour faire l'addition de deux rationnels (du même signe), il faut multiplier le numérateur de l'un par le dénominateur de l'autre, sommer les deux naturels ainsi obtenus pour obtenir le numérateur du résultat, puis faire la multiplication des dénominateurs pour obtenir le dénominateur du résultat. Cela fait trois multiplication et une additions de naturels. En plus, on pourrait simplifier le résultat en divisant et le numérateur et le dénominateur par leur pgdc. 3.3) Pour faire la comparaison de deux fractions, il faut d'abord les rammener au dénominateur commun, comme on fait pour l'addition (= deux multiplications de naturels) ; ensuite, on pourra comparer les deux naturels ainsi obtenus (= même complexité de la comparaisons des naturels). Donc, la complexité sera du même ordre que deux multiplications et une comparaisons de naturels.