24點游戲題庫演算法分析

来源:https://www.cnblogs.com/arv000/archive/2022/06/28/16421576.html
-Advertisement-
Play Games

​一、4數種類分析 統計分析 從標有1-10的數字的10個小球中取出1個小球記錄小球的數字,然後將小球放回,如此反覆4次取出4小球的數字組成的序號一共有多少種。註意:1.1.8.9 和1.8.1.9 算是一種。 需要分為一下幾種情況: 四個小球數字都相等情況: 一個有10種 三個小球數字相等: 一共 ...


一、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. 如果不存在就添加到列表中。

遍歷所有的數據。

#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類型直接表示數據,或者是數據運算結果,我們定義一個分數類,專門用來計算分數的,加、減、乘、除,這樣可以儘可能保存數據的正確性。

加法

\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點題庫分析。


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 最新的一份《The State of WebAssembly 2022》調查報告已出爐,“對於 WebAssembly 來說,這是相當不錯的一年”。報告的一些重點內容包括:Rust 的使用率和渴望度持續攀升Python 的使用量有了很大的提升JavaScript 已經成為一種可行的 WebAssem ...
  • 迴圈迭代: 1 public class steps { 2 public int js(int n) { 3 int one = 2; //初始化為第三級臺階最後跨一步的走法 4 int two = 1; //初始化為第三級臺階最後跨兩步(一下邁過去兩個臺階)的走法 5 int sum = 0; ...
  • 基本概念 指針代表記憶體地址。 通常在類型關鍵字的後面加字元*來表示指針,表示指針指向什麼類型的值。比如,char*表示一個指向字元的指針,float*表示一個指向float類型值的指針。 指針指向的可能還是指針,這時要用兩個星號**表示。 int** foo; 指針變數初始化 聲明指針變數之後,編譯 ...
  • 一. NIO 基礎 non-blocking io 非阻塞 IO 1. 三大組件 1.1 Channel & Buffer channel 有一點類似於 stream,它就是讀寫數據的雙向通道,可以從 channel 將數據讀入 buffer,也可以將 buffer 的數據寫入 channel,而之 ...
  • ​點擊藍色“程式員黃小斜”關註我喲 加個“星標”,每天和你一起多進步一點點! 本文來源 | 程式員求職面試(ID:CoderJob) 內容參考自 | 脈脈 近日,有位阿裡員工發帖稱,自己手下有兩個應屆生,985本碩和985本,但兩人無論性格、技術,還是家境都不一樣,問大家如何選擇。 原貼如下: 有不 ...
  • 面試官:看你簡歷上面寫著精通MySQL,我問你一個MySQL鎖相關的問題,你看一下這條SQL會對哪些數據加鎖? ...
  • 使用 Java 編譯項目時產生的報錯 java: Compilation failed: internal java compiler error 錯誤原因 導致這個錯誤的原因主要有三點: 編譯版本不匹配 JDK 版本不支持 記憶體不足 解決辦法 對於編譯版本不匹配,我們要先查看 IDEA 的編譯的 ...
  • 前言 嗨嘍,大家好!這裡是魔王吶~ 環境使用: Python 3.8 解釋器<運行代碼> Pycharm 編輯器 <寫代碼> 模塊使用]: requests >>> 數據請求 第三方模塊 pip install requests <工具> re <正則表達式模塊> 如果安裝python第三方模塊: ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...