MAC-IME-USP IMRE SIMON CARLOS EDUARDO FERREIRA

SALA 290A TEL.: 3818 6142 SALA 297A TEL.: 3818 6140

EMAIL is@ime.usp.br E-MAIL cef@ime.usp.br

MONITORA: ELIDIA Y. ITIKAWA MONITOR: MARCIO C. CABRAL

MAC 122 - Princípios de Desenvolvimento de Algoritmos

Segundo semestre de 2000

Exercício-Programa 2 - Entrega: 17 de outubro de 2000

Montando Pentaminós
(pode ser feito em duplas)

Todos vocês sabem o que é um dominó: uma peça formada pela junção de dois quadrados iguais. Um pentaminó é uma peça formada pela junção de 5 quadrados iguais. Existem 12 tipos diferentes de pentaminós, mostrados na figura abaixo.

Uma pergunta que perseguiu muitos matemáticos durante algum tempo foi quais retângulos de área 60 é possível construir usando exatamente cada uma das peças acima uma única vez (note que podemos rodar as peças, virá-las, etc)?

Sua tarefa neste exercício-programa é resolver este problema. Dados inteiros m e n, tais que mn = 60 seu programa deverá achar, se for possível, um jeito de montar os 12 pentaminós de forma a construir o retângulo dado.

Observações

• Seja criativo. Se seu programa fizer algo a mais do que foi pedido você poderá ganhar algum bônus na nota.
• Fique a vontade para estender seu programa além do exigido no enunciado acima (tetraminós, hexaminós, heptaminós, etc). Fique a vontade para consultar a biblioteca a respeito do problema, porém seu programa deverá achar e mostrar uma configuração válida (não vale ter uma tabela com as respostas...).
• Pode ser que seu programa demore para achar uma solução.