カスタードスワンプパズルのピクシーズ

Question

（リッチブラッドショーのおかげで）

次のパズルの最適な戦略を探しています。

新しい妖精の王様として、王国のカスタード・スワンプをマップするのはあなたの義務です。
沼は穏やかな霧で覆われており、全体にはカスタード島が散在しています。
沼の向こうにあなたのピクシーを送ることができ、各ポイントで低いか高いかを飛ぶように指示できます。
ピクサーがカスタードの上を飛び回ると、それは気を散らし、シーケンスを完了しません。 霧がとても厚いので、あなたが知っているのは、ピクシーが相手側にいるかどうかだけです。

コーディングに関しては

..

bool flutter(bool[size] swoop_map); 

これは妖精はswoopsの所定のシーケンスのために終了するかどうかを返します。

最も簡単な方法は、1回のスワップでシーケンスを渡すことです。それは「サイズ」のすべてのカスタード島を明らかにする。同様に歓迎されるであろう、このパズルの他の形態に

 C......C  (that is, custards at beginning and end) 

リンク： -
私はむしろカスタードの数に比例して何かしたいけどは様配列に問題があります。

Answer 1

これは分裂と征服を考えさせてくれます。たぶん、このようなものは、（これは少し壊れた擬似コードであることがフェンスポストエラーを持っているなどがあります。）：平易な英語で

retval[size] check() 
{ 
    bool[size] retval = ALLFALSE; 
    bool[size] flut1 = ALLFALSE; 
    bool[size] flut2 = ALLFALSE; 
    for (int i = 0; i < size/2; ++i) flut1[i] = TRUE; 
    for (int i = size/2; i < size; ++i) flut2[i] = TRUE; 
    if (flutter(flut1)) retval[0..size/2] = <recurse>check 
    if (flutter(flut2)) retval[size/2..size] = <recurse>check 
} 

、それはカスタードマップの各半分にフラッタを呼び出します。いずれかの半分が偽を返す場合、その半分の全体にはカスタードはありません。それ以外の場合は、半分の半分がアルゴリズムを再帰的に適用します。もっとうまくいくかどうかは分かりません。しかし、このアルゴリズムは、スワンプが大部分がカスタードである場合、色あせています。

アイデア2：平易な英語で

int itsize = 1 
bool[size] retval = ALLFALSE; 
for (int pos = 0; pos < size;) 
{ 
    bool[size] nextval = ALLFALSE; 
    for (int pos2 = pos; pos2 < pos + size && pos2 < size; ++pos2) nextval[pos2] = true; 
    bool flut = flutter(nextval) 
    if (!flut || itsize == 1) 
    { 
     for (int pos2 = pos; pos2 < pos + size && pos2 < size; ++pos2) retval[pos2] = flut; 
     pos+=itsize; 
    } 
    if (flut) itsize = 1; 
    if (!flut) itsize*=2; 
} 

、それはカスタードマップ、一度に一つの各要素に対してフラッタを呼び出します。カスタードが見つからない場合、次のコールは前のコールの2倍の数の要素になります。これはバイナリ検索のようなものです。検索するアイテムの数が分からないため、一方向のみを除きます。これがどれほど効率的かわかりません。

Answer 2

ブライアンの最初の除算と征服のアルゴリズムは、次のような意味で最適です。n乗の累乗で最大でk個のカスケードを持つすべての沼に、アルゴリズムは最悪ケースがCブライアン。 Brianのアルゴリズムでは、log2（n choose k）> = log2（（n/k）^ k）= k Omegaの情報理論上の下限が一定係数内にあるO（k log（n/k） k log（n/k））である。 （最後のステップを厳密にするためにk < = n/2のような仮定が必要ですが、この時点ではO（n）便の最大値に達しています）

ブライアンのアルゴリズムはなぜO （k log（n/k））便ですか？再帰深度iでは、最大（2^i、k）のフライトを最大で行います。 0 < = i < = log2（k）の和はO（k）である。 log2（k）< i < = log2（n）の和はk（log2（n）-log2（k））= k（log2（n/k））である。