用C++写倍数问题(利用分支限界实现):给出一个自然数N(0~4999,包括0和4999)和M个不同的十进制数字X1,X2,…,Xm(至少一个数)。找出由数字X1,X2,…,Xm构成的正整数,是N的最小倍数。每组数据之间有一个空行,数据格式如下: 第一行:数字N 第二行:数字M 接下来M行:数字X1,X2,…,Xm。 对每组测试数据,假如存在此数,则直接输出该数,占一行;否则输出0的代码。
时间: 2024-03-02 09:48:21 浏览: 291
好的,以下是用C++实现的倍数问题的代码:
```c++
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
// 定义状态类
struct Node {
int num; // 当前构造的数字
int mod; // 当前数字对N取余的余数
};
// 定义状态比较函数
bool operator<(const Node& a, const Node& b) {
return a.num > b.num; // 为了让小的节点先出队
}
int main() {
int N, M, X[10];
while (cin >> N >> M) {
for (int i = 0; i < M; i++) {
cin >> X[i];
}
// 初始化队列
priority_queue<Node> que;
for (int i = 0; i < M; i++) {
que.push({X[i], X[i] % N});
}
// 开始分支限界
int ans = 0;
bool vis[5000];
memset(vis, false, sizeof(vis));
while (!que.empty()) {
Node u = que.top();
que.pop();
if (vis[u.mod]) {
continue;
}
vis[u.mod] = true;
if (u.num % N == 0) {
ans = u.num;
break;
}
for (int i = 0; i < M; i++) {
Node v = {u.num * 10 + X[i], (u.mod * 10 + X[i]) % N};
que.push(v);
}
}
// 输出答案
cout << ans << endl;
}
return 0;
}
```
这个代码和前面的Python代码类似,只不过语法略有不同。首先定义了一个状态结构体`Node`,表示当前构造的数字和它对N取余的余数。然后读入数据,初始化队列,将每个数字X都作为起点加入队列。
接下来就是分支限界的过程。每次取出队首元素u,如果它的余数对应的状态已经被访问过,那么直接跳过。否则,标记这个状态已经被访问过,如果当前数字是N的倍数,那么更新答案并退出循环。否则,枚举下一个数字i,构造新的状态v,并将它加入队列。
最后,输出答案即可。
希望这个代码能够帮助你解决问题!
阅读全文