华为OJ之24点算法（非递归C++代码）

1问题描述

给定4个正整数，利用加减乘除判断是否可以组成24点。

2思路

有非递归与递归两种做法。此处介绍非递归。
4个正整数随机选择3个，进行三个数字的运算，共4种情况，不递归，列举出来即可。
三个数字运算随机选择2个，进行两个数字的运算，共3种情况。
两个数字运算加法和乘法各1种，减法和除法各2种，因此总共有6种运算结果。
把两个数字的运算结果与刚才三个数字时剩下的数再进行两个数字的运算又是6种结果，因此三个数运算总共可以得到3*6*6=108种运算结果。
最后将三个数的运算结果和4个数时剩下的数再次进行两个数字的运算，判断得到的6个结果是否有24点即可。
接下来举例子：
有正整数a,b,c,d
1. 选择3个：abc，剩下d
2. abc中选择ab，剩下c
3. a和b进行二数运算，得到6种结果放在resTwo[6]中
4. 将resTwo[]和c进行二数运算，结果共36种放在resThree[]中
最后将resThree[]和d进行二数运算，判断其6种结果中是否有结果为24。

3代码

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <iostream>
using namespace std;
void calTwo(double res[6], double a, double b){//二数运算
    res[0] = a+b;
    res[1] = a-b;
    res[2] = b-a;
    res[3] = a*b;
    res[4] = a*1.0/b;
    res[5] = b*1.0/a;
}
//三个数运算，总共108种结果，res存放三数运算的所有结果
void calThree(double res[108], int a, int b, int c){
double nextRes[6];
double firstRes[6];
int resNum = 0;
//随机选择两个为一组，二数运算结果放在firstRes[6]
    calTwo(firstRes, a, b);
for(int i = 0; i < 6; i++){
//得到firstRes后，对三个数中剩余的数进行二数运算，结果放在nextRes
        calTwo(nextRes, firstRes[i], c);
for(int j = 0; j < 6; j++){
            res[resNum++] = nextRes[j];
        }
    }
//不递归，直接列举另一种选择
    calTwo(firstRes, a, c);
for(int i = 0; i < 6; i++){
        calTwo(nextRes, firstRes[i], b);
for(int j = 0; j < 6; j++){
            res[resNum++] = nextRes[j];
        }
    }
    calTwo(firstRes, b, c);
for(int i = 0; i < 6; i++){
        calTwo(nextRes, firstRes[i], a);
for(int j = 0; j < 6; j++){
            res[resNum++] = nextRes[j];
        }
    }
}
bool is24Point(double a, double b){
double res[6];
    calTwo(res, a, b);
for(int i = 0; i < 6; i++){
if(res[i] <= 24.01 && res[i] >= 23.99){
return true;
        }
    }
return false;
}
//方法入口
bool Game24Points(int a, int b, int c, int d)
{
//TODO: Add codes here ...
double res[108];
//随机选择3个数，得到结果集放在res
    calThree(res, a, b, c);
for(int i = 0; i < 108; i++){
if(is24Point(res[i], d)){
return true;
        }
    }
//不递归，直接列举另一种选择
    calThree(res, a, b, d);
for(int i = 0; i < 108; i++){
if(is24Point(res[i], c)){
return true;
        }
    }
    calThree(res, a, c, d);
for(int i = 0; i < 108; i++){
if(is24Point(res[i], b)){
return true;
        }
    }
    calThree(res, b, c, d);
for(int i = 0; i < 108; i++){
if(is24Point(res[i], a)){
return true;
        }
    }
return false;
}
void main(){
cout << Game24Points(1, 2, 3, 4) << endl;
cout << Game24Points(7, 2, 1, 10) << endl;
cout << Game24Points(7, 7, 7, 7) << endl;
    system("pause");
}