请选择 进入手机版 | 继续访问电脑版

石家庄老站长

点击联系客服
客服QQ: 客服微信:
 找回密码
 立即注册
查看: 6|回复: 1

华为机器测试hj67: 24分游戏算法

[复制链接]

1

主题

1

帖子

-7

积分

限制会员

积分
-7
发表于 2021-9-13 07:20:40 | 显示全部楼层 |阅读模式
作者:史蒂芬

著作权声明:著作权归作者所有,商业转载请联系作者获得许可。非商业转载请注明出处

题目描述:

问题说明:给4个1-10数字,通过加法、乘法、除法得到24,就胜利了

输入:

四个1-10的数字。[数字允许重复,但每个数字只能使用一次,测试用例保证没有异常的数字。

输出:

Trueorfalse

本主题包含多组样例输入。

输入描述:

输入4个int整数

输出描述:

返回不能得到24分,不能输出true,也不能输出false

示例:

输入:

7 2 1 10

输出:

True

解题思路:

这个问题是深度优先遍历DFS的经典标题。输入1-10的4个数字,然后使用加法和乘法将结果除以24。使用Dfs函数进行迭代遍历解释,分四个阶段计算时,step为3,24,如果有结果,flag为true设置为。声明Num数组中有数字,并声明visit数组中当前是否可以使用数字。

假设输入数字为7654,则第一次巡回将为7 6 5 4,7 6 5-4。另外7 6-5 4。另外7 6 4 5。用这种方式类推DFS还处理后面的值,以及计算前面所有值的结果。也就是说,7 6 5*4投(7 6 5)*4。这时,请不要忘记,即使计算结果与预想的不一样,也有排序。后面是5*4 7 6的计算表达式。

注意:需要考虑其他情况,因为sum最初为0。否则,将显示0*X=0。

测试代码:

#include  iostream

Using  namespace  STD

double  num[4];

Bool  flag=false

bool  visit[4]={ 0 };

Void  dfs(int  step,double  sum)

{

If(flag)

Return

If(step==3)

{

If(总和==24)。)

{

Flag=true

Return

}

}

Else{

阶段;

FOR(INT  I=0;I4;I)。

{

If(!Visit[i])

{

visit[I]=true;

Dfs(step,SUM  Num[I]);

Dfs(step,SUM-Num[I]);

If(阶段!=0){

Dfs(step,SUM  * Num[I]);

Dfs(step,SUM/Num[I]);

}

visit[I]=false;

If(flag)

Return

}

}

}

}

Int  main()

{

while(cinnum[0]num[1]num[2]num[3])

{

Dfs(-1,0);

If(flag)

{

Cout  'true  'endl

}

Else{

Cout  'false  'endl

}

Flag=false

num[4]={ 0 };

visit[4]={ 0 };

}

return  0;

}

后来测试结果显示,1 9-1 2这个例子过不去,但(9-1)*(2 1)=24,上述算法考虑括号操作不周到,因此,一名小客大男子“ultraji”提供的算法创意变得更加完善,其中共享

逻辑是借next_permutation函数对4位数字进行排序,将3个运算符插入其中,然后使用for循环处理所有可能的括号情况。代码如下:

#include  iostream

#include  algorithm

#include  vector

#include  cmath

Using  namespace  STD

Double  op  (double  a,double  b,int  opera)

{

IF(Opera==0)return  A  B;

ELSE  IF(Opera==1)return  A-B;

ELSE  IF(Opera==2)return  A  * B;

ELSE  IF(Opera==3)return  A/B;

return  0;

}

Bool  cal  24 (vector  double  a,vector  int  o)

{

//考虑括号更改优先级

Bool  flag=false

If(o.empty()) {

IF(FABS(A[0]-24.0)0.01)FLAG=true;

} else  {

FOR(INT  I=0;I  o.size()!FlagI)。

{

A[i]=op(a[i],a[i  1],O[I]);

A  . Erase(A  . Begin()I  1);

o  . erase(o  . begin()I);

Flag  |=cal24(a,O);

}

}

Return  flag

}

Int  main()

{

Double  A[4];

INT  O[3];

While(cin  a[0] a[1] a[2] a[3])

{

Bool  flag=false

Sort(a,A  4);

道{

FOR(INT  I=0;I  4!FlagI) {

o[0]=I;

FOR(INT  J=0;Jay  4!FlagJ) {

o[1]=j;

FOR(INT  K=0;K  4!FlagK) {

o[2]=k;

Vectordouble  va(a,a  4):

Vectorint  vo(o,o  3):

If(cal24(va,VO))FLAG=true;

}

}

}

} while  (next_permutation(a,a  4))!FLAG);

IF(FLAG)Cout  ' true  ' endl;

Else  cout  ' false  ' endl

}

return  0;

}
回复

使用道具 举报

0

主题

595

帖子

-578

积分

限制会员

积分
-578
发表于 2021-9-13 13:09:20 | 显示全部楼层
过来看看的
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|无图版|手机版|小黑屋|石家庄@IT精英团

GMT+8, 2021-9-22 01:48 , Processed in 0.187201 second(s), 19 queries .

Powered by Discuz! X3.4

© 2001-2021 Comsenz Inc.

快速回复 返回顶部 返回列表