quarta-feira, 20 de dezembro de 2017

Problema da soma e subtração com números gigantes - overflow


Compartilhe!

O objetivo deste programa em C abaixo é fazer as operações de soma e subtração entre dois inteiros positivos grandes, dando como resultado da operação outro inteiro com até 30 dígitos.

O programa ainda possui um controle de erro para verificar se o valor do resultado tem mais de 30 dígitos, além do possível sinal de negativo ('-').

A entrada deve ser, por exemplo:
81
-
132

E a saída, nesse caso, deve ser:
000000000000000000000000000081
000000000000000000000000000132
-51

#include <stdio.h>

int main(){

    int a[31], b[31], r[32],
    dA=0, dB=0, dC, MAXIMO = 30, overflow = 0, zero = 1, 
    alg=0, vaiUm = 0, emprestaUm = 0, inverte=0, i=0;

    char c[MAXIMO+1], op;//Variáveis com inicializações.

    //Preencher os vetores a, b, c e r com zeros
    for(int p=0; p < MAXIMO; p++){
          a[p]=0; b[p]=0; c[p]=0; r[p]=0;
    }
    r[MAXIMO]=0;//Terminar de preencher o r.

    //Ler valor a (através do vetor de char c) e colocar no vetor a[].
    scanf("%s", c);
    for (dC=0;c[dC]!='\0';dC++);//Conta quantos dígitos tem c[].

    do{

        a[MAXIMO-dA-1] = c[dC-dA-1] - 48;//Colocar nas últimas posições do vetor a[] os valores de c[]. "-48" tem a ver com a conversão do char em int a partir da tabela ASCII.
        dA++;

    }while(dA!=dC);


    //Ler operação.
    scanf("%s", &op);

    //Ler valor b (através do vetor de char c) e colocar no vetor b[]. Exatamente a mesma coisa que o anterior.
    scanf("%s", c);
    for (dC=0;c[dC]!='\0';dC++);

    do{

        b[MAXIMO-dB-1] = c[dC-dB-1] - 48;
        dB++;

    }while(dB!=dC);

    //Verifica a operação de entrada sem realizar vaidação.
    if(op=='+'){//Se operação soma:

        for (int p=0; p < MAXIMO; p++){//A condição do for é parar quando percorrer todos os vetores r[] (vetor resposta), a[] e b[].
     
            alg = a[MAXIMO-1-p]+b[MAXIMO-1-p]+vaiUm;
        
            if (alg>9){ 

                alg = alg-10;
                vaiUm = 1;

            } else {

                vaiUm = 0;

            }

            r[MAXIMO-p]= alg;//Guarda no vetor resultado r[].

        }

        if(vaiUm) overflow = 1;//Se sobrou unidade é porque não deu para colocá-la no vetor, o que significa que não coube.

    } else {//Caso operação de subtração:

    //Quero verificar se o resultado será negativo ou positivo (sem realizar a operação, claro). Se negativo, quero que dê positivo para posteriormente colocar sinal de negativo: para isso, inverto a operação. Se positivo, a ordem será normal.

//Para descobrir se dará negativo, primeiro comparo o número de dígitos de A com o de B. Se menor, dará negativo. Se igual, terei que verificar qual é o primeiro dígito de A que é diferente de B na mesma posição dos vetores; encontrado esse valor, os comparo: se o dígito de A for menor que o de B, então dará negativo. Para todos os outros casos o resultado será positivo, e, quando for negativo, apenas inverterei a operação: em vez de A-B, será B-A e também será registrado que a ordem foi invertida, onde nesse caso guardo o valor 1 na posição 0 do vetor resultado r[], caso contrário (positivo) continua 0.

    if(dB>dA){ 

        inverte = 1;
    }
    else if(dA==dB){
        //printf("%d, %d", dA, dB);
        for(i=dA; (a[MAXIMO-i]==b[MAXIMO-i])&&(i!=0);i--);

        if(b[MAXIMO-i] > a[MAXIMO-i]&&i!=0) {
                  inverte = 1;
        }
    }

    //Realização da operação. Parecido com a operação de soma.
        for (int p=0; p < MAXIMO; p++){

            if (inverte){

                alg = b[MAXIMO-1-p]-a[MAXIMO-1-p];

            }else{

        alg = a[MAXIMO-1-p]-b[MAXIMO-1-p];

        }
            alg -= emprestaUm; 

            if (alg < 0){//Parecido com a operação de soma.

                alg = alg+10;
                emprestaUm = 1;

            } else {

                emprestaUm = 0;

            }

            r[MAXIMO-p]= alg;

        }

        if(emprestaUm){ 
    //Se faltou lugar para adicionar valor no vetor.
        overflow = 1;//Caso faltou: overflow.
        
    }else if(inverte) r[0]=1; //Registrar inversão de sinal. 

    }


    //Imprimir os resultados.
    for (int p=0; p < MAXIMO; p++)
    printf("%d",a[p]);//Imprime o vetor a[].

    printf("\n");

    for (int p=0; p < MAXIMO; p++)
    printf("%d",b[p]);//Imprime o vetor b[].

    printf("\n");

    if(overflow){//Imprime caso overflow.

        printf("overflow");

    }else{//Caso não houve overflow:

        if(r[0]) printf("-");//Imprime sinal negativo.

        for (int p=1; p < MAXIMO+1; p++)//Imprimi vetor resultado sem os zeros antes do número.
         if(r[p]!=0){//Encontrar um número diferente de 0 significa que a partir dessa posição começa o número.

                 zero = 0;//Se o resultado não for 0 de verdade, registrar isso.

                 for (int q=p; q < MAXIMO+1; q++)
                      printf("%d",r[q]);

                 break;//Para sair do for e não continuar mais, já que o número todo foi imprimido.

             }

        if(zero) printf("0");//Imprimir resultado zero se zero.

   }

    printf("\n");

    return 0;

}