9

昨夜のラグビーを観戦していたとき、ポイントを獲得できるのは 3、5、または 7 のくじでしかないことを考えると、不可能なスコアはないのではないかと考えていました。5=5、6=3+3、7=7、8=3+5、9=3+3+3、10=5+5 など。

その考えを 5、7、9 に拡張すると、次の可能なスコアが得られます。 

5,7,9,10,12,14 // and now all numbers are possible.

7、9、11 の場合: 

7,9,11,14,16,18,20,22,23,25,27 // all possible from here

私は頭の中でこれらを行いました.スコアのセットが与えられた場合、それを超えるすべてのスコアが達成可能な最低スコアを決定する優れたアルゴリズムを誰かが提案できますか.

私はそれを次のようにモデル化しました： 

forall a < 10:
   forall b < 10:
      forall c < 10:
          list.add(3a + 5b + 7c);
list.sort_smallest_first();

次に、3 よりも長いシーケンスのリストを確認します (最小スコア)。些細なケース以外では、かなり非現実的で遅いようです。

4

1 に答える 1

8

すべてのスコアが達成可能な達成不可能な数値は 1 つだけです。

これをフロベニウス数と呼びます。参照: http://en.wikipedia.org/wiki/Frobenius_number

wikiページには、それを解決するためのアルゴリズムへのリンクが必要です。たとえば、http: //www.combinatorics.org/Volume_12/PDF/v12i1r27.pdf

2 つの数値 a,b の場合、正確な式 (ab-ab) が既知であり (検索スペースを削減するために使用できます)、3 つの数値 a,b,ca の場合、急激な下限 (sqrt(3abc)-abc) と非常に高速なアルゴリズムが知られています。

数値が等差数列である場合、正確な式が知られています (wiki を参照)。あなたの例ではすべての数値が算術級数であるため、これについて言及します。

あなたの質問に答えるには、フロベニウス数を見つけてそれに 1 を加えます。

それが役立つことを願っています。

于 2010-08-12T04:53:40.533 に答える