C++程式：用行或列的最大公約數替換矩陣的每個元素

在這個方法中，我們需要用給定矩陣中每一行和每一列的最大公約數(GCD)來替換矩陣中的每個元素。

讓我們看一些輸入場景 -

假設我們得到一個m*n維的二維矩陣：

Input:
[[3, 2, 1, 4]
[7, 6, 2, 8]
[14, 20, 25, 17]];

在上面的矩陣中，第1行 gcd(3, 2, 1, 4) = 1，第2列 gcd(3, 7, 14) = 1。所以元素2（第1行第2列）變為最大值(1, 1) = 1。對所有元素依次執行此操作，我們的輸出結果應該變為

Result: [
   [1, 2, 1, 1]
   [1, 2, 1, 1]
   [1, 2, 1, 1]
]

再來看一個m*n維的二維矩陣：

Input:
[[3, 2, 5, 4]
[6, 6, 15, 8]
[12, 20, 25, 16]];

在上面的矩陣中，第1行 gcd(3, 2, 5, 4) = 1，第2列 gcd(2, 6, 20) = 2。所以元素2（第1行第2列）變為最大值(1, 2) = 2。對所有元素重複此過程，我們的輸出將是 -

Result: [
  [3 2 5 4]
  [3 2 5 4]
  [3 2 5 4]
]

演算法

  • 聲明瞭兩個函式 GCDArrayRow 和 GCDArrayColumn，分別用於查詢行和列中元素的最大公約數。

  • 找到第 i 行和第 j 列的最大公約數，以替換 matrix[i, j] 元素。

  • 對矩陣中的每個元素重複此過程，更新後的矩陣作為輸出結果列印。

示例

以下是用 C++ 實現的替換矩陣每個元素為行或列最大公約數的示例 -

在這個程式中，我們可以建立兩個陣列，稱為GCDArrayRow 和GCDArrayColumn，分別儲存各行和各列的公約數。在儲存所有行和列的公約數後，我們可以遍歷陣列並逐個計算每個元素的最大值。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void solve(vector<vector<int>>& arr) {
   vector<int> GCDArrayRow(arr.size(), 0), GCDArrayColumn(arr[0].size(), 0);
   for(int i=0;i<arr.size();i++) {
      for(int j=0;j<arr[i].size();j++) {
         GCDArrayRow[i] = __gcd(GCDArrayRow[i], arr[i][j]);
         GCDArrayColumn[j] = __gcd(GCDArrayColumn[j], arr[i][j]);
      }
   }
   for(int i=0;i<arr.size();i++) {
      for(int j=0;j<arr[i].size();j++) {
         arr[i][j] = max(GCDArrayColumn[j], GCDArrayRow[i]);
      }
   }
}
void printArray(vector<vector<int>>& arr) {
   for(int i=0;i<arr.size();i++) {
      for(int j=0;j<arr[i].size();j++) {
         cout << arr[i][j] << " ";
      }
      cout << "\n";
   }
   cout << "\n";
}
int main() {
   vector<vector<int>> arr = {
      {2, 6, 4, 8},
      {4, 6, 3, 9},
      {7, 21, 28, 7}
   };
   printArray(arr);
   solve(arr);
   printArray(arr);
   return 0;
}

輸出

2 6 4 8
4 6 3 9
7 21 28 7


2 3 2 2
1 3 1 1
7 7 7 7

結論

因此，我們可以觀察到，建立額外的行和列陣列可以幫我們完成工作。我們預先計算每行和每列的 GCD，然後遍歷並查詢兩者的最大值。演算法庫在 GCD 的內建函式 __gcd 函式中計算 GCD。我們也可以根據歐幾里得演算法編寫我們自己的 GCD 計算函式。

更新於: 2022年8月10日

392 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告

© . All rights reserved.