广度优先遍历算法

Question

对于给定的 n，我试图找到能被 n 整除的最小数字，并且数字总和为 n。

例如：对于 n = 10，输出应为 190，对于 n = 11，输出应为 209

我采用了广度优先遍历法来解决我的问题。

#include <iostream> 
#include <queue>
#include <string>
using namespace std;

class State{
    public:
        int sum,rem;
        string str;
        State(int s,int r,string st){
            sum = s;
            rem = r;
            str = st;
        }
};

int main() {
    int n,newSum,newRem;
    queue<State> q;
    cin>>n;
    bool visited[n+1][n+1] = {0};
    State curr = State(0,0,"");
    q.push(curr);
    visited[0][0] = 1;
    while(!q.empty()){
        curr = q.front();
        q.pop();
        if(curr.sum==n && curr.rem==0){
            cout<<curr.str<<endl;
            break;
        }
        for(int j=0; j<=9; j++){
            newSum = curr.sum + j;
            newRem = (curr.rem*10+j)%n;

            if(newSum > n){
                break;
            }

            else if(!visited[newSum][newRem]){
                curr = State(curr.sum+j, ((curr.rem*10)+j)%n,curr.str+to_string(j));
                q.push(curr);
                visited[newSum][newRem] = 1;
            }
        }
    }
    return 0;
}

我的代码，returns一个满足条件的数，但不是最小的数。对于 n = 10，我的代码给出 12340 对于 n = 11，我的代码给出 1010207

Ideone link: http://ideone.com/c4W48N

Answer 1

您应该尝试运行通过调试器，它会很快显示问题。

这一行：

curr = State(curr.sum+j, ((curr.rem*10)+j)%n,curr.str+to_string(j));
q.push(curr);

您正在为 curr 变量分配一个新值，您将在下一次循环中使用它。这意味着您尝试的不是 1、2、3 等，而是 1、12、123 等

您也在重新计算刚刚计算的项目。

您可以将其替换为

State newState = State(newSum, newRem, curr.str + to_string(j));
q.push(newState);

或更简单：

q.push(State(newSum, newRem, curr.str+to_string(j)));

广度优先遍历算法

Breadth First Traversal Algorithm

c++

breadth-first-search