Td bem... jah dei um jeito... Mas queria perguntar outra coisa: para n=4, fazendo backtracking, ele vai ficar beeeem custoso, neh? É normal ele não conseguir terminar? Pq no linux ele foi morto...
Ajudaria se eu usasse short int ou um char para representar a matriz? Quando complilo com a opção -O3, ele otimiza até que ponto o código?
Ajudaria se eu usasse short int ou um char para representar a matriz? Quando complilo com a opção -O3, ele otimiza até que ponto o código?
Querem uma dica que eu acho bem legal? Criem um vetor estático e associem a cada posição um caractere (esse vetor é de caracteres), tendo no máximo 10 caracteres numéricos (0-9) e tantas letras (no máximo 26) quanto vocês queiram. Resolvam o problema, mas ao invés de criar uma matriz de estruturas, façam uma matriz de inteiros que receba um índice desse vetor. Não é complicado né?
Backtracking é um tipo de algoritmo que é extremamente lerdo, mas é o único de busca exaustiva que vocês irão aprender. Para cara aumento de n, o trabalho dele aumenta em x^4, pois insere-se novos caracteres nas linhas e nas colunas. Considerando que é busca exaustiva, o trabalho aumenta muito mais. Qualquer tipo de otimização (vide dicas) ajuda bastante e pode tornar o algoritmo bastante rápido. Usar short int ajuda a diminuir o espaço ocupado pela matriz (é um ganho que você tem), mas não deve melhorar tanto o processamento.
Sugestão: ao testarem o código de vocês, escolham máquinas rápidas. As máquinas Windows do CEC serão muito lentas, ao passo que as Linux do CEC serão melhores. E as da Rede Linux não andam nos melhores dias.
É isso,
Abraços!
Backtracking é um tipo de algoritmo que é extremamente lerdo, mas é o único de busca exaustiva que vocês irão aprender. Para cara aumento de n, o trabalho dele aumenta em x^4, pois insere-se novos caracteres nas linhas e nas colunas. Considerando que é busca exaustiva, o trabalho aumenta muito mais. Qualquer tipo de otimização (vide dicas) ajuda bastante e pode tornar o algoritmo bastante rápido. Usar short int ajuda a diminuir o espaço ocupado pela matriz (é um ganho que você tem), mas não deve melhorar tanto o processamento.
Sugestão: ao testarem o código de vocês, escolham máquinas rápidas. As máquinas Windows do CEC serão muito lentas, ao passo que as Linux do CEC serão melhores. E as da Rede Linux não andam nos melhores dias.
É isso,
Abraços!
Os enunciados do EP parecem divergir um pouco da página do José para a página do Gubi, mas no "link oficial" desse EP, que é o da página do Gubi, diz apenas que o programa deve tratar 1<=n<=3, então a princípio eu não me preocuparia com os números acima de 9.
Quanto ao O3, se você tiver curiosidade pode ver exatamente o que ele faz nesta página:
http://gcc.gnu.org/onlinedocs/gcc-4.0.2/gcc/Optimize-Options.html
Quanto ao O3, se você tiver curiosidade pode ver exatamente o que ele faz nesta página:
http://gcc.gnu.org/onlinedocs/gcc-4.0.2/gcc/Optimize-Options.html
Com ordem 4 ele pode ficar bem demorado, principalmente se o problema não tiver solução. Mas para uma matriz vazia (só com pontos) deve rodar muito rapidamente.
A opção O3 ativa otimizações mais agressivas. A principal delas, para os programas que usamos no curso, é a transformação da chamada de funções pequenas em replicação do código, apesar de gastar mais espaço, ganha-se o tempo da chamada de funções. Existem outras otimizações, não habilitadas por -On, que nem sempre dão bom resultado.
Usar short ou char no lugar de int, para estruturas grandes, pode dar um aumento significativo de desempenho por causa da memória cache (uma memória mais rápida, usada para acessos freqüentes, mas de quantidade limitada).
A opção O3 ativa otimizações mais agressivas. A principal delas, para os programas que usamos no curso, é a transformação da chamada de funções pequenas em replicação do código, apesar de gastar mais espaço, ganha-se o tempo da chamada de funções. Existem outras otimizações, não habilitadas por -On, que nem sempre dão bom resultado.
Usar short ou char no lugar de int, para estruturas grandes, pode dar um aumento significativo de desempenho por causa da memória cache (uma memória mais rápida, usada para acessos freqüentes, mas de quantidade limitada).
Como disse a Vanessa, a página oficial do EP6 é a do Gubi. Que eu saiba, não havia links para essa versão preliminar do EP6. Em todo o caso, estou removendo o arquivo.
Resumindo: é para implementar para 1<=n<=3.
Zé Augusto
Resumindo: é para implementar para 1<=n<=3.
Zé Augusto
Entaum, na verdade, eu vi que tinha na página do gubi mesmo isso:
Para n>3, letras podem ser usadas para completar os dígitos.
E que havia exemplos de entradas para matrizes 4x4. Eh por isso q eu tinha perguntado...
Para n>3, letras podem ser usadas para completar os dígitos.
E que havia exemplos de entradas para matrizes 4x4. Eh por isso q eu tinha perguntado...