企业股权问题

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?)。

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

Answer 1

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

解决绝对所有权问题的Brute Force算法可以通过以下方式完成：

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

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