[pyar] Problemita

[Jesús Francisco]

El día 10 de junio de 2010 17:35, Daniel Moisset
<dmoisset en machinalis.com> escribió:
> 2010/6/10 Marcos Moyano <marcos en anue.biz>:
>> Hola lista,
>> Les paso un problemita que me estuvo comiendo la cabeza un buen rato del día
>> de hoy y lamentablemente no encontré una solución elegante. Por ahi algún
>> valiente con ganas me tire una mano :-)
>>

Otra forma, de abajo a arriba, solo para variar

>> A) Mirar el triangulo/grafo:
>>    5
>>   9 6
>>  4 6 8
>> 0 7 1 51

Comparo de dos en dos y solo agarro el mayor. 0 con 7 da 7, 7 con 1 da
1 y 1 con 5 da 5. Supongamos que esa función se llama F

F([0, 7, 1, 5]) -> [7, 7, 5]

Se lo sumo al de arriba y me queda la siguiente pirámide:

5
9 6
11 13 13

Hago lo mismo con esta pirámide y obtengo

5
22 19

y por último, obtengo esta pirámide

27

>> B) Arrancando desde arriba (5) y moviéndonos para abajo a numeros
>> adyacentes, vayamos sumándolos. La suma máxima es: 5 + 9 +  6 + 7 = 27
>> (ejemplo de otros caminos posibles son: 5 + 6 + 8 + 5, 5 + 9 + 4 + 7, 5 + 6
>> + 6 + 7, etc.) (Notar el último ejemplo)
>>
>> Alguien me tira una idea de como modelaría la estructura de manera que sea
>> *simple* la solución?
>
> Para que sea simple, lo haria en haskell :) . Ah, [OT]
>
> Algo del estilo:
>
> maxsuma Vacio = 0
> maxsuma (Arbol subarbol_izq valor subarbol_der) = valor + max (maxsuma
> subarbol_izq) (maxsuma subarbol_der)
>
> Supongo que la idea igual te sirve.
>
> Saludos,
>   D.
> _______________________________________________
> pyar mailing list pyar en python.org.ar
> http://listas.python.org.ar/listinfo/pyar
>
> PyAr - Python Argentina - Sitio web: http://www.python.org.ar/
>