Grand Nombre de Soustraction en C

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

L'objectif était de prendre deux structures (N1 et N2) par valeur, et de stocker la différence dans une structure passés par référence (N3). Nous avons été autorisés à assumer N3 a été lancé avec tous les '0'. La taille maximale que peut être n'importe quoi, de sorte que la solution reste encore à travailler si les chiffres sont plus de 100 chiffres.

Voici le code de base (d'origine peut être légèrement différent, c'est à partir de la mémoire)

#include <stdio.h>
#include <stdlib.h>
/* 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 que seulement environ 20 lignes ont été fournis pour la réponse complète. Ma méthode pour résoudre impliqués soustrayant les chiffres un à un, après la conversion en nombres entiers, puis les porte si le résultat est négatif. Cela a pris beaucoup plus d'espace que ce qui était prévu.

Basé sur la petite quantité de marques et de l'espace prévu à cette question, je suis porté à croire qu'il y a une assez trivial solution que je ne suis pas voyant. Quel est-il? J'ai maintenant terminé le cours, mais cette question me tracasse toujours!

Une solution complète n'est pas nécessaire, seulement le fonctionnement interne de la fonction difference.

Pas les opérateurs sur les bits sont utilisés, juste au cas où.

Pourriez-vous expliquer ce decimaldigit est censé être? Aussi, 5482090-4813145 est un peu plus de 668944. 😉
C'est des nombres à virgule flottante - <chiffres>.<decimaldigits>, par exemple, N1 est comme 5482090.00049 f.
Oh, je vois. Cela explique aussi le bizarre tout-en-un message d'erreur.

OriginalL'auteur Ian Elliott | 2009-08-22

  1. 5

    Cela devrait fonctionner si N1 >= N2. Cela suppose également que les tableaux sont disposés comme des 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);
    }
}
    Vous devriez probablement décomptage ne dans la deuxième boucle.
    C'était ma réponse originale à cette question, mais je ne pouvais pas vraiment le valider dans un cas où N2 > N1. Je devrais probablement que je viens de quitter comme cela, en regardant en arrière 🙁 Oh bien. Aussi, dans votre if (diff < 0) ne devriez-vous pas ajouter un autre pour revenir procéder à 0?
    Oh, et vous devriez ajouter un '0' à la suite: N3->decimalDigits[i] = diff + '0';
    Je suis en supposant que les tableaux sont disposés de manière les chiffres décimaux sont sur la droite, les chiffres sont sur la gauche, et le zéro-indices pour les deux se rencontrent au milieu.
    Vous aurez besoin de réinitialiser carry à un certain point.

    OriginalL'auteur Andrew Keeton

  2. 10

    La BigNumber problème dans la plupart des cours d'Informatique est conçu pour vous faire avoir à faire le calcul "à la main" exactement comme vous le décrivez: convertir chaque caractère en un entier, soustraire, et emprunter le cas échéant.

    Votre plan d'attaque, comme vous l'avez décrit, ne devrait être que quelques lignes. En pseudo-code, 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;

    (Et un peu Plus compliqué à appliquer la même logique pour les chiffres décimaux).

    Cela sonne comme vous avez eu la bonne idée, et peut-être un peu plus réfléchi à la mise en œuvre?

    Merci pour le pseudo-code!

    OriginalL'auteur VoteyDisciple

  3. 3

    Monsieur le professeur, la soustraction doit être définie dans les termes de l'addition. J'ai surchargé le unaire "-" de l'opérateur, et défini les bignum ajout systématique d'ailleurs. Je suis en utilisant 9 complément simplifier/vitesse la plus (pas fichus de transporter!) avec une table en fonction de réponse de recherche (pourquoi calculer les sommes lorsqu'il y a seulement 10 d'entre eux?). Le bigNum soustraction de routine (à vos spécifications) suivante:

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

    OriginalL'auteur Chris Judge