ruby - 算法/递归树挑战

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' 拥有 'B' 的 0.5 (50%)问题是定义一种方法，允许您确定特定公司通过拥有其他公司(直接和间接)拥有多少公司。到目前为止我确定的是:

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