轉(zhuǎn)載請(qǐng)保留作者和原始連接http://www.reibang.com/p/7768195814cf
2018-06-21更新
------------start------------
添加了Swift和Dart語(yǔ)言的實(shí)現(xiàn)。
https://github.com/aesean/TwentyFour/blob/master/Calculate.swift
https://github.com/aesean/TwentyFour/blob/master/calculate.dart
------------end------------
2018-06-19更新
------------start------------
評(píng)論說(shuō)希望能支持一些特殊規(guī)則計(jì)算惋鹅，代碼已經(jīng)更新了则酝。新代碼是用Kotlin寫(xiě)的，如果需要Java版本闰集，請(qǐng)嘗試用IDE自帶的插件自行轉(zhuǎn)換Java版沽讹。apk的UI沒(méi)有開(kāi)放支持任意數(shù)量的數(shù)字計(jì)算，只是開(kāi)放了支持計(jì)算任意結(jié)果武鲁。需要注意爽雄，有個(gè)非常討厭的情況是除法，如果不做四舍五入沐鼠，1/3*3得到的就不是1了挚瘟。實(shí)際代碼里做了約等，極端情況下可能會(huì)有計(jì)算錯(cuò)誤饲梭。如果你希望能完美精確計(jì)算乘盖，請(qǐng)自行擴(kuò)展MathRuleImpl，
實(shí)際代碼已經(jīng)支持計(jì)算任意數(shù)量的數(shù)字憔涉，以及任何你希望的結(jié)果订框。詳細(xì)請(qǐng)參考下面的源碼：
https://github.com/aesean/TwentyFour/blob/master/app/src/main/java/com/aesean/twentyfour/CalculateImpl.kt
代碼里的main方法示例了5，5兜叨，5穿扳，1四個(gè)數(shù)字計(jì)算結(jié)果的絕對(duì)值小于10的計(jì)算方式。其他規(guī)則請(qǐng)自行嘗試国旷，另外由于Tree的遍歷用到了遞歸矛物，所以如果數(shù)據(jù)個(gè)數(shù)太多有可能會(huì)出現(xiàn)爆棧情況蟋滴，請(qǐng)自行優(yōu)化茂卦。
------------end------------

也可以下載apk恩掷，看下實(shí)際效果帚桩。
https://github.com/aesean/TwentyFour/raw/master/app-release.apk

黑夜給了我黑色的眼睛特漩，我卻用它來(lái)敲代碼吧雹，～笑～。
晚上一個(gè)朋友群里涂身，有人問(wèn)：5雄卷，5，5蛤售，1如何計(jì)算24丁鹉。當(dāng)然計(jì)算方式隨手Google一下就有，但這一下子讓我覺(jué)得通過(guò)某種算法肯定可以逆向推出這個(gè)公式悴能。其實(shí)很早就有這個(gè)想法揣钦，就是一直沒(méi)思路，也懶就一直沒(méi)弄漠酿，這次一下心血來(lái)潮就做了下實(shí)現(xiàn)冯凹。
用Java寫(xiě)的，源碼可以參考這里：
https://github.com/aesean/TwentyFour/blob/master/app/src/main/java/com/aesean/twentyfour/TwentyFour.java

這里介紹下思路炒嘲。通常第一眼看到這個(gè)問(wèn)題宇姚，會(huì)非常頭疼，逆向算24的計(jì)算公式夫凸，這怎么搞浑劳。
我們先看下前面：5，5夭拌，5魔熏，1的計(jì)算結(jié)果：(5-(1/5))*5=24。這里仔細(xì)看下啼止，這個(gè)結(jié)果有這樣一種規(guī)律道逗，我們先假定加減乘除的運(yùn)算用'?'代替，無(wú)論最終的計(jì)算公式是什么献烦，結(jié)果一定是a?b=24這種形式滓窍。然后a和b可能是四個(gè)原始數(shù)之一，或者也是a?b這種形式由兩個(gè)數(shù)計(jì)算出來(lái)的巩那。那我們先把a(bǔ)?b這種形式計(jì)算結(jié)果寫(xiě)個(gè)方法出來(lái)吏夯。

private static float[] math(float a, float b) {
    float[] result = new float[6];
    result[0] = a + b;
    result[1] = a - b;
    result[2] = a × b;
    result[3] = a / b;
    return result;
}

這個(gè)方法就是兩個(gè)數(shù)運(yùn)算后所有可能的結(jié)果。這里注意即横，參數(shù)選float是因?yàn)榭赡軙?huì)有上面5－1/5這種情況噪生，int型做除法運(yùn)算會(huì)丟失精度，所以這里強(qiáng)轉(zhuǎn)為float型东囚，避免除法出錯(cuò)跺嗽。這里返回的浮點(diǎn)型數(shù)組就是a與b做加減乘除后的結(jié)果。
好了到了這里其實(shí)我們這個(gè)方法配合排列組合，已經(jīng)可以計(jì)算任意兩個(gè)數(shù)通過(guò)加減乘除如何等于24了桨嫁。直接遍歷排列植兰，然后調(diào)用math返回的結(jié)果判斷是否等于24就可以了。

現(xiàn)在我們需要把兩個(gè)數(shù)的情況璃吧，擴(kuò)展到四個(gè)數(shù)楣导。我們?cè)倏?5-(1/5))*5=24這個(gè)結(jié)果，這個(gè)結(jié)果其實(shí)可以這么理解畜挨，我們可以把最終的結(jié)果看成是a?b?c?d＝24筒繁，abcd分別第一，第二巴元，第三毡咏，第四個(gè)數(shù)务冕。第一個(gè)數(shù)與第二個(gè)數(shù)math血当，然后結(jié)果與第三個(gè)數(shù)math，得出的結(jié)果與第四個(gè)數(shù)math臊旭。然后將abcd四個(gè)數(shù)，排列出所有可能的排列啥刻，然后就能計(jì)算這四個(gè)數(shù)在這種形式((a?b)?c)?d下的所有可能的結(jié)果了奸鸯。
排列我們寫(xiě)個(gè)方法來(lái)實(shí)現(xiàn)，這里不貼源碼了可帽，我寫(xiě)的排列寫(xiě)的比較懶娄涩，也比較爛，只支持4個(gè)數(shù)的排列映跟。其實(shí)這里寫(xiě)的好應(yīng)該是支持任意數(shù)量的數(shù)的排列蓄拣。

private static float[][] arrange(float[] value) {
    .....
    return result;
}

這里返回一個(gè)二維數(shù)組，包含了所有排列結(jié)果努隙。
然后我們借助這個(gè)排列返回的結(jié)果球恤，然后配合math方法就可以計(jì)算所有這種((a?b)?c)?d形式下的計(jì)算結(jié)果了。寫(xiě)成代碼應(yīng)該類(lèi)似下面這樣

public static void start(float[] mNum) {
    float[] value0 = math(mNum[0], mNum[1]);
    // 1-1-1-1
    //當(dāng)三個(gè)數(shù)與一個(gè)數(shù)計(jì)算的時(shí)候
    for (int i = 0; i < value0.length; i++) {
        float[] value1 = math(value0[i], mNum[2]);
        for (int i1 = 0; i1 < value1.length; i1++) {
            float[] value2 = math(value1[i1], mNum[3]);
            for (int i2 = 0; i2 < value2.length; i2++) {
                if (value2[i2] == 24f) {
                     //成功計(jì)算出24
                }
        }
    }
}

先前兩個(gè)數(shù)做math運(yùn)算荸镊，然后跟第三個(gè)數(shù)做math咽斧，然后結(jié)果和第四個(gè)數(shù)做math堪置，那這種形式先不說(shuō)能不能覆蓋全部可能的情況，先看看能不能覆蓋(5-(1/5))*5=24张惹，可以實(shí)際跑下代碼晋柱，發(fā)現(xiàn)并不能。但這里打印結(jié)果發(fā)現(xiàn)可以計(jì)算出－24诵叁，問(wèn)題在哪兒？問(wèn)題出5-(1/5)上钦椭，這里并不是前兩個(gè)數(shù)的結(jié)果與第三個(gè)運(yùn)算拧额，這里是第一個(gè)數(shù)與第二三個(gè)數(shù)的結(jié)果做運(yùn)算。
這里頭疼了彪腔，按照現(xiàn)在的math方法侥锦，我們需要把所有可能的abcd運(yùn)算形式寫(xiě)出來(lái)，可能要寫(xiě):(a?(b?c))?d德挣，a?((b?c)?d)恭垦，a?(d?(b?c))，等等好多情況格嗅。比較笨的情況就是將所有結(jié)果全部列舉出來(lái)番挺，一共四個(gè)數(shù)結(jié)果也不是非常多。
但是有個(gè)更加優(yōu)雅的解決方法屯掖。我們?cè)倏聪掠?jì)算結(jié)果玄柏，其中包含24，這表示什么贴铜，這表示把x-y粪摘，換成y-x就可以了。也就是說(shuō)對(duì)于減法運(yùn)算需要處理?yè)Q位的情況绍坝，其實(shí)不光是減法徘意，除法也存在換位問(wèn)題，我們現(xiàn)在計(jì)算方式應(yīng)該還會(huì)計(jì)算出1/24這種情況轩褐。再看
(a?(b?c))?d椎咧，
a?((b?c)?d)，
a?(d?(b?c))
這些形勢(shì)灾挨，其實(shí)都是換位邑退。(a?(b?c))?d和a?(d?(b?c))的區(qū)別其實(shí)就是一個(gè)換位，而且如果這兩個(gè)計(jì)算里(a?(b?c))?d的第三個(gè)問(wèn)號(hào)和a?(d?(b?c))的第一個(gè)問(wèn)號(hào)是減法或者除法的時(shí)候才會(huì)出現(xiàn)結(jié)果不一致的情況劳澄。
好了地技，原因明白，那怎么處理呢秒拔？非常簡(jiǎn)單莫矗，改造下math方法就行了。

private static float[] math(float a, float b) {
    float[] result = new float[6];
    result[0] = a + b;
    result[1] = a - b;
    result[2] = a × b;
    result[3] = a / b;
    result[4] = b / a;
    result[5] = b - a;
    return result;
}

我們?cè)趍ath方法里把可能的換位情況加進(jìn)去。
這時(shí)候看下能不能覆蓋到(5-(1/5))5＝24作谚，我們一定覆蓋到(1/5-5)5這種情況三娩，這個(gè)很容易明白，但因?yàn)槲覀兗恿藫Q位妹懒，所以第二個(gè)減號(hào)a－b可以被換位為b－a雀监，變成這樣(5-(1/5))5，實(shí)際跑下眨唬，看下效果会前。
成功計(jì)算出24。這時(shí)候其實(shí)已經(jīng)可以覆蓋到很多種情況下的計(jì)算24了匾竿。還漏了一種情況瓦宜。就是((a?b)?c)?d，再加上換位岭妖，無(wú)法解決這種情況(100-96)(10-6)临庇，這種情況抽象下就是:(a?b)?(c?d)＝24，我們前面的運(yùn)算可以解決所有的最后一步是和abcd四個(gè)數(shù)之一做運(yùn)算的情況昵慌，但還有一種是最后是兩個(gè)運(yùn)算結(jié)果之間的運(yùn)算假夺。所以start方法還應(yīng)該加入(a?b)?(c?d)這種情況。

//當(dāng)兩個(gè)數(shù)與兩個(gè)數(shù)計(jì)算的時(shí)候
    float[] rightTwo = math(mNum[2], mNum[3]);
    for (int i = 0; i < value0.length; i++) {
        for (int i1 = 0; i1 < rightTwo.length; i1++) {
            float[] result = math(value0[i], rightTwo[i1]);
            for (int i2 = 0; i2 < result.length; i2++) {
                if (result[i2] == 24f) {
                     // 成功計(jì)算出24
                }
            }
        }
    }

加上后斋攀，我們?cè)儆?jì)算下侄泽，發(fā)現(xiàn)成功解決(100-96)*(10-6)=24了。那我們?cè)傧胂霑?huì)不會(huì)還有沒(méi)有覆蓋到情況蜻韭。我們逆推下悼尾，最終無(wú)論怎么算24都是兩個(gè)數(shù)的?運(yùn)算，然后這兩個(gè)數(shù)要么一個(gè)來(lái)計(jì)算得出肖方，一個(gè)來(lái)自abcd闺魏，要么兩個(gè)都來(lái)自計(jì)算得出。不存在第三種情況俯画。然后針對(duì)第一種里析桥，那個(gè)計(jì)算得出的數(shù)，一定是兩個(gè)數(shù)計(jì)算然后和剩下一個(gè)數(shù)做?運(yùn)算艰垂，不存在其他情況泡仗。而第二種的，更簡(jiǎn)單了猜憎，兩個(gè)數(shù)?運(yùn)算娩怎，剩下兩個(gè)數(shù)?運(yùn)算，結(jié)果再?運(yùn)算也不存在其他情況胰柑。好了截亦，現(xiàn)在應(yīng)該是所有情況都覆蓋到了爬泥。
那還有個(gè)問(wèn)題，我們代碼可以跑到 // 成功計(jì)算出24這一行崩瓤，那怎么格式化輸出實(shí)際的公式呢袍啡？也很簡(jiǎn)單，math方法返回的數(shù)組是所有的結(jié)果却桶，而結(jié)果在數(shù)組里的位置代表了計(jì)算時(shí)候所使用的運(yùn)算形式境输。我們可以寫(xiě)這樣一個(gè)方法把index轉(zhuǎn)化為運(yùn)算符號(hào)。

private static String getSymbol(int index) {
    switch (index) {
        case 0:
            return " + ";
        case 1:
            return " - ";
        case 2:
            return " * ";
        case 3:
            return " / ";
        case 4:
            return " / ";
        case 5:
            return " - ";
        default:
            throw new RuntimeException("未知的index類(lèi)型");
    }
}

然后我們通過(guò)start方法里每一層的for循環(huán)的i參數(shù)就可以拿到計(jì)算最終結(jié)果的時(shí)候所使用的符號(hào)了颖系。
代碼類(lèi)似這樣：

String p0, p1, p2;if (i < 4) {
    p0 = LEFT_BRACKETS + (int) mNum[0] + getSymbol(i) + (int) mNum[1] + RIGHT_BRACKETS;
} else {
    p0 = LEFT_BRACKETS + (int) mNum[1] + getSymbol(i) + (int) mNum[0] + RIGHT_BRACKETS;
}
if (i1 < 4) {
    p1 = LEFT_BRACKETS + p0 + getSymbol(i1) + (int) mNum[2] + RIGHT_BRACKETS;
} else {
    p1 = LEFT_BRACKETS + (int) mNum[2] + getSymbol(i1) + p0 + RIGHT_BRACKETS;
}
if (i2 < 4) {
    p2 = p1 + getSymbol(i2) + (int) mNum[3];
} else {
    p2 = (int) mNum[3] + getSymbol(i2) + p1;
}

這里的4寫(xiě)法很不好畴嘶，懶的改了，這里的4就是math方法里的大于4的運(yùn)算都是需要顯示換位的集晚，所以這里需要根據(jù)是否大于4決定顯示輸出是否換位。
到了這里区匣，大致過(guò)程就結(jié)束了偷拔。
如果把前面的思路敲進(jìn)Android，差不多就是這個(gè)樣子亏钩。

Paste_Image.png

Paste_Image.png

Paste_Image.png

還有整個(gè)計(jì)算會(huì)有重復(fù)計(jì)算的情況莲绰，所以會(huì)有結(jié)果除重，還有結(jié)果格式化輸出注意換位等細(xì)節(jié)就不詳細(xì)說(shuō)了姑丑，具體可以直接參考源碼蛤签。

轉(zhuǎn)載請(qǐng)保留作者和原始連接http://www.reibang.com/p/7768195814cf
也可以下載apk，https://github.com/aesean/TwentyFour/raw/master/app-release.apk