Ver Feed RSS

root@blog:/# chmod o+r *

Quantos porcos e quantas galinhas?

Avalie este Post de Blog
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!
>>>

Atualizado 23-02-2010 em 16:27 por Magnun

Categorias
Python , Artigos , Artigos

Comentários

  1. Avatar de PEdroArthurJEdi
    Por força bruta? Huahuahua

    Já tinha visto esse problema na disciplina de Matemática Computacional. Resolvemos da maneira como você descreveu, por sistemas lineares.

    Bem lembrado do SciPy. Tem muito material na net. Junto com o Matplotlib dá para fazer umas brincadeiras muito legais. Ótimo para quem quer fugir dos pacotes proprietários ou tá com preguiça de aprender um novo software (Scilab, por exemplo).

    Mudando um pouco de assunto, tem uma apresentação muito boa sobre Python e Inteligência Computacional. Ela pode ser baixada em http://us.pycon.org/media/2009/talkd...009_AI_Alt.pdf (em inglês).
  2. Avatar de Magnun
    E ai PEdroArthurJEdi!!

    Acho que quando estudamos muito (principalmente quem faz engenharia), nosso cérebro passa a enxergar as coisas de forma diferente. Eu sou mestre pra fazer isso... Sempre escolho o caminho mais difícil pra resolver as coisas. Quando vi a solução do nosso colega, percebi a possibilidade de usar sistemas lineares, mas não me toquei que podia fazer uma substituição simples. Acabei buscando uma solução por matrizes.

    Vou baixar a apresentação e dar uma lida, valeu pela dica.
  3. Avatar de PEdroArthurJEdi
    Concordo contigo. Por isso dei gargalhada devido a solução por força bruta. Nunca tinha pensado em fazer dessa forma. E acho que seria a última coisa que teria tentado.

    Uma coisa que recomendo a todos que estudam computação ou áreas correlatas e que possuem bom conhecimento sobre programação, é que participem do ICPC da ACM (International Collegiate Programming Contest), a famosa Maratona de Programação. Participei de duas, o que exigiu muito estudo e dedicação. Vale muito a pena. Meus colegas de time e eu aprendemos diversas técnicas de programação e com certeza exercitamos muito essa capacidade de observar problemas por diferentes ópticas.

    Lembro de um problema que para resolver tivemos que tentar de três formas diferentes devido ao limite de tempo de execução do software.

    Enfim, não tem nada melhor que quebrar a cabeça com problemas bem elaborados ¹!

    ¹ Até tem... mas vamos desconsiderar por enquanto :-)
  4. Avatar de Magnun
    Com certeza cara... Ainda vou tentar participar dessas maratonas, mas o que me falta é um grupo pra isso! Pode ver que todos meus projetos eu desenvolvo sozinho. E o pior é q eu sei que o ideal é pelo menos ter mais um. Muitas vezes fixamos em um ponto e não vemos o restante, com alguém acompanhando isso é evitado facilmente.

    Até mais...
  5. Avatar de yjmenezes
    Muito legal o problema.

    Segue uma solucao com o Octave, outra joia de ferramenta.



    octave:1> A=[1,1;2,4]
    octave:2> L=[20;56]
    octave:3> x=inv(A)*L

    x =
    12
    8

    []s
    julio
  6. Avatar de beirsdorf
    só minha ex-professora Elda com sistemas lineares para responder isso.

+ Enviar Comentário



Visite: BR-Linux ·  VivaOLinux ·  Dicas-L