Autor da análise: churrumino
Resumo
Dado uma matriz NxM, e 2 valores P e Q. Dividindo a matriz NxM em matrizes PxQ (consecutivas, ou seja, N % P = 0 e M % Q = 0), devolva a matriz PxQ que tiver a maior soma de seus elementos.
Solução
Para resolver este problema de força bruta. Teremos uma variável auxiliar que guardará o maior valor obtido até o momento, que será a saída. Começando em N=0 e M=0, lemos a primeira matriz que vai de 0x0 até (P-1)x(Q-1), e vemos se o valor somado é maior que a variável auxiliar; caso seja, substitui o valor da variável auxiliar. Depois avançamos M em Q unidades, e lemos a nova matriz que vai de 0xQ até Nx(Q+Q-1). Avançamos horizontalmente até que chegamos em Q. Feito isso avançamos N com P unidades, e voltamos Q ao início. Faremos esse laço até chegar a P.
Em palavras mais simples: irá ler um quadrado PxQ na matriz e procurar a soma dos valores, caso seja maior que a variável, substitui. Após isso vamos ao quadrado PxQ do lado, e assim sucessivamente até acabar a primeira "linha". Depois avançamos para o quadrado da linha de baixo, e faremos isso até acabar a matriz.
Supondo que a entrada seja uma matriz 4x4, e que P e Q sejam 2. A leitura será a seguinte:
1: | x x x x x x x x x x x x x x x x |
2: | x x x x x x x x x x x x x x x x |
3: | x x x x x x x x x x x x x x x x |
4: | x x x x x x x x x x x x x x x x |
Testes
Entrada
3 3 1 1
1 2 3
1 3 3
1 10 1
Saída
10
Discuta o problema
Gostei da sua explicação. Dei uns pitacos no texto. :-)
Agora … e se o problema for:
existe alguma relação com o problema da prova? O problema dessa prova é um caso especial?
Procure referências sobre o problema que eu enunciei acima. Leia e se achar interessante insira um pequeno texto relacionando os dois e dando para os próximos alunos a oportunidade de ir além.
Abraço,
wanderley