Je viens de terminer mon examen dans un cours d'introduction C environ 20 minutes. La première question à l'examen m'a quelque peu pris garde à la garde et impliquait de trouver la différence deux grands nombres.
L'objectif était de prendre deux structures (N1 et N2) par valeur et stocker la différence dans une structure transmise par référence ( N3). Nous avons été autorisés à assumer que N3 a été initié avec tous les '0. La taille maximale peut être n'importe quoi, la solution doit donc toujours fonctionner si les chiffres sont supérieurs à 100 chiffres.
Voici le code de base (l'original peut être légèrement différent, c'est à partir de la mémoire) Le problème n'est pas tant dans la recherche d'une solution à Ce problème, mais que seulement environ 20 lignes ont été fournies pour la réponse complète. Ma méthode de résolution de la soustraction des chiffres 1 à la fois après la conversion en entiers, puis de faire des transactions appropriées si le résultat était négatif. Cela a pris substantiellement plus d'espace que ce qui a été fourni. sur la base de la petite quantité de marques et de l'espace prévu à cette question, je suis à croire qu'il y a une solution assez triviale 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, juste les fonctionnements internes de la fonction Aucun opérateur bitwise ne doit être utilisé, juste au cas où. différence .
3 Réponses :
Le problème de bignombre dans la plupart des classes informatiques est conçu pour que vous puissiez faire l'arithmétique «à la main» précisément comme vous le décrivez: Convertissez chaque caractère en un entier, soustrayez et empruntez le cas échéant.
Votre plan d'attaque , comme vous l'avez décrit, ne devrait être que quelques lignes. En pseudocode, quelque chose comme ceci: (plus un peu de tracas supplémentaire pour appliquer également la même logique sur les chiffres décimaux.) Ça sonne comme Vous avez eu la bonne idée et peut-être juste sur-pensée de la mise en œuvre?
Cela devrait fonctionner si n1> = n2 code>. Cela suppose également que les tableaux sont présentés comme dn ... D2D1D0.E0E1 ... EM CODE>. 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);
}
}
Vous devriez probablement descendre dans la deuxième boucle également.
C'était ma réponse originale, mais je ne pouvais pas vraiment la valider dans un cas où N2> N1. Je devrais probablement que je viens de le laisser comme ça, en regardant en arrière :( oh bien. Aussi, dans votre si (diff <0) ne doit-il pas ajouter d'autre pour revenir à un transport à 0?
Oh, et vous devriez ajouter '0' au résultat: n3-> décimaldigits [i] = diff + '0';
@avakar, je suppose que les matrices sont aménagées de sorte que les chiffres décimaux sont à droite, les chiffres sont à gauche et les indices zéro pour les deux rencontrent au milieu.
En ce qui concerne la règle sèche (ne vous répétez pas vous-même), je préférerais la fusion des chiffres et des décimaldigits dans un tableau, les exécutant à travers un cycle puis la division. :)
@avakar, je viens de réaliser que les chiffres sont constitués de matrices Char . @Voteydiscle et @ian, j'ai corrigé le bit porter .
Bien fait, bien que maintenant, j'ai envie de me tirer sur le pied pour être si proche et abandonner.
@Andrew, oui, le tableau de charme m'a attiré de la garde jusqu'à la fin, mais ce n'est pas une grosse affaire.
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 Bignum ailleurs. J'utilise 9's Complément pour simplifier / accélérer l'addition (pas de Poussky Port requis!) Avec une recherche de réponse basée sur une table (pourquoi calculer les sommes quand il n'y en a que 10?). La routine de soustraction de Bignum (à vos spécifications) suit:
void bigDifference(bigNum N1, bigNum N2, bigNum *N3) {
bigSum(N1, -N2, N3);
}
Pourriez-vous expliquer ce que
décimaldigit est censé être? En outre, 5482090-4813145 est un peu plus de 668944.;)Ce sont des chiffres avec point flottant - , par ex. N1 est comme 5482090.00049F.
Oh je vois. Cela explique également l'erreur bizarre hors-vue.