PUC-Rio
Departamento de Informática
Profs. Edward Hermann Haeusler e Marcus Vinicius Poggi
Período: 2000.1
INTRODUÇÃO À ENGENHARIA (CTC 1002) (33B)
Projeto de Engenharia em Informática
Descrição: O trabalho consiste no desenvolvimento
de um algoritmo. Um algoritmo é uma caracterização precisa,
sem ambigüidades, de um
método para resolver um problema. Este algoritmo deverá estar descrito,
em sua versão final, de forma clara sobre uma notação completamente definida.
O trabalho será realizado por grupos de 3 ou 4 alunos (não
haverá exceções).
O problema a ser resolvido é o de propor a próxima jogada em um
jogo que confontrará dois algoritmos. Uma partida entre dois
jogadores consiste na aplicação alternada e sucessiva dos algoritmos
de cada jogador.
Uma implementação de um algoritmo é a sua realização em uma
linguagem de computação que execute em um computador capaz de
reconhecê-la.
A implementação do algoritmo desenvolvido pode ser feita em qualquer linguagem
de computação. Entretanto, embora esta iniciativa seja recomendada e agilize
a apresentação, a
implementação NÃO acrescentará pontos à avaliação.
Importante: caso o grupo deseje utilizar uma implementação do seu algoritmo
na apresentação, esta deverá ser entregue junto com sua versão final
em disquete e em listagem.
O Jogo:
Duplo Jogo-da-Velha 3D
-
O tabuleiro: Um cubo 3 × 3 × 3
que possui, portanto, 27 posições que podem ser ocupadas.
- Os jogadores: São dois, o jogador A e o jogador B, que
utilizam os símbolos 1, 2, 3 e 4. O jogador A terá como seus
símbolos o 1 e o 4, enquanto que o jogador B terá como seus o 2
e o 3.
- O andamento do jogo: Os símbolos devem ser colocados
no tabuleiro na ordem 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, ...; portanto
o jogador A sempre começa o jogo, sendo seguido por dois lances do
jogador B, que por sua vez será seguido por dois lances do jogador A
e assim sucessivamente.
- O vencedor: Vence o jogo o jogador cujo símbolo
vencer em um dos 9 jogos-da-velha que se entrelaçam no cubo, ou
que completar uma das quatro diagonais do cubo.
Para uma visualização mais clara, considere a vista frontal do cubo
com a seguinte numeração:
Primeiro Plano Segundo Plano Terceiro Plano
1 | 2 | 3 10 | 11 | 12 19 | 20 | 21
4 | 5 | 6 13 | 14 | 15 22 | 23 | 24
7 | 8 | 9 16 | 17 | 18 25 | 26 | 27
Assim, os restantes 6 jogos-da-velha usuais são:
1 | 2 | 3 4 | 5 | 6 7 | 8 | 9
10 | 11 | 12 13 | 14 | 15 16 | 17 | 18
19 | 20 | 21 22 | 23 | 24 25 | 26 | 27
1 | 10 | 19 2 | 11 | 21 3 | 12 | 21
4 | 13 | 22 5 | 14 | 24 6 | 15 | 24
7 | 16 | 25 8 | 17 | 27 9 | 18 | 27
As quatro diagonais do cubo são, portanto, (1, 14, 27), (3, 14, 25),
(7, 14, 21) e (9, 14, 19).
Em outra palavras, vence o jogador cujo símbolo COMPLETAR PRIMEIRO
uma das 49 triplas de posições no cubo que se seguem:
(1, 2, 3), (1, 4, 7), (1, 5, 9), (1, 10, 19), (1, 11, 21),
(1, 13, 25), (1, 14, 27), (2, 5, 8), (2, 11, 20), (2, 14, 26),
(3, 6, 9), (3, 5, 7), (3, 12, 21), (3, 11, 19),
(3, 14, 25), (3, 15, 27), (4, 5, 6), (4, 13, 22), (4, 14, 24),
(5, 14, 23), (6, 15, 24), (6, 14, 22), (7, 8, 9), (7, 16, 25),
(7, 13, 19), (7, 17, 27), (7, 14, 21), (8, 17, 26),
(8, 14, 20), (9, 18, 27), (9, 15, 21), (9, 17, 25), (9, 14, 19),
(10, 11, 12), (10, 14, 18), (10, 13, 16), (11, 14, 17),
(12, 15, 18), (12, 14, 16), (13, 14, 15), (16, 17, 18), (19, 20, 21),
(19, 22, 25), (19, 23, 27), (20, 23, 26), (21, 24, 27),
(21, 23, 25), (22, 23, 24) e (25, 26, 27).
Caso as 27 posições sejam preenchidas e nenhum símbolo complete uma
das triplas acima, o jogo termina EMPATADO e diz-se que ``deu Velha
3D!''.
Premiação:
O prêmio do melhor projeto em Informática será atribuído ao
grupo vencedor do TORNEIO que será realizado entre os algoritmos
concebidos.
A tabela do torneio será definida ao longo do mês de Maio, sendo
as partidas realizadas a partir da terceira semana de Junho.
Uma partida será a sequência de dois jogos onde cada grupo
jogará como jogador A e como jogador B. Caso um grupo vence os dois
jogos, este será obviamente o vencedor. Caso haja uma vitória para
cada grupo, será vencedor aquele que venceu o jogo com menos lances.
Nos demais casos, a partida será considereda empatada.
Caso a partida NÃO permita empates, serão jogados mais dois
jogos com o mesmo critério acima. Se o empate persistir,
haverá um cara ou coroa para decidir que foi o vencedor.
Decorrer dos Jogos: para que haja uma verificação exaustiva dos
algoritmos desenvolvidos, em uma partida os grupos executarão o
algoritmo do seu oponente. Se em algum momento um algoritmo é
incapaz de indicar uma posição válida (uma das 27 posições que esteja
vazia) para o seu símbolo, o seu grupo PERDE o jogo em andamento.
Avaliação: Será baseada na criatividade do projeto assim
como na capacidade de realização e desenvolvimento das idéias
apresentadas. A colocação no torneio também contribui para a nota,
que poderá ser distinta para membros de um mesmo grupo, visto que a
participação de cada aluno no projeto será avaliada.
Documentos a serem entregues:
28/04/2000 - Especificação do projeto a ser desenvolvido
Este documento deve apresentar a forma como o projeto será
apresentado e as idéias iniciais do grupo.
26/05/2000 - Especificação detalhada
Este documento apresenta para o algoritmo: uma descrição em
português do procedimento, geral e dos módulos utilizados; uma
descrição precisa dos passos que executam cada módulo; uma descrição funcional do projeto.
Junho/Julho - Versão final do projeto
Documento contendo a especificaão detalhada e o algoritmo
passível de ser executado (por pessoa ou computador). No caso de
implementação em alguma linguagem de computação, esta deve ser
entregue em papel e em meio magnético.
This document was translated from LATEX by HEVEA.