อภิปรายปัญหาที่เกี่ยวกับการขยายเมทริกซ์ (Expanding matrix) เมทริกซ์ที่ขยายตัวคือเมทริกซ์ที่ขนาดเพิ่มขึ้นอย่างต่อเนื่องโดยปัจจัยบางอย่าง
ที่นี่เรามีเมทริกซ์ของตัวอักษรที่ขนาดขยายตัวด้วยปัจจัย 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 ] ...
นี่คือเมทริกซ์ที่ขยายตัวสองตัวแรก ดังนั้นถ้าเราได้รับลำดับตัวอักษร "bcc" เราต้องคืนค่าลำดับที่อยู่ทางซ้ายมือของมัน คือ "add" นอกจากนี้ เมทริกซ์ถูกสมมติว่าเป็นวงกลม คือ ถ้าลำดับที่กำหนดอยู่ที่ (i, 0) ให้คืนค่าลำดับที่ (i, N-1) ตัวอย่างเช่น:
Input: abb Output: aba คำอธิบาย: ลำดับที่อยู่ทางซ้ายของ abb คือ aba ในเมทริกซ์ 8X8 Input: aadc Output: aacd Input: abbcd Output: abbcc
วิธีการหาคำตอบ
มองปัญหาแรกและวิธีแก้ที่คิดได้คือ หาเมทริกซ์ที่ขยายตัวซึ่งมีลำดับที่กำหนด แต่ดูไม่ซับซอนมาก เราต้องสร้างเมทริกซ์ก่อนแล้วค่อยค้นหาลำดับ
วิธีที่มีประสิทธิภาพ (Efficient Approach)
หลังจากมองเมทริกซ์ที่ขยายตัวบางส่วน เราพบรูปแบบที่ผ่านซึ่งเราสามารถเห็นองค์ประกอบก่อนหน้าได้ คือ:
- เดินทางผ่านลำดับตัวอักษรจากดัชนีสุดท้าย
- ถ้าองค์ประกอบที่ดัชนีนั้นคือ '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();
// เดินทางผ่านสตริงจากท้าย
for (int i = n; i >= 0; i--) {
// ถ้าองค์ประกอบเป็น b หรือ d ให้เปลี่ยนและหยุดเดินทาง
if (seq[i] == 'b') {
seq[i] = 'a';
break;
}
if (seq[i] == 'd') {
seq[i] = 'c';
break;
}
// ถ้าองค์ประกอบเป็น a หรือ c ให้เปลี่ยนและไปยังองค์ประกอบถัดไป
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++ สำหรับปัญหานี้ซึ่งเราสามารถเขียนในภาษาโปรแกรมใดๆ เช่น C, Java, Python ฯลฯ ได้ เราหวังว่าบทช่วยสอนนี้จะเป็นประโยชน์
