雁过无痕

《编程之美》读书笔记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