java - 公司股权问题

Question

我刚刚在网上偶然发现了这个问题。它有点像这样。

有些公司持有其他公司的股份。我想知道一家公司是否拥有另一家公司。

所以，问题是这样的，如果公司 1 拥有公司 2 超过 75% 的股份，他就自动拥有它。另一个转折是，如果公司 1 拥有公司 3 超过 75% 的股份，而公司 3 拥有公司 2 超过 75% 的股份，那么公司 1 拥有公司 2。

这里有一个更清晰的例子:

Company 1 owns 50% of Company 2
Company 1 owns 75% of Company 3
Company 3 owns 25% of Company 2

Therefore, Company 1 owns Company 2

我认为这将涉及递归，按公司拆分所有权过程。但是，我无法弄清楚如何实现这一点。非常感谢您的帮助!

*更新:很抱歉没有正确定义问题。问题由记录组成，包含三个数据，如上所示，问题是找出某公司是否拥有另一家公司(例如公司 1 是否拥有公司 2？)。

所以我计划将每个所有权值存储给所有者(对于直接所有权)并减少间接所有者的所有权值(如果拥有 > 75%，则替换为下一个所有者)直到它到达基数。感谢您的建议!

Answer 1

我不对这份名单做任何假设，它可以有多长以及有多少公司参与其中。我也不假设所有公司都相互关联。列表可能会形成许多不同的所有权图。我还假设允许某种形式的共同所有权的场景是可能的(A 拥有 B 的 75%，B 拥有 A 的 75%，我承认这种情况很奇怪，但从数学上讲没有什么可以阻止这种情况发生)

可以这样解决绝对所有权的暴力算法:

第一步 - 确定一家公司与其他公司的所有关联。

Let C be the company of interest
Let A be the list of companies C has associations with.
Let Astar be a list of companies not already visited, initially containing C.
Let dist be the distance of companies from C, initially set to 0.

While Astar is not empty
    Let X be the first in Astart, remove X from Astar
    Add X to A
    dist++
    For each company Y that X has stakes in
        if Y is not in Astar, 
            Set Y.dist = dist
            Add Y to Astar

现在我们有一个 C 可能拥有的公司列表 (A)，原始列表中的所有其他公司都可以忽略。

现在让我们计算实际所有权。在这里，我们尝试计算 C 在所有其他公司中拥有的实际股份。如果 C 拥有 X 的 50%，而 X 拥有 Y 的 50%，则 C 拥有 Y 的 25%。考虑到 75% 的规则，如果在任何时候一家公司拥有另一家公司 70% 或更多的股份，我们将自动转换 75% % 到 100%。

Let X[] be an array containing the stakes X has in all other companies within A, initially set to 0

For each company in A
   Let X be the company the furthest away from C not already visited in A.
   Mark X as visited.
   For each edge E leading away from X to company Y
       if the Y is marked visited in A
           For each edge F leading away from Y to company Z
               Set X[Z] = F * E   
               If X[Z] >= 75%
                   Set F = 100%
                   remove visited mark on X
       else
           For each company W that Y has stakes in
              Set X[W] = Y[W] * E 

这将执行一种回溯算法，在建立所有权时重新评估股份。最后，您应该得到数组 C[]，其中包含 C 在所有其他公司中拥有的所有净股份。如果超过 75%，则 C 拥有它。

这是一个非常粗暴的算法，最好将两个过程合并为一个以使其成为一个更优雅的解决方案，尽管在这一点上我更喜欢获得有效的证据而不是看起来或表现良好的东西。我没有尝试过，只是在心里跑过，所以我可能会错得很离谱。但是我认为它会涵盖相互所有权周期。但是，要查看共同所有权，您必须为列表中的每个公司重复替换 C 的过程。这样您就可以直接从每家公司看到所有权的完整图片。

--- 编辑 ---

希望我没有误解，这个问题确实很难完全理解。如果我们有大量公司并且所有权以三元组定义，那么您可以通过让列表将所有三元组捆绑在一起来执行以下操作。这将创建一个更大的图，但解决一个图比解决一组相互依赖的图要容易得多