การคูณเมทริกซ์กระจัดกระจายใน C ++

สมมุติว่าเรามีเมทริกซ์ A กับ B สองตัว เราต้องหาผลลัพธ์ของ AB เราอาจถือว่าหมายเลขคอลัมน์ของ A เท่ากับหมายเลขแถวของ B

ดังนั้น ถ้าอินพุตเป็นแบบ [[1,0,0],[-1,0,3]] [[7,0,0],[0,0,0],[0,0,1]] ,

จากนั้นผลลัพธ์จะเป็น [[7,0,0],[-7,0,3]]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• r1 :=ขนาดของ A, r2 :=ขนาดของ B

• c1 :=ขนาดของ A[0], c2 :=ขนาดของ B[0]

• กำหนด 2D array ret ของคำสั่ง r1 x c2

• กำหนดอาร์เรย์ sparseA[r1] ของคู่

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • สำหรับการเริ่มต้น j :=0 เมื่อ j

    • ถ้า A[i, j] ไม่เท่ากับ 0 แล้ว −

      • ใส่ { j, A[i, j] } ที่ส่วนท้ายของ sparseA[i]

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • สำหรับการเริ่มต้น j :=0 เมื่อ j <ขนาดของ sparseA[i] อัปเดต (เพิ่ม j โดย 1) ทำ -

    • สำหรับการเริ่มต้น k :=0 เมื่อ k

      • x :=องค์ประกอบแรกของ sparseA[i, j]

      • ถ้า B[x, k] ไม่เท่ากับ 0 แล้ว −

        • ret[i, k] :=ret[i, k] + องค์ประกอบที่สองของ sparseA[i, j] * B[x, k]

• รีเทิร์น

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

คลาสโซลูชัน {สาธารณะ:vector multiply(vector&A, vector&B) { int r1 =A.size(); int r2 =B.size(); int c1 =A[0].size(); int c2 =B[0].size(); เวกเตอร์ <เวกเตอร์  ret(r1, เวกเตอร์ > sparseA[r1]; for(int i =0; i  
อินพุต
 <ล่วงหน้า>{{1,0,0},{-1,0,3}},{{7,0,0},{0,0,0},{0,0,1}}

ผลลัพธ์

[[7, 0, 0, ],[-7, 0, 3, ],]