编程之美——一摞烙饼的排序（暴搜+剪枝）(代码片段)

 1 /**** 前缀排序 ****/
 2 #include<stdio.h>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 const int maxn = 100 + 10;
 8 int n, arr[maxn];            //烙饼个数和烙饼数组
 9 int arr_cmp[maxn];
10 int arr_tmp[maxn];                //记录初始数组
11 
12 int search_times = 0;        //总搜索次数
13 int max_swap;            //最小交换次数
14 int arr_swap[2 * maxn];        //最终翻转方案
15 int tarr_swap[2 * maxn];    //当前翻转方案
16 
17 void Init()
18 
19     for (int i = 0; i < n; i++)  arr_tmp[i] = arr_cmp[i] = arr[i];
20     sort(arr_cmp, arr_cmp + n);
21     max_swap = 2 * (n - 1);
22 
23 
24 void Reverse(int* arr,int start, int end)
25 
26     for (int i = start, j = end; i < j; i++, j--)
27         swap(arr[i], arr[j]);
28 
29 
30 int LowerBound()
31 
32     int ret = 0;
33     for (int i = 1; i < n; i++)
34         if (arr[i - 1] > arr[i])  ret++;
35     return ret;
36 
37 
38 bool IsSort()
39 
40     for (int i = 0; i < n; i++)
41         if (arr_cmp[i] != arr[i])  return false;
42     return true;
43 
44 
45 void Search(int step)
46 
47     search_times++;
48 
49     if (IsSort())    //已排好序
50     
51         if (step < max_swap)
52         
53             max_swap = step;
54             for (int i = 0; i < max_swap;i++)  arr_swap[i] = tarr_swap[i];
55         
56     
57 
58     if ((step + LowerBound()) > max_swap)  return;
59 
60     for (int i = 1; i <= n; i++)
61     
62         Reverse(arr,0, i);
63         tarr_swap[step] = i;
64         Search(step + 1);
65         Reverse(arr,0, i);
66     
67 
68 
69 void Print()
70 
71     printf("搜索次数：%d
", search_times);
72     printf("翻转次数: %d
", max_swap);
73     for (int i = 0; i < max_swap; i++)  printf("%d ", arr_swap[i]);
74     printf("
具体的翻转情况：
");
75     for (int i = 0; i < max_swap; i++)
76     
77         Reverse(arr_tmp, 0, arr_swap[i]);
78         for (int j = 0; j < n; j++)  printf("%d ", arr_tmp[j]);
79         printf("
");
80     
81 
82 
83 int main()
84 
85     scanf("%d", &n);
86     for (int i = 0; i < n; i++)  scanf("%d", &arr[i]);
87     Init();
88     Search(0);
89     Print();
90 

  1 #include<stdio.h>
  2 #include<cstring>
  3 #include<cassert>         //assert宏的原型定义在<assert.h>中
  4 #include<algorithm>
  5 using namespace std;
  6 
  7 class laobing
  8 
  9 private:
 10     int* m_CakeArray;        //烙饼信息数组
 11     int m_nCakeCnt;            //烙饼个数
 12     int m_nMaxSwap;            //最多翻转次数
 13     int* m_SwapArray;        //最终翻转烙饼位置
 14     int* m_ReverseCakeArray;        //当前烙饼数组
 15     int* m_ReverseCakeArraySwap;    //当前翻转烙饼位置
 16     int m_nSearch;            //搜索次数
 17 
 18 public:
 19     laobing()
 20     
 21         int m_CakeCnt = 0;
 22         int m_nMaxSwap = 0;
 23     
 24     ~laobing()
 25     
 26         if (m_CakeArray != NULL)  delete m_CakeArray;
 27         if (m_SwapArray != NULL)  delete m_SwapArray;
 28         if (m_ReverseCakeArray != NULL)  delete  m_ReverseCakeArray;
 29         if (m_ReverseCakeArraySwap != NULL)  delete m_ReverseCakeArraySwap;
 30     
 31 
 32     //计算烙饼翻转信息
 33     //pCakeArray    存储烙饼数组
 34     //nCakeCnt      烙饼个数
 35     void run(int* pCakeArray, int nCakeCnt)
 36     
 37         Init(pCakeArray, nCakeCnt);
 38         m_nSearch = 0;
 39         Search(0);
 40     
 41 
 42     //输出交换过程
 43     void OutputArray(int* CakeArray, int nCakeCnt, int* m_SwapArray, int m_nMaxSwap)
 44     
 45         for (int i = 0; i < m_nMaxSwap; i++)   //每一次交换
 46         
 47             Reverse(CakeArray, 0, m_SwapArray[i]);
 48             for (int i = 0; i < nCakeCnt; i++)  printf("%d ", CakeArray[i]);
 49             printf("
");
 50         
 51     
 52 
 53     //输出烙饼具体的翻转情况
 54     void Output()
 55     
 56         for (int i = 0; i < m_nMaxSwap; i++)  printf("%d ", m_SwapArray[i]);
 57         printf("
");
 58         printf("Search Times: %d
", m_nSearch);
 59         printf("Total Times: %d
", m_nMaxSwap);
 60 
 61         OutputArray(m_CakeArray, m_nCakeCnt, m_SwapArray, m_nMaxSwap);
 62     
 63 private:
 64     void Init(int *pCakeArray, int nCakeCnt)
 65     
 66         assert(pCakeArray != NULL);        //其作用是如果它的条件返回错误，则终止程序执行。
 67         assert(nCakeCnt > 0);
 68 
 69         //初始化烙饼数组
 70         m_nCakeCnt = nCakeCnt;
 71         m_CakeArray = new int[m_nCakeCnt];
 72         assert(m_CakeArray != NULL);
 73         for (int i = 0; i < m_nCakeCnt; i++)
 74             m_CakeArray[i] = pCakeArray[i];
 75 
 76         //设置最多交换次数
 77         m_nMaxSwap = UpBound(m_nCakeCnt);
 78 
 79         //初始化交换数组结果
 80         m_SwapArray = new int[m_nMaxSwap];
 81         assert(m_SwapArray != NULL);
 82 
 83         //初始化中间交换结果
 84         m_ReverseCakeArray = new int[m_nCakeCnt];
 85         for (int i = 0; i < m_nCakeCnt; i++)
 86             m_ReverseCakeArray[i] = m_CakeArray[i];
 87         m_ReverseCakeArraySwap = new int[m_nMaxSwap];
 88     
 89 
 90     //寻找当前翻转次数的上界
 91     //n个烙饼，翻转最大的n-2烙饼最多需要2*(n-2)次，剩下的2个最多1次，因而上限值为2*n-3，
 92     //因此，m_nMaxSwap初始值可以取2*n-3+1=2*n-2，这样每步与m_nMaxSwap的判断就可以取大等于号。
 93     int UpBound(int nCakeCnt)
 94     
 95         return 2 * (nCakeCnt - 1);  
 96     
 97 
 98     //寻找当前翻转次数的下界
 99     int LowerBound(int* pCakeArray, int nCakeCnt)
100     
101         int ret = 0;
102 
103         //根据当前数组的顺序信息来判断最少需要交换多少次
104         for (int i = 1; i < nCakeCnt; i++)
105         
106             //判断位置相邻的两个烙饼是否是尺寸相邻的
107             int tmp = pCakeArray[i] - pCakeArray[i - 1];
108             if (tmp == 1 || tmp == -1)  continue;
109             else  ret++;
110         
111         if (pCakeArray[nCakeCnt - 1] != nCakeCnt - 1)  ret++;  //判断下界时，如果最大的烙饼不在最后一个位置，则要多翻转一次
112         return ret;
113     
114 
115     //排序的主函数
116     void Search(int step)
117     
118         m_nSearch++;
119         // // 估算这次搜索所需要的最小交换次数  
120         int nEstimate = LowerBound(m_ReverseCakeArray, m_nCakeCnt);
121         if (step + nEstimate >= m_nMaxSwap)  return;        //剪枝
122 
123         //如果已经排好序，直接输出
124         if (IsSort(m_ReverseCakeArray, m_nCakeCnt))
125         
126             if (step < m_nMaxSwap)
127             
128                 m_nMaxSwap = step;
129                 for (int i = 0; i < m_nMaxSwap; i++)  m_SwapArray[i] = m_ReverseCakeArraySwap[i];
130             
131             return;
132         
133 
134         //递归进行翻转
135         for (int i = 1; i < m_nCakeCnt; i++)
136         
137             Reverse(m_ReverseCakeArray, 0, i);
138             m_ReverseCakeArraySwap[step] = i;
139             Search(step + 1);    //递归
140             Reverse(m_ReverseCakeArray,0, i);        //回溯
141         
142     
143 
144     //检查是否排好序
145     bool IsSort(int * pCakeArray, int nCakeCnt)
146     
147         for(int i = 1;i < nCakeCnt;i++)
148             if (pCakeArray[i - 1] > pCakeArray[i])  return false;
149         return true;
150     
151 
152     //翻转烙饼信息
153     void Reverse(int* m_arr,int nBegin, int nEnd)
154     
155         assert(nEnd > nBegin);
156 
157         for (int i = nBegin, j = nEnd; i < j; i++, j--)
158             swap(m_arr[i], m_arr[j]);
159     
160 ;
161 
162 const int maxn = 100 + 10;
163 int n, arr[maxn];
164 
165 int main()
166 
167     laobing lb;
168     laobing* p = new laobing();
169     scanf("%d", &n);
170     for (int i = 0; i < n; i++)  scanf("%d", &arr[i]);
171 
172     p->run(arr, n);
173     p->Output();
174 
175     lb.run(arr, n);
176     return 0;
177