当前位置 博文首页 > 爱新觉罗?炒饭的博客:2016年第七届蓝桥杯省赛(C/C++ A组) 第六
解答一:
nclude<iostream>
#include<cmath>
using namespace std;
int a[14]={0,1,2,3,4,5,6,7,8,9,10,11,12,13};
int ans=0;
void judge()
{
if(a[1]+a[2]==a[3])
{
if(a[4]-a[5]==a[6])
{
if(a[7]*a[8]==a[9])
{
if(a[10]==a[11]*a[12])
ans++;
}
}
}
}
void dfs(int begin,int end,int ar[])
{
if(begin==end)
{
judge();
}
else
{
for(int i=begin;i<=end;i++)
{
swap(ar[i],ar[end]);
dfs(begin,end-1,a);
swap(ar[i],ar[end]);
}
}
}
int main()
{
dfs(1,13,a);
cout<<ans<<endl;
return 0;
}
解答二:
#include<iostream>
#include<cmath>
using namespace std;
int ans=0;
bool visit[15];
int a[15];
void dfs(int n)
{
if(n==3)
{
if(a[1]+a[2]<=13&&!visit[a[1]+a[2]])
{
visit[a[1]+a[2]]=true;
dfs(4);
visit[a[1]+a[2]]=false;
}
return;
}
if(n==6)
{
if(a[4]+a[5]<=13&&!visit[a[4]+a[5]])
{
visit[a[4]+a[5]]=true;
dfs(7);
visit[a[4]+a[5]]=false;
}
return;
}
if(n==9)
{
if(a[7]*a[8]<=13&&!visit[a[7]*a[8]])
{
visit[a[7]*a[8]]=true;
dfs(10);
visit[a[7]*a[8]]=false;
}
return;
}
if(n==12)
{
if(a[10]/a[11]<=13&&a[10]%a[11]==0&&!visit[a[10]/a[11]])
ans++;
return;
}
for(int i=1;i<=13;i++)
{
if(!visit[i])
{
visit[i]=true;
a[n]=i;
dfs(n+1);
visit[i]=false;
}
}
}
int main()
{
dfs(1);
cout<<ans<<endl;
return 0;
}
解答一用时很长才能出答案,解答二用时很短。
解答二是dfs+剪枝