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: Sorteio de Brindes no SuperMercado Algorítmico

Data de Entrega: 21 de novembro de 2014, 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 2014-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!

O supermercado Algorítmico está fazendo uma promoção: quando faz uma compra, o cliente participa de um sorteio e, se agraciado, ganha um prêmio: um telefone celular que permite a rolagem da tela apenas com movimento dos olhos. (Exemplo: para mover o conteúdo da tela para cima o usuário faz movimentos com o olho na vertical, de baixo para cima.)

O sorteio é feito da seguinte maneira: o comprador fala um número entre 1 e 512. O posto mantém em um computador um vetor de inteiros com 256 posições. Este vetor é preenchido com números aleatórios entre 1 e 512. Você deve usar recursos da linguagem de programação para gerar os números aleatórios. O programa deve permitir criar um novo vetor a qualquer momento. Deve ser possível imprimir na tela este vetor, de forma limpa e compacta.

Quando o comprador fala um número, é feita uma pesquisa no vetor. Se o número estiver no vetor: o comprador ganha o prêmio. Implemente os algoritmos da Pesquisa Sequencial e Pesquisa Binária para fazer a busca do número no vetor. O programa deve contar o número de comparações realizadas em cada pesquisa.

Para executar a Pesquisa Binária é necessário antes ordenar o vetor. Você vai fazê-lo usando o algoritmo QuickSort e outro algoritmo da sua escolha. Seu programa deve contar quantas comparações cada método utiliza para ordenar o vetor. Para o QuickSort utilize duas estratégias de escolha de pivô: o primeiro elemento do vetor e o elemento que corresponde à mediana do primeiro, meio e último elementos.

Uma opção do menu deve permitir a execução de ordenações e buscas (TODOS os algoritmos) um número X de vezes. X é fornecido pelo usuário. O programa gera X vetores aleatórios e calculando a média do número de comparações utilizadas por todos os algoritmos de ordenação e pesquisa em cada vetor. O número para busca deve também ser gerado de forma aleatória para cada vetor aleatório. No log mostre médias calculadas para X=10, X=100 e X=1000.

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