Números racionais

Este projeto foi inicialmente proposto pelo prof. Marcos Castilho para a disciplina de Programação 1 (CI1001).

Este trabalho tem como objetivo a implementação de um Tipo Abstrato de Dados (TAD) para números racionais, além de praticar o desenvolvimento de programas na linguagem C. A partir deste trabalho passaremos a entender como escrever programas que usam mais de um arquivo fonte.

Conceitualmente, um Tipo Abstrato de Dados (TAD) é uma abstração do dado, isto é, das informações armazenadas em memória. No caso deste trabalho, o TAD em questão são números racionais (também conhecidos como frações).

A principal característica de um TAD é que a maneira como se armazena o dado na memória não é relevante para que se possa manipular os dados. Em outras palavras, basta conhecer a abstração e ter disponível um conjunto de funções que manipulam os dados abstratamente. No caso de números racionais, seriam funções para:

• construir um número racional, informando numerador e denominador
• simplificar um racional
• fazer operações aritméticas com racionais (+ - × ÷)
• comparar dois racionais (= < >)
• imprimir um racional
• …

Na linguagem C é possível implementar este conceito de maneira elegante pela construção de um módulo escrito em arquivos separados que definem concretamente como um racional é implementado e que também contém as funções que manipulam efetivamente estes dados.

Uma vez que o módulo está pronto, é possível construir programas que usem este módulo e nos quais o dado está abstraído. Isto é, quem constrói o programa principal (main) não precisa (nem deve) conhecer a implementação concreta. Em outras palavras, se o módulo define que um número racional é uma struct com este ou aquele campo, quem implementa o programa principal não deve acessar os campos da estrutura, mas apenas usar as funções que a manipulam.

Consulte a página sobre organização de código para uma explicação com exemplos.

Você deve implementar um programa que manipule números racionais, que são números da forma ^a/_b, onde a e b são números inteiros.

Você deve baixar este arquivo e abri-lo para poder fazer o trabalho, pois irá precisar de todos os arquivos ali contidos:

• racionais.h: arquivo de cabeçalho com os protótipos das funções (não deve ser alterado).
• racionais.c: arquivo que implementa as operações sobre números racionais (“esqueleto” a completar).
• tp1.c: código que usa a biblioteca de racionais (“esqueleto” a completar).
• makefile: arquivo do utilitário “make” para compilar seu código.

No arquivo racionais.h foi definida uma estrutura (struct) para o tipo abstrato de dados racional e os protótipos das funções que permitem manipular essa estrutura. Você deve implementar essas funções no arquivo racionais.c.

Este enunciado foi produzido pelo prof. Castilho para este projeto.

O programa principal (tp1.c) contém a função main. Ele deve incluir o header racionais.h e ter um laço principal que implemente corretamente em C o seguinte pseudocódigo:

inicialize a semente aleatória (uma única vez em todo o código)
- sugestão: use "srand (0)" para facilitar os testes

leia um n tal que 0 < n < 100
leia um max tal que 0 < max < 30

para todo i de 1 ate n faca
  /* use um único espaço em branco separando números na mesma linha */
  imprima o valor de i seguido de um ":" e um espaço em branco

  sortear dois racionais r1 e r2
  - os numeradores e denominadores devem estar entre 0 e max
  imprima r1 e r2, na mesma linha e não mude de linha
  se r1 ou r2 for inválido, então:
    imprima "NUMERO INVALIDO" e retorne 1

  calcule r1 + r2
  calcule r1 - r2
  calcule r1 * r2
  calcule r1 / r2
  se a divisão for invalida, então:
    imprima "DIVISAO INVALIDA" e retorne 1

  imprima na mesma linha r1 + r2
  imprima na mesma linha r1 - r2
  imprima na mesma linha r1 * r2
  imprima na mesma linha r1 / r2
  mude de linha
  
fim_para

retorne 0

Em C, a geração de números aleatórios é usualmente feita usando as funções srand e rand, conforme o exemplo abaixo:

#include <stdlib.h>
 
int main ()
{
   int x ;
 
   srand (0) ; // inicia a semente do gerador de aleatórios com 0
 
   ...
   x = rand () % 1000 ; // gera um aleatório entre 0 e 999 
   ...
}

O fluxo de execução e a saída do programa variam em função dos dados de entrada (n e max) e do valor inicial do gerador de números aleatórios.

Considerando n = 10, max = 17 e semente aleatória 10, o programa faz todas suas iterações:

10 17
1: 13/4 2/17 229/68 213/68 13/34 221/8
2: 12/17 5/13 241/221 71/221 60/221 156/85
3: 17/5 1 22/5 12/5 17/5 17/5
4: 0 2 2 -2 0 0
5: 3/8 17/12 43/24 -25/24 17/32 9/34
6: 6/5 7/13 113/65 43/65 42/65 78/35
7: 8 16 24 -8 128 1/2
8: 1/3 9/17 44/51 -10/51 3/17 17/27
9: 3/2 14/9 55/18 -1/18 7/3 27/28
10: 9 3/8 75/8 69/8 27/8 24

Observações:

1. repare, por exemplo, nas iterações 4, 7 ou 10, onde há números racionais que foram simplificados no formato VALOR/1, deixando de exibir o denominador;
2. consultar o arquivo racionais.h para mais detalhes e regras sobre as simplificações.

Nesta execução, com n = 10, max = 17 e semente aleatória 0, o programa executa até o primeiro retorne 1, com r1 ou r2 inválidos:

10 17
1: 1/16 9/7 151/112 -137/112 9/112 7/144
2: 5/7 5/6 65/42 -5/42 25/42 6/7
3: 15 14/13 209/13 181/13 210/13 195/14
4: 2 5/4 13/4 3/4 5/2 8/5
5: INVALIDO 8/5 NUMERO INVALIDO

Observações:

1. na quinta iteração, r1 seria 6/0, ou seja, um número racional inválido. Então, em vez de se exibir o número inválido, a mensagem INVALIDO é exibida em seu lugar;
2. não confundir a mensagem INVALIDO acima com a mensagem NUMERO INVALIDO do pseudocódigo (a mesma que está à direita de 8/5 no exemplo de execução;
3. consultar o arquivo racionais.h para mais detalhes e regras sobre a mensagem INVALIDO.

Nesta execução, com n = 10, max = 17 e semente aleatória 4, o programa termina após encontrar o segundo retorne 1 (da divisão inválida):

10 17
1: 7/5 5/4 53/20 3/20 7/4 28/25
2: 7/13 15/13 22/13 -8/13 105/169 7/15
3: 14/11 2/3 64/33 20/33 28/33 21/11
4: 1/2 13/6 8/3 -5/3 13/12 3/13
5: 10/7 15/11 215/77 5/77 150/77 22/21
6: 5/2 2/3 19/6 11/6 5/3 15/4
7: 9/16 0 DIVISAO INVALIDA

Entregue um único arquivo tp1.tgz que contenha por sua vez os seguintes arquivos:

• racionais.h: o mesmo arquivo fornecido, não o modifique
• racionais.c: sua implementação das funções definidas em racionais.h
• tp1.c: contém a função main que usa os racionais
• makefile

Importante:

• Use boas práticas de programação, como endentação, bons nomes para variáveis, comentários no código, bibliotecas, defines, etc. Um trabalho que não tenha sido implementado com boas práticas vale zero.
• Na dúvida, não tome decisões sobre a especificação, pergunte!
• Dúvidas podem e devem ser resolvidas durante as aulas.
• Dúvidas com relação a este enunciado devem ser solucionadas via e-mail para prog1prof@inf.ufpr.br, assim todos os professores da disciplina receberão os questionamentos.