稍微修改了一下《编程之美》里的烙饼排序
源代码貌似有不少错误，m_nCakeCnt这里就出了不少问题，因为数组是从0开始的，很多地方 <要改成 <=，
还有那个search递归调用里最后一个revert，我没有明白什么意思，就去掉了，然后在for循环也对sorted加个判断，如果是，就可以break出来了。代码如下，请高手指教，我是菜鸟，非常需要指教。
#include <stdio.h>
#include <assert.h>
class CPrefixSorting
{
public:
CPrefixSorting()
{
m_nCakeCnt = 0;
m_nMaxSwap = 0;
}
~CPrefixSorting()
{
if( m_CakeArray != NULL )
{
delete m_CakeArray;
}
if( m_SwapArray != NULL )
{
delete m_SwapArray;
}
if( m_ReverseCakeArray != NULL )
{
delete m_ReverseCakeArray;
}
if( m_ReverseCakeArraySwap != NULL )
{
delete m_ReverseCakeArraySwap;
}
}
void Run(int* pCakeArray, int nCakeCnt)
{
Init(pCakeArray, nCakeCnt);
m_nSearch = 0;
Search(0);
}
void Output()
{
printf("\nm_SwapArray: ");
for(int i = 0; i < m_nMaxSwap; i++)
{
m_SwapArray[i] = m_ReverseCakeArraySwap[i];
printf("%d ", m_SwapArray[i]);
}
printf("\n|Search Times| : %d\n", m_nSearch);
printf("Total Swap times = %d\n", m_nMaxSwap);
printf("m_ReverseCakeArray: \n");
PrintArray( m_ReverseCakeArray, m_nCakeCnt );
}
private:
void Init(int* pCakeArray, int nCakeCnt)
{
assert(pCakeArray != NULL);
assert(nCakeCnt > 0);
m_nCakeCnt = nCakeCnt;
m_CakeArray = new int[m_nCakeCnt + 1];
assert(m_CakeArray != NULL);
for(int i = 0; i <= m_nCakeCnt; i++)
{
m_CakeArray[i] = pCakeArray[i];
}
printf( "m_CakeArray values, cake num:%d \n", (m_nCakeCnt + 1) );
PrintArray( m_CakeArray, m_nCakeCnt );
printf( "\n" );
m_nMaxSwap = UpBound(m_nCakeCnt);
m_SwapArray = new int[m_nMaxSwap + 1];
assert(m_SwapArray != NULL);
m_ReverseCakeArray = new int[m_nCakeCnt + 1];
for(int i = 0; i <= m_nCakeCnt; i++)
{
m_ReverseCakeArray[i] = m_CakeArray[i];
}
m_ReverseCakeArraySwap = new int[m_nMaxSwap + 1];
}
int UpBound(int nCakeCnt)
{
return nCakeCnt*2;
}
int LowerBound(int* pCakeArray, int nCakeCnt)
{
int t, ret = 0;
for(int i = 1; i < nCakeCnt; i++)
{
t = pCakeArray[i] - pCakeArray[i-1];
if((t == 1) || (t == -1))
{
}
else
{
ret++;
}
}
return ret;
}
void Search(int step)
{
int i, nEstimate;
int sortedFlag = 0;
m_nSearch++;
nEstimate = LowerBound(m_ReverseCakeArray, m_nCakeCnt);
if(step + nEstimate > m_nMaxSwap)
{
printf("\nShould Return!!!! \n");
printf("step:%d, nEstimate:%d, m_nMaxSwap:%d, m_nSearch:%d \n",
step, nEstimate, m_nMaxSwap, m_nSearch);
return;
}
printf("\nstep:%d, nEstimate:%d, m_nMaxSwap:%d, m_nSearch:%d \n",
step, nEstimate, m_nMaxSwap, m_nSearch);
PrintArray( m_ReverseCakeArray, m_nCakeCnt );
printf( "\n" );
if(IsSorted(m_ReverseCakeArray, m_nCakeCnt))
{
sortedFlag = 1;
printf("IsSorted!!!! \n");
if(step <= m_nMaxSwap)
{
m_nMaxSwap = step;
for(i = 0; i < m_nMaxSwap; i++)
m_SwapArray[i] = m_ReverseCakeArraySwap[i];
}
return;
}
printf( "total m_nCakeCnt:%d\n", m_nCakeCnt );
for(i = 1; i <= m_nCakeCnt; i++)
{
printf("1-> ");
PrintArray( m_ReverseCakeArray, m_nCakeCnt );
printf( "i:%d\n",i );
Revert(0, i);
printf("2-> ");
PrintArray( m_ReverseCakeArray, m_nCakeCnt );
printf( "i:%d\n",i );
m_ReverseCakeArraySwap[step] = i;
printf( "m_ReverseCakeArraySwap[%d]:%d\n", step, m_ReverseCakeArraySwap[step] );
Search(step + 1);
printf( "\nreturn from (step+1):%d, i:%d\n", step+1, i );
//Revert(0, i);
printf("3-> ");
PrintArray( m_ReverseCakeArray, m_nCakeCnt );
printf( "i:%d\n",i );
if( !sortedFlag )
{
if(IsSorted(m_ReverseCakeArray, m_nCakeCnt))
{
printf("It is Sorted, should break!!!! \n");
break;
}
}
}
}
bool IsSorted(int *pCakeArray, int nCakeCnt)
{
for(int i = 1; i <= nCakeCnt; i++)
{
if(pCakeArray[i-1] > pCakeArray[i])
{
return false;
}
}
return true;
}
void Revert(int nBegin, int nEnd)
{
assert(nEnd > nBegin);
int i, j, t;
for(i = nBegin, j = nEnd; i < j; i++, j--)
{
t = m_ReverseCakeArray[i];
m_ReverseCakeArray[i] = m_ReverseCakeArray[j];
m_ReverseCakeArray[j] = t;
}
}
void PrintArray( int *Array, int n)
{
for( int i = 0; i <=n; i++ )
printf( "%d ", Array[i] );
}
private:
int* m_CakeArray;// 烙饼信息数组
int m_nCakeCnt;// 烙饼个数
int m_nMaxSwap;// 最多交换次数。根据前面的推断，这里最多为
// m_nCakeCnt * 2
int* m_SwapArray;// 交换结果数组
int* m_ReverseCakeArray;// 当前翻转烙饼信息数组
int* m_ReverseCakeArraySwap;// 当前翻转烙饼交换结果数组
int m_nSearch;// 当前搜索次数信息
};
main()
{
//int CakeArray[10] = { 2, 5, 7, 10, 6, 1, 4, 3, 5, 9 };
//int CakeCnt = 9;
//int CakeArray[3] = { 5, 2, 1 };
//int CakeCnt = 2;
//int CakeArray[2] = { 5, 2 };
//int CakeCnt = 1;
//int CakeArray[4] = { 5, 2, 10, 4 };
//int CakeCnt = 3;
int CakeArray[5] = { 5, 2, 10, 4, 7 };
int CakeCnt = 4;
CPrefixSorting CakeSort;
CakeSort.Run(CakeArray, CakeCnt);
CakeSort.Output();
return 0;
}
[解决办法]
其實這本書要探討的不在於這個問題就是~
