C. 凑算式(11分)【蓝桥杯】
具体出处
2016蓝桥杯cpp组
【第七届】【省赛】【B组】
题目描述
本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。
B DEF
A + --- + ------- = 10
C GHI
这个算式中 A ~ I 代表 0 ~ 9 的数字,不同的字母代表不同的数字。
比如: 6+8/3+952/7146+8/3+952/714 就是一种解法, 5+3/1+972/4865+3/1+972/486 是另一种解法。
这个算式一共有多少种解法?
运行限制
最大运行时间:1s
最大运行内存: 128M
AC代码:
做法1:dfs回溯全排列暴力枚举
#include<bits/stdc++.h>
using namespace std;
bool st[15];
int num[15], ans;
void dfs(int n){
if(n==10){
// for(int i = 1; i<=9; ++i)
// cout<<num[i]<<" ";
// cout<<"\n";
int x = num[4] * 100 + num[5] * 10 + num[6];
int y = num[7] * 100 + num[8] * 10 + num[9];
if (num[1] * num[3] * y + num[2] * y + x * num[3] == 10 * num[3] * y){
ans++;
return;
}
}
for(int i = 1; i<=9; ++i){
if(st[i]) continue;
st[i] = 1;
num[n] = i;
dfs(n+1);
st[i] = 0;
}
}
int main(){
dfs(1); //这个1表示第一个位置
cout<<ans;
return 0;
}
做法2:全排列函数next_permutation全排列暴力枚举
#include<bits/stdc++.h>
using namespace std;
int a[9] = {1,2,3,4,5,6,7,8,9};
int b, c, d, e;
int ans;
int main(){
do{
b = a[0]*a[2]*(a[6]*100+a[7]*10+a[8]);
c = a[1]*(a[6]*100+a[7]*10+a[8]);
d = (a[3]*100+a[4]*10+a[5])*a[2];
e = 10*a[2]*(a[6]*100+a[7]*10+a[8]);
if(b+c+d==e) ans++;
}while(next_permutation(a, a+9));
cout<<ans;
return 0;
}