C ++ ส่งคืนองค์ประกอบก่อนหน้าในเมทริกซ์ขยาย

อภิปรายปัญหาตามการขยายเมทริกซ์ เมทริกซ์การขยายคือเมทริกซ์ที่มีขนาดเพิ่มขึ้นอย่างต่อเนื่องโดยปัจจัยบางอย่าง

ในที่นี้ เรามีเมทริกซ์ของอักขระที่มีขนาดขยายด้วยปัจจัย 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++ สำหรับปัญหานี้ ซึ่งเราสามารถเขียนในภาษาการเขียนโปรแกรมใดๆ เช่น C, Java, Python เป็นต้น เราหวังว่าคุณจะพบว่าบทช่วยสอนนี้มีประโยชน์