《编程之美》读书笔记22： 1.16 24点游戏（补充）
给定n个数，能否只通过加减乘除计算得到24？
书上给出的最后一种解法，通过使用集合记录中间结果来减少冗余计算。本以为，程序会占用大量的内存，用一个极端的例子（13, 773, 28, 98, 731, 1357,97357246这7个数）测试了一下实现的程序，发现程序竟然占用了1G以上的内存（无论集合的实现采用STL中的set还是unordered_set），但后来，取7个均在1到13之间的数，再重新测试了下发现，程序所占用的内存比想像的小的多，也就几兆。
对数值都在1到13之间的n个数的所有组合进行判断。在n等于4时，实现的程序约过1秒就给出了结果，而n等于5时，程序要运行58秒，效率实在差，可以通过这几方面优化：
① 保存每个集合的子集合的编号：
对给定的n，共有1到2^n – 1个集合，每个集合的子集合编号是固定的，但原程序每计算一个n个数的组合，都要对这些子集合编号计算一遍，可以保存每个集合的子集合编号，减少大量的重复计算。
② 改进计算子集合编号的算法：
原程序的算法的时间复杂度是O(4^n)，在n较大时，相当慢。
③ 对最后一个集合是否含有24的判断：
原程序要遍历该集合所有的元素，效率比较差，可以考虑，在将两个集合合并到该集合时，只对取出的两个元素的计算结果是否为24进行判断，这样不仅省去最后的遍历，而且不用将结果插入到最后的那个集合中，省去了大量操作。
采用①和③两种改进方法后，程序运行时间由原来的58秒缩短到了14秒，但这还不能让人满意。对2,3,5,6,8这5个数，如果用书上的第一种方法，可以只调用4次函数就可以得到结果：2+3+5+6+8=24，但用集合的方法来处理，却要对所有的集合进行子集合合并后才能给出结果，这造成了效率极差，可以这样改进该算法：
初始有n个集合：每一次任意取出2个集合，合并后，放回去，再取出任意2个集合，重复前面的操作，直到只剩下一个集合为止。
例如：初始有5个数，把这5个数分别放到5个集合，并分别编号为：1、2、4、8、16。任意取出2个集合，假设为1和4，将1和4合并，得到编号为5(=1+4)的集合，剩下的集合为：5、2、16、8，再取出2个，假设为5和8，合并后，得到13、2、16，再取2个，假设为13和16，合并后得到29、2，当剩下2个集合时，可以直接对这两个集合间的的计算结果是否为24进行判断，直接得出结果，省去不必要的合并（合并后再判断是否有元素近似等于24，程序运行时间8s多，而直接对计算结果判断，程序只要运行1s多）。
优化后的程序，只要运行1s多。但其效率还是不如书上的第一种方法的改进版，仔细想想，n越大，集合的元素也就越多，两个集合之间的合并，就越耗时间。而且采用集合保存中间结果，表面上减少了重复状态，会提高效率，但实际上，由于采用了集合，就多了很多不必要的计算，（比如，对2+3+5+6+8=24，最少只要4次计算就能得出结果，采用集合合并后，则要计算几百次（约为6^4）），再加上实现集合所采用的数据结构的开销，效率高不了。
24_set_1
1
#include <iostream>
2#include <fstream>
3#include <unordered_set>
4#include <vector>
5#include <ctime>
6#include <cmath>
7using namespace std;
8typedef unordered_set<double> mset;
9
10unsigned long long all_size=0;
11unsigned long long big_size=0;
12
13
14bool calc(int src[], size_t N, double M = 24.0)
15
{
16
if (N == 0 || src == NULL) return false;
17 mset result[1 << N];
18 for (size_t i = 0; i < N; ++i) result[1<<i].insert((double)src[i]);
19
for (size_t i =1; i < (1<<N); ++i) {
20 for (size_t j = 1; j <= (i >> 1); ++j) {
21 if ((i & j) != j) continue;
22 for (mset::iterator p = result[j].begin(); p != result[j].end(); ++p) {
23 double va = *p;
24 size_t k = i ^ j;
25 for (mset::iterator q = result[k].begin(); q != result[k].end(); ++q) {
26 double vb = *q;
27 result[i].insert(va + vb);
28 result[i].insert(va - vb);
29 result[i].insert(vb - va);
30 result[i].insert(va * vb);
31 if (vb != 0.0) result[i].insert(va / vb);
32 if (va != 0.0) result[i].insert(vb / va);
33
}
34 }
35 }
36 }
37
38 size_t j = (1 << N) - 1;
39 all_size=0;
40 big_size=result[j].size();
41 for (size_t i =1; i < (1<<N); ++i) all_size += result[i].size();
42 for (mset::iterator p = result[j].begin(); p != result[j].end(); ++p) {
43 if (fabs(M - *p) < 1e-9) return true;
44 }
45 return false;
46
}
47
48
49void calc_range(int first, int last,size_t N, double M = 24, string filename="nul")
50{
51 if (N ==0 || first >= last || filename.empty()) return;
52 clock_t ta = clock();
53 vector<int> vv(N, first);
54 int *end = &vv[N-1], *p = end, *arr = &vv[0];
55 ofstream ofs(filename.c_str());
56 size_t count = 0;
57 size_t count_b = 0;
58 unsigned long long max_big_size =0, max_all_size = 0;
59 while(true){
60 ++count_b;
61 if (calc(arr,N, M)) {
62 ofs.width(4);
63 ofs<< ++count << " ";
64 for (size_t i = 0; i < N; ++i) {
65 ofs.width(2);
66 ofs << arr[i]<< " ";
67 }
68 ofs << "\n";
69 if (max_big_size < big_size) max_big_size = big_size;
70 if (max_all_size < all_size) max_all_size = all_size;
71 }
72 while (p >= arr && *p >= last) --p;
73 if (p < arr) break;
74 int tmp = ++*p;
75 while (p < end) *++p = tmp;
76 }
77 ofs.close();
78 const char sep[] = "/";
79 cout << "total: " << count << sep << count_b << "\n"
80 << max_big_size << sep << max_all_size << "\n"
81 << "time: " << clock() - ta << "\n\n";
82}
83
84int main()
85{
86 calc_range(1,13,5,24,"nul");
87 cin.get();
88}
89
24_set_2.cpp
1
2#include <iostream>
3#include <fstream>
4#include <vector>
5#include <deque>
6#include <unordered_set>
7#include <ctime>
8#include <cmath>
9using namespace std;
10
11typedef unordered_set<double> MSET;
12typedef MSET::iterator MSETI;
13typedef deque<size_t>::iterator DQI;
14
15const size_t N = 5;
16const double M = 24;
17static MSET result[1<<N];
18//static vector<MSET> result(1<<N);
19//static vector<MSET> result(1<<N, MSET(256));
20static deque<size_t> dq[1<<N];
21size_t max_size = 0;
22
23inline void init()
24{
25 size_t count = 0;
26 for (size_t i =1; i < (1<<N); ++i) {
27 for (size_t j = 1; j <= (i >> 1); ++j) {
28 if ((i & j) != j) continue;
29 dq[i].push_back(j);
30 ++count;
31 }
32 }
33 cout << "total sets: " << count << "\n";
34}
35
36inline bool isequal_m(double na)
37{
38 const double zero = 1e-9;
39 if (fabs(na - M) < zero) return true;
40 return false;
41}
42
43bool calc(int src[])
44{
45 if (N == 0 || src == NULL) return false;
46 const size_t ii = (1 << N) - 1;
47 for (size_t i =1; i <= ii; ++i) result[i].clear();
48 for (size_t i = 0; i < N; ++i) result[1<<i].insert((double)src[i]);
49 for (size_t i = 1; i < ii; ++i) {
50 for (DQI r = dq[i].begin(), re = dq[i].end(); r != re; ++r){
51 size_t j = *r;
52 for (MSETI p = result[j].begin(), pe = result[j].end(); p != pe; ++p) {
53 double va = *p;
54 size_t k = i - j;
55 for (MSETI q = result[k].begin(),qe = result[k].end(); q != qe; ++q) {
56 double vb = *q;
57 result[i].insert(va + vb);
58 result[i].insert(va - vb);
59 result[i].insert(vb - va);
60 result[i].insert(va * vb);
61 if (va != 0 && vb != 0) {
62 result[i].insert(va / vb);
63 result[i].insert(vb / va);
64 }
65 }
66 }
67 }
68 }
69
70 for (size_t j = 1; j < ii; ++j) {
71 if (max_size < result[j].size()) max_size = result[j].size();
72 }
73
74 for (DQI r = dq[ii].begin(), re = dq[ii].end(); r != re; ++r) {
75 size_t j = *r;
76 for (MSETI p = result[j].begin(), pe = result[j].end(); p != pe; ++p) {
77 double va = *p;
78 size_t k = ii - j;
79 for (MSETI q = result[k].begin(),qe = result[k].end(); q != qe; ++q) {
80 double vb = *q;
81 if (isequal_m(va + vb)) return true;
82 if (isequal_m(va - vb)) return true;
83 if (isequal_m(vb - va)) return true;
84 if (isequal_m(va * vb)) return true;
85 if (va != 0 && vb != 0) {
86 if (isequal_m(va / vb)) return true;
87 if (isequal_m(vb / va)) return true;
88 }
89 }
90 }
91 }
92 return false;
93}
94
95
96void calc_range(int first, int last, string filename="nul")
97{
98 if (N ==0 || first >= last || filename.empty()) return;
99 clock_t ta = clock();
100 init();
101 vector<int> vv(N, first);
102 int *end = &vv[N-1], *p = end, *arr = &vv[0];
103 ofstream ofs(filename.c_str());
104 size_t count = 0;
105 size_t count_b = 0;
106 while(true){
107 ++count_b;
108 if (calc(arr)) {
109 ofs.width(4);
110 ofs<< ++count << " ";
111 for (size_t i = 0; i < N; ++i) {
112 ofs.width(2);
113 ofs << arr[i]<< " ";
114 }
115 ofs << "\n";
116 }
117 while (p >= arr && *p >= last) --p;
118 if (p < arr) break;
119 int tmp = ++*p;
120 while (p < end) *++p = tmp;
121 }
122 ofs.close();
123 const char sep[] = "/";
124 cout << "total: " << count << sep << count_b << "\n"
125 << "max_size: " << max_size << "\n"
126 << "time: " << clock() - ta << "\n\n";
127
128}
129
130int main()
131{
132 calc_range(1,13,"nul");
133 cin.get();
134}
135
24_set_3.cpp
1
2#include <iostream>
3#include <fstream>
4#include <vector>
5#include <unordered_set>
6#include <ctime>
7#include <cmath>
8using namespace std;
9
10typedef unordered_set<double> MSET;
11typedef MSET::const_iterator MSETI;
12
13const size_t N = 5;
14const double M = 24;
15static MSET result[1<<N];
16static size_t num[N];
17//static vector<MSET> result(1<<N);
18//static vector<MSET> result(1<<N, MSET(256));
19size_t count_expr = 0;
20size_t count_func= 0;
21
22bool calc(size_t step);
23
24bool calc_num(int src[])
25{
26 if (M <= 1) {
27 if (M == 1 && src[0] == 24) return true;
28 return false;
29 }
30 for (size_t i = 0, j = 1; i < N; ++i, j *= 2) num[i] = j;
31 for (size_t i = 1; i < (1 << N); ++i) result[i].clear();
32 for (size_t i = 0; i < N; ++i) result[1<<i].insert((double)src[i]);
33 return calc(N);
34}
35
36inline void merge_set(size_t i, size_t j)
37{
38 const size_t k = i + j;
39 for (MSETI p = result[i].begin(), pe = result[i].end(); p != pe; ++p) {
40 double va = *p;
41 for (MSETI q = result[j].begin(),qe = result[j].end(); q != qe; ++q) {
42 double vb = *q;
43 result[k].insert(va + vb);
44 result[k].insert(va - vb);
45 result[k].insert(vb - va);
46 result[k].insert(va * vb);
47 if (va != 0 && vb != 0) {
48 result[k].insert(va / vb);
49 result[k].insert(vb / va);
50 }
51 }
52 }
53}
54
55inline bool isequal_m(double na)
56{
57 const double zero = 1e-9;
58 if (fabs(na - M) < zero) return true;
59 return false;
60}
61
62inline bool merge_set2(size_t i, size_t j)
63{
64 for (MSETI p = result[i].begin(), pe = result[i].end(); p != pe; ++p) {
65 double va = *p;
66 for (MSETI q = result[j].begin(),qe = result[j].end(); q != qe; ++q) {
67 double vb = *q;
68 if (isequal_m(va + vb)) return true;
69 if (isequal_m(va - vb)) return true;
70 if (isequal_m(vb - va)) return true;
71 if (isequal_m(va * vb)) return true;
72 if (va != 0 && vb != 0) {
73 if (isequal_m(va / vb)) return true;
74 if (isequal_m(vb / va)) return true;
75 }
76 }
77 }
78 return false;
79}
80
81bool calc(size_t step)
82{
83 ++count_func;
84 if (step == 2) {
85 ++count_expr;
86 return merge_set2(num[0], num[1]);
87 }
88 // if (step == 1) {
89 // ++count_expr;
90 // size_t j = (1 << N) - 1;
91 // for (MSETI q = result[j].begin(),qe = result[j].end(); q != qe; ++q)
92 // if (isequal_m(*q)) return true;
93 // return false;
94 // }
95
96 --step;
97 for (size_t i = 0; i < step; i++){
98 for(size_t j = i + 1; j <= step; j++) {
99 size_t na = num[i];
100 size_t nb = num[j];
101 num[i] = na + nb;
102 num[j] = num[step];
103 merge_set(na, nb);
104 if (calc(step)) return true;
105 num[i] = na;
106 num[j] = nb;
107 }
108 }
109 return false;
110}
111
112void calc_range(int first, int last, string filename="nul")
113{
114 if (N ==0 || first >= last || filename.empty()) return;
115 clock_t ta = clock();
116 vector<int> vv(N, first);
117 int *end = &vv[N-1], *p = end, *arr = &vv[0];
118 ofstream ofs(filename.c_str());
119 size_t count = 0;
120 size_t count_b = 0;
121 while(true){
122 ++count_b;
123 if (calc_num(arr)) {
124 ofs.width(4);
125 ofs<< ++count << " ";
126 for (size_t i = 0; i < N; ++i) {
127 ofs.width(2);
128 ofs << arr[i]<< " ";
129 }
130 ofs << "\n";
131 }
132 while (p >= arr && *p >= last) --p;
133 if (p < arr) break;
134 int tmp = ++*p;
135 while (p < end) *++p = tmp;
136 }
137 ofs.close();
138 const char sep[] = "/";
139 cout << "total: " << count << sep << count_b << "\n"
140 << count_expr << "/" << count_func << "\n"
141 << "time: " << clock() - ta << "\n\n";
142
143}
144
145int main()
146{
147 calc_range(1,13,"nul");
148 cin.get();
149}
150
151
152
153