Ditulis dalam C++, cari sepasang nombor dalam matriks dengan jumlah tertentu

Dalam artikel ini, kita akan membincangkan program untuk mencari pasangan dengan jumlah tertentu dalam matriks tertentu. Contohnya -

Input : matrix[n][m] = { 
   { 4, 6, 4, 65 }, 
   { 56, 1, 12, 32 },
   { 4, 5, 6, 44 },
   { 13, 9, 11, 25 } 
}, SUM = 20

Output : Pair exists.
Explanation : Sum = 20 is equal to the sum of numbers 9 and 11 which exists in the matrix.

Input : matrix[n][m] = { 
   { 5, 7, 3, 45 },  
   { 63, 5, 3, 7 },  
   { 11, 6, 9, 5 },
   { 8, 6, 14, 15 } 
}, SUM = 13
Output : Pair does not exist.
Explanation : No pair exists in the matrix whose sum is equal to 7.

Cara Mencari Penyelesaian

Sekarang kami akan menerangkan dua cara berbeza untuk mencari penyelesaian kepada masalah di atas.

Kaedah Brute Force

Pertimbangkan setiap pasangan dalam matriks yang diberikan, semak sama ada jumlah pasangan itu sama dengan SUM yang diberikan, jika ya, cetak "Pair tidak ada"; . Menggunakan kaedah ini adalah sangat mudah, tetapi ia meningkatkan kerumitan masa kepada O((N*M)2).

Kaedah yang cekap

Atur cara ini boleh menyimpan semua elemen matriks dengan menggunakan cincang, kemudian lelaran melalui matriks dan semak sama ada perbezaan [SUM & (elemen indeks)] adalah sama. Jika ya, cetak "Exist" dan keluar dari program. Jika TIDAK, "tidak wujud" selepas melintasi cetakan.

Contoh

#include <bits/stdc++.h>
using namespace std;

#define n 4
#define m 4

int main() {
   int matrix[n][m] = { 
      { 5,7, 3,45 },
      { 63, 5, 3, 7 },
      { 11, 6, 9, 5 },
      { 8, 6, 14, 15 } 
   };

   int sum = 7;
   unordered_set<int> hash;

   for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
         if (hash.find(sum - matrix[i][j]) != hash.end()) {
            cout << "Pair exists." << endl;
            return 0;
         } else {
            hash.insert(matrix[i][j]);
         }
      }
   }

   cout << "Pair does not exist." << endl;
   return 0;
}

Output

Pair does not exist.

Penerangan kod di atas

• Isytihar tatasusunan dua dimensi dan simpan elemen di dalamnya.
• Lintas tatasusunan untuk mencari jika (jumlah - Matriks[i][j]) != hash.end().
• Jika syarat dipenuhi, cetak "Pair contains" dan kembalikan dari fungsi utama.
• Jika tidak, teruskan merentasi tatasusunan dan akhirnya cetak "Pair does notify.".

Kesimpulan

Dalam artikel ini, kami membincangkan mencari pasangan atau tatasusunan 2D dengan jumlah tertentu dalam matriks kami membincangkan kedua-dua kekerasan dan cara yang cekap untuk menyelesaikan masalah ini. Kami membincangkan program C++ untuk menyelesaikan masalah ini. Walau bagaimanapun, kita boleh menulis program ini dalam mana-mana bahasa lain seperti C, Java, Python, dll. Kami berharap artikel ini dapat membantu anda.

Atas ialah kandungan terperinci Ditulis dalam C++, cari sepasang nombor dalam matriks dengan jumlah tertentu. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!