24點游戲簡介
一副牌中抽去大小王逼蒙，從剩下的52張中任意抽取4張牌，用加寄疏、減是牢、乘、除和括號把牌面上的數(shù)算成24陕截，每張牌都必須使用驳棱，且只能用一次。舉例如下：
【1】 1艘策、2蹈胡、3、4，那么1x2x3x4 = 24罚渐，4/(1/(2x3)) = 24却汉，(1+2+3)x4 = 24等等。
【2】 4荷并、6合砂、8、10源织，那么(8-6)x10+4 = 24翩伪，(10-6)x4+8 = 24。
【3】 5谈息、4缘屹、3、3侠仇，那么(5+4)x3-3 = 24轻姿，(5-3)x4x3 = 24，(3/3+5)x4 = 24等等逻炊。
求解算法
用窮舉法列出所有算式互亮，如果結(jié)果等于24則輸出。那么如何窮舉呢余素？
經(jīng)過觀察豹休，無論什么樣的算式，不管運算符順序怎么樣桨吊，不管括號怎么加威根，都可以用如下方法窮舉：
【1】最開始是4個數(shù)，例如 6屏积、7医窿、8、9炊林。
【2】從4個數(shù)中選擇兩個數(shù)，例如6和7卷要。4選2共6中選法渣聚。
【3】將兩個數(shù)進行加減乘除運算，例如加法運算僧叉，6+7奕枝。
【4】運算結(jié)果13和剩余的2個數(shù)8和9組成3個數(shù)，13瓶堕、8隘道、9。
【5】從三個數(shù)中選擇兩個數(shù)，例如13和8谭梗。3選2共3中選法忘晤。
【6】將兩個數(shù)進行加減乘除運算，例如除法運算激捏，13/8设塔，或者8/13。
【7】運算結(jié)果和剩余的1個數(shù)組成2個數(shù)远舅，例如13/8闰蛔、9。
【8】最后一步加減乘除運算图柏，例如乘法運算序六，13/8 x 9。
注意步驟【3】蚤吹、【6】难咕、【8】，因為加法和乘法符合交換律距辆，不分順序余佃，所以一共6中四則運算。對于除法跨算，還要檢查除數(shù)是否為0爆土。例如上面提到的算式
(1+2+3)x4 = 24，可以看做：
【1】4個數(shù)1诸蚕、2步势、3、4背犯。
【2】選擇1和2坏瘩。
【3】選擇加法。
【4】運算結(jié)果3和剩余2個數(shù)組成3個數(shù) 3漠魏、3倔矾、4。
【5】選擇3和3柱锹。
【6】選擇加法哪自。
【7】運算結(jié)果6和剩余1個數(shù)組成2個數(shù) 6、4禁熏。
【8】選擇乘法壤巷。再舉一個例子，例如算式
(11-3)/(5-7) = -4瞧毙，可以看做：
【1】4個數(shù)3胧华、5寄症、7、11矩动。
【2】選擇3和11有巧。
【3】選擇后面的數(shù)減前面的數(shù)的減法。
【4】運算結(jié)果8和剩余2個數(shù)組成3個數(shù) 8铅忿、5剪决、7。
【5】選擇5和7檀训。
【6】選擇減法柑潦。
【7】運算結(jié)果-2和剩余1個數(shù)組成2個數(shù) -2、8峻凫。
【8】選擇后面的數(shù)除以前面的數(shù)的除法渗鬼。-
繪制個示意圖：
C語言代碼
實際代碼中，對于求解算法的步驟【3】荧琼、【6】譬胎、【8】中的減法，只保留了較大的數(shù)減去較小的數(shù)的運算命锄，丟棄了較小的數(shù)減去較大的數(shù)的運算堰乔。總的窮舉次數(shù)也能算出來脐恩，6 x 5 x 3 x 5 x 1 x 5 = 2250 次镐侯。
//==============================================================================
// Copyright (C) 2019 王小康. All rights reserved.
//
// 作者: 王小康
// 描述: 24點游戲求解程序
// 日期: 2019-04-15
//
//==============================================================================
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct {
int integer;
int remainder;
int denominator;
char *string;
} VALUE_T;
static int level_3(VALUE_T *a, VALUE_T *b){
int va, vb, integer, remainder, denominator = a->denominator * b->denominator;
int num = 0;
// +
va = (a->integer * denominator + a->remainder * b->denominator);
vb = (b->integer * denominator + b->remainder * a->denominator);
integer = (va + vb) / denominator;
remainder = (va + vb) % denominator;
if((integer == 24) && (remainder == 0)){
printf("%s+%s = 24\n", a->string, b->string);
num++;
}
// -
va = (a->integer * denominator + a->remainder * b->denominator);
vb = (b->integer * denominator + b->remainder * a->denominator);
if(va >= vb){
integer = (va - vb) / denominator;
remainder = (va - vb) % denominator;
if((integer == 24) && (remainder == 0)){
printf("%s-%s = 24\n", a->string, b->string);
num++;
}
}
else{
integer = (vb - va) / denominator;
remainder = (vb - va) % denominator;
if((integer == 24) && (remainder == 0)){
printf("%s-%s = 24\n", b->string, a->string);
num++;
}
}
// *
va = (a->integer * a->denominator + a->remainder);
vb = (b->integer * b->denominator + b->remainder);
integer = (va * vb) / denominator;
remainder = (va * vb) % denominator;
if((integer == 24) && (remainder == 0)){
printf("%sx%s = 24\n", a->string, b->string);
num++;
}
// /
va = (a->integer * a->denominator + a->remainder) * b->denominator;
vb = (b->integer * b->denominator + b->remainder) * a->denominator;
if(vb){
integer = va / vb;
remainder = va % vb;
if((integer == 24) && (remainder == 0)){
printf("%s/%s = 24\n", a->string, b->string);
num++;
}
}
if(va){
integer = vb / va;
remainder = vb % va;
if((integer == 24) && (remainder == 0)){
printf("%s/%s = 24\n", b->string, a->string);
num++;
}
}
return num;
}
static int level_2(VALUE_T *a, VALUE_T *b, VALUE_T *c){
char stringBuffer[32];
VALUE_T value;
int va, vb, denominator = a->denominator * b->denominator;
int num = 0;
// +
va = (a->integer * denominator + a->remainder * b->denominator);
vb = (b->integer * denominator + b->remainder * a->denominator);
value.integer = (va + vb) / denominator;
value.remainder = (va + vb) % denominator;
value.denominator = denominator;
sprintf(stringBuffer, "(%s+%s)", a->string, b->string);
value.string = stringBuffer;
num += level_3(&value, c);
// -
va = (a->integer * denominator + a->remainder * b->denominator);
vb = (b->integer * denominator + b->remainder * a->denominator);
if(va >= vb){
value.integer = (va - vb) / denominator;
value.remainder = (va - vb) % denominator;
sprintf(stringBuffer, "(%s-%s)", a->string, b->string);
}
else{
value.integer = (vb - va) / denominator;
value.remainder = (vb - va) % denominator;
sprintf(stringBuffer, "(%s-%s)", b->string, a->string);
}
value.denominator = denominator;
value.string = stringBuffer;
num += level_3(&value, c);
// *
va = (a->integer * a->denominator + a->remainder);
vb = (b->integer * b->denominator + b->remainder);
value.integer = (va * vb) / denominator;
value.remainder = (va * vb) % denominator;
value.denominator = denominator;
sprintf(stringBuffer, "(%sx%s)", a->string, b->string);
value.string = stringBuffer;
num += level_3(&value, c);
// /
va = (a->integer * a->denominator + a->remainder) * b->denominator;
vb = (b->integer * b->denominator + b->remainder) * a->denominator;
if(vb){
value.integer = va / vb;
value.remainder = va % vb;
value.denominator = vb;
sprintf(stringBuffer, "(%s/%s)", a->string, b->string);
value.string = stringBuffer;
num += level_3(&value, c);
}
if(va){
value.integer = vb / va;
value.remainder = vb % va;
value.denominator = va;
sprintf(stringBuffer, "(%s/%s)", b->string, a->string);
value.string = stringBuffer;
num += level_3(&value, c);
}
return num;
}
static int level_1(VALUE_T *a, VALUE_T *b, VALUE_T *c, VALUE_T *d){
char stringBuffer[32];
VALUE_T value;
int va, vb, denominator = a->denominator * b->denominator;
int num = 0;
// +
va = (a->integer * denominator + a->remainder * b->denominator);
vb = (b->integer * denominator + b->remainder * a->denominator);
value.integer = (va + vb) / denominator;
value.remainder = (va + vb) % denominator;
value.denominator = denominator;
sprintf(stringBuffer, "(%s+%s)", a->string, b->string);
value.string = stringBuffer;
num += level_2(&value, c, d);
num += level_2(&value, d, c);
num += level_2(c, d, &value);
// -
va = (a->integer * denominator + a->remainder * b->denominator);
vb = (b->integer * denominator + b->remainder * a->denominator);
if(va >= vb){
value.integer = (va - vb) / denominator;
value.remainder = (va - vb) % denominator;
sprintf(stringBuffer, "(%s-%s)", a->string, b->string);
}
else{
value.integer = (vb - va) / denominator;
value.remainder = (vb - va) % denominator;
sprintf(stringBuffer, "(%s-%s)", b->string, a->string);
}
value.denominator = denominator;
value.string = stringBuffer;
num += level_2(&value, c, d);
num += level_2(&value, d, c);
num += level_2(c, d, &value);
// *
va = (a->integer * a->denominator + a->remainder);
vb = (b->integer * b->denominator + b->remainder);
value.integer = (va * vb) / denominator;
value.remainder = (va * vb) % denominator;
value.denominator = denominator;
sprintf(stringBuffer, "(%sx%s)", a->string, b->string);
value.string = stringBuffer;
num += level_2(&value, c, d);
num += level_2(&value, d, c);
num += level_2(c, d, &value);
// /
va = (a->integer * a->denominator + a->remainder) * b->denominator;
vb = (b->integer * b->denominator + b->remainder) * a->denominator;
if(vb){
value.integer = va / vb;
value.remainder = va % vb;
value.denominator = vb;
sprintf(stringBuffer, "(%s/%s)", a->string, b->string);
value.string = stringBuffer;
num += level_2(&value, c, d);
num += level_2(&value, d, c);
num += level_2(c, d, &value);
}
if(va){
value.integer = vb / va;
value.remainder = vb % va;
value.denominator = va;
sprintf(stringBuffer, "(%s/%s)", b->string, a->string);
value.string = stringBuffer;
num += level_2(&value, c, d);
num += level_2(&value, d, c);
num += level_2(c, d, &value);
}
return num;
}
static int level_0(int a, int b, int c, int d){
char buffer[4][4];
sprintf(buffer[0],"%d", a);
sprintf(buffer[1],"%d", b);
sprintf(buffer[2],"%d", c);
sprintf(buffer[3],"%d", d);
VALUE_T value[4];
value[0].integer = a;
value[0].remainder = 0;
value[0].denominator = 1;
value[0].string = buffer[0];
value[1].integer = b;
value[1].remainder = 0;
value[1].denominator = 1;
value[1].string = buffer[1];
value[2].integer = c;
value[2].remainder = 0;
value[2].denominator = 1;
value[2].string = buffer[2];
value[3].integer = d;
value[3].remainder = 0;
value[3].denominator = 1;
value[3].string = buffer[3];
int num = 0;
num += level_1(&value[0], &value[1], &value[2], &value[3]);
num += level_1(&value[0], &value[2], &value[1], &value[3]);
num += level_1(&value[0], &value[3], &value[1], &value[2]);
num += level_1(&value[1], &value[2], &value[0], &value[3]);
num += level_1(&value[1], &value[3], &value[0], &value[2]);
num += level_1(&value[2], &value[3], &value[0], &value[1]);
return num;
}
////////////////////////////////////////////////////////////////////////////////
static int parameterCheck(int argc, char* argv[]){
char *p;
int value;
while(*argv){
p = *argv;
if((*p < '1') || (*p > '9')) return 1;
p++;
while(*p){
if((*p < '0') || (*p > '9')) return 1;
p++;
}
value = atoi(*argv);
if((value < 1) || (value > 13)) return 1;
argv++;
}
return 0;
}
static void help(char *name){
printf("Usage : %s num1 num2 num3 num4\n", name);
printf("Example: %s 5 5 5 1\n", name);
}
int main(int argc, char* argv[]){
if(argc < 5){
help(argv[0]);
return 0;
}
if(parameterCheck(argc-1, argv+1)){
help(argv[0]);
return 0;
}
int num = level_0(atoi(argv[1]), atoi(argv[2]), atoi(argv[3]), atoi(argv[4]));
printf("total = %d\n", num);
return 0;
}
運行測試
錯誤的參數(shù)測試
測試 12、2驶冒、9苟翻、10 以及運行時間
上面是普通測試，下面是網(wǎng)上搜索的骗污，被稱為超難的幾組24點游戲題崇猫，看看求解效果：
（5、5需忿、5诅炉、1）
（1、4贴谎、5汞扎、6）
（1、3擅这、7、8）
（2景鼠、5仲翎、5痹扇、10）
（3、3溯香、8鲫构、8）
（1、2玫坛、7结笨、7）
（2、5湿镀、7炕吸、8）
（1、3勉痴、4赫模、6）
如何去重問題
對于算式字符串字面值完全相同的算式非常容易去重，但是
有些算式字符串字面值不同而含義明顯相同蒸矛，例如：
((1+2)+3)x4 = 24和(1+(2+3))x4 = 24含義重復(fù)瀑罗；
((5+9)-6)x3 = 24和((9-6)+5)x3 = 24含義重復(fù)；
((9-5)x3)x2 = 24和((9-5)x2)x3 = 24含義重復(fù)等等雏掠。
留待以后想辦法解決斩祭。
