BYR Achieve · 镜像论坛

//下面是在VC6下能运行的代码 #include <cstdio> #include <cassert> #define Assert assert /**********************************************************************/ // // 烙饼排序实现 // /**********************************************************************/ class CPrefixSorting { public: CPrefixSorting() { m_nCakeCnt = 0; m_nMaxSwap = 0; } // // 计算烙饼翻转信息 // @param // pCakeArray 存储烙饼索引数组 // nCakeCnt 烙饼个数 // void Run(int* pCakeArray, int nCakeCnt) { Init(pCakeArray, nCakeCnt); m_nSearch = 0; Search(0); } // // 输出烙饼具体翻转的次数 // void Output() { for(int i = 0; i < m_nMaxSwap; i++) { printf("%d ", m_SwapArray[i]); } printf("\n |Search Times| : %d\n", m_nSearch); printf("Total Swap times = %d\n", m_nMaxSwap); } private: // // 初始化数组信息 // @param // pCakeArray 存储烙饼索引数组 // nCakeCnt 烙饼个数 // void Init(int* pCakeArray, int nCakeCnt) { Assert(pCakeArray != NULL); Assert(nCakeCnt > 0); m_nCakeCnt = nCakeCnt; // 初始化烙饼数组 m_CakeArray = new int[m_nCakeCnt]; Assert(m_CakeArray != NULL); for(int i = 0; i < m_nCakeCnt; i++) { m_CakeArray[i] = pCakeArray[i]; } // 设置最多交换次数信息 m_nMaxSwap = UpBound(m_nCakeCnt); // 初始化交换结果数组 m_SwapArray = new int[m_nMaxSwap]; Assert(m_SwapArray != NULL); // 初始化中间交换结果信息 m_ReverseCakeArray = new int[m_nCakeCnt]; for(i = 0; i < m_nCakeCnt; i++) { m_ReverseCakeArray[i] = m_CakeArray[i]; } m_ReverseCakeArraySwap = new int[m_nMaxSwap]; } // // 寻找当前翻转的上界 // // 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; m_nSearch++; // 估算这次搜索所需要的最小交换次数 nEstimate = LowerBound(m_ReverseCakeArray, m_nCakeCnt); if(step + nEstimate > m_nMaxSwap) return; // 如果已经排好序，即翻转完成，输出结果 if(IsSorted(m_ReverseCakeArray, m_nCakeCnt)) { if(step < m_nMaxSwap) { m_nMaxSwap = step; for(i = 0; i < m_nMaxSwap; i++) m_SwapArray[i] = m_ReverseCakeArraySwap[i]; } return; } // 递归进行翻转 for(i = 1; i < m_nCakeCnt; i++) { Revert(0, i); m_ReverseCakeArraySwap[step] = i; Search(step + 1); Revert(0, i); } // // true : 已经排好序 // false : 未排序 // 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; } } 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; // 当前搜索次数信息 }; int main() { CPrefixSorting cps; int cake[] = {3, 2, 1, 6, 5, 4, 9, 8, 7, 0}; cps.Run(cake, sizeof(cake)/sizeof(int)); cps.Output(); } 哪位牛人帮我分析分析程序思路，递归看不太懂，尤其是变量m_ReverseCakeArraySwap

《编程之美》中一摞烙饼的排序