Soustraction de grand nombre en C

Je viens de terminer mon examen dans un cours d’introduction au C il y a environ 20 minutes. La première question de l’examen m’a pris un peu au dépourvu et consistait à trouver la différence deux grands nombres.

Le but était de prendre deux structures (N1 et N2) en valeur et de stocker la différence dans une structure passée par référence (N3). Nous avons été autorisés à supposer que N3 était initié avec tous les ‘0’. La taille MAX peut être n’importe quoi, donc la solution doit encore fonctionner si les nombres sont supérieurs à 100 chiffres.

Voici le code de base (l’original peut être légèrement différent, c’est de la mémoire)

#include  #include  /* MAX can be any length, 10, 50, 100, etc */ #define MAX 10 struct bignum { char digit[MAX]; char decimaldigit[MAX/2]; }; typedef struct bignum bigNum; void difference(bigNum, bigNum, bigNum *); /* Original values in N1 and N2 N1.digit = { '0', '0', '0', '5', '4', '8', '2', '0', '9', '0'}; N1.decimaldigit { '0', '0', '0', '4', '9' }; N2.digit = { '0', '0', '0', '4', '8', '1', '3', '1', '4', '5'}; N2.decimaldigit { '8', '0', '1', '2', '0' }; */ /* Result would be: N3.digit = { '0', '0', '0', '0', '6', '6', '8', '9', '4', '4'} N3.decimaldigit { '1', '9', '9', '2', '9' } */ 

Le problème n’est pas tant de trouver une solution à ce problème, mais seulement environ 20 lignes environ ont été fournies pour une réponse complète. Ma méthode de résolution impliquait de soustraire les chiffres un à un après la conversion en nombres entiers, puis de créer des reports appropriés si le résultat était négatif. Cela a pris beaucoup plus de place que prévu.

Sur la base du petit nombre de marques et de l’espace prévu pour cette question, j’ai l’impression qu’il existe une solution assez sortingviale que je ne vois pas. Qu’Est-ce que c’est? J’ai maintenant terminé le cours mais cette question me dérange toujours!

Une solution complète n’est pas nécessaire, mais uniquement le fonctionnement interne de la difference fonction.

Aucun opérateur bit à bit ne doit être utilisé, juste au cas où.

Cela devrait fonctionner si N1 >= N2 . Cela suppose également que les tableaux sont disposés comme dn...d2d1d0.e0e1...em .

 char digchr(int); // Converts a single-digit integer into a character. void difference(bigNum N1, bigNum N2, bigNum *N3) { int carry = 0; for (int i = MAX / 2 - 1; i >= 0; i--) { int diff = N1.decimalDigits[i] - N2.decimalDigits[i] - carry; if (diff < 0) { diff += 10; carry = 1; } else { carry = 0; } N3->decimalDigits[i] = digchr(diff); } for (int i = 0; i < MAX; i++) { int diff = N1.digits[i] - N2.digits[i] - carry; if (diff < 0) { diff += 10; carry = 1; } else { carry = 0; } N3->digits[i] = digchr(diff); } } 

Le problème BigNumber dans la plupart des cours d’informatique est conçu pour vous obliger à faire l’arithmétique “à la main” exactement comme vous le décrivez: convertissez chaque caractère en entier, soustrayez et empruntez le cas échéant.

Votre plan d’attaque, comme vous l’avez décrit, ne devrait comporter que quelques lignes. En pseudocode, quelque chose comme ceci:

 for each character (right to left): difference = N1.digit[i] - N2.digit[i]; if (difference < 0) N1.digit[i - 1]--; difference += 10; N3.digit[i] = difference; 

(Plus un peu de tracas supplémentaire pour appliquer la même logique aux chiffres décimaux aussi.)

On dirait que vous avez eu la bonne idée et peut-être juste trop pensé à la mise en œuvre?

Cher professeur, la soustraction doit être définie en termes d’addition. J’ai surchargé l’opérateur “-” unaire et défini la routine d’addition de bignum ailleurs. J’utilise le complément de 9 pour simplifier / accélérer l’ajout (aucun report gênant requirejs!) Avec une recherche de réponse sous forme de tableau (pourquoi calculer les sums lorsqu’il n’y en a que 10?). La routine de soustraction bigNum (selon vos spécifications) est la suivante:

 void bigDifference(bigNum N1, bigNum N2, bigNum *N3) { bigSum(N1, -N2, N3); }