一个能出分数，小数，百分数四则混合运算的程序。
先随机生成一颗二叉树，作为表达式树。
然后，将叶子随机一个分数。
之后，进行dfs，计算答案。
若答案不在合法范围内，则从头来。
判断括号，dfs括号深度来决定是”{}“，”[]“，”（）“。
最后，dfs输出本道题目，并随机分数的三种输出方式。
格式为markdown。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define ll long long
ll gcd(ll a,ll b)
{
if(a<0)a=-a;
if(b<0)b=-b;
while(b!=0)
{
ll t=a%b;
a=b;b=t;
}
return a;
}
struct SFs
{
ll fz,fm;
SFs(){}
SFs(ll Fz,ll Fm)
{
fz=Fz;fm=Fm;
}
};
SFs yuef(SFs rt)
{
ll g=gcd(rt.fz,rt.fm);
rt.fz/=g;rt.fm/=g;
if(rt.fz<0&&rt.fm<0)
{
rt.fz=-rt.fz;
rt.fm=-rt.fm;
}
return rt;
}
SFs operator+(SFs a,SFs b)
{
SFs rt(a.fz*b.fm+a.fm*b.fz,a.fm*b.fm);
return yuef(rt);
}
SFs operator-(SFs a,SFs b)
{
SFs rt(a.fz*b.fm-a.fm*b.fz,a.fm*b.fm);
return yuef(rt);
}
SFs operator*(SFs a,SFs b)
{
SFs rt(a.fz*b.fz,a.fm*b.fm);
return yuef(rt);
}
SFs operator/(SFs a,SFs b)
{
SFs rt(a.fz*b.fm,a.fm*b.fz);
return yuef(rt);
}
int ma,mb,mc,md;
char zk[3][6]={"$($","$[$","$\{$"},yk[3][6]={"$)$","$]$","$\}$"},fu[5][10]={" + "," $-$ "," × "," ÷ "};
SFs randfs()
{
SFs rt=yuef(SFs(rand()%ma+1,rand()%mb+1));
if(rand()%2==0)
rt.fz=-rt.fz;
return rt;
}
int mabs(int s)
{
return s>=0?s:-s;
}
bool check(SFs x)
{
return mabs(x.fz)<=mc&&mabs(x.fm)<=md&&x.fz&&x.fm;
}
double getxs(SFs x,bool &cg)
{
ll t=x.fm;
while(t%2==0)t/=2;
while(t%5==0)t/=5;
if(mabs(t)!=1)
{
cg=false;
return -1;
}
cg=true;
return double(x.fz)/x.fm;
}
int cl[1002],cr[1002],fh[1002],sl=0,sd[1002];
bool yz[1002];SFs sz[1002];
int randtree(int n)
{
int rt=++sl;
yz[rt]=false;
if(n==0)
{
fh[rt]=-1;yz[rt]=true;
sz[rt]=randfs();
return rt;
}
fh[rt]=rand()%4;
int xl=rand()%n;
cl[rt]=randtree(xl);
cr[rt]=randtree(n-1-xl);
return rt;
}
bool dfs(int u)
{
if(yz[u])
return false;
if(dfs(cl[u])||dfs(cr[u]))
return true;
if(fh[u]==0)sz[u]=sz[cl[u]]+sz[cr[u]];
else if(fh[u]==1)sz[u]=sz[cl[u]]-sz[cr[u]];
else if(fh[u]==2)sz[u]=sz[cl[u]]*sz[cr[u]];
else sz[u]=sz[cl[u]]/sz[cr[u]];
if(!check(sz[u]))return true;
return sz[u].fz==0||(sz[u].fz==1&&sz[u].fm==1);
}
bool check(int ro)
{
if(dfs(ro))
return false;
return check(sz[ro]);
}
bool kuoh(int x,int y)
{
if(y==cr[x])
{
int ty=y;
while(!yz[ty])
ty=cl[ty];
if((sz[ty].fz<0)^(sz[ty].fm<0))
return true;
}
if(fh[x]==0)
return false;
else if(fh[x]==1)
return y==cr[x]&&(fh[y]==0||fh[y]==1);
else if(fh[x]==2)
return fh[y]==0||fh[y]==1;
else
return fh[y]==0||fh[y]==1||(y==cr[x]&&fh[y]!=-1);
}
char tmp[1002],out[10002];
void outfs(SFs x)
{
if(x.fm<0)
x.fz=-x.fz,x.fm=-x.fm;
if(x.fm==1)
sprintf(tmp,"$%lld$",x.fz);
else
{
if(x.fz<0)sprintf(tmp,"$-\frac{%lld}{%lld}$",-x.fz,x.fm);
else sprintf(tmp,"$\frac{%lld}{%lld}$",x.fz,x.fm);
}
}
void routfs(SFs x)
{
if(x.fm==1)
sprintf(tmp,"$%lld$",x.fz);
else
{
bool cg;
double t=getxs(x,cg);
if(!cg)
{
if(x.fz<0)sprintf(tmp,"$-\frac{%lld}{%lld}$",-x.fz,x.fm);
else sprintf(tmp,"$\frac{%lld}{%lld}$",x.fz,x.fm);
}
else
{
int r=rand()%4;
if(r==0||r==1)
sprintf(tmp,"$%g$",t);
else if(r==2)
sprintf(tmp,"$%g\%%$",t*100);
else
{
if(x.fz<0)sprintf(tmp,"$-\frac{%lld}{%lld}$",-x.fz,x.fm);
else sprintf(tmp,"$\frac{%lld}{%lld}$",x.fz,x.fm);
}
}
}
}
void dfskh(int u)
{
sd[u]=0;if(yz[u])return;
if(kuoh(u,cl[u]))
{
dfskh(cl[u]);
if(sd[cl[u]]+1>sd[u])sd[u]=sd[cl[u]]+1;
}
else
{
dfskh(cl[u]);
if(sd[cl[u]]>sd[u])sd[u]=sd[cl[u]];
}
if(kuoh(u,cr[u]))
{
dfskh(cr[u]);
if(sd[cr[u]]+1>sd[u])sd[u]=sd[cr[u]]+1;
}
else
{
dfskh(cr[u]);
if(sd[cr[u]]>sd[u])sd[u]=sd[cr[u]];
}
if(sd[u]>2)sd[u]=2;
}
void dfs2(int u)
{
if(yz[u])
{
routfs(sz[u]);
strcat(out,tmp);
return;
}
if(kuoh(u,cl[u]))
{
strcat(out,zk[sd[cl[u]]]);
dfs2(cl[u]);
strcat(out,yk[sd[cl[u]]]);
}
else
dfs2(cl[u]);
strcat(out,fu[fh[u]]);
if(kuoh(u,cr[u]))
{
strcat(out,zk[sd[cr[u]]]);
dfs2(cr[u]);
strcat(out,yk[sd[cr[u]]]);
}
else
dfs2(cr[u]);
}
int su[10002];
SFs getans(int n)
{
out[0]=0;
while(1)
{
sl=0;
int ro=randtree(n);
if(check(ro))
{
dfskh(ro);dfs2(ro);
strcat(out," = ");
return sz[ro];
}
}
}
int main()
{
srand(time(NULL));
int n,m;
printf("题数，符号数，最大分子，最大分母，答案最大分子，答案最大分母：
");
scanf("%d%d%d%d%d%d",&m,&n,&ma,&mb,&mc,&md);
SFs ans[10000];
freopen("题目.txt","w",stdout);
for(int i=1;i<=m;i++)
{
ans[i]=getans(n);
printf("第%d题： ",i);
printf("%s
",out);
}
fclose(stdout);
freopen("答案.txt","w",stdout);
for(int i=1;i<=m;i++)
{
outfs(ans[i]);
printf("第%d题： %s",i,tmp);
double t;bool cg;
t=getxs(ans[i],cg);
if(cg&&mabs(ans[i].fm)!=1)
printf(" 或 $%g$",t);
printf("
");
}
fclose(stdout);
return 0;
}