프로그래밍의 아름다움 - 케이크 문제

밀전병 한 무더기를 큰 것은 아래에 눌러 놓고, 작은 것은 위에서 두드려 놓고, 한 손은 한 번에 위의 떡 몇 장만 잡고 그것들을 위아래로 뒤집어 놓을 수 있다.여러 번 반복한 후에 떡을 잘 배열하다.떡 배열에 필요한 최소한의 횟수를 물어보다.
문제: 떡을 배열하는 데 필요한 최소 횟수를 봅시다.
가장 좋은 문제를 찾으면 궁거법을 쓸 생각을 할 수 있다.돌아가는 방식으로 모든 회전 방식을 두루 훑어보다.그리고 가장 작은 값을 찾습니다.
먼저 맨 위의 두 장을 뒤집고 횟수를 하나 더 해서 요구에 도달했는지 확인하고 없으면 이미 뒤집은 기초 위에서 계속 귀속할 수 있다.순서가 정해지면 이것은 퇴출 조건이다.
물론 책에서 최적화를 하고 현재 떡의 순서를 평가했다. 몇 장의 떡이 서로 인접하지 않은 위치에 있는지 보고 평가치를 제시했다. 만약에 현재 실행 중인 뒤집기 횟수 + 미래에 뒤집기 횟수 > 2(n-1)가 가장 필요한 뒤집기 횟수일 때 바로 물러날 수 있다.
프로그램에서 FindSwapCount의 반환 값을 주목할 수 있습니다. 그 중의 알고리즘을 최적화하여 반환 값을 최대한 크게 (당연히 합리적이어야 한다) 하면 반환 횟수를 대폭 줄일 수 있습니다.
예를 들어 테스트 시 떡 크기의 순서는 {3,1,2}이고 이것은 적어도 두 번 뒤집어야 한다.현재 프로그램은 79번을 찾아야 합니다. FindSwapCount의 반환 값을 2배로 바꾸면 51번을 찾아야 합니다.
만약에 {5,1,2,4,3}로 테스트를 진행하면 375289:39057이 비교적 뚜렷하다.

#include <iostream>

using namespace std;

int nMax = 0;
int nSearchTime = 0;

void Print(int *pData, int nLen)
{
    int i = 0;
    for (i = 0; i < nLen; i++)
        cout << pData[i] << " ";

    cout << endl;
}

void Swap(int *pData, int nStart, int nEnd)
{
    int nTemp = 0;

    while (nStart < nEnd)
    {
        nTemp = pData[nStart];
        pData[nStart] = pData[nEnd];
        pData[nEnd] = nTemp;
        nStart++;
        nEnd--;
    }
}

int FindSwapCount(int* pData, int nLen)
{
    int n = 0, i = 0;

    for (i = 1; i < nLen; i++)
    {
        if ((pData[i] - pData[i-1] > 1) || (pData[i] - pData[i-1] < -1))
        {
            n++;
        }
    }
    return n;
}

bool IsOk(int *pData, int nLen)
{
    int i = 0;

    for (i = 1; i < nLen; i++)
    {
        if (pData[i] < pData[i-1])
            return false;
    }

    return true;
}

void Search(int nStep, int* pData, int nLen)
{
    int i = 0;
    int nEsti = 0;
    nSearchTime++;

    nEsti = FindSwapCount(pData, nLen);
    if (nStep + nEsti > 2*nLen)
        return;

    if (IsOk(pData, nLen))
    {
        if (nStep < nMax)
        {
            nMax = nStep;
            cout << nMax << endl;
        }
        return;
    }

    for (i = 1; i < nLen; i++)
    {
        Swap(pData, 0, i);
        Search(nStep+1, pData, nLen);
        Swap(pData, 0, i);
    }

}

void main()
{
    int value = 0;
    //int test[10] = {3,1,2,6,5,4,9,8,7,0};
    //int nLen = 10;

    //int test[5] = {5,1,2,4,3};
    //int nLen = 5;

    int test[3] = {3,1,2};
    int nLen = 3;

    Print(test, nLen);
    nMax = nLen * 2;
    Search(0, test, nLen);
    cout << nMax << " search times: "<< nSearchTime <<endl;
    //Print(test, nLen);

    cin >> value;

}