Giải thuật cây/Thuật toán đệ quy

Question

Tôi đang gặp sự cố khi cố gắng hiểu cách sử dụng đệ quy với sự cố này. Tôi đang sử dụng Ruby để giải quyết nó bởi vì đó là ngôn ngữ duy nhất tôi biết cho đến nay!

Bạn có một số hash của các công ty sở hữu các công ty khác:

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

Ví dụ ['A','B'] => 0.5 có nghĩa là công ty 'A' sở hữu 0,5 (50%) 'B' Câu hỏi đặt ra là xác định một phương pháp mà cho phép bạn xác định bao nhiêu của một công ty một công ty cụ thể sở hữu (trực tiếp và gián tiếp) thông qua việc sở hữu các công ty khác. Những gì tôi đã xác định cho đến thời điểm này:

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

Điều này trả về một mảng các công ty trực tiếp sở hữu. Bây giờ, đây là những gì tôi đang nghĩ phương pháp total_ownership sẽ như thế nào.

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

Vì lợi ích của ví dụ này chúng ta hãy giả sử chúng ta đang tìm kiếm total_ownership('A','E')

Rõ ràng, điều này không làm việc. Những gì tôi có thể không thực sự tìm ra là làm thế nào để "lưu trữ" các giá trị của mỗi cấp đệ quy và làm thế nào để thiết lập các trường hợp cơ sở chính xác. Nếu bạn không thể giúp tôi với nó trong Ruby, tôi cũng không quan tâm đến mã giả.

Answer 1

Hmm, dường như đối với tôi nó phải được

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