c++ - 生成直至给定数字N的步进数

如果数字中所有相邻数字的绝对差为1，则该数字称为步进数。
步进数示例：-0,1,2,3,4,5,6,7,8,9,10,12,21,23，…
我必须生成步进数到给定的数字n。生成的数字应该是有序的。
我用了一个简单的方法，把所有的数字移到n，然后检查它是否是步进数。我的老师告诉我这是蛮力，需要更多的时间。现在，我必须优化我的方法。
有什么建议。

最佳答案

步进数可以使用广度优先的类似搜索的方法生成。
示例以查找从0到n的所有步进数
->0是步进数，它在范围内
所以展示一下。
->1是一个步进数，找到1的邻域，即。，
10号和12号，把他们推到队伍里
如何得到10和12？
这里U是1，最后一个数字也是1
V=10+0=10（加上最后一位数字-1）
V=10+2=12（加上最后一位数字+1）
然后对10和12执行同样的操作，这将导致
101，123，121但这些数字超出范围。
现在从10和12转换成的任何数字都将产生
变成一个大于21的数，所以不需要探索
他们的邻居。
->2是一个步进数，找到2的邻居即。
21，23岁。
->生成步进数直到N。
其他步进数是3，4，5，6，7，8，9。
在给定范围内生成步进数的C++代码：

#include<bits/stdc++.h>
using namespace std;

// Prints all stepping numbers reachable from num
// and in range [n, m]
void bfs(int n, int m)
{
    // Queue will contain all the stepping Numbers
    queue<int> q;

    for (int i = 0 ; i <= 9 ; i++)
        q.push(i);

    while (!q.empty())
    {
        // Get the front element and pop from the queue
        int stepNum = q.front();
        q.pop();

        // If the Stepping Number is in the range
        // [n, m] then display
        if (stepNum <= m && stepNum >= n)
            cout << stepNum << " ";

        // If Stepping Number is 0 or greater than m,
        // need to explore the neighbors
        if (stepNum == 0 || stepNum > m)
            continue;

        // Get the last digit of the currently visited
        // Stepping Number
        int lastDigit = stepNum % 10;

        // There can be 2 cases either digit to be
        // appended is lastDigit + 1 or lastDigit - 1
        int stepNumA = stepNum * 10 + (lastDigit- 1);
        int stepNumB = stepNum * 10 + (lastDigit + 1);

        // If lastDigit is 0 then only possible digit
        // after 0 can be 1 for a Stepping Number
        if (lastDigit == 0)
            q.push(stepNumB);

        //If lastDigit is 9 then only possible
        //digit after 9 can be 8 for a Stepping
        //Number
        else if (lastDigit == 9)
            q.push(stepNumA);

        else
        {
            q.push(stepNumA);
            q.push(stepNumB);
        }
    }
}

//Driver program to test above function
int main()
{
    int n = 0, m = 99;

    // Display Stepping Numbers in the
    // range [n,m]
    bfs(n,m);
    return 0;
}

访问link。
上述链接同时具有BFS和DFS方法。
它将为您提供不同语言的解释和代码来解决上述问题。

关于c++ - 生成直至给定数字N的步进数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/57090013/