列印第 N 個階梯數或自傳數

---

在這個問題中，我們將列印第 N 個階梯數。

解決該問題的樸素方法是遍歷自然數，檢查每個數是否為階梯數，並找到第 N 個階梯數。另一種方法可以使用佇列資料結構。

問題陳述

我們給定一個正整數 N。我們需要列印第 N 個階梯數。如果一個數的兩個相鄰數字之間的差為 1，則該數稱為階梯數。

示例

輸入

N = 15

輸出

34

解釋

階梯數為 1、2、3、4、5、6、7、8、9、10、12、21、23、32、34。因此，第 15 個階梯數是 34。

輸入

N = 2

輸出

2

解釋

1 到 10 位數都是階梯數。

方法 1

在這種方法中，我們將遍歷自然數，直到找到第 N 個階梯數。為了找到階梯數，我們將檢查每個相鄰數字的差。

演算法

• 步驟 1 − 將 p 初始化為 1，並使用迴圈進行遍歷，直到 n 大於 0。

• 步驟 2 − 在迴圈中，透過傳遞 p 作為引數呼叫 checkForStepping() 函式，以檢查 p 是否為階梯數。

• 步驟 2.1 − 在 checkForStepping() 函式中，將 num % 10 的值儲存到表示前一個數字的 p_digit 中。同時，將 num 除以 10。

• 步驟 2.2 − 當 num 大於 0 時進行遍歷。

• 步驟 2.3.1 − 將數字的最後一位數字儲存在 c_digit 變數中。

• 步驟 2.3.2 − 如果 c_digit 和 p_digit 之間的絕對差值不為 1，則返回 false。

• 步驟 2.3.3 − 使用 c_digit 的值更新 p_digit，並將 num 除以 10。

• 步驟 3 − 如果該數字是階梯數，則將 n 的值減 1。

• 步驟 4 − 將 p 的值加 1。

• 步驟 5 − 返回 p – 1，因為在最後一次迭代中，p 加 1。

示例

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

bool checkForStepping(int num) {
   int p_digit = num % 10;
   num /= 10;
   while (num) {
      // Get the current digit
      int c_digit = num % 10;
      // Check the difference between adjacent digits
      if (abs(p_digit - c_digit) != 1)
         return false;
      p_digit = c_digit;
      num /= 10;
   }
   return true;
}
int NthSteppingNumber(int n) {
   int p = 1;
   // Finding N stepping numbers
   while (n > 0) {
      if (checkForStepping(p)) {
         n--;
      }
      p++;
   }
   return p - 1;
}
int main() {
   int N = 15;
   cout << "The Nth Stepping or Autobiographical number is " << NthSteppingNumber(N) << "\n";
   return 0;
}

輸出

The Nth Stepping or Autobiographical number is 34

• 時間複雜度 − O(P)，其中 P 是我們需要遍歷的自然數總數。

• 空間複雜度 − O(1)

方法 2

在這種方法中，我們將使用佇列資料結構來儲存先前的階梯數。之後，我們將透過對先前的階梯數執行乘法、加法和模運算來找到下一個階梯數。

演算法

• 步驟 1 − 定義佇列以儲存先前的數字。另外，定義 temp 整數變數。

• 步驟 2 − 將 1 到 10 的數字插入佇列，因為它們是階梯數。

• 步驟 3 − 現在，使用迴圈進行 N 次遍歷。

• 步驟 3.1 − 從佇列中彈出第一個元素。

• 步驟 3.2 − 如果該數字不能被 10 整除，則將 temp * 10 + temp % 10 − 1 插入佇列。它從當前數字生成一個新的階梯數。例如，如果當前數字是 2，則它生成 21。

• 步驟 3.3 − 如果 temp % 10 不等於 9，則將 temp * 10 + temp % 10 + 1 插入佇列。它從 2 生成 23。

• 步驟 4 − 返回 temp 值。

示例

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

int NthSteppingNumber(int K) {
   queue<int> que;
   int temp;
   // Insert 1 to 9
   for (int p = 1; p < 10; p++)
      que.push(p);
   for (int p = 1; p <= K; p++) {
      temp = que.front();
      que.pop();
      // When the number is not divisible by 10
      if (temp % 10 != 0) {
         que.push(temp * 10 + temp % 10 - 1);
      }
      // When the number doesn't contain 9 as a last digit
      if (temp % 10 != 9) {
         que.push(temp * 10 + temp % 10 + 1);
      }
   }
   return temp;
}
int main() {
   int N = 15;
   cout << "The Nth Stepping or Autobiographical number is " << NthSteppingNumber(N) << "\n";
   return 0;
}

輸出

The Nth Stepping or Autobiographical number is 34

• 時間複雜度 − O(N)

• 空間複雜度 − O(N) 用於在佇列中儲存數字。

結論

在第一種方法中，我們需要進行 P 次遍歷，但在第二種方法中，我們進行的遍歷次數等於 N。當我們需要找到一個很大的階梯數（例如第 10000 個階梯數）時，第一種方法可能會更耗時。