1

誰かが共有したG+の投稿に出くわしました：

If
  A B C D E F G H I J  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z

Equals
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Then
  K + N + O + W + L + E + D + G + E = 96% 
  H + A + R + D + W + O + R + K     = 98%

But
  A + T + T + I + T + U + D + E     = 100%

そのため、そしてそれを楽しむために、パーセントトリックを無視し、残りの話をG+のコメントに任せます。

しかし、私は自分自身に問いかけます。与えられた単語リスト（n個の単語の固定セット）から合計100個の単語をすべて見つけるための最良のアプローチ（アルゴリズム）は何でしょうか？

4

2 に答える 2

3

簡単なアプローチが良いと思います-それはO（n）です：

  1. 各文字をポイント値に関連付けるハッシュテーブルを作成します
  2. リストをループします。単語ごとに、ハッシュテーブルの文字に関連付けられている数値の値を合計します。合計が100の場合は、単語を印刷するか、何らかの方法で見つかったものとしてマークします（新しいリストなどに追加します）...

（ 「単語」は任意の長さにすることができると言えば、O（n ）について議論することができます。ただし、単語リストが特定の言語の単語のサブセットである場合、これは問題ではありません。単語の最大文字数の場合、アルゴリズムはO（nm）です。それでも、ある時点で各文字と各単語を「見る」必要があるため、これ以上あるとは想像できません。時間効率の良いアルゴリズム。）

于 2012-07-18T07:22:11.407 に答える
2

同様の問題がここで説明されています。ただし、特定の問題は、より簡単なアプローチを示唆しています。単語リスト内の単語の数は制限されており、最も長い単語の長さまでの文字の順列の数よりも常に少ないため、次のように進めるのが最善です。

charToNum文字を対応する番号にマップする関数があるとしましょう。

for each word in wordlist
  sum := 0
  for each character in word
    sum := sum + charToNum(character)
    if (sum > 100)
      break // Correct result no longer possible
  if (sum == 100)
    Add the word to the result set
于 2012-07-18T07:26:34.247 に答える