thoga31 Posted March 2, 2013 at 06:43 PM Report #497648 Posted March 2, 2013 at 06:43 PM (edited) Este é mais um desafio simples mas que acho divertido. Tem resolução por brute force ou por métodos matemáticos. Descrição: são vários os exercícios e jogos que envolvem os chamados quadrados mágicos. Estes são quadrados, geralmente 3x3, cujos elementos, em determinada ordem, cumprem determinados requisitos. Por exemplo: Objectivo: Considere-se as primeiras 9 potências de 2: [1,2,4,8,16,32,64,128,256]. Considere-se um quadrado mágico de 3x3. Pretende-se saber qual o quadrado mágico que, quando preenchido com estes números, os produtos das linhas, colunas e diagonais sejam iguais. Restrições: Não podem partir do quadrado mágico dito "convencional" (imagem anterior) para dar a solução. Isso é considerado fraude. Se querem evitar brute force, apliquem raciocínio matemático. Devem-se excluir repetições e quadrados invertidos. Para ser mais claro com exemplos: Invertidos: 2 7 6 | 8 3 4 9 5 1 | 1 5 9 4 3 8 | 6 7 2 Linhas vs colunas: 2 7 6 | 2 9 4 9 5 1 | 7 5 1 4 3 8 | 6 1 8 Espelho: 2 7 6 | 6 7 2 9 5 1 | 1 5 9 4 3 8 | 8 3 4 Tudo isto são consideradas repetições. Isto porque existe uma solução única e que, se o output inicial não for "tratado", poderá dar umas 8 soluções possíveis mas que são o mesmo. Verifiquem que outras situações podem existir que levam à multiplicidade de soluções. Analisem bem o caso e vejam a forma mais eficaz de os eliminar. Edited March 3, 2013 at 06:16 PM by thoga31 Restrições alteradas Knowledge is free!
thoga31 Posted March 2, 2013 at 08:49 PM Author Report #497664 Posted March 2, 2013 at 08:49 PM import Data.List (permutations) magicSquare = head . filter condition . map setTri . permutations . map (2^) $ [0..8] where setTri [] = [] setTri (a:b:c:xs) = [[a, b, c]] ++ setTri xs condition xs = line xs && row xs && diagonal xs where line (x:[]) = True line (x:xs) = (product x) == (product . head $ xs) && (line xs) row ((x:[]):(y:[]):(z:[]):_) = True row (x:y:z:_) = (product . map head $ [x, y, z]) == (product . map middle $ [x, y, z]) && (row . map tail $ [x, y, z]) diagonal (a:b:c:_) = product [head a, middle b, last c] == product [last a, middle b, head c] middle = head . tail main = mapM_ print magicSquare http://ideone.com/3jSRro Knowledge is free!
polska Posted March 3, 2013 at 12:57 AM Report #497681 Posted March 3, 2013 at 12:57 AM Eu não estou a perceber uma coisa.. Ao usarmos essas restrições encontramos apenas uma solução certo? Então o nosso programa mal encontre a primeira solução imprime e termina, não é necessário continuar pois só vai encontrar a mesma solução em repetições.. Ou estou há algo que me está a escapar? Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.
HappyHippyHippo Posted March 3, 2013 at 10:36 AM Report #497703 Posted March 3, 2013 at 10:36 AM Tem resolução por brute force ou por métodos matemáticos. desta vez decidi em vez de apresentar os cálculos matemáticos, apresentar por aplicação: #include <stdio.h> int main() { char magic[3][3] = {{2, 7, 6}, {9, 5, 1}, {4, 3, 8}}; // quadrado mágico convencional int i, j; for (i = 0; i < 3; i++) { for (j = 0; j < 3; j++) { printf("%3d ", 1 << (magic[i][j] - 1)); } printf("\n"); } return 0; } IRC : sim, é algo que ainda existe >> #p@p Portugol Plus
thoga31 Posted March 3, 2013 at 06:21 PM Author Report #497773 Posted March 3, 2013 at 06:21 PM Se assim o pedem... Restrições: Não podem partir do quadrado mágico dito "convencional" (imagem anterior) para dar a solução. Isso é considerado fraude. Se querem evitar brute force, apliquem raciocínio matemático. Eu não estou a perceber uma coisa.. Ao usarmos essas restrições encontramos apenas uma solução certo? Então o nosso programa mal encontre a primeira solução imprime e termina, não é necessário continuar pois só vai encontrar a mesma solução em repetições.. Ou estou há algo que me está a escapar? É exactamente esse o ponto: tu irias encontrar 8 soluções, e essas 8 são todas equivalentes. Logo, o truque está em parar a análise assim que se encontra uma solução. É por isso que na minha solução utilizei a função head: aproveitando a característica do Haskell de ser lazy, assim que o processo devolva uma solução, ele pára, pois essa primeira solução é a "cabeça" da lista total de soluções. Knowledge is free!
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now