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

recursividad en programacion

Question

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.

Answer 1

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

Answer 2

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