資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學N位階梯數的個數 - 空間最佳化方案
在本文中，我們將學習階梯數。我們將使用多種C++技術來查詢也是階梯數的N位數的可能個數。我們還將討論最節省空間的解決方案。
讓我們首先討論階梯數。這些數字的相鄰數字之間的差為1。例如，321 - 每個相鄰數字 (3, 2, 1) 的差都連續為1。
在這裡，我們將給出N的值，然後我們必須找到所有N位階梯數的個數。
輸入輸出場景
給定N，輸出為N位階梯數的個數。
Input: N = 3 Output: 32 Input: N = 4 Output: 61
對於N = 3，可能的階梯數是32。這些數字是101、121、123、210、212、232、234、321等等。
使用迭代
我們將迭代所有N位數，並檢查它們是否是階梯數。
首先，我們建立一個名為steppingNumber的函式，用於檢查一個數是否是階梯數。這是一個布林函式，所以它返回true或false。
在這個函式中，我們使用to_string()將數字轉換為字串。然後，我們迭代所有數字，並找到每個數字之間的差。如果差值不為1，則返回false。否則，結果為true。
接下來，我們建立函式來計算階梯數。在這個函式中，我們從第一個N位數迭代到最後一個N位數。對於每個數字，我們應用steppingNumber函式。如果函式返回true，則變數count加1。
示例
讓我們看一個例子：
#include <iostream>
#include <cmath>
using namespace std;
bool steppingNumber(int i) {
string numStr = to_string(i);
for (int j = 1; j < numStr.length(); j++) {
int diff = abs(numStr[j] - numStr[j - 1]);
if (diff != 1) {
return false;
}
}
return true;
}
int possibleNumbers(int N) {
int begin = pow(10, N - 1);
int end = pow(10, N) - 1;
int count = 0;
for (int i = begin; i <= end; i++) {
if (steppingNumber(i)) {
count++;
}
}
return count;
}
int main() {
int N = 3;
cout << "Number of " << N << " digit stepping numbers are " <<
possibleNumbers(N);
return 0;
}
輸出
Number of 3 digit stepping numbers are 32
注意 - 這種方法非常簡單，效率不高。它會進行冗餘計算，並且耗時更長。
使用空間最佳化方法
在這裡，我們使用這樣一個概念：在階梯數中，每個數字都比前一個數字大1或小1。
我們有兩個陣列，它們分別儲存N位階梯數和(N – 1)位階梯數的個數。
我們從2迴圈到N。在這個迴圈中，我們執行兩個for迴圈，每個迴圈從0到9（因為數字可以在0-9之間）。對於每個數字，我們使用currentCount陣列的值更新previousCount陣列的值。
如果(k > 0)，我們將previousCount[k – 1]的值新增到currentCount陣列。這是因為如果第一個數字等於(k – 1)，則將1加到(N – 1)位數字的第一個數字會得到N位階梯數。
如果(k < 9)，我們將previousCount[k + 1]的值新增到currentCount陣列。這是因為如果第一個數字等於(k + 1)，則將1加到(N – 1)位數字的第一個數字會得到N位階梯數。
接下來，我們新增currentCount陣列的值之和。
示例
以下是一個例子：
#include <iostream>
using namespace std;
int possibleNumbers(int N) {
int previousCount[10] = {0};
int currentCount[10] = {1, 1, 1, 1, 1, 1, 1 ,1, 1, 1};
for (int j = 2; j <= N; ++j) {
for (int k = 0; k <= 9; ++k) {
previousCount[k] = currentCount[k];
currentCount[k] = 0;
}
for (int k = 0; k <= 9; ++k) {
if (k > 0)
currentCount[k] += previousCount[k - 1];
if (k < 9)
currentCount[k] += previousCount[k + 1];
}
}
int count = 0;
for (int k = 1; k <= 9; ++k) {
count += currentCount[k];
}
return count;
}
int main() {
int N = 5;
cout << "Number of " << N << " digit stepping numbers are " <<
possibleNumbers(N);
return 0;
}
輸出
Number of 5 digit stepping numbers are 116
使用動態規劃方法
我們將使用單個一維陣列來儲存計算結果，而不是使用兩個一維陣列（如前面的方法）。
示例
#include <iostream>
#include <vector>
using namespace std;
long long possibleNumbers(int N){
vector<long long> dp(10, 1);
if (N == 1)
return 10;
for (int i = 2; i <= N; i++) {
vector<long long> new_dp(10, 0);
new_dp[0] = dp[1];
new_dp[9] = dp[8];
for (int j = 1; j <= 8; j++)
new_dp[j] = dp[j - 1] + dp[j + 1];
dp = new_dp;
}
long long totalCount = 0;
for (int j = 1; j <= 9; j++)
totalCount += dp[j];
return totalCount;
}
int main(){
int N = 4;
cout << "Number of " << N << " digit stepping numbers are " <<
possibleNumbers(N);
return 0;
}
輸出
Number of 4 digit stepping numbers are 61
結論
我們討論了查詢N位階梯數個數的不同方法。第一種方法是使用迭代的簡單方法。第二種方法使用兩個一維陣列來儲存計算結果，是一種空間最佳化的方案。在第三種方法中，我們使用單個一維陣列代替兩個這樣的陣列，這使得程式碼效率更高。
瀏覽量：122
