生成直到给定数字 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。提到的 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

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

Generate stepping numbers upto a given number N

c++

c

algorithm

breadth-first-search