====== Números racionais ====== {{ fraction-bart.png?250|}}:!: Este projeto foi inicialmente proposto pelo prof. [[https://www.inf.ufpr.br/marcos/|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. ===== Tipos Abstratos de Dados ===== Conceitualmente, um [[https://en.wikipedia.org/wiki/Abstract_data_type|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. ===== Atividade ===== 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 {{tp1.tgz|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 {{tp1.pdf |enunciado}} foi produzido pelo prof. Castilho para este projeto. ==== Programa principal ==== 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 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 ... } ==== Exemplos de funcionamento ==== 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. === a) Todos os passos do algoritmo === 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: - 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; - consultar o arquivo ''racionais.h'' para mais detalhes e regras sobre as simplificações. === b) Fim antecipado 1 === 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: - 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; - 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; - consultar o arquivo ''racionais.h'' para mais detalhes e regras sobre a mensagem ''INVALIDO''. === c) Fim antecipado 2 === 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 ===== Entregáveis ===== 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.