算法/递归树挑战

Question

我在尝试理解如何使用这个问题的递归时遇到了麻烦.我正在使用Ruby来解决它,因为这是迄今为止我所知道的唯一语言!

你有一些拥有其他公司的公司:

@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 }

例如,['A','B'] => 0.5意味着公司'A'拥有0.5(50%)的'B'.问题是定义一种方法,允许您通过拥有其他公司来确定特定公司(直接和间接)拥有多少公司.到目前为止我所确定的:

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

这将返回公司直接拥有的公司数组.现在,我正在考虑的是total_ownership方法的样子.

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

为了这个例子,让我们假设我们正在寻找 total_ownership('A','E')

显然,这不起作用.我无法弄清楚的是如何"存储"每个递归级别的值以及如何正确设置基本案例.如果你在Ruby中无法帮助我,我也不介意伪代码.

Answer 1

嗯，在我看来应该是

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