24点游戏题库算法分析

技术分享 4年前 (2022-06-29) 0 999+

关注

一、4数种类分析

统计分析

从标有1-10的数字的10个小球中取出1个小球记录小球的数字，然后将小球放回，如此反复4次取出4小球的数字组成的序号一共有多少种。注意：1.1.8.9 和1.8.1.9 算是一种。

需要分为一下几种情况：

四个小球数字都相等情况：

一个有10种

三个小球数字相等：

一共有10*9种 = 90

两个小球数字相等，另外两个小球数字不相等

一共有10 * ( 9 * 8 /2 )种 = 360

10表示：10个相等的两个小球

( 9 * 8 /2 )表示：另外两个小球不相等的情况。

两个小球数字相等，另外两个小球也相等。

一共有(10*9)/2 中 = 45

四个小球数字都不想等

$24点游戏题库算法分析$ 编辑 = 10* 9 * 8 * 7 / (4 * 3 *2 *1 ) = 210

编辑 = 10* 9 * 8 * 7 / (4 * 3 *2 *1 ) = 210

总数为=10 + 90 + 360 + 45 + 210 = 715

代码分析

代码中我们可以直接使用遍历的方式进行穷举，

1 . 对比记录列表中的数据是否存在，如果存在就忽略。

2. 如果不存在就添加到列表中。

遍历所有的数据。

#define MAXNUM 10 QList<struNum> initList() {     QList<struNum> list;     for (int i1 = 1;i1 <= MAXNUM; i1++) {         for (int i2 = 1;i2 <= MAXNUM; i2++) {             for (int i3 = 1;i3 <= MAXNUM; i3++) {                 for (int i4 = 1;i4 <= MAXNUM; i4++) {                     struNum num(i1,i2,i3,i4);                     if(!isInList(num,list)){                         list.append(num);                     }                 }             }         }     }     return list; }

判断是否存在列表中

typedef  struct SNUM{     SNUM(int num1,int num2,int num3,int num4){         this->num1 = num1;         this->num2 = num2;         this->num3 = num3;         this->num4 = num4;     }     int num1 =0;     int num2 =0;     int num3 =0;     int num4 =0;     int c = 0;  // 四个数能够计算24算法。 }struNum; bool isInList(struNum num, QList<struNum> list) {     int numList[4] = {num.num1,num.num2,num.num3,num.num4};     bool result = false;     for (int i1 = 0 ; i1 < 4; i1 ++) {         for (int i2 = 0 ; i2 < 4; i2 ++){             if(i1 == i2) continue;             for (int i3 = 0 ; i3 < 4; i3 ++){                 if(i2 == i3 || i1 == i3) continue;                 for (int i4 = 0 ; i4 < 4; i4 ++){                     if(i1 == i4 || i2 == i4 || i3 == i4) continue;                       foreach(auto item ,list){                             if(item.num1 == numList[i1]                                 && item.num2 == numList[i2]                                 && item.num3 == numList[i3]                                 && item.num4 == numList[i4]){                                 result = true;                             }                       }                 }             }         }     }     return result; }

二、四数排列算法分析

4个数按照顺序排列，一共有多少种排列方法。

我们可以使用遍历方法，将所有的数字进行遍历，那么可以得到一下算法。可以看到以下算法的步骤需要经过4*4*4*4 次运算。那么我们通过观察可以优化代码算法。

优化前

4*4*4*4 = 256次运算

   int numList[4] = {num1,num2,num3,num4};     for (int i1 = 0 ; i1 < 4; i1 ++) {         for (int i2 = 0 ; i2 < 4; i2 ++){             for (int i3 = 0 ; i3 < 4; i3 ++){                 for (int i4 = 0 ; i4 < 4; i4 ++){                   if(i1 != i2 && i1 != i3 && i1 != i4 && i2 != i3 && i2 != i4 && i3 != i4){                         qInfo()<<numList[i1]<<" "<<numList[i2] <<" "<< numList[i3] <<" "<<" "<< numList[i4];                         c++;                    }                 }             }         }     } 点击并拖拽以移动

优化后

4*3*2 = 24 次运算。

 1 int numList[4] = {num1,num2,num3,num4};  2     int c =0;  3     for (int i1 = 0 ; i1 < 4; i1 ++) {  4         for (int i2 = 0 ; i2 < 4; i2 ++){  5             if(i1 == i2) continue;  6             for (int i3 = 0 ; i3 < 4; i3 ++){  7                 if(i2 == i3 || i1 == i3) continue;  8                 for (int i4 = 0 ; i4 < 4; i4 ++){  9                     if(i1 == i4 || i2 == i4 || i3 == i4) continue; 10                      qInfo()<<numList[i1]<<" "<<numList[i2] <<" "<< numList[i3] <<" "<<" "<< numList[i4]; 11                         c++; 12                 } 13             } 14         } 15     }

三、分数计算类

由于计算过程中可能会遇到分数计算，因此我们不能使用int类型直接表示数据，或者是数据运算结果，我们定义一个分数类，专门用来计算分数的，加、减、乘、除，这样可以尽可能保存数据的正确性。

加法

24点游戏题库算法分析编辑

编辑

减法

24点游戏题库算法分析编辑

编辑

乘法

24点游戏题库算法分析编辑

编辑

除法

$24点游戏题库算法分析$ 编辑

编辑

LNum.h

 1 #ifndef LNUM_H  2 #define LNUM_H  3   4 class LNum  5 {  6   7 public:  8     LNum(int Molecule);  9     LNum(int Molecule,int Denominator); 10     int getMolecule();                   // 获取分子 11     int getDenominator();                // 获取分母 12     void setMolecule(int molecule);      // 设置分子 13     void setDenominator(int denominator);// 设置分母 14     double data(); 15     LNum operator + ( LNum p1); 16     LNum operator - ( LNum p1); 17     LNum operator * ( LNum p1); 18     LNum operator / ( LNum p1); 19     bool operator ==( LNum p1) ; 20 private: 21     // 分子 22     int m_iMolecule = 1; 23     // 分母 24     int m_iDenominator = 1; 25     void Equivalency();         // 约分 26  27 }; 28  29 #endif // LNUM_H

LNum.cpp

  1 #include "lnum.h"   2    3    4 LNum::LNum(int num)   5     :m_iMolecule(num)   6     ,m_iDenominator(1)   7 {   8    9 }  10   11 LNum::LNum(int Molecule, int Denominator)  12     :m_iMolecule(Molecule)  13     ,m_iDenominator(Denominator)  14 {  15   16 }  17   18 int LNum::getMolecule()  19 {  20     Equivalency();  21     return m_iMolecule;  22 }  23   24 int LNum::getDenominator()  25 {  26     Equivalency();  27     return  m_iDenominator;  28 }  29   30 void LNum::setMolecule(int molecule)  31 {  32     m_iMolecule = molecule;  33 }  34   35 void LNum::setDenominator(int denominator)  36 {  37     m_iDenominator = denominator;  38 }  39   40 double LNum::data()  41 {  42     Equivalency();  43     if(m_iDenominator == 1){  44         return m_iMolecule;  45     }  46     return double(m_iMolecule)/double(m_iDenominator);  47 }  48   49 void LNum::Equivalency()  50 {  51     int num = m_iMolecule> m_iDenominator?m_iDenominator:m_iMolecule;  52   53     for (int i  = 2 ; i < num ;i++) {  54         if(m_iDenominator%i == 0 && m_iMolecule%i ==0){  55             m_iDenominator = m_iDenominator/i;  56             m_iMolecule = m_iMolecule/i;  57             num = m_iMolecule> m_iDenominator?m_iDenominator:m_iMolecule;  58         }  59     }  60 }  61   62 LNum LNum::operator +(LNum p1)  63 {  64     LNum res(getMolecule(),getDenominator());  65     res.setMolecule(getMolecule()*p1.getDenominator() + getDenominator()*p1.getMolecule());  66     res.setDenominator(getDenominator()*p1.getDenominator());  67     return  res;  68 }  69   70 LNum LNum::operator -(LNum p1)  71 {  72     LNum res(getMolecule(),getDenominator());  73     res.setMolecule(getMolecule()*p1.getDenominator() - getDenominator()*p1.getMolecule());  74     res.setDenominator(getDenominator()*p1.getDenominator());  75     return  res;  76 }  77   78 LNum LNum::operator *(LNum p1)  79 {  80     LNum res(getMolecule(),getDenominator());  81     res.setMolecule(getMolecule()*p1.getMolecule());  82     res.setDenominator(getDenominator()*p1.getDenominator());  83     return  res;  84 }  85   86 LNum LNum::operator /(LNum p1)  87 {  88     LNum res(getMolecule(),getDenominator());  89     res.setMolecule(getMolecule()*p1.getDenominator());  90     res.setDenominator(getDenominator()*p1.getMolecule());  91     return  res;  92 }  93   94 bool LNum::operator ==(LNum p1)  95 {  96     if (getMolecule() == p1.getMolecule() && getDenominator() == p1.getDenominator()) {  97         return true;  98     }  99     else{ 100         return false; 101     } 102  103 }

四、加减乘除操作符遍历

第一步将操作符数字化，方便遍历。可以得到如下公式。x为操作符标识。

 1 double jisuan(LNum num1,LNum num2,int x){  2     switch (x) {  3     case 0:  4         return num1+num2;  5     case 1:  6         return num1-num2 ;  7     case 2:  8         return num1*num2;  9     case 3: 10         return num1/num2 ; 11     } 12     return 0; 13 }

五、探测4个数是否能计算24

循环遍历4个数的不同位置，并且循环遍历算法。判断其内容是否为24如果是24那么表示可以计算成功。

 1 int is24OK(LNum num1, LNum num2, LNum num3, LNum num4)  2 {  3     int result = 0;  4      QList<struRecordNum> list;  5     LNum numList[4] = {num1,num2,num3,num4};  6         // 交换4个数字的顺序。  7         for (int i1 = 0 ; i1 < 4; i1 ++) {  8             for (int i2 = 0 ; i2 < 4; i2 ++){  9                 if(i1 == i2) continue; 10                 for (int i3 = 0 ; i3 < 4; i3 ++){ 11                     if(i2 == i3 || i1 == i3) continue; 12                     for (int i4 = 0 ; i4 < 4; i4 ++){ 13                         if(i1 == i4 || i2 == i4 || i3 == i4) continue; 14                         //  qInfo()<<numList[i1]<<" "<<numList[i2] <<" "<< numList[i3] <<" "<<" "<< numList[i4]; 15                           int x=suanfatongji(numList[i1],numList[i2],numList[i3],numList[i4],&list); 16                           if(x !=0){ 17                               qInfo()<<"x:"<<x; 18                               result += x; 19                           } 20                     } 21                 } 22             } 23         } 24         return result; 25 } 26  27 int suanfatongji(LNum num1, LNum num2, LNum num3, LNum num4, QList<struRecordNum> *list) 28 { 29         LNum sum = 0; 30  31         int c= 0; 32         for(int i1 = 0 ; i1 < 4; i1 ++){ 33             for(int i2 = 0 ; i2 < 4; i2 ++ ){ 34                 for(int i3 = 0 ; i3 < 4; i3 ++){ 35                     sum = jisuan(jisuan(jisuan (num1,num2,i1),num3,i2),num4,i3) ; 36                     if(24.0  == sum.data()){ 37                         // 是否找到相同的算法，因为有重复数字可能导致算法想法和数字相同的情况。 38                         bool result = false; 39                         for(auto item : *list){ 40                             if(item.num1 == static_cast<int>(num1.data()) 41                             && item.num2 == static_cast<int>(num2.data()) 42                             && item.num3 == static_cast<int>(num3.data()) 43                             && item.num4 == static_cast<int>(num4.data()) 44                             && item.option1 == i1 45                             && item.option2 == i2 46                             && item.option3 == i3){ 47                                 result = true; 48                             } 49                         } 50                         if(!result){ 51                             struRecordNum tmpItem; 52                             tmpItem.num1 =  static_cast<int>(num1.data()); 53                             tmpItem.num2 =  static_cast<int>(num2.data()); 54                             tmpItem.num3 =  static_cast<int>(num3.data()); 55                             tmpItem.num4 =  static_cast<int>(num4.data()); 56                             tmpItem.option1 =  i1; 57                             tmpItem.option2 =  i2; 58                             tmpItem.option3 =  i3; 59                             list->append(tmpItem); 60                              c++; 61                              qInfo()<< "(( "<< num1.data() <<strOption(i1) << num2.data() <<")"<<strOption(i2)<< num3.data()<<")" <<strOption(i3)<< num4.data(); 62                         } 63                     } 64                 } 65             } 66         } 67         return c; 68 }