生成直到给定数字 N 的步进数字
Generate stepping numbers upto a given number 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(加上 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 方法。
它将针对上述问题为您提供不同语言的解释和代码。
我们也可以使用简单的规则移动到下一个步进数字并生成它们以避免存储"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
如果一个数中所有相邻数字的绝对差都为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(加上 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 方法。 它将针对上述问题为您提供不同语言的解释和代码。
我们也可以使用简单的规则移动到下一个步进数字并生成它们以避免存储"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