1

「ブレイクはメアリーより背が高く、メアリーはスーより背が高く、サムはメアリーより背が低く、ジョンはメアリーより背が高い」のような文を解析しているとします。

次のようになります。

Sue, Sam
Mary
John, Blake

多分：

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

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

スーとサムのどちらが背が低い/背が高いのかわからないし、ジョンとブレイクのどちらが背が低い/背が高いのかわからないので、2 人は同じ列に並んでいます。

しかし、後で、「ブレイクはジョンよりも背が低い」という文を与えることができます。これは、次のようになります。

Sue, Sam
Mary
Blake
John

考え？ここに飛び込もうとすると台無しになってしまうのはわかっているので、それを表現する最善の方法を考えていました。上記のような配列ですか、それともツリー配列ですか?

あとで「ブレイクとスーどっちが背が低い？」みたいな質問をしようと思っています。答えはスーです。

4

1 に答える 1

3

それは有向グラフで表すことができます。2 人の身長に関する相対的な情報がある場合は、身長の高い人または低い人のどちらかを指すように、2 人の間にエッジを追加します。(一貫している限り、これは問題ではありません。) 誰かが他の人より背が低いか高いかを確認するには、その人が他の人の祖先か子孫かを確認します。サイクルが形成されている場合、それは情報が矛盾していることを意味します。

PHP では、おそらくPersonクラスがあります。それぞれに、より背が高い (短い) のPerson配列があります。Person次に、オブジェクトの配列を取得しPersonます。リンクを作成するには、最も背の高い (背の低い) 人物を背の低い (背の高い) 人物の背の高い (背の低い) 配列に追加します。

人物 A が人物 B より背が低い (背が高い) かどうかをテストするには、人物 A から始めて、すべての直接的および推移的な背の高い (背の低い) 人物を再帰的に調べます。B さんに到達した場合、A さんは B さんより背が低い (背が高い) ということになります。A さんと B さんを入れ替えてみて、結果が得られるかどうかを確認してください。それでも明確な結果が得られない場合は、人物 A と B の相対的な身長を決定するのに十分な情報がありません。

情報が矛盾している場合、上記のように再帰すると無限再帰になります。

于 2013-05-29T04:20:37.373 に答える