《程式設計之美》讀書筆記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）），再加上實作集合所采用的資料結構的開銷，效率高不了。