雁過無痕

《編程之美》讀書筆記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