커스터드 늪 퍼즐의 픽시

StackOverflow https://stackoverflow.com/questions/894423

문제

(Rich Bradshaw 덕분에)

다음 퍼즐에 대한 최적의 전략을 찾고 있습니다.

새로운 요정 왕으로서, 왕국의 커스터드 늪을 매핑하는 것이 당신의 의무입니다.
늪은 미묘한 안개로 덮여 있으며 커스터드 섬이 흩어져 있습니다.
늪을 가로 질러 픽시를 보낼 수 있으며, 각 지점에서 낮거나 높게 날도록 지시합니다.
픽시가 커스터드 위로 내려 가면 산만 해지고 시퀀스를 완료하지 않습니다. 안개가 너무 두껍기 때문에, 당신이 아는 것은 픽시가 다른쪽에 도착했는지 여부입니다.

코딩 용어로 .. 

bool flutter( bool[size] swoop_map );

이것은 주어진 시퀀스에 대해 픽시가 종료되었는지 여부를 반환합니다.

가장 간단한 방법은 단 하나의 Swoop만으로 순서대로 통과하는 것입니다. 그것은 모든 커스터드 제도가 '크기'시도로 드러납니다.
오히려 커스터드 수에 비례하는 것이 아니지만 다음과 같은 시퀀스에 문제가 있습니다.

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

이 퍼즐의 다른 형태에 대한 링크도 환영받을 것입니다.

도움이 되었습니까?

해결책

이것은 내가 분열과 정복을 생각하게한다. 어쩌면 이와 같은 것 (이것은 약간 깨진 의사 코드입니다. 펜스 포스트 오류 등이있을 수 있습니다) :

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;
}

평범한 영어에서는 커스터드 맵의 각 요소에서 한 번에 하나씩 플러터를 부릅니다. 커스터드를 찾지 못하면 다음 호출은 이전 호출보다 두 배나 많은 요소에 있습니다. 이것은 하나의 방향으로 만 검색하는 항목을 모르기 때문에 이진 검색과 비슷합니다. 나는 이것이 얼마나 효율적인지 전혀 모른다.

다른 팁

Brian의 첫 번째 분할 및 정복 알고리즘은 다음과 같은 의미에서 최적입니다. N Squares와 최대 K 커스터드가있는 모든 늪에 Brian보다 C 시간보다 더 좋은 최악의 경우가없는 일정한 C가 있습니다. Brian의 알고리즘은 O (k log (n/k)) 비행을 사용합니다.이 비행은 일정한 요인 내에있는 Log2의 정보 이론적 하한 (n 선택 k)> = log2 ((n/k)^k) = k Omega ( K log (N/K)). (마지막 단계를 엄격하게 만들려면 k <= n/2와 같은 가정이 필요하지만,이 시점에서 우리는 이미 최대 O (n) 항공편에 도달했습니다.)

Brian의 알고리즘이 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))입니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top