公司股权问题

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 的过程。然后您就可以从每家公司直接看到完整的所有权情况。

--- 编辑 ---

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

Answer 2

我认为以下方法有效，但我没有彻底测试它。坦白说，我不确定我是否理解您的要求。

根据输入构建有向图。每个命名的公司都成为一个顶点。每条边代表公司之间的所有权关系，其权重等于所有权百分比。

要确定哪些公司属于特定公司，请使用以下伪代码：

Let company C be the company of interest
Let T be a table of all companies and their total ownership by company C
Let S be the set of companies completely owned by C, initially containing only C itself

While S is not empty:
    Choose an unvisited company X from S
    Mark X as visited
    For each edge leading away from X to another company Y:
        Add the edge's weight to T[Y]
        If T[Y] >= 75, add Y to S