RE: Dúvidas do EP3 de Est. de Dados

[Yoshiharu Kohayakawa <yoshi@ime.usp.br>]

Um aluno escreveu (on Friday, 1 Jun 2001, at 20:48:55 -0300):
 > Algumas dúvidas quanto o EP3 (contagem de poliminós) de E.D.:
 > 
 > -> Estava escrito na proposta que pode-se entregar até 2 versões do EP, uma 
 > elementar e uma caprichada. Há problema se se entregar só uma? 

Não, se você não implementar dois algoritmos substancialmente diferentes, não
é necessário você entregar 2 versões.

 >                                                                E se for 
 > entregar uma, deve ser bem caprichada ou pode ser "elementar"? 

Bem, deve ser a melhor que você tiver...!

 >                                                                Quanto da 
 > estratégia de Knuth deve ser aproveitada para que o EP não seja "elementar"? 

É algo difícil de se quantificar.  Uma idéia que faz grande diferença é a de
contar os poliminós sem efetivamente gerá-los todos explicitamente.

 > Usei a idéia dele de contar apenas os retângulos com altura maior ou igual à 
 > largura.
 >
 > -> Imagino que não seja esperado de nós que sejamos capazes de fazer um EP 
 > capaz de calcular o número de poliminós de até 46 quadrados. 

Ele consegue agora fazer para 47!

 >                                                              Qual um bom 
 > número "máximo" que o nosso EP deve ser capaz de calcular? Fiz uma primeira 
 > versão que faz os cálculos em "tempo útil" para até 8 quadrados. Para 9, 
 > demora uns bons minutos. Para 10, então...

Vamos ver o que a turma consegue!  Yoshi

 > Abraços!
 > 
 > [...]