ventajas recursivos recursividad programacion iterativos ejemplos desventajas complejidad calcular analisis algoritmos ruby algorithm recursion tree

ruby - recursivos - Algoritmo/desafío del árbol de recursión



recursividad en programacion (2)

Hmm, me parece que debería ser

def total_ownership(entity, security) indirect = portfolio(entity).inject(0) do |sum, company| share = @hsh[[entity, company]] sum + (share || 0) * total_ownership(company,security) end direct = @hsh[[entity, security]] || 0 indirect + direct end

Tengo problemas para tratar de entender cómo usar la recursión con este problema. ¡Estoy usando Ruby para resolverlo porque ese es el único idioma que conozco hasta ahora!

Usted tiene algunos hash de firmas que poseen otras firmas:

@hsh = { [''A'',''B''] => 0.5, [''B'',''E''] => 0.2, [''A'',''E''] => 0.2, [''A'',''C''] => 0.3, [''C'',''D''] => 0.4, [''D'',''E''] => 0.2 }

Por ejemplo [''A'',''B''] => 0.5 significa que la empresa ''A'' posee 0.5 (50%) de ''B'' La pregunta es definir un método que le permita determinar qué tanto de una empresa una empresa en particular posee (directa e indirectamente) a través de ser dueño de otras firmas. Lo que he determinado hasta ahora:

def portfolio(entity) portfolio = [] @hsh.keys.each do |relationship| portfolio << relationship.last if relationship.first == entity end portfolio end

Esto devuelve una matriz de las empresas que una empresa posee directamente. Ahora, aquí está lo que estoy pensando en cómo se verá el método de propiedad total.

def total_ownership(entity, security) portfolio(entity).inject() do |sum, company| sum *= @hsh[[entity,company]] total_ownership(company,security) end end

Por el bien de este ejemplo, asumamos que estamos buscando total_ownership(''A'',''E'')

Obviamente, esto no funciona. Lo que realmente no puedo descifrar es cómo "almacenar" los valores de cada nivel recursivo y cómo establecer correctamente el caso base. Si no puedes ayudarme con eso en Ruby, tampoco me importa el pseudo-código.


def total_ownership(a, b) direct_ownership(a, b) + indirect_ownership(a, b) end def direct_ownership(a, b) @hsh[[a, b]] || 0 end def indirect_ownership(a, b) portfolio(a).map do |portfolio_item| @hsh[[a, portfolio_item]] * total_ownership(portfolio_item, b) end.inject(&:+) || 0 end