雁過(guò)無(wú)痕

《編程之美》讀書(shū)筆記22：    1.16  24點(diǎn)游戲（補(bǔ)充）

給定n個(gè)數(shù)，能否只通過(guò)加減乘除計(jì)算得到24？

書(shū)上給出的最后一種解法，通過(guò)使用集合記錄中間結(jié)果來(lái)減少冗余計(jì)算。本以為，程序會(huì)占用大量的內(nèi)存，用一個(gè)極端的例子（13, 773, 28, 98, 731, 1357,97357246這7個(gè)數(shù)）測(cè)試了一下實(shí)現(xiàn)的程序，發(fā)現(xiàn)程序竟然占用了1G以上的內(nèi)存（無(wú)論集合的實(shí)現(xiàn)采用STL中的set還是unordered_set），但后來(lái)，取7個(gè)均在1到13之間的數(shù)，再重新測(cè)試了下發(fā)現(xiàn)，程序所占用的內(nèi)存比想像的小的多，也就幾兆。

對(duì)數(shù)值都在1到13之間的n個(gè)數(shù)的所有組合進(jìn)行判斷。在n等于4時(shí)，實(shí)現(xiàn)的程序約過(guò)1秒就給出了結(jié)果，而n等于5時(shí)，程序要運(yùn)行58秒，效率實(shí)在差，可以通過(guò)這幾方面優(yōu)化：

① 保存每個(gè)集合的子集合的編號(hào)：

對(duì)給定的n，共有1到2^n – 1個(gè)集合，每個(gè)集合的子集合編號(hào)是固定的，但原程序每計(jì)算一個(gè)n個(gè)數(shù)的組合，都要對(duì)這些子集合編號(hào)計(jì)算一遍，可以保存每個(gè)集合的子集合編號(hào)，減少大量的重復(fù)計(jì)算。

② 改進(jìn)計(jì)算子集合編號(hào)的算法：

原程序的算法的時(shí)間復(fù)雜度是O(4^n)，在n較大時(shí)，相當(dāng)慢。

③ 對(duì)最后一個(gè)集合是否含有24的判斷：

原程序要遍歷該集合所有的元素，效率比較差，可以考慮，在將兩個(gè)集合合并到該集合時(shí)，只對(duì)取出的兩個(gè)元素的計(jì)算結(jié)果是否為24進(jìn)行判斷，這樣不僅省去最后的遍歷，而且不用將結(jié)果插入到最后的那個(gè)集合中，省去了大量操作。

采用①和③兩種改進(jìn)方法后，程序運(yùn)行時(shí)間由原來(lái)的58秒縮短到了14秒，但這還不能讓人滿(mǎn)意。對(duì)2,3,5,6,8這5個(gè)數(shù)，如果用書(shū)上的第一種方法，可以只調(diào)用4次函數(shù)就可以得到結(jié)果：2+3+5+6+8=24，但用集合的方法來(lái)處理，卻要對(duì)所有的集合進(jìn)行子集合合并后才能給出結(jié)果，這造成了效率極差，可以這樣改進(jìn)該算法：

初始有n個(gè)集合：每一次任意取出2個(gè)集合，合并后，放回去，再取出任意2個(gè)集合，重復(fù)前面的操作，直到只剩下一個(gè)集合為止。

例如：初始有5個(gè)數(shù)，把這5個(gè)數(shù)分別放到5個(gè)集合，并分別編號(hào)為：1、2、4、8、16。任意取出2個(gè)集合，假設(shè)為1和4，將1和4合并，得到編號(hào)為5(=1+4)的集合，剩下的集合為：5、2、16、8，再取出2個(gè)，假設(shè)為5和8，合并后，得到13、2、16，再取2個(gè)，假設(shè)為13和16，合并后得到29、2，當(dāng)剩下2個(gè)集合時(shí)，可以直接對(duì)這兩個(gè)集合間的的計(jì)算結(jié)果是否為24進(jìn)行判斷，直接得出結(jié)果，省去不必要的合并（合并后再判斷是否有元素近似等于24，程序運(yùn)行時(shí)間8s多，而直接對(duì)計(jì)算結(jié)果判斷，程序只要運(yùn)行1s多）。

優(yōu)化后的程序，只要運(yùn)行1s多。但其效率還是不如書(shū)上的第一種方法的改進(jìn)版，仔細(xì)想想，n越大，集合的元素也就越多，兩個(gè)集合之間的合并，就越耗時(shí)間。而且采用集合保存中間結(jié)果，表面上減少了重復(fù)狀態(tài)，會(huì)提高效率，但實(shí)際上，由于采用了集合，就多了很多不必要的計(jì)算，（比如，對(duì)2+3+5+6+8=24，最少只要4次計(jì)算就能得出結(jié)果，采用集合合并后，則要計(jì)算幾百次（約為6^4）），再加上實(shí)現(xiàn)集合所采用的數(shù)據(jù)結(jié)構(gòu)的開(kāi)銷(xiāo)，效率高不了。

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