2

25 のバースツールが並んでいます。バーに入るお客様は、次の 2 つのルールに従います。

  1. お客様は常に他のお客様から一番離れた席に座ります。
  2. 顧客が別の顧客のすぐ隣に座ることは決してありません。

この 2 つのルールを使用して、バーに最大数の顧客が座れるようにするには、最初の顧客をどこに配置する必要がありますか?

25回の排便状態で解けます。しかし、n スツールの一般的なアルゴリズムを理解することはできません。

4

3 に答える 3

5

その音からすると、これは、ランドール・マンローが閉じた形の方程式や最適な小便器数のプロットなど、優れた分析を作成した国際小便器プロトコル（ICUP）とほぼ同じです。この回答の残りを読む前に、彼の記事を読む必要があります。

投稿の中で、ランドールは次のように述べています。

[I]ぎこちない数の空いている小便器が並んでいるバスルームに入ると、最後の小便器の1つを取るのではなく、3分の1の距離を取ることができます。これにより、厄介な行が2つの最適な行に分割され、最悪のシナリオが最良のシナリオに変わります。

彼はそれ以上の詳細には立ち入りませんが、それは私たちがやろうとしていることを示唆しています。小便器（この場合はスツール）の数が少ない場合は、2つの異なる最適なサブグループの最後になるように、最初の人を座席に着席させることができます。

7シートの場合、基本的な選択動作はこれを相殺します。

1 _ _ 3 _ _ 2

空いている席を4つ残します。しかし、代わりに最初の人を3番目の位置に着席させると、最適な3つと5つのサブグループが得られ、可能な占有者が1つ増えます。

3 _ 1 _ 4 _ 2

25の場合、基本的な動作も同様に最適ではなく、困惑する前に9/25の占有率になります。

1 _ _ 6 _ _ 4 _ _ 7 _ _ 3 _ _ 8 _ _ 5 _ _ 9 _ _ 2

しかし、次のように、誰かを9の位置に配置して、最適な9の17のサブグループを作成することができます。

3 _ 8 _ 5 _ 9 _ 1 _ 10 _ 6 _ 11 _ 4 _ 12 _ 7 _ 13 _ 2

最適な13/25の占有率につながります。

より一般的には、座席数よりも少ない最適な最大数を見つけて、そこに最初の人を着席させると（25の場合は17で、反対方向から9番目に相当します）、常に占有可能な椅子の数が最大になると思います。25のような最悪のシナリオでは、これはceil(n/3)Randallが言及しているものと同等です。

平均的なケース（基本的な着席動作を使用して最良でも最悪でもない）では、最適なサブグループを1つしか作成できず、他のサブグループを最適とは言えない場所に残すため、一人称を着席させるだけでは常に50％の占有率に達するとは限りません。したがって、最適ではないシートの数を最小限に抑えるために、最適なサブグループを最大にします。たとえば、20シートの場合、17を取り、17 4グループを作成します。これにより、可能な限り多くのシートが最適化され、2つだけが空になります。

2 _ 7 _ 4 _ 8 _ 3 _ 9 _ 5 _ 10 _ 1 _ _ 6

4つのグループは、実際には技術的には最良の場合と最悪の場合の両方ですが、パターンがどのようにスケーリングするかを確認できることを願っています。

于 2012-09-24T20:13:57.317 に答える
0

これが私の分析です。

議論のために、最初の人がどちらかの端に近すぎず、真ん中のどこかに座っているとしましょう. これにより、次のようなパターンが得られます。ここで、x は空席を表し、_ は空席を表します。

_ _ _ ... _ x _ ... _ _ _

この人の左側に最初に座った顧客は、一番左端に座ります。同様に、この人の右側に最初に座った顧客は、一番右端に座ります。これにより、次のようなパターンが残ります。ここで、-m- は m 連続する自由席を示します。

x _ -m- _ x _ -n- _ x

これを総座席数 s = m + n + 7 の「基本構成」と呼びます。

さて、問題はサイズ m と n の 2 つのサブ問題に分割され、各エリアのできるだけ中央近くに座っている顧客によってそれぞれが満たされます。

最終占有率を最大にするには、m と n を次のように定義される「理想的な」数値にする必要があります。

a is ideal if a = 2b + 3 and b is ideal  (i.e., we will get -b- _ x _ -b-).

ここでの考え方は、(1) a の真ん中の席を取り、(2) サイズ b の 2 つのサブ問題を再帰的に解くことによって、理想的な席数を最大限に占有できるということです。

最小理想数は 1 です。

これから、最初のいくつかの理想的な数を構築できます。

1, 5, 13, 29, ...

ここで、s = 25 の場合、基本構成は 25 = m + n + 7 であり、m と n が理想的であることを望みます。25 - 7 = 18 と 18 = 5 + 13 が理想的です。

したがって、25 席の場合、最初の人を 4 + 5 = 9 または 4 + 13 = 17 の席に座らせると、最大占有率が保証されます。

終了する前に確認する最後の 1 つのこと: 最初の顧客がエンド スツールに座っていたらどうなるでしょうか? 次に、2 番目の顧客が座った後、

x _ -m- _ x

ここで、m は理想的な数でなければなりません。25 席の場合、これは 25 - 4 = m = 21 となり、理想的ではありません。そのため、最初のお客様は両端に座ることができず、最大 25 席までご利用いただけます。

たぁああああ！

于 2012-09-27T03:02:09.090 に答える