• 24点游戏题库算法分析

    目录

    一、4数种类分析

    二、四数排列算法分析

    三、分数计算类

    四、加减乘除操作符遍历

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

    六、源码地址

    一、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

    • 四个小球数字都不想等

    C_{10}^{4} = 10* 9 * 8 * 7 / (4 * 3 *2 *1 ) = 210 

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

    代码分析

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

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

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

    遍历所有的数据。

    1. #define MAXNUM 10
    2. QList<struNum> initList()
    3. {
    4.     QList<struNum> list;
    5.     for (int i1 = 1;i1 <= MAXNUM; i1++) {
    6.         for (int i2 = 1;i2 <= MAXNUM; i2++) {
    7.             for (int i3 = 1;i3 <= MAXNUM; i3++) {
    8.                 for (int i4 = 1;i4 <= MAXNUM; i4++) {
    9.                     struNum num(i1,i2,i3,i4);
    10.                     if(!isInList(num,list)){
    11.                         list.append(num);
    12.                     }
    13.                 }
    14.             }
    15.         }
    16.     }
    17.     return list;
    18. }

    判断是否存在列表中

    1. typedef  struct SNUM{
    2.     SNUM(int num1,int num2,int num3,int num4){
    3.         this->num1 = num1;
    4.         this->num2 = num2;
    5.         this->num3 = num3;
    6.         this->num4 = num4;
    7.     }
    8.     int num1 =0;
    9.     int num2 =0;
    10.     int num3 =0;
    11.     int num4 =0;
    12.     int c = 0;  // 四个数能够计算24算法。
    13. }struNum;
    14. bool isInList(struNum num, QList<struNum> list)
    15. {
    16.     int numList[4] = {num.num1,num.num2,num.num3,num.num4};
    17.     bool result = false;
    18.     for (int i1 = 0 ; i1 < 4; i1 ++) {
    19.         for (int i2 = 0 ; i2 < 4; i2 ++){
    20.             if(i1 == i2) continue;
    21.             for (int i3 = 0 ; i3 < 4; i3 ++){
    22.                 if(i2 == i3 || i1 == i3) continue;
    23.                 for (int i4 = 0 ; i4 < 4; i4 ++){
    24.                     if(i1 == i4 || i2 == i4 || i3 == i4) continue;
    25.                       foreach(auto item ,list){
    26.                             if(item.num1 == numList[i1]
    27.                                 && item.num2 == numList[i2]
    28.                                 && item.num3 == numList[i3]
    29.                                 && item.num4 == numList[i4]){
    30.                                 result = true;
    31.                             }
    32.                       }
    33.                 }
    34.             }
    35.         }
    36.     }
    37.     return result;
    38. }

    二、四数排列算法分析

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

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

    优化前

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

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

    优化后

    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类型直接表示数据，或者是数据运算结果，我们定义一个分数类，专门用来计算分数的，加、减、乘、除，这样可以尽可能保存数据的正确性。

    加法

    \frac{a}{b}+\frac{c}{d}=\frac{a*d+b*c}{d*b}

    减法

    \frac{a}{b}-\frac{c}{d} = \frac{a*d-b*c}{b*d}

    乘法

    \frac{a}{b}*\frac{c}{d} = \frac{a*c}{b*d}

    除法

    \frac{a}{b}/\frac{c}{d}=\frac{a*d}{b*c}

    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. }

    六、源码地址

    啊渊 / QT博客案例 · GitCode 24点题库分析。

  • 相关阅读:
    navicat 导入dmp文件
    JAVA毕设项目足球信息发布平台（java+VUE+Mybatis+Maven+Mysql）
    windows系统下mysql的主从复制
    Taro进阶
    基于springboot小型车队管理系统毕业设计源码
    Idea部署dubbo-admin
    事件总线及插槽
    HTML5CSS3提高导读
    怎么能还不会2PC、3PC？赶快学起来
    wordpress后台不能登录（多次重定向）,前台样式里面https加载不上该怎么办呢？
  • 原文地址：https://blog.csdn.net/arv002/article/details/125453746