5. 快算24

题目描述

一副牌，除了大小王之外还有52张，从1到13每个数目各有四张。要求设计一个程序，对于任意给出52张牌中的四张，运用＋－×÷四种运算来判断能否每个数只能用一次，但不能不用，算出24来。注意，给出的4个数是无序的。

测试用例

输入

1 1 1 1
2 3 4 1
7 2 1 1
           

输出

no
yes
yes
           

分析

全排列

坑点：有分数情况如 5×(5–1/5)=24 5 × ( 5 – 1 / 5 ) = 24 ，就不能用int表示，要使用浮点数。

参考：24点游戏算法

代码

#include<iostream>
#include<math.h>
#include<string>
using namespace std;

double in_num[];
string temp_str[];

bool is24(int num)
{
    if (num == )
        return (fabs(in_num[] - ) < );

    for (int i = ; i < num; i++) 
    {
        for (int j = i + ; j < num; j++)
        { 
            double num_a = in_num[i]; 
            double num_b = in_num[j]; 
            string str_a = temp_str[i]; 
            string str_b = temp_str[j];

            in_num[j] = in_num[num - ];  // 移动最后一个数
            temp_str[j] = temp_str[num - ];  // 移动最后一个式子

            temp_str[i] = "(" + str_a + "+" + str_b + ")";  // +
            in_num[i] = num_a + num_b;
            if (is24(num - ))
                return true;

            temp_str[i] = "(" + str_a + "-" + str_b + ")";  // -
            in_num[i] = num_a - num_b;
            if (is24(num - ))
                return true;
            temp_str[i] = "(" + str_b + "-" + str_a + ")";
            in_num[i] = num_b - num_a;
            if (is24(num - ))
                return true;

            temp_str[i] = "(" + str_a + "*" + str_b + ")";  // *
            in_num[i] = num_a * num_b;
            if (is24(num - ))
                return true;

            if (num_b != ) 
            {
                temp_str[i] = "(" + str_a + "/" + str_b + ")";  // /
                in_num[i] = num_a / num_b;
                if (is24(num - ))
                    return true;
            }
            if (num_a != ) 
            {
                temp_str[i] = "(" + str_b + "/" + str_a + ")";
                in_num[i] = num_b / num_a;
                if (is24(num - ))
                    return true;
            }

            in_num[i] = num_a; 
            in_num[j] = num_b;
            temp_str[i] = str_a;
            temp_str[j] = str_b;
        }
    }

    return false;

}
int main()
{
    while (~scanf("%lf %lf %lf %lf",&in_num[],&in_num[],&in_num[],&in_num[]))
    {
        if (is24())
            printf("yes\n");
        else
            printf("no\n");
    }

    return ;
}