2

単語検索で考えられるすべての配置を体系的に試すことは合理的でしょうか?

グリッドは一般に 15*15 (幅 15 セル、高さ 15 セル) の寸法を持ち、配置する約 15 の単語を含み、それぞれを 8 つの可能な方向に配置できます。したがって、一般的に、可能なすべての配置を次のように計算できるようです: width*height*8_directions_to_place_word*number of words

したがって、このようなグリッドの場合、15*15*8*15 = 27,000 を試すだけでよいように思えますが、これはそれほど悪くはないようです。私は巨大な数を期待しているので、グリッドサイズと単語数が非常に小さいか、私の数学に怪しいものがあります。

4

1 に答える 1

2

x正式に言えば、それが行数であり列数であると仮定するとy、すべての可能な単語のすべての可能な方向のすべての確率を合計する必要があります。

入力は次のとおりです。 x、、（単語の平均の長さ）、y（単語の総数）ln

だからあなたは

  • 水平方向では、単語は各行でtoから右に、またはlから左に向かっ0てx-l開始できます。x2x(x-l)
  • 同じアプローチが縦の単語に使用されます：それらは下0に行くことから上にy-l行くことlへ行くことができyます。っていうことは2y(y-l)
  • 対角線の単語の場合、フィールドの長方形は使用できないため、考えられるすべての開始位置x*yを考慮して減算する必要があります。l^2前と同じように、4つの可能な方向があるので、4を掛けます4*(x*y - l^2)。

次に、結果全体に含まれる単語の数を掛けます。

total = n*(2*x*(x-l)+2*y*(y-l)+4*(x*y-l^2)
于 2010-04-08T15:43:07.950 に答える