生成步进数，直到给定的数N

Question

如果一个数字中的所有相邻数字的绝对差值为1，则该数字称为步进数字。

步数示例:- 0,1,2,3,4,5,6,7,8,9,10,12,21,23，...

我必须生成步进数，直到给定的数N。生成的数应该是有序的。

我使用了一种简单的方法，将所有数字移动到N，并检查它是否是步进数字。我的老师告诉我这是一种暴力行为，需要更多的时间。现在，我必须优化我的方法。

有什么建议吗。

Answer 1

步数可以使用类似广度优先搜索的方法生成。

查找从0到N的所有步数的示例

-> 0是一个步进数字，它在范围内，因此请显示它。-> 1是一个步进号，找到1的邻居，即10和12，并将它们推入队列

如何得到10和12？

这里U是1，最后一个数字也是1

V= 10 +0= 10 (添加lastDigit -1)

V= 10 +2= 12 (加上lastDigit +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两种方法。它将为您提供上述问题的解释和不同语言的代码。

Answer 2

我们也可以使用简单的规则来移动到下一个步进编号并生成它们，以避免存储"parents“。

C.f.OEIS sequence

#include <iostream>

int next_stepping(int n) {
    int left = n / 10;
    if (left == 0)
        return (n + 1);   // 6=>7

    int last = n % 10;
    int leftlast = left % 10;
    if (leftlast - last == 1 & last < 8)
        return (n + 2);   // 32=>34

    int nxt = next_stepping(left);
    int nxtlast = nxt % 10;
    if (nxtlast == 0)
        return (nxt * 10 + 1);  // to get 101

    return (nxt * 10 + nxtlast - 1);   //to get 121
}

int main()
{
    int t = 0;
    for (int i = 1; i < 126; i++, t = next_stepping(t)) {
        std::cout << t << "\t";
        if (i % 10 == 0)
            std::cout << "\n";
    }
}

0       1       2       3       4       5       6       7       8       9
10      12      21      23      32      34      43      45      54      56
65      67      76      78      87      89      98      101     121     123
210     212     232     234     321     323     343     345     432     434
454     456     543     545     565     567     654     656     676     678
765     767     787     789     876     878     898     987     989     1010
1012    1210    1212    1232    1234    2101    2121    2123    2321    2323
2343    2345    3210    3212    3232    3234    3432    3434    3454    3456
4321    4323    4343    4345    4543    4545    4565    4567    5432    5434
5454    5456    5654    5656    5676    5678    6543    6545    6565    6567
6765    6767    6787    6789    7654    7656    7676    7678    7876    7878
7898    8765    8767    8787    8789    8987    8989    9876    9878    9898
10101   10121   10123   12101   12121