基於擴展矩陣討論一個問題。擴展矩陣是尺寸以某一因子不斷增加的矩陣。
這裡我們有一個字元矩陣，其尺寸以2的倍數擴展，也就是如果原始矩陣的尺寸是N * N，那麼擴展後的矩陣尺寸變成2N * 2N。我們給出了一個字元序列位於 (i, j) 處，我們需要傳回位於 (i, (j - N - 1)%N) 處的字元序列。
讓我們透過視覺化一些初始擴展矩陣來理解。
Given Matrix -> [ a, b ] [ c, d ], 2 X 2 matrix
Multiplying with { a, b, c, d }
A X [ a, b ]
B X [ a, b ]
C X [ a, b ]
D X [ a, b ]
[ c, d ] [ c, d ] [ c, d ] [ c, d ]
Expanded Matrix -> [ aa, ab, ba, bb ]
[ ac, ad, bc, bd ]
[ ca, cb, da, db ]
[ cc, cd, dc, dd ], 4X4 matrix
To expand again, multiply it by { a, b, c, d } and a matrix of size 8X8 will be formed.
Expanded Matrix - > [ aaa, aab, aba, abb, baa, bab, bba, bbb ]
[ aac, aad, abc, abd, bac, bad, bbc, bbd ]
[ aca, acb, ada, adb, bca, bcb, bda, bdb ]
[ acc, acd, adc, add, bcc, bcd, bdc, bdd ]
[ caa, cab, cba, cbb, daa, dab, dba, dbb ]
[ cac, cad, cbc, cbd, dac, dad, dbc, dbd ]
[ cca, ccb, cda, cdb, dca, dcb, dda, ddb ]
[ ccc, ccd, cdc, cdd, dcc, dcd, ddc, ddd ]這是兩個初始擴展矩陣；假設我們得到了一個字元序列“bcc”，那麼我們需要返回剛剛剩餘的序列，即“add”。另外，假設矩陣是循環的，即如果給定序列位於(i, 0)，則傳回(i, N-1) 處的序列
Input: abb Output: aba Explanation: The sequence just left to abb is aba in the 8X8 matrix. Input: aadc Output: aacd Input: abbcd Output: abbcc
首先考慮問題，想到的唯一解決方案是找到包含給定序列但看起來不是很複雜的擴展矩陣。我們需要先形成矩陣，然後搜尋序列。
在查看了一些最初擴展的矩陣之後，我們發現了一種模式，透過該模式我們可以看到前一個元素。即
從最後一個索引開始遍歷字元序列。
如果索引元素是 ' b'或'd'，然後將其更改為'a'或'c'並停止遍歷數組。
如果索引元素為'a'或'c'， ' 將其變更為 'b' 或 'd' 並移至下一個索引並檢查它。
C 程式碼上述方法
#include <bits/stdc++.h>
using namespace std;
int main (){
string seq = "abbcd";
int n = seq.length ();
// traverse through the string from last.
for (int i = n; i >= 0; i--){
// if the element is b or d, change them and stop traversing.
if (seq[i] == 'b'){
seq[i] = 'a';
break;
}
if (seq[i] == 'd'){
seq[i] = 'c';
break;
}
// if an element is b or d, change them and move to the next element.
if (seq[i] == 'a')
seq[i] = 'b';
else if (seq[i] == 'c')
seq[i] = 'd';
}
cout << "The Previous sequence is: " << seq;
return 0;
}The previous sequence is: abbcc
以上是在一個擴展矩陣中，傳回C++中的前一個元素的詳細內容。更多資訊請關注PHP中文網其他相關文章！
