一、总结
一句话总结:把多元运算转化为两元运算,先从四个数中取出两个数进行运算,然后把运算结果和第三个数进行运算,再把结果与第四个数进行运算。在求表达式的过程中,最难处理的就是对括号的处理,而这种思路很好的避免了对括号的处理。 这种思路的话算法就是全排列(数的)加枚举(符号)。
二、24点游戏算法
题目描述
问题描述:给出4个1-10的数字,通过加减乘除,得到数字为24就算胜利 输入: 4个1-10的数字。[数字允许重复,测试用例保证无异常数字] 输出: true or false
输入描述:
输入4个int整数
输出描述:
返回能否得到24点,能输出true,不能输出false
解答一:
DFS搜索
1 #include <stdio.h>
2 #include <algorithm>
3 using namespace std;
4 const int N=4;
5 int num[N];
6 int isSolve=0;
7 void dfs(int index,int currentNum,int arr[])
8 {
9 if(currentNum==24)
10 {
11 isSolve=1;
12 return;
13 }
14 if(isSolve||currentNum>24||index>=4)
15 return;
16 for(int operFlag=0;operFlag<4;operFlag++)
17 {
18 switch(operFlag)
19 {
20 case 0:
21 dfs(index+1,currentNum+arr[index],arr);
22 break;
23 case 1:
24 dfs(index+1,currentNum-arr[index],arr);
25 break;
26 case 2:
27 dfs(index+1,currentNum*arr[index],arr);
28 break;
29 case 3:
30 dfs(index+1,currentNum/arr[index],arr);
31 break;
32 }
33 if(isSolve)
34 return;
35 }
36 }
37 int main()
38 {
39 while(scanf("%d%d%d%d",&num[0],&num[1],&num[2],&num[3])>0)
40 {
41 isSolve=0;
42 sort(num,num+4);
43 do
44 {
45 dfs(1,num[0],num);
46 if(isSolve)
47 break;
48 } while (next_permutation(num,num+4));
49 if(isSolve)
50 printf("true\n");
51 else
52 printf("false\n");
53 }
54 return 0;
55 }
解答二:
//搞了半天原来是可以有括号的,全排列+递归就可以了,而全排列本身又可以递归来做。
//不要忘记恢复现场就行。
#include<iostream>
using namespace std;
inline void Swap(int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}
bool is24(int a[], int begin, int end, double tot)
{
if (begin==end-1) return (a[begin] == tot);
else
{
bool ans = false;
for (int i = begin; i<end; i++)
{
swap(a[i], a[end-1]);
ans = ans || is24(a, begin, end - 1, tot + a[end - 1]) || is24(a, begin, end - 1, tot - a[end - 1]) || is24(a, begin, end - 1, tot * a[end - 1]) || is24(a, begin, end - 1, tot / a[end - 1]);
swap(a[i], a[end-1]);
}
return ans;
}
}
int main()
{
int a[4];
while (cin >> a[0] >> a[1] >> a[2]>>a[3])
{
if (is24(a, 0,4, 24)) cout << "true" << endl;
else cout << "false" << endl;
}
}
三、关于24点游戏的编程思路与基本算法
24点游戏的算法,其中最主要的思想就是穷举法。所谓穷举法就是列出4个数字加减乘除的各种可能性,包括括号的算法。我们可以将表达式分成以下几种:首先我们将4个数设为a,b,c,d,,其中算术符号有+,-,*,/,。其中有效的表达式有a,ab-cd,等等。列出所有有效的表达式。其中我们用枚举类型将符号定义成数字常量,比如用1表示+,2表示-等。如下是我对穷举法的一种编程语言。在编程的头部要对变量做下定义。其中a,b,c,d的范围是1到10。这就需要在定义变量的时候要有限制。在vc++中的编程中,在定义控件的变量范围可以直接填写变量的最大和最小,在此编程中的最大是10,最小是1。这就给编程写语句带来了方便。
运用C/C++语言开发工具Microsoft Visual C++ 6.0,利用它简单、明了的开发特点对课本知识进行系统的实践,并且通过对各个知识点的运用进行所需的程序编写。首先,要充分理解每个程序涉及的算法,牢记实现算法的每一个步骤;其次,再在计算机上利用C语言编写出代码,要求结构清晰,一目了然;最后,要对程序进行优化,使程序实现优秀的运行功能。在编写程序的过程中要充分理解并能熟练使用对应的算法,竟可能多的涉及课本中的知识点。总之通过实行整体方案,最终使程序达到运行状态,并且实现良好的运行效果。
故做了如下的计划安排,将这项工程分为两大部分:程序的设计和程序的调试。
首先在程序的设计部分由分为几个步骤:
其次,进行程序的调试。
设计方法和内容
在做某件事时,一个好的方法往往能起到事半功倍的效果。在这个课程的设计上,我选择了C++语言作为算法的描述语言,因为C++语言具有丰富的表达能力以及代码的高效性,并且有着良好的移植性和灵活性。同时,采用“自顶向下,个个击破”的程序设计思路和思想,充分运用C++语言强大的功能。使该课程设计做起来更加的简单。
我将这个课程设计整体分成了两个部分。一个是数据结构定义部分和算法部分。这两大部分有机的结合共同构成了该课程设计的程序,运行该程序就可以将该课程设计的功能实现了。
程序的设计思想和内容
(一)算法一:
24点游戏的算法,其中最主要的思想就是穷举法。所谓穷举法就是列出4个数字加减乘除的各种可能性。我们可以将表达式分成以下几种:首先我们将4个数设为a,b,c,d,,将其排序列出四个数的所有排序序列组合(共有A44=24种组合)。再进行符号的排列表达式,其中算术符号有+,—,*,/,(,)。其中有效的表达式有a*(b-c/b),a*b-c*d,等等。列出所有有效的表达式。其中我们用枚举类型将符号定义成数字常量。如下是我对穷举法的一种编程语言。在编程的头部要对变量做下定义。其中a,b,c,d的范围是1到10。这就需要在定义变量的时候要有限制。在vc++中的MFC编程中,在定义控件的变量范围可以直接填写变量的最大和最小,在此编程中的最大是10,最小是1。这就给编程写语句带来了方便(因为其自动会生成语句)。下面我介绍下穷举法的主要实现,我们知道要实现24点的算法,就是通过4个数字,4个运算符号和2对括号(最多为2对),通过各种组合判断其结果是否为24。我们用a,b,c,d代替4个数字。考虑每种可能,总的算法就有7种可能。分别为:
1没括号的(形如a*b*c*d);
2有括号的(形如(a * b) * c * d);
3有括号的(形如(a * b * c) * d);
4有括号的(形如a * (b * c) * d);
5有括号的(形如(a * b) * (c * d));
6有括号的(形如((a * b) * c) * d);
7有括号的(形如(a * (b * c)) * d)。
接下来就是对每一种进行分析判断。
以上就是穷举法的基本实现算法
首先穷举的可行性问题。我把表达式如下分成三类:
1、 列出四个数的所有排序序列组合(共有A44=24种组合)。
2、 构筑一个函数,列出所有运算表达式。
3、 输入数据计算。
(二)算法二:
24点游戏的算法,还有另外一种算法。
把多元运算转化为两元运算,先从四个数中取出两个数进行运算,然后把运算结果和第三个数进行运算,再把结果与第四个数进行运算。在求表达式的过程中,最难处理的就是对括号的处理,而这种思路很好的避免了对括号的处理。基于这种思路的一种算法:
因为能使用的4种运算符 – * / 都是2元运算符,所以本文中只考虑2元运算符。2元运算符接收两个参数,输出计算结果,输出的结果参与后续的计算。
由上所述,构造所有可能的表达式的算法如下:
(1) 将4个整数放入数组中
(2) 在数组中取两个数字的排列,共有 P(4,2) 种排列。对每一个排列,
(2.1) 对 – * / 每一个运算符,
(2.1.1) 根据此排列的两个数字和运算符,计算结果
(2.1.2) 改表数组:将此排列的两个数字从数组中去除掉,将 2.1.1 计算的结果放入数组中
(2.1.3) 对新的数组,重复步骤 2
(2.1.4) 恢复数组:将此排列的两个数字加入数组中,将 2.1.1 计算的结果从数组中去除掉
可见这是一个递归过程。步骤 2 就是递归函数。当数组中只剩下一个数字的时候,这就是表达式的最终结果,此时递归结束。
在程序中,一定要注意递归的现场保护和恢复,也就是递归调用之前与之后,现场状态应该保持一致。在上述算法中,递归现场就是指数组,2.1.2 改变数组以进行下一层递归调用,2.1.3 则恢复数组,以确保当前递归调用获得下一个正确的排列。
括号 () 的作用只是改变运算符的优先级,也就是运算符的计算顺序。所以在以上算法中,无需考虑括号。括号只是在输出时需加以考虑。
-
-
-
if ( fabs(number[0] - VOLUE) <= LING )
-
{ cout << exp[0] << "\t\t";
-
-
-
-
-
-
-
-
-
for(int i=0; i < n; i++) {
-
for (int j = i + 1; j < n; j++) {
-
-
-
-
-
number[j] = number[n - 1];
-
-
-
-
exp[i]= '('+ expa + '+' + expb + ')';
-
-
-
exp[i]='('+ expa+ '-' + expb + ')';
-
-
-
exp[i] = '('+expb + '-' + expa + ')';
-
-
-
exp[i]= '('+ expa +'*'+ expb+ ')';
-
-
-
-
exp[i] ='('+expa+'/' + expb + ')';
-
-
-
-
-
exp[i]='('+expb + '/'+ expa + ')';
-
-
-
-
-
-
-
-
-
-
附录A 原程序代码
算法一:
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
if ((a<0)||(a>10)||(b<0)||(b>10)||(c<0)||(c>10)||(d<0)||(d>10))
-
{ cout<<"你输入的输入不对,重新输入"<<endl;
-
-
int Calculate ( float x, float y, float z, float w);
-
Calculate(a,b,c,d); Calculate(a,b,d,c); Calculate(a,c,d,b);
-
Calculate(a,c,b,d); Calculate(a,d,b,c); Calculate(a,d,c,b);
-
Calculate(b,a,c,d); Calculate(b,a,d,c); Calculate(b,c,a,d);
-
Calculate(b,c,d,a); Calculate(b,d,c,a); Calculate(b,d,a,c);
-
Calculate(c,a,b,d); Calculate(c,a,d,b); Calculate(c,b,d,a);
-
Calculate(c,b,a,d); Calculate(c,d,a,b); Calculate(c,d,b,a);
-
Calculate(d,a,b,c); Calculate(d,a,c,b); Calculate(d,b,c,a);
-
Calculate(d,b,a,c); Calculate(d,c,a,b); Calculate(d,c,b,a);
-
-
int Calculate ( float x, float y, float z, float w)
-
-
if (x+y+z+w==24) cout<<x<<"+"<<y<<"+"<<z<<"+"<<w<<"=24"<<endl;
-
else if (x+y+z-w==24) cout<<x<<"+"<<y<<"+"<<z<<"-"<<w<<"=24"<<endl;
-
else if ((x+y)*(z+w)==24) cout<<"("<<x<<"+"<<y<<")*("<<z<<"+"<<w<<")=24"<<endl;
-
else if ((x-y)*(z+w)==24) cout<<"("<<x<<"-"<<y<<")*("<<z<<"+"<<w<<")=24"<<endl;
-
else if ((x-y)*(z-w)==24) cout<<"("<<x<<"-"<<y<<")*("<<z<<"-"<<w<<")=24"<<endl;
-
else if ((x+y+z)*w==24) cout<<"("<<x<<"+"<<y<<"+"<<z<<")*"<<w<<"=24"<<endl;
-
else if ((x-y-z)*w==24) cout<<"("<<x<<"-"<<y<<"-"<<z<<")*"<<w<<"=24"<<endl;
-
else if ((x+y-z)*w==24) cout<<"("<<x<<"+"<<y<<"-"<<z<<")*"<<w<<"=24"<<endl;
-
else if ((x*y*z)/w==24) cout<<"("<<x<<"*"<<y<<"*"<<z<<")/"<<w<<"=24"<<endl;
-
else if ((x*y)*(z+w)==24) cout<<"("<<x<<"*"<<y<<")*("<<z<<"+"<<w<<")=24"<<endl;
-
else if ((x*y)*(z-w)==24) cout<<"("<<x<<"*"<<y<<")*("<<z<<"-"<<w<<")=24"<<endl;
-
else if ((x*y)*z-w==24) cout<<"("<<x<<"*"<<y<<")*("<<z<<")-"<<w<<"=24"<<endl;
-
else if ((x*y)*z+w==24) cout<<"("<<x<<"*"<<y<<")*("<<z<<")+"<<w<<"=24"<<endl;
-
else if (x*y*z*w==24) cout<<x<<"*"<<y<<"*"<<z<<"*"<<w<<"=24"<<endl;
-
else if ((x+y)+(z/w)==24) cout<<"("<<x<<"+"<<y<<")+("<<z<<"/"<<w<<")"<<"=24"<<endl;
-
else if ((x+y)*(z/w)==24) cout<<"("<<x<<"+"<<y<<")*("<<z<<"/"<<w<<")"<<"=24"<<endl;
-
else if ((x*y)+z+w==24) cout<<"("<<x<<"*"<<y<<")+"<<z<<"+"<<w<<"=24"<<endl;
-
else if ((x*y)+z-w==24) cout<<"("<<x<<"*"<<y<<")+"<<z<<"-"<<w<<"=24"<<endl;
-
else if ((x*y)-(z/w)==24) cout<<"("<<x<<"*"<<y<<")-("<<z<<"/"<<w<<")"<<"=24"<<endl;
-
else if ((x*y)+(z/w)==24) cout<<"("<<x<<"*"<<y<<")-("<<z<<"/"<<w<<")"<<"=24"<<endl;
-
else if ((x*y)-z-w==24) cout<<"("<<x<<"*"<<y<<")-"<<z<<"-"<<w<<"=24"<<endl;
-
else if ((x*y)+(z*w)==24) cout<<"("<<x<<"*"<<y<<")+("<<z<<"*"<<w<<")"<<"=24"<<endl;
-
else if ((x*y)-(z*w)==24) cout<<"("<<x<<"*"<<y<<")-("<<z<<"*"<<w<<")"<<"=24"<<endl;
-
else if ((x*y)/(z*w)==24) cout<<"("<<x<<"*"<<y<<")/("<<z<<"*"<<w<<")"<<"=24"<<endl;
-
else if ((x*y)/(z-w)==24) cout<<"("<<x<<"*"<<y<<")/("<<z<<"-"<<w<<")"<<"=24"<<endl;
-
else if ((x*y)/(z+w)==24) cout<<"("<<x<<"*"<<y<<")/("<<z<<"+"<<w<<")"<<"=24"<<endl;
-
else cout<<"不可以组成24"<<endl;
-
-
算法二:
-
-
-
-
-
const double LING = 1E-6;
-
-
-
-
-
-
-
-
-
-
-
if ( fabs(number[0] - VOLUE) <= LING )
-
-
cout << expression[0] << "\t\t";
-
-
-
-
-
-
-
-
-
-
-
for (int j = i + 1; j < n; j++)
-
-
-
string expressiona, expressionb;
-
-
-
number[j] = number[n - 1];
-
expressiona = expression[i];
-
expressionb = expression[j];
-
expression[j] = expression[n - 1];
-
expression[i]= '('+ expressiona + '+' + expressionb + ')';
-
-
-
expression[i]='('+ expressiona+ '-' + expressionb + ')';
-
-
-
expression[i] = '('+expressionb + '-' + expressiona + ')';
-
-
-
expression[i]= '('+ expressiona +'*'+ expressionb+ ')';
-
-
-
-
-
expression[i] ='('+expressiona+'/' + expressionb + ')';
-
-
-
-
-
-
expression[i]='('+expressionb + '/'+ expressiona + ')';
-
-
-
-
-
-
expression[i] = expressiona;
-
expression[j] = expressionb;
-
|
请发表评论