算法/遞歸樹挑戰

我在試圖理解如何對這個問題使用遞歸時遇到了麻煩。我使用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中不能幫助我，我也不介意僞代碼。

來源

2012-04-15 Alexander Lucic

+1有趣的問題。如果是作業，它應該被標記爲這樣。 – steenslag 2012-04-15 22:38:04

爲了確認，total_ownership（'A'，'E'）的解決方案是（0.5 * 0.2）+ 0.2 +（0.3 * 0.4 * 0.2）？ – sunnyrjuneja 2012-04-15 22:45:30

不！只是一個問題，我想知道如何解決遞歸問題。謝謝你的提示，雖然 – 2012-04-15 22:47:11

嗯，在我看來，它應該是

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

來源

2012-04-15 23:00:03

非常感謝你的幫助;它現在更有意義 – 2012-04-15 23:19:57

現在的獎金挑戰。如果A公司擁有B公司，B公司擁有A公司的股票投資組合？你的代碼打破了... – btilly 2012-04-16 00:31:29

沒錯，雖然問題確實提到了「樹」... – 2012-04-16 06:53:27

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

來源

2012-04-15 23:04:42 Leventix

感謝您的替代方法！ – 2012-04-15 23:20:34

算法/遞歸樹挑戰

回答

相關問題