首页 > 编程入门 文章详情

puzzle（0151）《24点》

编程入门 行业动态 更新时间:2024-10-25 10:21:31

<a href=https://www.elefans.com/category/jswz/34/1691290.html style=puzzle（0151）《24点》"/>

puzzle（0151）《24点》

目录

一，24点游戏的规则和分类

二，24点游戏的求解

1，思路1

CSU 1600: Twenty-four point（第（1a）类）

HDU 1427 24点游戏（第（1b）类）

2，思路2

三，特殊组合分析

一，24点游戏的规则和分类

按照运算规则来分类的话，首先24的基本规则：

4个数字可以任意排序，可以任意加括号，运算符+-*/这4个可以选择，但是在选择的时候有2类：

（a）无限制任意选择

（b）必须满足，在计算的过程中不会出现2个数的除法产生分数的情况，在此限制之下运算符可以任选

这2类的区别是，（a）类允许（5-1/5）*5这样的式子，而（b）类不允许

如果按照可能出现的数字来分类的话，有2类：

（1）扑克牌类：1,2,3,4,5,6,7,8,9,10,11,12,13

（2）计算器类：0,1,2,3,4,5,6,7,8,9

所以，交叉分类的话，一共有4种：（1a）（1b）（2a）（2b）

二，24点游戏的求解

思路大致可以分2类，即下面的思路1和思路2

1，思路1

先枚举4个数在表达式中的顺序，24种，然后再枚举计算顺序和运算符，使得4个数化为3个数，

然后再化为2个数，最后化为1个数看是不是24

CSU 1600: Twenty-four point（第（1a）类）

题目：

Description

Given four numbers, can you get twenty-four through the addition, subtraction, multiplication, and division? Each number can be used only once.

Input

The input consists of multiple test cases. Each test case contains 4 integers A, B, C, D in a single line (1 <= A, B, C, D <= 13).

Output

For each case, print the “Yes” or “No”. If twenty-four point can be get, print “Yes”, otherwise, print “No”.

Sample Input

2 2 3 9
1 1 1 1 
5 5 5 1

Sample Output

Yes
No
Yes

Hint

For the first sample, (2/3+2)*9=24.

代码：

#include<iostream>
using namespace std;bool ok(double a)
{return a > 23.99999&&a < 24.00001;
}bool ok(double a, double b)
{if (b == 0)return ok(a);return ok(a + b) || ok(a - b) || ok(a*b) || ok(a / b);
}bool ok(double a, double b, double c)
{if (b == 0)return ok(a, c);if (c == 0)return ok(a, b);if (ok((a + b), c) || ok((a - b), c) || ok((a * b), c)|| ok(a / b, c))return true;if (ok(a, b + c) || ok(a, b - c) || ok(a, b * c)|| ok(a, b / c))return true;return false;
}bool ok(double a, double b, double c, double d)
{if (ok(a + b, c, d) || ok(a - b, c, d) || ok(a * b, c, d)|| ok(a / b, c, d))return true;if (ok(a, b + c, d) || ok(a, b - c, d) || ok(a, b * c, d)|| ok(a, b / c, d))return true;if (ok(a, b, c + d) || ok(a, b, c - d) || ok(a, b, c * d)|| ok(a, b, c / d))return true;return false;
}bool ok1(int a, int b, int c, int d)
{return ok(a, b, c, d) || ok(a, c, b, d) || ok(b, a, c, d) || ok(b, c, a, d) || ok(c, a, b, d) || ok(c, b, a, d);
}int main()
{int a, b, c, d;while (cin >> a >> b >> c >> d){if (ok1(a, b, c, d) || ok1(b, c, d, a) || ok1(c, d, a, b) || ok1(d, a, b, c))cout << "Yes" << endl;else cout << "No" << endl;}return 0;
}

HDU 1427 24点游戏（第（1b）类）

题目：

Description

速算24点相信绝大多数人都玩过。就是随机给你四张牌，包括A(1),2,3,4,5,6,7,8,9,10,J(11),Q(12),K(13)。要求只用'+','-','*','/'运算符以及括号改变运算顺序，使得最终运算结果为24(每个数必须且仅能用一次)。游戏很简单，但遇到无解的情况往往让人很郁闷。你的任务就是针对每一组随机产生的四张牌，判断是否有解。我们另外规定，整个计算过程中都不能出现小数。 

Input

每组输入数据占一行，给定四张牌。 

Output

每一组输入数据对应一行输出。如果有解则输出"Yes"，无解则输出"No"。 

Sample Input

A 2 3 6

3 3 8 8

Sample Output

Yes

No

主要的思路就是函数的嵌套。

这个题目我是只用一个字符ch记录所有输入的，空格会自动忽略，0我就人为忽略，遇到0就读取下一个字符，这样，A就是表示1,1就是表示10

代码：

#include<iostream>
using namespace std;int number(char c)
{if (c == 'A')return 1;if (c == 'J')return 11;if (c == 'Q')return 12;if (c == 'K')return 13;if (c == '1')return 10;return c - '0';
}bool ok(int a, int b)
{if (a + b == 24)return true;if (a - b == 24)return true;if (a*b == 24)return true;if (a != 0 && a == 24 * b)return true;return false;
}bool ok(int a, int b, int c)
{if (b == 0){if (ok(a, c))return true;return false;}if (c == 0){if (ok(a, b))return true;return false;}if (ok((a + b), c) || ok((a - b), c) || ok((a * b), c))return true;if (a%b == 0 && ok(a / b, c))return true;if (ok(a, b + c) || ok(a, b - c) || ok(a, b * c))return true;if (b%c == 0 && ok(a, b / c))return true;return false;
}bool ok(int a, int b, int c, int d)
{if (ok(a + b, c, d) || ok(a - b, c, d) || ok(a * b, c, d))return true;if (a%b == 0 && ok(a / b, c, d))return true;if (ok(a, b + c, d) || ok(a, b - c, d) || ok(a, b * c, d))return true;if (b%c == 0 && ok(a, b / c, d))return true;if (ok(a, b, c + d) || ok(a, b, c - d) || ok(a, b, c * d))return true;if (c%d == 0 && ok(a, b, c / d))return true;return false;
}bool ok1(int a, int b, int c, int d)
{if (ok(a, b, c, d) || ok(a, c, b, d) || ok(b, a, c, d) || ok(b, c, a, d) || ok(c, a, b, d) || ok(c, b, a, d))return true;return false;
}int main()
{	char ch;int a, b, c, d;while (cin >> ch){if (ch == '0')cin >> ch;a = number(ch);cin >> ch;if (ch == '0')cin >> ch;b = number(ch);cin >> ch;if (ch == '0')cin >> ch;c = number(ch);cin >> ch;if (ch == '0')cin >> ch;d = number(ch);if (ok1(a, b, c, d)||ok1(b,c,d,a)||ok1(c,d,a,b)||ok1(d,a,b,c))cout << "Yes" << endl;else cout << "No" << endl;}return 0;
}

2，思路2

从4个数里面任取2个数，枚举计算顺序和运算符变成1个数，使得总共化为3个数，然后再化为2个数，最后化为1个数看是不是24

编程之美上面用的就是这类思路。

三，特殊组合分析

有少数的特殊组合，如5 5 5 1，只能（5-1/5）*5得出24，对于b类规则是得不到24的，否则也不用区分a类和b类规则了。

为了方便，将上面的代码略微修改变成如下代码：

#include<iostream>
using namespace std;bool ok(int a, int b)
{if (a + b == 24 || a - b == 24 || a*b == 24 || a != 0 && a == 24 * b){cout << a << " " << b << endl;return true;}return false;
}bool ok(int a, int b, int c)
{if (b == 0){if (ok(a, c))return true;return false;}if (c == 0){if (ok(a, b))return true;return false;}if (ok((a + b), c) || ok((a - b), c) || ok((a * b), c))return true;if (a%b == 0 && ok(a / b, c))return true;if (ok(a, b + c) || ok(a, b - c) || ok(a, b * c))return true;if (b%c == 0 && ok(a, b / c))return true;return false;
}bool ok(int a, int b, int c, int d)
{if (ok(a + b, c, d) || ok(a - b, c, d) || ok(a * b, c, d))return true;if (a%b == 0 && ok(a / b, c, d))return true;if (ok(a, b + c, d) || ok(a, b - c, d) || ok(a, b * c, d))return true;if (b%c == 0 && ok(a, b / c, d))return true;if (ok(a, b, c + d) || ok(a, b, c - d) || ok(a, b, c * d))return true;if (c%d == 0 && ok(a, b, c / d))return true;return false;
}bool ok1(int a, int b, int c, int d)
{if (ok(a, b, c, d) || ok(a, c, b, d) || ok(b, a, c, d) || ok(b, c, a, d) || ok(c, a, b, d) || ok(c, b, a, d))return true;return false;
}int main()
{int a, b, c, d;while (scanf("%d %d %d %d",&a,&b,&c,&d)){if (ok1(a, b, c, d) || ok1(b, c, d, a) || ok1(c, d, a, b) || ok1(d, a, b, c))cout << "Yes" << endl;else cout << "No" << endl;}return 0;
}

下面分析（a）和（b）的区别，到底有多少例子（以下简称必出现分数例子），是在（b）类规则下是计算不出结果的，在（a）类下是可以的。

比如1,5,5,5就是一个特殊例子，不难发现，这样的例子只有6种情况：

（a-b/c）*d 和 （b/c-a）*d 和 （a+b/c）*d 和   d/（a-b/c）和 d/（b/c-a） 和 d/（a+b/c）

以下将可以用上述6种方法计算出来的例子称为可出现分数例子。

必出现分数例子，肯定都是可出现分数例子，但是反过来未必，

比如9,9,6,2，（9+9-6）*2=24,（2+6/9）*9=24

所以下面讨论，对于扑克牌类，可出现分数例子有哪些，其中又有哪些是必出现分数例子。

将6种情况化成整型方程：

(a*c-b)*d=24*c 和 (b-a*c)*d=24*c 和 (a*c+b)*d=24*c 和 c*d=24*(a*c-b) 和 c*d=24*(b-a*c) 和 c*d=24*(a*c+b)

求出所有可出现分数例子的代码：

#include<iostream>
using namespace std;bool ok(int a, int b, int c, int d)
{
if ((a*c - b)*d == 24 * c || (b - a*c)*d == 24 * c || (a*c + b)*d == 24 * c)return true;
if (c*d == 24 * (a*c - b) || c*d == 24 * (b - a*c) || c*d == 24 * (a*c + b))return true;
return false;
}int main()
{for (int a = 1; a <= 13; a++)for (int b = 1; b <= 13; b++)for (int c = 1; c <= 13; c++)for (int d = 1; d <= 13; d++)if (b%c  && ok(a, b, c, d))cout << a << " " << b << " " << c << " " << d << endl;return 0;
}

输出：

1 1 2 12
1 2 3 8
1 2 4 12
1 3 2 12
1 3 4 6
1 3 6 12
1 4 3 8
1 4 6 8
1 4 8 12
1 5 3 9
1 5 4 6
1 5 6 4
1 5 8 9
1 5 10 12
1 6 4 12
1 6 8 6
1 6 9 8
1 6 12 12
1 7 5 10
1 7 6 4
1 7 8 3
1 7 12 10
1 8 6 8
1 8 12 8
1 9 6 12
1 9 8 3
1 9 12 6
1 10 6 9
1 10 8 6
1 10 12 4
1 11 3 9
1 11 8 9
1 11 12 2
1 11 13 13
1 12 8 12
1 12 9 8
1 13 11 11
1 13 12 2
2 2 3 9
2 2 5 10
2 2 11 11
2 2 13 13
2 3 2 12
2 4 6 9
2 4 10 10
2 5 2 12
2 5 3 8
2 6 4 12
2 6 9 9
2 7 3 8
2 7 4 6
2 8 12 9
2 9 4 6
2 9 6 12
2 10 4 12
2 10 6 8
2 10 7 7
2 11 6 4
2 12 8 12
2 13 6 4
2 13 8 9
3 1 3 9
3 2 6 9
3 3 5 10
3 3 7 7
3 3 9 9
3 4 12 9
3 5 2 12
3 6 10 10
3 7 2 12
3 8 3 8
3 9 5 5
3 9 11 11
3 10 3 8
3 10 4 12
3 11 4 6
3 13 4 6
4 4 3 9
4 4 5 5
4 4 7 7
4 7 2 12
4 8 5 10
4 8 6 9
4 8 10 5
4 9 2 12
4 11 3 8
4 12 9 9
4 13 3 8
5 1 5 5
5 2 10 5
5 7 3 9
5 9 2 12
5 11 2 12
5 11 7 7
5 13 5 10
6 6 5 5
6 10 3 9
6 11 2 12
6 12 10 5
6 13 2 12
7 11 5 5
7 13 2 12
7 13 3 9

一共103组

再看着其中有多少组是必出现分数例子。

可以把上面的2个代码整合起来，也可以把上面的输出输入到第1个程序里面判断。

最后可以得到，必出现分数例子只有如下17个（其中有2个是重复的）

1 3 4 6     ——— 6/(1-3/4)
1 5 4 6     ——— 6/(5/4-1)
1 5 6 4     ———4/(1-5/6) （这2个是重复的）
1 6 8 6     ——— 6/(1-6/8)
1 12 8 12  ———12/(12/8-1)
2 2 11 11    ——— (2+2/11)*11
2 2 13 13     ——— (2-2/13)*13
2 4 10 10   ———(2+4/10)*10
2 10 7 7   ———(2+10/7)*7
3 3 7 7   ——— (3+3/7)*7
3 5 2 12  ——— 12/(3-5/2)
3 8 3 8    ——— 8/(3-8/3)
4 4 7 7    ——— (4-4/7)*7
5 1 5 5    ——— (5-1/5)*5
5 2 10 5  ——— (5-2/10)*5
5 11 7 7 ——— (5-11/7)*7
7 11 5 5  ———(7-11/5)*5

更多推荐

puzzle（0151）《24点》

本文发布于:2023-06-27 07:03:31，感谢您对本站的认可！
本文链接:https://www.elefans.com/category/jswz/34/907736.html
版权声明:本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
本文标签：puzzle

发布评论

评论列表 （有 0 条评论）

最近发表

草根站长

>www.elefans.com

编程频道|电子爱好者 - 技术资讯及电子产品介绍！

热门文章

标签列表