2010-12-02 3 views
0

私はお互いに人の配列を照合しています。彼らは自分自身と一致することはできませんし、各人は他の人と一致することができます。私はこれを取り組んだが、端のケースに遭遇した。一致している人物が自分とまだ一致していない唯一の人物である場合、私たちは立ち往生しています。ギフト寄付のために人の配列を照合する、このエッジケースを扱う方法

例:

$names = array('Dad','Mom','Harrald','Yu','Sandra','Dave', 'Andy & Kim'); 
$drawn = array(); 
$tn = count($names)-1; 
$i = mt_rand(0, $tn); 

foreach ($names as $name) {   
    while($name == $names[$i] || in_array($names[$i], $drawn)) { 
      $i = mt_rand(0, $tn); 
    } 
    echo $name. ' has ' . $names[$i].'<br />'; 
    array_push($drawn, $names[$i]); 
} 

これは作り出すことができる:
お父さんはサンドラ
ママゆう
Harraldはデイブ
...などを持っている持っている、など

ときに問題があります'Andy & Kim'がまだに追加されていない唯一の要素である場合、配列の最後の要素に到達します。 'Andy & Kim'配列の場合、 'Andy & Kim'を自分自身にマッチさせることができないため、端点ケースが発生します。私の例では、これはループ中に閉じ込められ、最終的にタイムアウトになることがあります。あなたはこれをどう対処しますか(これは私のおかげで、私のお母さんがマッチアップスクリプトを使って、これが潜在的な問題であることを理解したことに気づきました)。

ああ、このようなパターンを実装するより良い方法は、最も興味深いものです。どうも!

答えて

0

既に一致している相手と一致しない場合は、できません。これが奇数の仕組みです。 :/

このように、すでに一致している相手と一致するか、教師にあなたに悪い入力を与えないように依頼してください。 ;)

+0

明らかに。私のポイントは、どうやって対処するのですか?私は誰かがこれが宿題だと思うだろうと思っていました...笑...私はまだ若くて、まだ学生であることを望みます。 – Lothar

+0

これは本当にあなたがこの問題にどう対処したいかの問題です。しかし、あなたが意味することは、あなたがすでに他の人と一緒に拾った人のどれに過負荷をかけたらいいですか?あなたはそれら3つを取って、それらからリングを作ることができます。それとも、大事なことをするのか。私のポイント。これはプログラミングの問題ではなく、要件の問題です。 – DampeS8N

+0

マークは、リングを行う方法を持って、正しい。 – DampeS8N

1

確かに、繰り返しを使用するよりも、配列をシャッフルする方が簡単です。 1位〜2位、2位〜3位などと一致させ、最後を1位と再び一致させて円を完成させます

1

その時点でバックトラックする必要があります。バックトラックを必要とするアルゴリズムはたくさんあります。あなたが見つけたように、以前の段階で行った選択は実際には不可能だったからです。 以前の選択肢を何らかの形で保存する必要があるため、不可能な状態になったとき(またはすべての解決策を引き出すことがタスクである場合)、完全に探索されていない最後の選択肢に戻り、別の選択。