需要找出一个密码,密码提示信息: 1. 密码是一个十进制的数(不超过20位,可用long long表示) 2. 由给定的M个数(可重复使用)中的某些构成 3. 是一个给定十进制整数的N的正整数倍 4. 3≤N≤5000,1≤M≤10 5. M个数的输入是无序的,每个数的范围在0-9 6. 密码如果存在,输出最小的那个密码,不存在”So Sorry”(密码不含前导零)
时间: 2024-02-01 12:14:42 浏览: 86
这是一个简单的暴力搜索问题,可以使用深度优先搜索(DFS)来解决。下面是一个示例代码:
```
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
vector<int> nums; // 存储输入的M个数
long long n; // 给定的十进制整数N
bool dfs(long long cur, long long target) {
if (cur % target == 0 && cur / target > 0) { // 如果当前数是目标数的倍数且大于0
cout << cur << endl;
return true;
}
if (cur > target * n) { // 如果当前数已经超过了目标数的n倍
return false;
}
for (int i = 0; i < nums.size(); i++) {
if (cur == 0 && nums[i] == 0) { // 避免前导零
continue;
}
if (dfs(cur * 10 + nums[i], target)) {
return true;
}
}
return false;
}
int main() {
int m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int num;
cin >> num;
nums.push_back(num);
}
sort(nums.begin(), nums.end()); // 将输入的M个数排序,方便后面的搜索
if (!dfs(0, n)) {
cout << "So Sorry" << endl;
}
return 0;
}
```
该程序首先读入给定的十进制整数N和M个数,然后对M个数进行排序。接下来,程序从0开始进行DFS搜索,每次将当前数乘以10并加上M个数中的一个,直到找到一个是目标数N的倍数的数,或者当前数已经超过了N的n倍。如果找到了一个是目标数N的倍数的数,则输出该数,并返回true;否则继续搜索。如果最终都没有找到,则输出"So Sorry"。
阅读全文