題目
分析
深度優先搜尋周遊每一種情況，去翻轉次數最小的，當然，還要加一些剪枝，畢竟O(nn)的時間複雜度。
代碼
C風格
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\n", search_times);
72 printf("翻轉次數: %d\n", max_swap);
73 for (int i = 0; i < max_swap; i++) printf("%d ", arr_swap[i]);
74 printf("\n具體的翻轉情況：\n");
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("\n");
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 } C++風格
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("\n");
50 }
51 }
52
53 //輸出烙餅具體的翻轉情況
54 void Output()
55 {
56 for (int i = 0; i < m_nMaxSwap; i++) printf("%d ", m_SwapArray[i]);
57 printf("\n");
58 printf("Search Times: %d\n", m_nSearch);
59 printf("Total Times: %d\n", 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 } 參考連結：
https://blog.csdn.net/tianshuai1111/article/details/7659673
http://blog.sina.com.cn/s/blog_a2aa00d70101ewuf.html
https://blog.csdn.net/ML_algorithmResearch/article/details/50405548
個性簽名：時間會解決一切