溫馨提示×

溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》

如何運用算法實現(xiàn)“24點”數(shù)學(xué)游戲？

發(fā)布時間：2020-05-27 16:23:07 來源：億速云 閱讀：302 作者：鴿子 欄目：編程語言

“24點”是一種數(shù)學(xué)游戲，正如象棋、圍棋一樣是一種人們喜聞樂見的娛樂活動。它始于何年何月已無從考究，但它以自己獨具的數(shù)學(xué)魅力和豐富的內(nèi)涵正逐漸被越來越多的人們所接受。今天就為大家分享一道關(guān)于“24點”的算法題目。

話不多說，直接看題。

題目：你有 4 張寫有 1 到 9 數(shù)字的牌。你需要判斷是否能通過 *，/，+，-，(，) 的運算得到 24。

示例 1：

輸入: [4, 1, 8, 7]

輸出: True

解釋: (8-4) * (7-1) = 24

示例 2：

輸入: [1, 2, 1, 2]

輸出: False

注意：

  • 除法運算符 / 表示實數(shù)除法，而不是整數(shù)除法。例如 ：4 / (1 - 2/3) = 12 。
  • 每個運算符對兩個數(shù)進行運算。特別是我們不能用 - 作為一元運算符。例如，[1, 1, 1, 1] 作為輸入時，表達式 -1 - 1 - 1 - 1 是不允許的。
  • 你不能將數(shù)字連接在一起。例如，輸入為 [1, 2, 1, 2] 時，不能寫成 12 + 12 。

題目分析

拿到題目，第一反應(yīng)就可以想到暴li求解。如果我們要判斷給出的4張牌是否可以通過組合得到24，那我們只需找出所有的可組合的方式進行遍歷。

4個數(shù)字，3個操作符，外加括號，基本目測就能想到組合數(shù)不會大到超出邊界。所以，我們只要把他們統(tǒng)統(tǒng)列出來，不就可以進行求解了嗎？說干就干！

我們首先定義個方法，用來判斷兩個數(shù)的的所有操作符組合是否可以得到24。

func judgePoint24_2(a, b float64) bool {
    return a+b == 24 || a*b == 24 || a-b == 24 || b-a == 24 || a/b == 24 || b/a == 24 
}

但是這個方法寫的正確嗎？其實不對！因為在計算機中，實數(shù)在計算和存儲過程中會有一些微小的誤差，對于一些與零作比較的語句來說，有時會因誤差而導(dǎo)致原本是等于零但結(jié)果卻小于或大于零之類的情況發(fā)生，所以常用一個很小的數(shù) 1e-6 代替 0，進行判讀！

(1e-6：表示1乘以10的負6次方。Math.abs(x)<1e-6 其實相當于x==0。1e-6(也就是0.000001)叫做epslon，用來抵消浮點運算中因為誤差造成的相等無法判斷的情況。這個知識點需要掌握！)

舉個例子：

func main() {
    var a float64
    var b float64
    b = 2.0
    //math.Sqrt：開平方根
    c := math.Sqrt(2)
    a = b - c*c
    fmt.Println(a == 0)                  //false
    fmt.Println(a < 1e-6 && a > -(1e-6)) //true
}

這里直接用 a==0 就會得到false，但是通過 a < 1e-6 && a > -(1e-6) 卻可以進行準確的判斷。

所以我們將上面的方法改寫：

 //go語言
 //judgePoint24_2：判斷兩個數(shù)的所有操作符組合是否可以得到24
 func judgePoint24_2(a, b float64) bool {
     return (a+b < 24+1e-6 && a+b > 24-1e-6) ||
         (a*b < 24+1e-6 && a*b > 24-1e-6) ||
         (a-b < 24+1e-6 && a-b > 24-1e-6) ||
         (b-a < 24+1e-6 && b-a > 24-1e-6) ||
         (a/b < 24+1e-6 && a/b > 24-1e-6) ||
         (b/a < 24+1e-6 && b/a > 24-1e-6) 
}

完善了通過兩個數(shù)來判斷是否可以得到24的方法，現(xiàn)在我們加一個判斷三個數(shù)是否可以得到24的方法。

//硬核代碼，不服來辯！
func judgePoint24_3(a, b, c float64) bool {
    return judgePoint24_2(a+b, c) ||
        judgePoint24_2(a-b, c) ||
        judgePoint24_2(a*b, c) ||
        judgePoint24_2(a/b, c) ||
        judgePoint24_2(b-a, c) ||
        judgePoint24_2(b/a, c) ||

        judgePoint24_2(a+c, b) ||
        judgePoint24_2(a-c, b) ||
        judgePoint24_2(a*c, b) ||
        judgePoint24_2(a/c, b) ||
        judgePoint24_2(c-a, b) ||
        judgePoint24_2(c/a, b) ||

        judgePoint24_2(c+b, a) ||
        judgePoint24_2(c-b, a) ||
        judgePoint24_2(c*b, a) ||
        judgePoint24_2(c/b, a) ||
        judgePoint24_2(b-c, a) ||
        judgePoint24_2(b/c, a)
}

好了。三個數(shù)的也出來了，我們再加一個判斷4個數(shù)為24點的方法：（排列組合，我想大家都會....）

前方高能！?。?/p>

前方高能?。?！

前方高能?。。?/p>

//硬核代碼，不服來辯！
func judgePoint24(nums []int) bool {
    return judgePoint24_3(float64(nums[0])+float64(nums[1]), float64(nums[2]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[0])-float64(nums[1]), float64(nums[2]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[0])*float64(nums[1]), float64(nums[2]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[0])/float64(nums[1]), float64(nums[2]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[1])-float64(nums[0]), float64(nums[2]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[1])/float64(nums[0]), float64(nums[2]), float64(nums[3])) ||

        judgePoint24_3(float64(nums[0])+float64(nums[2]), float64(nums[1]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[0])-float64(nums[2]), float64(nums[1]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[0])*float64(nums[2]), float64(nums[1]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[0])/float64(nums[2]), float64(nums[1]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[2])-float64(nums[0]), float64(nums[1]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[2])/float64(nums[0]), float64(nums[1]), float64(nums[3])) ||

        judgePoint24_3(float64(nums[0])+float64(nums[3]), float64(nums[2]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[0])-float64(nums[3]), float64(nums[2]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[0])*float64(nums[3]), float64(nums[2]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[0])/float64(nums[3]), float64(nums[2]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[3])-float64(nums[0]), float64(nums[2]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[3])/float64(nums[0]), float64(nums[2]), float64(nums[1])) ||

        judgePoint24_3(float64(nums[2])+float64(nums[3]), float64(nums[0]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[2])-float64(nums[3]), float64(nums[0]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[2])*float64(nums[3]), float64(nums[0]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[2])/float64(nums[3]), float64(nums[0]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[3])-float64(nums[2]), float64(nums[0]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[3])/float64(nums[2]), float64(nums[0]), float64(nums[1])) ||

        judgePoint24_3(float64(nums[1])+float64(nums[2]), float64(nums[0]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[1])-float64(nums[2]), float64(nums[0]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[1])*float64(nums[2]), float64(nums[0]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[1])/float64(nums[2]), float64(nums[0]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[2])-float64(nums[1]), float64(nums[0]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[2])/float64(nums[1]), float64(nums[0]), float64(nums[3])) ||

        judgePoint24_3(float64(nums[1])+float64(nums[3]), float64(nums[2]), float64(nums[0])) ||
        judgePoint24_3(float64(nums[1])-float64(nums[3]), float64(nums[2]), float64(nums[0])) ||
        judgePoint24_3(float64(nums[1])*float64(nums[3]), float64(nums[2]), float64(nums[0])) ||
        judgePoint24_3(float64(nums[1])/float64(nums[3]), float64(nums[2]), float64(nums[0])) ||
        judgePoint24_3(float64(nums[3])-float64(nums[1]), float64(nums[2]), float64(nums[0])) ||
        judgePoint24_3(float64(nums[3])/float64(nums[1]), float64(nums[2]), float64(nums[0]))
}

Go語言示例

搞定收工，我們整合全部代碼如下：

//硬核編程...
func judgePoint24(nums []int) bool {
    return judgePoint24_3(float64(nums[0])+float64(nums[1]), float64(nums[2]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[0])-float64(nums[1]), float64(nums[2]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[0])*float64(nums[1]), float64(nums[2]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[0])/float64(nums[1]), float64(nums[2]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[1])-float64(nums[0]), float64(nums[2]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[1])/float64(nums[0]), float64(nums[2]), float64(nums[3])) ||

        judgePoint24_3(float64(nums[0])+float64(nums[2]), float64(nums[1]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[0])-float64(nums[2]), float64(nums[1]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[0])*float64(nums[2]), float64(nums[1]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[0])/float64(nums[2]), float64(nums[1]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[2])-float64(nums[0]), float64(nums[1]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[2])/float64(nums[0]), float64(nums[1]), float64(nums[3])) ||

        judgePoint24_3(float64(nums[0])+float64(nums[3]), float64(nums[2]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[0])-float64(nums[3]), float64(nums[2]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[0])*float64(nums[3]), float64(nums[2]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[0])/float64(nums[3]), float64(nums[2]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[3])-float64(nums[0]), float64(nums[2]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[3])/float64(nums[0]), float64(nums[2]), float64(nums[1])) ||

        judgePoint24_3(float64(nums[2])+float64(nums[3]), float64(nums[0]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[2])-float64(nums[3]), float64(nums[0]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[2])*float64(nums[3]), float64(nums[0]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[2])/float64(nums[3]), float64(nums[0]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[3])-float64(nums[2]), float64(nums[0]), float64(nums[1])) ||
        judgePoint24_3(float64(nums[3])/float64(nums[2]), float64(nums[0]), float64(nums[1])) ||

        judgePoint24_3(float64(nums[1])+float64(nums[2]), float64(nums[0]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[1])-float64(nums[2]), float64(nums[0]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[1])*float64(nums[2]), float64(nums[0]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[1])/float64(nums[2]), float64(nums[0]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[2])-float64(nums[1]), float64(nums[0]), float64(nums[3])) ||
        judgePoint24_3(float64(nums[2])/float64(nums[1]), float64(nums[0]), float64(nums[3])) ||

        judgePoint24_3(float64(nums[1])+float64(nums[3]), float64(nums[2]), float64(nums[0])) ||
        judgePoint24_3(float64(nums[1])-float64(nums[3]), float64(nums[2]), float64(nums[0])) ||
        judgePoint24_3(float64(nums[1])*float64(nums[3]), float64(nums[2]), float64(nums[0])) ||
        judgePoint24_3(float64(nums[1])/float64(nums[3]), float64(nums[2]), float64(nums[0])) ||
        judgePoint24_3(float64(nums[3])-float64(nums[1]), float64(nums[2]), float64(nums[0])) ||
        judgePoint24_3(float64(nums[3])/float64(nums[1]), float64(nums[2]), float64(nums[0]))
}

func judgePoint24_3(a, b, c float64) bool {
    return judgePoint24_2(a+b, c) ||
        judgePoint24_2(a-b, c) ||
        judgePoint24_2(a*b, c) ||
        judgePoint24_2(a/b, c) ||
        judgePoint24_2(b-a, c) ||
        judgePoint24_2(b/a, c) ||

        judgePoint24_2(a+c, b) ||
        judgePoint24_2(a-c, b) ||
        judgePoint24_2(a*c, b) ||
        judgePoint24_2(a/c, b) ||
        judgePoint24_2(c-a, b) ||
        judgePoint24_2(c/a, b) ||

        judgePoint24_2(c+b, a) ||
        judgePoint24_2(c-b, a) ||
        judgePoint24_2(c*b, a) ||
        judgePoint24_2(c/b, a) ||
        judgePoint24_2(b-c, a) ||
        judgePoint24_2(b/c, a)
}

func judgePoint24_2(a, b float64) bool {
    return (a+b < 24+1e-6 && a+b > 24-1e-6) ||
        (a*b < 24+1e-6 && a*b > 24-1e-6) ||
        (a-b < 24+1e-6 && a-b > 24-1e-6) ||
        (b-a < 24+1e-6 && b-a > 24-1e-6) ||
        (a/b < 24+1e-6 && a/b > 24-1e-6) ||
        (b/a < 24+1e-6 && b/a > 24-1e-6)
}

由于代碼過于硬核，

我們直接擊敗100%的對手：

（沒想到吧！代碼還可以這么寫~）

如何運用算法實現(xiàn)“24點”數(shù)學(xué)游戲？


向AI問一下細節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手