Universidade Federal do Paraná
Departamento de Informática
Disciplina CI056 - Algoritmos e Estruturas de Dados II
2o Período do BCC, IBM, MI
Prof. Elias P. Duarte Jr.

Trabalho Prático 2 (2017/2, Turma A): A Mega Quina

Data de Entrega: 12 de novembro de 2017, sexta-feira -> são mais de 3 semanas de prazo, organize-se!

Os alunos devem informar por e-mail a URL do trabalho, usando o subject "TP2 ALGORITMOS II 2017-2" -- máximo cuidado para enviar exatamente este subject, OK?

OBS.: O trabalho deve ser feito em dupla; os dois membros da equipe devem se reunir para fazer todo o código!

Participe do sorteio da Mega Quina! Ganha o jogo quem acerta se 5 números estão em um vetor de números aleatórios, inteiros positivos. Se não acertar 5, quem sabe 4? Ou 3? Ou 2? Ou 1? Se não acertar nenhum, jogue de novo!

O programa da Mega Quina deve inicialmente receber como parâmetro de entrada o tamanho de um vetor de inteiros, que deve ser preenchido com números aleatórios de 1 até um valor máximo também fornecido como parâmetro. ATENÇÃO: deve ser possível imprimir na tela este vetor, de forma limpa e compacta.

Em seguida este programa permite que o usuário entre com 5 números inteiros positivos (na faixa permitida -- faça a consistência dos dados!). Informe ao usuário se ganhou o jogo, ou seja os 4 dos números fornecidos estão no vetor; informe também se 3, 2, 1 ou nenhum número está no vetor. Permita ao jogador jogar quantas vezes quiser. Se preferir faça a interface simples, na própria linha de comando.

Para cada número informado pelo jogador, utilize tanto a Pesquisa Sequencial como a Pesquisa Binária. Para cada pesquisa mostre quantas comparações foram utilizadas por cada método.

Para poder usar a Pesquisa Binária você ordenar o vetor. Ordene cada vetor de números aleatórios gerado com três algoritmos diferentes: SelectSort, BubbleSort, e MergeSort. Para cada ordenação, mostre (A) o número de comparações utilizadas e (2) o número de movimentações de elementos utilizadas.

No log, mostre execuções para vetores de tamanhos variados, mas inclua vetores de 8, 64, 256, 512 e 1024 elementos. Sugere-se que para um vetor de N elementos sejam gerados números aleatórios entre 1 e N, podem ser gerados números repetidos. Para aumentar as chances de ganhar você pode diminuir a margem em algumas execuções.

Deve ser construída uma página Web, que contém em documentos HTML, os seguintes itens:

  • Relatório de como foi feito o trabalho e quais foram os resultados obtidos. Use desenhos, diagramas, figuras, todos os recursos que permitam ao professor compreender como a dupla estruturou o trabalho e quais resultados obteve.
  • Listagem do programa em C;
  • Log dos testes executados: mostre explicitamente diversos casos testados, lembre-se à a partir desta listagem de testes que o professor vai medir até que ponto o trabalho está funcionando.

    Observações:

  • Não serão aceitos trabalhos impressos, nem em meio ótico/magnético.
  • Todos os trabalhos serão defendidos no laboratório, portanto certifique-se que seu trabalho funciona aqui!

    Importante: capriche na legibilidade e organização.

    Prof. Elias P. Duarte Jr.     Departamento de Informática     UFPR