root@blog:/# chmod o+r *

Hoje eu estava lendo alguns sites através do Google Reader e dentre todos os assuntos um se destacou. Foi um post do Sérgio Luiz do blog Vivaotux. Nesse post ele apresenta o seguinte problema:

Um fazendeiro tem um bando de porcos e um bando de galinhas. Ele sai para o terreiro e observa 20 cabeças e 56 pernas. Quantos porcos e quantas galinhas que ele tem?

O Sérgio apresentou uma solução em Python onde ele utilizava a 'força bruta' para achar a solução. Achei a solução muito bem elaborada, eu não teria conseguido pensado em algo assim! Confiram o código ao vivo no post dele aqui. Nos comentários deixei outra possibilidade de solução, e pensando agora, enquanto escrevo esse post, percebi que existe terceira forma de resolver esse problema!

Vamos primeiro abordar o problema...

Enquanto eu lia o código, me lembrei das aulas de álgebra linear e calculo numérico e pense: deve ter uma maneira mais direta de se resolver isso. Pegando o problema do início, o que temos é um sistema de 2 equações e 2 variáveis:

equação 1: numero_de_galinhas + numero_de_porcos = numero_de_cabecas
equação 2: 2*numero_de_galinhas + 4*numero_de_porcos = numero_de_pernas

Para ser mais matemático, vamos dizer que o numero de galinhas é X e o numero de porcos é Y. Para simplificar, vamos pegar o numero de pernas e cabeças dados no exemplo: 56 e 20, respectivamente. Reescrevendo a equação, e destacando as constantes unitárias temos:


equação 1: 1*X + 1*Y = 20
equação 2: 2*X + 4*Y = 56


As duas maneira que consegui pensar podem ser classificadas como simples e complexa. Vamos pela complexa primeiro...



Resolução de sistemas lineares através de matrizes

Um sistema linear pode ser representado por matrizes da seguinte forma:

[Coeficientes]*[Variaveis] = [Constantes]

Isto é, a matriz de coeficientes multiplicada pela matriz de variáveis é igual a matriz de constantes, onde a matriz de coeficientes é composta pelos coeficientes das variáveis X e Y, a matriz de variáveis é composta pelos próprios X e Y e a matriz de constantes é compostas pelas constantes após o sinal de igual. Dessa forma temos o seguintes:

Matriz coeficientes:

Código :

| 1     1 |
|         |
| 2     4 |

Matriz Variáveis:

Código :

| X |
|   |
| Y |

Matriz Constantes:

Código :

| 20 |
|    |
| 56 |

Juntando tudo temos:
Matriz coeficientes:

Código :

| 1     1 |   | X |   | 20 |
|         | * |   | = |    |
| 2     4 |   | Y |   | 56 |

Para resolver o sistema tudo que temos que fazer é isolar a matriz das variáveis:

Código :

| X |   | 1   1 |-1   | 20 |
|   | = |       |  *  |    |
| Y |   | 2   4 |     | 56 |

Isto é, a Matriz das variáveis é igual à multiplicação entre a matriz dos coeficientes inversa (por isso o -1) e a matriz das constantes.

Agora vem a mágica! Para fazer isso em Python só precisamos de um import! Segue o código:

Código :

from scipy import matrix
 
def resolve_fazenda(cabecas, pernas):
    # 1*galinhas + 1*porcos = cabecas
    # 2*galinhas + 4*porcos = pernas
    # Cria a matriz de coeficientes
    Mcoef = matrix([[ 1, 1], # Coeficiente da primeira equação
                    [ 2, 4]], # Coeficiente da segunda equação
                  )
    # Cria a matriz de constantes
    Mconst = matrix([[cabecas], [pernas]])
    # Calcula a multiplicação entre a matriz dos coeficientes inversa e a matriz das constantes
    # Aqui eu chamei ela de Matriz Solução
    Msolucao = Mcoef.getI()*Mconst
    # Apresenta a solução
    print 'Tem %s galinhas e %s porcos na fazenda!'%(float(Msolucao[0]), float(Msolucao[1]))
 
 
# Vamos fazer alguns testes!
resolve_fazenda(20, 56) #Tem 12.0 galinhas e 8.0 porcos na fazenda!
resolve_fazenda(21, 62) #Tem 11.0 galinhas e 10.0 porcos na fazenda!

Ok, agora a forma simples...



Solução algébrica por isolamento

Vamos retomar as equações (substituindo os valores constantes por C e P apra cabeças e pernas, respectivamente):
equação 1: X + Y = c
equação 2: 2*X + 4*Y = P

Isolando o X na primeira equação obtemos:
X = C - Y (equação 3)

Substituindo o X a equação 2 obtemos:
Y = (P/2) - C (equação 4)

Agora usamos as equações 3 e 4 para resolver o problema:

Código :

def resolve_fazenda2(cabecas, pernas):
    # Porcos = (Pernas/2) - Cabecas
    # Galinhas = Cabeças - Porcos
    porcos = float(pernas/2) - cabecas
    galinhas = cabecas - porcos
    # Apresenta a solução
    print 'Tem %s galinhas e %s porcos na fazenda!'%(galinhas, porcos)
 
 
# Vamos fazer alguns testes!
resolve_fazenda2(20, 56) #Tem 12.0 galinhas e 8.0 porcos na fazenda!
resolve_fazenda2(21, 62) #Tem 11.0 galinhas e 10.0 porcos na fazenda!

Em ambos os exemplos, vale a pena adicionar testes se os valores encontrados são inteiros porque, com certeza, não faz sentido ter "galinhas negativas" e "porcos negativos" no resultado!

Código :

>>> resolve_fazenda(10, 20)
Tem 10.0 galinhas e 0.0 porcos na fazenda!
>>> resolve_fazenda(11, 20)
Tem 12.0 galinhas e -1.0 porcos na fazenda!
>>> resolve_fazenda(12, 20)
Tem 14.0 galinhas e -2.0 porcos na fazenda!
>>>