1

假设我正在解析如下语句：“布莱克比玛丽高，玛丽比苏高，山姆比玛丽矮，约翰比玛丽高”

看起来像：

Sue, Sam
Mary
John, Blake

也许：

Array(
    [0] => Array(
        [0] => Sue
        [1] => Sam
    )

    [1] => Mary
    [2] => Array(
        [0] => John
        [1] => Blake
    )
)

我们不知道 Sue 和 Sam 哪个更矮/更高，我们也不知道 John 和 Blake 哪个更矮/更高，所以他们坐在同一条线上。

但后来我可以给它声明：“布莱克比约翰短”，这将使它看起来像：

Sue, Sam
Mary
Blake
John

想法？我知道如果我只是尝试跳到这里我会把它弄得一团糟，所以我只是想知道代表它的最佳方式。像上面这样的数组还是树数组？

我正在考虑稍后给它一个问题，例如“谁更矮，布莱克还是苏？” 答案是苏。

4

1 回答 1

3

这可以用有向图来表示。当您有关于两个人身高的相对信息时，在他们之间添加一条边，使其指向较高或较短的人。（只要你始终如一，这无关紧要。）要查看某人是否比另一个人矮或高，请查看他们是另一个人的祖先还是后代。如果形成循环，则说明信息不一致。

在 PHP 中，您可能会有一个Person类。每个Person都会有一个Persons 数组，它们比它们高（短）。然后你会有一个Person对象数组。要创建链接，您需要将最高（最短）的人添加到最短（最高）人的较高（较短）数组中。

要测试人 A 是否比人 B 矮（高），从人 A 开始，然后递归所有直接和传递的高（矮）人。如果你到达 B 人，A 人比 B 人矮（高）。尝试交换 A 人和 B 人，看看是否会产生结果。如果仍然没有确定的结果，那么就没有足够的信息来确定人 A 和 B 的相对高度。

在信息不一致的情况下，如上递归会导致无限递归。

于 2013-05-29T04:20:37.373 回答