アルゴリズム/再帰ツリーチャレンジ

Question

この問題で再帰を使用する方法を理解しようとしています。私はRubyを使って解決しています。なぜなら、それがこれまでに知っている唯一の言語だからです！

あなたが他の企業を所有する企業のいくつかのハッシュを持っている：例えば、['A','B'] => 0.5については

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

は、企業が「」「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 

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