Scratch编程一级 题库
共 121 道题
,第 7 / 7 页
· 按题型筛选,点「查看答案」核对解析
121
简答题
偏难
42 点
42 是:
· 组合数学上的第 5 个卡特兰数
· 字符'*'的 ASCII 码
· 钼的原子序数
· 6 与 9 的乘积结果的 13 进制表示
· 生命、 宇宙以及任何事情的终极答案
· 以及……表达式(1+5)/2*(6-4)*7 的值
因此, 小机器人 Marvin 发明了这个叫 42 点的小游戏。在这个游戏中,玩家会获得 n 个数。 玩家需要使用'+'、 '-'、 '*'、 '/'、 '('、 ')'以及这 n 个数构成一个合法的中缀表达式, 并使得该表达式的值为 42。 n 个数之间的顺序可以改变。 表达式运算过程中只能出现整数。
由于过于抑郁, Marvin 无力完成这个游戏, 于是来找你帮忙。 你的任务是对于给定的 n 个数, 判断他们是否能根据上述游戏规则算出 42。
时间限制: 1000
内存限制: 65536
输入
第一行为一个数 n, 1<=n<=6。 第二行为 n 个数, 每个数均为[1,13]范围内的整数。
输出
输出一行, 若可以算出 42 则输出“YES”, 否则输出“NO”(注意大小写)。
样例输入
6 1 5 2 6 4 7
样例输出
YES
答案与解析
参考答案
#include <iostream>
using namespace std;
bool dfs(int a[], int n) {
if (n == 1) {
return a[0] == 42;
}
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int b[10];
int m = 0;
for (int k = 0; k < n; ++k) {
if (k == i || k == j)
continue;
b[m++] = a[k];
}
++m;
b[m - 1] = a[i] + a[j];
if (dfs(b, m))
return 1;
b[m - 1] = a[i] - a[j];
if (dfs(b, m))
return 1;
b[m - 1] = a[j] - a[i];
if (dfs(b, m))
return 1;
b[m - 1] = a[i] * a[j];
if (dfs(b, m))
return 1;
if (a[j] != 0)
b[m - 1] = a[i] / a[j];
if (dfs(b, m))
return 1;
if (a[i] != 0)
b[m - 1] = a[j] / a[i];
if (dfs(b, m))
return 1;
}
}
return 0;
}
int main() {
int n;
int a[10];
cin >> n;
for (int i = 0; i < n; ++i)
cin >> a[i];
if (dfs(a, n))
cout << "YES" << endl;
else
cout << "NO" << endl;
system("pause");
return 0;
}