MAC122 - Princípios de Desenvolvimento de Algoritmos - IME

Primeiro Exercício-Programa
Entregar até 18 22 de setembro

Representação e Manipulação de Números "Inteiros Grandes"

Muitas linguagens possuem tipos de dados ou bibliotecas que implementam números inteiros arbitrariamente grandes ("big integers"). Neste exercício-programa você criará uma implementação de "inteiros grandes" para a linguagem C. O objetivo do exercício-programa é representar números inteiros de comprimento (quase) arbitrário e implementar operações aritméticas com esses números. Você implementará as seguintes operações aritméticas com "inteiros grandes": + (adição), - (subtração), * (multiplicação), / (divisão inteira) e % (resto da divisão inteira). Você construirá também uma calculadora simplificada que efetua essas operações.

Como os números que vamos manipular podem ser muito grandes, eles não cabem em variáveis do tipo int ou long. Assim, para representar cada número, vamos utilizar um vetor inteiro que armazena em cada posição um dígito do número. Os valores dos dígitos decimais do número serão armazenados a partir da posição 1 do vetor, do dígito menos significativo para o mais significativo. A posição 0 do vetor conterá as informações de sinal e de comprimento (quantidade de dígitos decimais) do número, no formato especificado a seguir.

Especificação do formato para representação de "inteiros grandes"

Por exemplo, o "inteiro grande" -321938492382734 deverá ser armazenado num vetor indexado de 0 a 50 (MAX_DIGITOS), da seguinte forma:

-15 4 3 7 2 83 2 9 4 8 3 9 1 2 3? ? ... ? ?? ?? ? ? ?? ?? ? ? ?? ?? ?

Note que o número de posições do vetor que armazena um "inteiro grande" deve ser MAX_DIGITOS + 1, já que a posição zero tem um uso especial. No exemplo acima, note que o -15 na posição zero indica que o "inteiro grande" armazenado no vetor é negativo, que o valor do dígito mais significativo desse "inteiro grande" está na posição 15 do vetor, e que esse "inteiro grande" tem 15 dígitos decimais.

Note, ainda, que o comprimento dos nossos "inteiros grandes" não é completamente arbitrário, pois ele é limitado pela constante MAX_DIGITOS. Como é bem fácil aumentar o valor dessa constante, no início deste enunciado falamos em números inteiros de "comprimento (quase) arbitrário". Quando estudarmos alocação dinâmica de memória (um pouco mais adiante, nas aulas de MAC0122), veremos como se poderia alocar dinamicamente o vetor com os dígitos de um "inteiro grande" e, dessa forma, eliminar a limitação sobre o comprimento dos "inteiros grandes".

Funções que você deve implementar

Implemente em seu programa, obrigatoriamente, as funções cujos protótipos estão dados a seguir.
  1. void zera(int num[]);
    Coloca no vetor num o "inteiro grande" 0 (zero).

  2. int soma(int num1[], int num2[], int res[]);
    Soma o "inteiro grande" armazenado no vetor num1 com o armazenado no vetor num2. Coloca o resultado (que é outro "inteiro grande") no vetor res. No caso de overflow (estouro da capacidade, ou seja, vai-um quando da soma dos dígitos mais significativos), a função deve devolver o valor 0 (zero). Caso contrário, a função deve devolver o valor 1 (um).
    Esta função deve ser implementada por meio de uma chamada à função soma_mesmo_sinal ou à função soma_sinais_opostos (vide abaixo), dependendo dos sinais dos dois números.

  3. int soma_mesmo_sinal(int num1[], int num2[], int res[]);
    Recebe nos vetores num1 e num2 dois "inteiros grandes" com o mesmo sinal (ambos positivos ou ambos negativos) que são as parcelas a serem somadas. A função efetua a soma e coloca o resultado (que é outro "inteiro grande") no vetor res. Note que esta função supõe que ambas as parcelas sejam positivas ou ambas sejam negativas. Ela deve calcular |num1|+|num2| e acertar o sinal de res. No caso de overflow (vai-um quando da soma dos dígitos mais significativos), a função deve devolver o valor 0 (zero). Caso contrário, a função deve devolver o valor 1 (um).

  4. void soma_sinais_opostos(int num1[], int num2[], int res[]);
    Recebe nos vetores num1 e num2 dois "inteiros grandes" com sinais opostos e tais que o módulo do primeiro (num1) seja maior ou igual ao módulo do segundo (num2). A função soma os dois números e coloca o resultado (que é outro "inteiro grande") no vetor res. Como as duas parcelas têm sinais opostos, a operação efetuada é na verdade uma subtração: a função deve calcular |num1|-|num2| e acertar o sinal de res.

  5. int subtrai(int num1[], int num2[], int res[]);
    Subtrai o "inteiro grande" armazenado no vetor num2 do armazenado no vetor num1 (ou seja, calcula num1-num2). Coloca o resultado no vetor res. No caso de overflow (vai-um quando da soma dos dígitos mais significativos), a função deve devolver o valor 0 (zero). Caso contrário, a função deve devolver o valor 1 (um). Dica: Observe que o que esta função faz é somar num1 com o oposto de num2. Implemente-a com uma chamada à função soma.

  6. int multiplica(int num1[], int num2[], int res[]);
    Multiplica o "inteiro grande" armazenado no vetor num1 pelo armazenado no vetor num2. Coloca o produto (que é outro "inteiro grande") no vetor res. Para obter o produto, esta função emprega o algoritmo usual de multiplicação de dois números. (É claro que deve ser usada a função soma_mesmo_sinal e a função multiplica_digito, cujo protótipo aparece abaixo.) No caso de overflow (vai-um quando da soma dos dígitos mais significativos), a função deve devolver o valor 0 (zero). Caso contrário, a função deve devolver o valor 1 (um).

  7. int multiplica_digito(int num[], int d, int k, int res[]);
    Multiplica por d e por 10k o "inteiro grande" armazenado no vetor num. Coloca o resultado (que é outro "inteiro grande") no vetor res. Esta função pressupõe que o inteiro d satifaz 0 < d <= 9 e que o inteiro k é não negativo. No caso de overflow (vai-um quando da multiplicação pelo dígito mais significativo) a função deve devolver o valor 0 (zero). Caso contrário, a função deve devolver o valor 1 (um).

  8. int divide(int num1[], int num2[], int quoc[], int resto[]);
    Divide o "inteiro grande" armazenado no vetor num1 pelo armazenado no vetor num2. Coloca o quociente inteiro no vetor quoc e o resto no vetor resto. Para efetuar a divisão, esta função deve fazer subtrações sucessivas, chamando a função soma_sinais_opostos e a função soma1 cujo protótipo aparece abaixo. No caso do divisor (o "inteiro grande" no vetor num2) ser zero, a função deve devolver o valor 0 (zero). Caso contrário, a função deve devolver o valor 1 (um).

  9. void copia(int destino[], int origem[]);
    Recebe um "inteiro grande" no vetor origem e o copia para o vetor destino.

  10. int soma1(int num[]);
    Soma 1 (um) ao "inteiro grande" armazenado no vetor num. Devolve 0 (zero) em caso de overflow e 1 (um) caso contrário.

  11. int compara_modulo(int num1[], int num2[]);
    Compara os valores absolutos dos "inteiros grandes" armazenados nos vetores num1 e num2. Devolve o valor 1 (um) se o módulo do "inteiro grande" em num1 for maior do que o módulo do "inteiro grande" em num2. Devolve 0 (zero) se o módulo do "inteiro grande" em num1 for igual ao módulo do "inteiro grande" em num2. Devolve o valor -1 (menos um) se o módulo do "inteiro grande" em num1 for menor do que o módulo do "inteiro grande" em num2.
Sete das funções acima recebem vetores num1 e num2 com "inteiros grandes": soma, soma_mesmo_sinal, soma_sinais_opostos, subtrai, multiplica, divide e compara_modulo. Nenhuma dessas funções deve alterar o conteúdo do vetor num1 ou do vetor num2. Em outras palavras, no retorno de uma chamada a qualquer uma dessas funções, os vetores num1 e num2 devem continuar contendo os mesmos "inteiros grandes" que eles continham quando a função foi chamada. Se alguma dessas funções fizer alguma modificação no conteúdo do vetor num1 ou do vetor num2, a modificação tem de ser temporária: antes de retornar, a função deve restaurar o conteúdo original do vetor modificado. De modo análogo, a função multiplica_digito não deve alterar o conteúdo do vetor num e a função copia não deve alterar o contetúdo do vetor origem.

A calculadora

Usando as funções acima, escreva um programa C que trabalha com "inteiros grandes" e funciona como uma calculadora simplificada. A entrada do programa será uma sequência de linhas, cada uma contendo os dados para uma operação. Mais precisamente, cada linha da entrada conterá um número inteiro (precedido ou não de sinal), um operador, dentre os cinco possíveis, e um outro número inteiro (precedido ou não de sinal). Os cinco operadores permitidos são: + (adição), - (subtração), * (multiplicação), / (divisão inteira) e % (resto da divisão inteira).

A saída do programa será outra sequência de linhas (uma para cada linha da entrada) com os resultados das operações especificadas pelas linhas da entrada. Se ocorrer overflow ou divisão por zero, o programa deve imprimir uma mensagem de erro.

Aqui você encontra um exemplo de arquivo de entrada. Teste o seu programa com esse arquivo!

Aqui você encontra um arquivo com a saída do programa para o exemplo de entrada acima.

O arquivo de entrada e o de saída

O programa pedirá ao operador o nome do arquivo de entrada e o nome do arquivo de saída. Esta é uma possível interação do operador com o programa: 
Digite o nome do arquivo de entrada: entrada1.txt
Digite o nome do arquivo de saida: saida1.txt
Se o nome do arquivo de entrada for vazio (isso acontecerá caso o operador digite a tecla "Entra" quando o programa pedir o nome do arquivo de entrada, sem digitar nada antes da tecla "Entra"), o programa considerará que a entrada é a "entrada padrão" (stdin, normalmente associada ao teclado). De modo análogo, se o nome do arquivo de saída for vazio, o programa considerará que a saída é a "saída padrão" (stdout, normalmente associada à tela).

Se o nome do arquivo de entrada for não vazio, o programa lerá os dados de entrada do arquivo especificado. Se o nome do arquivo de saída for não vazio, o programa escreverá os dados de saída no arquivo especificado.

A criação de um arquivo de entrada

O arquivo de entrada deve ser um arquivo de texto puro (ASCII), sem informações de formatação. Para criar um arquivo de entrada, use o mesmo editor de texto que você usa para editar programas em C. Não use programas como o Word ou outros editores de texto que incluem no arquivo informações de formatação tais como tipos e tamanhos de fonts, dimensões das margens, distâncias entre linhas, divisão do texto em parágrafos, etc.

Certifique-se que o seu arquivo de entrada não contém linhas em branco no final, pois isso pode fazer diferença para o seu programa. Certifique-se também que todas as linhas do arquivo de entrada (inclusive a última) são terminadas por um caractere de fim de linha (new line).

A leitura do arquivo de entrada e a gravação no arquivo de saída

Para fazer a leitura de um arquivo de entrada e a gravação da saída em um arquivo, você precisa primeiro abrir o arquivo de entrada e o arquivo de saida. Faça isso utilizando a seguinte receita no seu programa: 

#define MAX_NOME_ARQ 256
    ...

    /*----- Declaracoes das variaveis para leitura e gravacao em arquivos -----*/

    char buffer[MAX_NOME_ARQ];           /* para ler os nomes dos arquivos */
    char nome_arq_entrada[MAX_NOME_ARQ] = ""; /* nome do arquivo de entrada */
    char nome_arq_saida[MAX_NOME_ARQ]= "";   /* nome do arquivo de saida */

    FILE *entrada;                       /* arquivo de entrada aberto */
    FILE *saida;                         /* arquivo de saida aberto */

    ...

    /*----- Primeiros comandos do seu programa -----*/

    /* Leitura do nome do arquivo de entrada */
    printf("Digite o nome do arquivo de entrada: ");
    fgets(buffer, MAX_NOME_ARQ, stdin);
    sscanf(buffer, "%s", nome_arq_entrada);

    /* Leitura do nome do arquivo de saida */
    printf("Digite o nome do arquivo de saida: ");
    fgets(buffer, MAX_NOME_ARQ, stdin);
    sscanf(buffer, "%s", nome_arq_saida);

    /* Se o nome do arquivo de entrada for nao vazio, 
       abre o arquivo de entrada para leitura ("r") */
    if (nome_arq_entrada[0] != '\0') {
        entrada = fopen(nome_arq_entrada, "r");
        if (entrada == NULL) {
            printf("Arquivo de entrada nao encontrado!\n");
            exit(1);
        }
    }
    else {
        entrada = stdin;
    }

    /* Se o nome do arquivo de saida for nao vazio, 
       abre o arquivo de saida para escrita ("w") */
    if (nome_arq_saida[0] != '\0') {
        saida = fopen(nome_arq_saida, "w");
        if (saida == NULL) {
            printf("Erro na abertura do arquivo de saida!\n");
            exit(1);
        }
    }
    else {
        saida = stdout;
    }

Tendo feito isso, a variável entrada se referirá ao arquivo de entrada e a variável saida se referirá ao arquivo de saída. Note que as variáveis entrada e saida tem um tipo especial (FILE *), que representa um arquivo aberto. É esse o tipo devolvido pela função fopen, que abre um arquivo para leitura ("r") ou para escrita ("w"). Observe, ainda, que esse é o único trecho do programa que usa os nomes dos arquivos. Esses nomes só são usados para abrir os arquivos. Daí para a frente, qualquer referência ao arquivo de entrada será feita por meio da variável entrada e qualquer referência ao arquivo de saída será feita por meio da variável saida.

No restante do seu programa utilize a função fscanf para ler dados do arquivo de entrada e a função fprintf para escrever dados no arquivo de saída. Essas funções (que também estão na biblioteca <stdio.h>) funcionam de modo semelhante ao scanf e ao printf. A única diferença é que elas recebem um parâmetro a mais, que especifica o arquivo do qual o fscanf lê os dados ou no qual o fprintf escreve os dados. Para informar ao fscanf qual é o arquivo de entrada, passe como parâmetro a variável entrada. Para informar ao fprintf qual é o arquivo de saída, passe como parâmetro a variável saida.

Caso o nome do arquivo de entrada seja vazio, a variável entrada conterá o valor stdin, que representa a "entrada padrão" (normalmente associada ao teclado). Nessa situação, quando você usar 

    fscanf(entrada, ...);
para ler dados da entrada, na realidade você estará executando uma chamada fscanf(stdin, ...), que é exatamente equivalente a uma chamada scanf(...).

De modo análogo, caso o nome do arquivo de saída seja vazio, a variável saida conterá o valor stdout, que representa a "saída padrão" (normalmente associada à tela). Nessa situação, quando você usar 

    fprintf(saida, ...);
para escrever dados na saída, na realidade você estará executando uma chamada fprintf(stdout, ...), que é exatamente equivalente a uma chamada printf(...).

Neste exercício-programa o arquivo de entrada deve ser lido caractere a caractere (utilizando-se o formato de leitura "%c"), pois os números são muito grandes para serem lidos com formatos numéricos como "%d" ou "%ld". Seu programa deve ler cada número como uma sequência de caracteres e converter o número para o formato de "inteiro grande".

Caso a entrada não seja a "entrada padrão", seu programa deve fechar o arquivo de entrada depois de ler todos os dados. Faça isso com a seguinte chamada: 

    fclose(entrada);

De modo análogo, caso a saída não seja a "saída padrão", seu programa deve fechar o arquivo de saída depois de gravar todos os dados. Faça isso com a seguinte chamada: 

    fclose(saida);

Funções adicionais para entrada e saída

As seguintes funções de entrada e saída devem ser implementadas:
  1. int le_linha_arquivo(FILE *arq, int num1[], int num2[], char *op);
    Tenta ler a próxima linha do arquivo de entrada arq. Se não houver próxima linha, devolve o valor 0 (zero). Caso contrário lê todos os caracteres da linha, inclusive o caractere new line presente ao final da linha. Neste caso a função armazena no vetor num1 o primeiro "inteiro grande" presente na linha lida, armazena em *op o operador (um caractere) presente na linha, armazena no vetor num2 o segundo "inteiro grande" presente na linha, e devolve o valor 1 (um).

    Esta função deve ser usada no programa principal, para saber se existe mais uma linha no no arquivo de entrada e para ler essa linha. Seu programa principal conterá uma repetição como esta: 

        while (le_linha_arquivo(entrada, num1, num2, &op)) {
        /* efetua a operação especificada na linha lida */
        ...
    }
  2. void escreve_numero_arquivo(FILE *arq, int num[]);
    Escreve no arquivo de saída arq o "inteiro grande" armazenado no vetor num.

Observações