...进从1到13中任选4个数,运用+,-,*,/,()使其最后的值为24,这怎么...

发布网友 发布时间：2024-10-23 22:46

我来回答

共5个回答

热心网友 时间：8分钟前

/*
程序主要使用了正则表达式（编译原理的内容）和计算用字符串表示的表达式两种技术。

算24点的一般形式，用正则表达式表示有一下几种：
( ( ( E O E ) O E ) O E ) = 24
( ( E O ( E O E ) ) O E ) = 24
( ( E O E ) O ( E O E ) ) = 24
( ( E O E ) O ( E O E ) ) = 24
( E O ( ( E O E ) O E ) ) = 24
( E O ( E O ( E O E ) ) ) = 24

其中 E 表示数字，O表示操作符 。
程序的思想就是穷举法，把上面六个式子中的 E 用合法的数字替换，
O 用合法的操作符替换，看是否能得出结果。显然计算结果时还要
计算字符串表示的表达式。

例如：( ( ( 1 + 2 ) + 3 ) * 4 ) = 24 就是一种替换 ，等号左边是一个
用字符串表示的表达式。

这种方法的【优点】是思路简单，而且容易扩展 。
（如不是用四个数字而是任意个，并且可以使用加减乘除以外的运算）

当然这种方法的【缺点】是产生大量我们一般认为重复的式子。
如 ( ( ( 1 + 2 ) + 3 ) * 4 ) = 24 和 ( ( 1 + ( 2 + 3 ) ) * 4 ) = 24
去掉不必要的括号和，都能化成：
(1 + 2 + 3 )*4 = 24 ，因此一般我们认为上面这两个式子是相同的。

*/

#include <iostream>
#include <cstring>
#include <cmath>
#include <string>
#include <ctime>
#include <cstdlib>
using namespace std;

const int MAX_AVAILABAL_NUMBER_NUM = 20;
const int MAX_AVAILABAL_OPERATOR_NUM = 10;
const int MAX_REGULAR_EXPRESSION_NUM = 100;
const int MAX_LEAGAL_EXPRESSION_NUM = 4000;
const int MAX_LEN = MAX_AVAILABAL_NUMBER_NUM * 10;

#define SAVE 0
#define PRINT 1
#define EMPTY -1

// 将整数 num 装换成字符串保存着 s 中
char * Num_To_Str(char s[],int num)
{
int len = (int)log10(num)+1;

s[len--]='\0';

do
{
s[len--]=(num%10)+'0';
num/=10;
}while(num);

return s;
}

// 替换字符 s[p] 为字符串 t
char* Replace(char s[],int p,char t[])
{
int ls,lt,i,j,k;
ls = strlen(s);
lt = strlen(t);
for(i=ls+lt-1;i>=(p+lt);i--)
s[i]=s[i-lt+1];

for(j=p,k=0;t[k]!='\0';j++,k++)
s[j]=t[k];

return s;
}

typedef struct
{
int number;
int appear_time;
}Node;

//记录产生表达式所需的信息
class Expression_Imformation
{
public:
void Init();
void Init_All_Answer();
void Init_Calculate();
void Init_Guess();
void Generate_Expression(char start[],char rule[],int T,int t);
void Calculate(int num_of_chose_number,int num_of_chose_operator);
int Precedence(char op);
double Calculate_Expression(char *S1,bool & Is_A_Leagal_Expression );
char* Transform(char *S1 ,bool & Is_A_Leagal_Expression);
private:

int num_of_used_number; // 产生表达式需要数据个数，默认为 4 个数据
double reslut; // 表达式的结果，默认为 24

// 可使用的数据范围，默认 1-13，每个数据可出现多次
int num_of_available_number;
Node available_number[MAX_AVAILABAL_NUMBER_NUM];

// 可使用的符号类型，默认加减乘除
int num_of_available_operator;
char available_operator[MAX_AVAILABAL_OPERATOR_NUM][5];

// 正则表达式
// 如 ( ( E O E ) O ( E O E ))
// 其中 E 表示数据，O 表示操作符
int num_of_regular_expression;
char regular_expression[MAX_REGULAR_EXPRESSION_NUM][MAX_LEN];

// 符合结果的表达式
int num_of_leagal_expression;
char leagal_expression[MAX_LEAGAL_EXPRESSION_NUM][MAX_LEN];

//临时变量，Generate_Expression 函数使用
int chose_number[MAX_AVAILABAL_NUMBER_NUM];
char chose_operator[MAX_AVAILABAL_NUMBER_NUM-1][5];

int save_or_print; // 控制结果直接输出还是保存
};

void Expression_Imformation::Init()
{
num_of_used_number = 4;
reslut = 24.0;

num_of_available_operator = 4;
strcpy(available_operator[0],"+");
strcpy(available_operator[1],"-");
strcpy(available_operator[2],"*");
strcpy(available_operator[3],"/");

//产生正则表达式
num_of_regular_expression = 0;
char start[MAX_LEN] = "E";
char rule[MAX_LEN] = "( E O E )";
Generate_Expression(start,rule,num_of_used_number-1,0);

// cout<<num_of_regular_expression<<endl;
// for(int i=0;i<num_of_regular_expression;i++)
// cout<<i+1<<" "<<regular_expression[i]<<endl;

num_of_leagal_expression = 0;

save_or_print = PRINT;
}

void Expression_Imformation::Init_All_Answer()
{
Init();
cout<<"**********All_AnswerS**********"<<endl;
num_of_available_number = 13;
for(int i=0;i<num_of_available_number;i++)
{
available_number[i].number = i+1;
available_number[i].appear_time = num_of_used_number;
}

save_or_print = PRINT;
num_of_leagal_expression = 0;
Calculate(0,0);
}

void Expression_Imformation::Init_Calculate()
{
int i,j,temp;
char option[MAX_LEN];

Init();

while(1)
{
cout<<"***********Calculate***********"<<endl;
num_of_available_number = 0;
for(int i=0;i<num_of_used_number;i++)
{
cout<<"Input the "<<i+1<<"th number : ";
cin>>temp;
for(j=0;j<num_of_available_number;j++)
if(temp == available_number[j].number)
break;

if(j<num_of_available_number)
available_number[j].appear_time++;
else
{
available_number[j].number = temp;
available_number[j].appear_time = 1;
num_of_available_number++;
}
}

save_or_print = PRINT;
num_of_leagal_expression = 0;
Calculate(0,0);

if(num_of_leagal_expression == 0)
cout<<"No Solution!"<<endl;

cout<<"continue?(Y/N)"<<endl;
cin>>option;
if(!( strcmp(option,"Y")==0 || strcmp(option,"y")==0 ))
return ;
}
}

void Expression_Imformation::Init_Guess()
{
char option[MAX_LEN];
char answer[MAX_LEN];
int i,j,temp;
bool Is_A_Leagal_Expression;
int try_time = 3;

Init();
srand(time(NULL));

while(1)
{
cout<<"*************Guess*************"<<endl;
num_of_leagal_expression = 0;

while( num_of_leagal_expression == 0)
{
num_of_available_number = 0;
for(i=0;i<num_of_used_number;i++)
{
temp = rand()%13+1;
for(j=0;j<num_of_available_number;j++)
if(temp == available_number[j].number)
break;

if(j<num_of_available_number)
available_number[j].appear_time++;
else
{
available_number[j].number = temp;
available_number[j].appear_time = 1;
num_of_available_number++;
}
}

save_or_print = SAVE;
Calculate(0,0);
}

cout<<"Question : ";
for(i=0;i<num_of_available_number;i++)
for(j=0;j<available_number[i].appear_time;j++)
cout<<available_number[i].number<<" ";
cout<<endl;

try_time = 3;
while(try_time--)
{
cout<<"Your answer: ";
cin>>answer;

if(Calculate_Expression(answer,Is_A_Leagal_Expression) == reslut && Is_A_Leagal_Expression == true)
{
cout<<"Right!"<<endl;
break;
}
else
cout<<"Wrong!"<<endl;

}
for(i=0;i<num_of_leagal_expression;i++)
cout<<"Solution #"<<i+1<<" :"<<endl<<leagal_expression[i]<<endl<<endl;

cout<<"continue?(Y/N)"<<endl;
cin>>option;
if(!( strcmp(option,"Y")==0 || strcmp(option,"y")==0 ))
return ;

}
}

void Expression_Imformation::Generate_Expression(char start[],char rule[],int T,int t)
{
int i;
char temp[MAX_LEN];

if(t==T)
{
strcpy(regular_expression[num_of_regular_expression++],start);
return;
}

else
{
for(i=0;start[i]!='\0';i++)
if(start[i]=='E')
{
strcpy(temp,start);
Replace(start,i,rule);
Generate_Expression(start,rule,T,t+1);
strcpy(start,temp);
}
}
}

void Expression_Imformation::Calculate(int num_of_chose_number,int num_of_chose_operator)
{
int i,j,p,counter;
int p_chose_number,p_chose_operator;
char temp[MAX_LEN],int_to_num[MAX_LEN];
bool Is_A_Leagal_Expression;
if(num_of_chose_number == num_of_used_number)
{
if(num_of_chose_operator == (num_of_chose_number - 1))
{
//枚举所有正则表达式
for(p=0;p<num_of_regular_expression;p++)
{
strcpy(temp,regular_expression[p]);
p_chose_number = p_chose_operator = 0;

// 替换正则表达式中的 E (数字)和 O(操作符)
for(i=0;temp[i]!='\0';i++)
{
if(temp[i]=='E')
{
Replace(temp,i,Num_To_Str(int_to_num,chose_number[p_chose_number]));
i+=strlen(int_to_num);
p_chose_number++;
}
else if(temp[i]=='O')
{
Replace(temp,i,chose_operator[p_chose_operator]);
i+=strlen(chose_operator[p_chose_operator]);
p_chose_operator++;
}
}//for(i)

if(reslut == Calculate_Expression(temp,Is_A_Leagal_Expression))
{
if(save_or_print == PRINT)
cout<<"Soultion #"<<(num_of_leagal_expression+1)<<" : "<<endl<<temp<<endl<<endl;
else
strcpy(leagal_expression[num_of_leagal_expression],temp);

num_of_leagal_expression++;
}
}//for(p)
}
else
{
for(i=0;i<num_of_available_operator;i++)
{
strcpy(chose_operator[num_of_chose_operator],available_operator[i]);
Calculate(num_of_chose_number,num_of_chose_operator+1);
}
}
}
else
{
for(i=0;i<num_of_available_number;i++)
{
counter=0;
for(j=0;j<num_of_chose_number;j++)
if(chose_number[j] == available_number[i].number)
counter++;
if(counter<available_number[i].appear_time)
{
chose_number[num_of_chose_number] = available_number[i].number;
Calculate(num_of_chose_number+1,num_of_chose_operator);
}
}
}
}

// 运算符优先级
int Expression_Imformation::Precedence(char op)
{
switch(op)
{
case'+':
case'-':
return 1;
case'*':
case'/':return 2;
case'^':return 3;
case'(':
case'@':
default:
return 0;
}
}

// 将字符串 S1 中序表达式转化成前序表达式
char* Expression_Imformation::Transform(char *S1 ,bool & Is_A_Leagal_Expression)
{
char stack[MAX_LEN];
int stack_top = EMPTY;

char * S2 = new char[strlen(S1)];

int i=0,j=0;
char ch=S1[i];
stack[++stack_top] = '@';
Is_A_Leagal_Expression = true;

while(ch)
{
if(ch==' ') ch=S1[++i];
else if(ch=='(')
{
stack[++stack_top] = ch;
ch=S1[++i];
}
else if(ch==')')
{
while(stack_top!=EMPTY && stack[stack_top]!='(')
S2[j++]=stack[stack_top--];

if(stack_top == EMPTY)
{
Is_A_Leagal_Expression = false;
goto Label;
}

stack_top--;
ch=S1[++i];
}
else if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='^')
{
if(stack_top == EMPTY)
{
Is_A_Leagal_Expression = false;
goto Label;
}

char w=stack[stack_top];
while(Precedence(w)>=Precedence(ch))
{
S2[j++]=w;
stack_top--;
if(stack_top == EMPTY)
break;
w=stack[stack_top];
}
stack[++stack_top] = ch;
ch=S1[++i];
}
else
{
if((ch<'0'||ch>'9')&&ch!='.')
{
Is_A_Leagal_Expression = false;
goto Label;
}
while((ch>='0'&&ch<='9')||ch=='.')
{
S2[j++]=ch;
ch=S1[++i];
}
S2[j++]=' ';
}
}//end while

if(stack_top == EMPTY)
{
Is_A_Leagal_Expression = false;
goto Label;
}

ch=stack[stack_top--];
while(ch!='@')
{
if(ch=='(')
{
Is_A_Leagal_Expression = false;
goto Label;
}
else
{
S2[j++]=ch;
ch=stack[stack_top--];
}
}

S2[j++]='\0';
strcpy(S1,S2);
Label:
delete []S2;
return S1;
}

// 计算表达式 S1 的值
double Expression_Imformation::Calculate_Expression(char *S1,bool & Is_A_Leagal_Expression )
{
double S[MAX_LEN];
int S_top = EMPTY;

double x,y;
int i=0,k;

Node check[MAX_AVAILABAL_NUMBER_NUM];
int check_p = 0;

char *str = new char [strlen(S1)];
strcpy(str,S1);
Transform(str,Is_A_Leagal_Expression);
if(Is_A_Leagal_Expression == false)
return 0.0;

while(str[i])
{
if(str[i]==' ')
{
i++;
continue;
}

switch(str[i])
{
case '+':
if(S_top<1)
{
Is_A_Leagal_Expression = false;
goto Label;
}
x=S[S_top]+S[S_top-1];
S_top-=2;
i++;
break;
case '-':
if(S_top<1)
{
Is_A_Leagal_Expression = false;
goto Label;
}
x=S[S_top-1] - S[S_top];
S_top-=2;
i++;
break;
case '*':
if(S_top<1)
{
Is_A_Leagal_Expression = false;
goto Label;
}
x=S[S_top-1] * S[S_top];
S_top-=2;
i++;
break;
case '/':
if(S_top<1)
{
Is_A_Leagal_Expression = false;
goto Label;
}
x=S[S_top-1] / S[S_top];
S_top-=2;
i++;
break;
case '^':
if(S_top<1)
{
Is_A_Leagal_Expression = false;
goto Label;
}
x=pow(S[S_top-1],S[S_top]);
S_top-=2;
i++;
break;
default:
x=0;
while(str[i]>='0'&&str[i]<='9')
{
x=x*10+str[i]-'0';
i++;
}

if(str[i]=='.')
{
i++;
y=0;
double j=10.0;
while(str[i]>='0'&&str[i]<='9')
{
y=y+(str[i]-'0')/j;
i++;
j*=10;
}
x+=y;

// 记录输入的数字
for(k=0;k<check_p;k++)
if(check[k].number == (int)x)
check[k].appear_time++;

if(k==check_p)
{
check[check_p].number = (int)x;
check[check_p].appear_time =1;
check_p++;
}
}
}//switch

S[++S_top]=x;

}//end while

if(S_top == EMPTY)
{
Is_A_Leagal_Expression = false;
goto Label;
}

// 检查输入数字的合法性
for(k=0;k<check_p;k++)
{
for(i=0;i<num_of_available_number;i++)
if(available_number[i].number == check[k].number && available_number[i].appear_time >= check[check_p].appear_time)
break;
if(i==num_of_available_number)
break;
}

if(k < check_p)
{
Is_A_Leagal_Expression = false;
goto Label;
}

x=S[S_top--];
Label:
return x;

}

int main(int argc, char *argv[])
{
class Expression_Imformation game;

// 用户输入数字，系统求解（给出全部解）
game.Init_Calculate();
// 系统给出数字，用户求解（保证有解） 。用户必须用系统给出的数字求解，最多试3次
game.Init_Guess();
// 给定数据范围（如1-13）和可使用的操作符（如加减乘除），求出所有解
game.Init_All_Answer();

return 0;
}

热心网友 时间：1分钟前

游戏无法就是 死循环 while(1)

知道游戏完成到退出

#include <time.h>

int main(int argc, char* argv[])
{
int a[4],i;
//while(1)
{

srand((unsigned)time(NULL));

for(i=0;i<4;i++)
{
a[i]=rand()%12+1;
}

for(i=0;i<4;i++)
{
printf("%d\t",a[i]);
}
}
getch();
return 0;
}
还没完成哦~！

热心网友 时间：3分钟前

貌似相当复杂啊！+，-，*，/，还有（），难做，费时间。

热心网友 时间：1分钟前

具体答案可以参考《编程之美》 里面有详细的Source code
思想就是穷举，穷举所有的排列组合
然后根据默认规则给出优化，如果想提高自身的算法及代码实现能力，可以参考着书的优化步骤自己做一边，对你没啥坏处，自己动手做一遍，比看答案好不少，而且可以比较出你与高手之间编程的差距，里面的代码都是微软高手写的，不管是优化还是思想以及编码规范，都是很好的教材

热心网友 时间：9分钟前

随便写的