首頁 >後端開發 >C++ >使用C++編寫,將以下內容翻譯為中文:在刪除陣列的一部分後,計算K個陣列的最小公共和

使用C++編寫,將以下內容翻譯為中文:在刪除陣列的一部分後,計算K個陣列的最小公共和

王林
王林轉載
2023-09-12 11:41:07917瀏覽

使用C++編寫,將以下內容翻譯為中文:在刪除陣列的一部分後,計算K個陣列的最小公共和

在使用C 陣列時,我們有時需要計算多個陣列中的最小公共和,同時刪除它們後綴的一部分。在本文中,我們將使用C 來探討這個問題的有效解決方案。

文法

讓我們先分析我們選擇的方法的語法,然後再繼續在我們的程式碼中實現它 -

int findMinimumCommonSum(vector<vector<int>>& arrays, int suffixToRemove);

演算法

這裡是解決刪除部分數組後綴後求最小公和問題的逐步演算法 -

  • 首先定義函數findMinimumCommonSum,該函數接受兩個參數 - arrays,一個表示數組的二維向量,和suffixToRemove,一個表示要從每個數組的後綴中刪除的元素數量的整數。

  • 初始化一個變數minimumSum來儲存最小公共和,並將其初始值設為一個較大的值。

  • 迭代遍歷陣列向量中的每個陣列。

  • 確定目前陣列的大小。

  • 為了避免以空數組結束,應考慮跳過 suffixToRemove 超過或等於目前數組總大小的迭代。在這種情況下刪除所有字元不會產生任何有意義的輸出。

  • 計算從索引 0 到 size - suffixToRemove - 1 的陣列元素總和,並將其儲存在變數 currentSum 中。

  • 如果currentSum小於minimumSum,則使用currentSum的值來更新minimumSum。

  • 遍歷所有陣列後,minimumSum將包含在刪除指定後綴後陣列中的最小公共和。

方法 1:暴力破解

在這個方法中,我們將產生要刪除的後綴的所有可能組合,並計算每個組合的總和。所有組合中最小的和就是最小公和。

範例

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int findMinimumCommonSum(vector<vector<int>>& arrays, int suffixToRemove) {
   int minimumSum = INT_MAX;
   int k = arrays.size();

   for (int i = 0; i < k; i++) {
      int size = arrays[i].size();

      if (suffixToRemove >= size)
         continue;

      vector<bool> suffix(size, false);
      fill(suffix.begin() + size - suffixToRemove, suffix.end(), true);

      do {
         int currentSum = 0;
         
         for (int j = 0; j < k; j++) {
            int arraySum = 0;
            for (int l = 0; l < size; l++) {
               if (!suffix[l])
                  arraySum += arrays[j][l];
            }
            currentSum += arraySum;
         }

         if (currentSum < minimumSum)
            minimumSum = currentSum;

      } while (next_permutation(suffix.begin(), suffix.end()));
   }

   return minimumSum;
}

int main() {
   vector<vector<int>> arrays = {{1, 2, 3},
                                 {4, 5, 6},
                                 {7, 8, 9}};

   int suffixToRemove = 1;

   int minimumCommonSum = findMinimumCommonSum(arrays, suffixToRemove);

   cout << "Minimum Common Sum: " << minimumCommonSum << endl;

   return 0;
}

輸出

Minimum Common Sum: 27

說明

在暴力法中,我們的目標是找到在從它們的後綴中移除指定數量的元素後,多個數組之間的最小公共和。此方法涉及產生所有可能的要移除的後綴的組合,併計算每個組合的和。所有組合中的最小和將是最小公共和。

為了實現這個方法,我們定義了一個名為findMinimumCommonSum 的函數,它接受兩個參數:數組(表示數組的2D 向量)和suffixToRemove(表示要從每個數組後綴中刪除的元素數量的整數)。

在函數內部,我們初始化一個變數minimumSum來儲存最小的公共和,初始值設定為int型別的最大可能值。然後我們遍歷數組向量中的每個數組。對於每個數組,我們確定其大小並檢查suffixToRemove值是否小於大小。

如果條件滿足,我們使用布林向量產生所有可能的後綴組合。我們將最後suffixToRemove個元素填入true,其餘元素填入false。對於每個數組,我們確定其大小,並檢查suffixToRemove值是否小於大小。

我們透過計算與後綴向量中的假指示符對應的陣列值的總和來進行處理,對於每個組合。我們針對所有陣列重複此過程,相應地更新currentSum。

最後,我們將currentSum與minimumSum進行比較,如果currentSum較小,則更新minimumSum。在遍歷所有陣列和組合之後,minimumSum將包含在刪除指定後綴後的最小公共和。

方法2:高效排序

在這個方法中,我們將按非遞減順序對陣列進行排序,併計算每個陣列的前size - suffixToRemove個元素的總和。所有數組中的最小總和將是最小公共總和。

範例

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int findMinimumCommonSum(vector<vector<int>>& arrays, int suffixToRemove) {
   int minimumSum = INT_MAX;
   int k = arrays.size();

   for (int i = 0; i < k; i++) {
      int size = arrays[i].size();

      if (suffixToRemove >= size)
         continue;

      sort(arrays[i].begin(), arrays[i].end());

      int currentSum = 0;
      for (int j = 0; j < size - suffixToRemove; j++)
         currentSum += arrays[i][j];

      if (currentSum < minimumSum)
         minimumSum = currentSum;
   }

   return minimumSum;
}

int main() {
   vector<vector<int>> arrays = {{1, 2, 3},
                                 {4, 5, 6},
                                 {7, 8, 9}};

   int suffixToRemove = 1;

   int minimumCommonSum = findMinimumCommonSum(arrays, suffixToRemove);

   cout << "Minimum Common Sum: " << minimumCommonSum << endl;
   
   return 0;
}

輸出

Minimum Common Sum: 3

說明

在高效排序方法中,我們的目標是在從後綴中刪除指定數量的元素後找到多個陣列之間的最小公和。這種方法利用了這樣一個事實:對陣列進行排序可以簡化最小和的計算。

為了實現這個方法,我們定義了一個名為findMinimumCommonSum 的函數,它接受兩個參數:數組(表示數組的2D 向量)和suffixToRemove(表示要從每個數組後綴中刪除的元素數量的整數)。

在函數內部,我們初始化一個變數minimumSum來儲存最小的公共和,初始值設定為int型別的最大可能值。然後我們遍歷數組向量中的每個數組。對於每個數組,我們確定其大小並檢查suffixToRemove值是否小於大小。

當滿足了這個先決條件後,我們的下一步之一將是按升序排列我們數組中的所有個別組件;這種方法主要有助於確保較小的對象位於其初始部分,以提高排列和可讀性。

接下來,我們計算排序數組中前 size - suffixToRemove 個元素的和。這對應於從後綴中刪除指定數量的元素。我們相應地更新 currentSum。

最後,我們將currentSum與minimumSum進行比較,如果currentSum較小,則更新minimumSum。在遍歷所有陣列之後,minimumSum將包含在刪除指定後綴後的最小公共和。

這種方法非常高效,因為它不需要像暴力方法那樣產生和迭代所有可能的組合。相反,它利用排序屬性來簡化最小和的計算,從而提高效能。

結論

在本文中,我們探討了一種在C 中找到K個陣列中最小公共和的高效方法,該方法在刪除它們的後綴的一部分後進行。我們討論了兩種方法-暴力法和高效排序法。暴力法涉及產生所有後綴的組合,而高效排序法對數組進行排序併計算前幾個元素的和。根據數組的大小和要刪除的後綴元素的數量,高效排序法通常更有效率。透過在C 程式中實作這些方法,您可以輕鬆地從多個陣列中找到最小的公共和,並且能夠有效地處理後綴的刪除。

以上是使用C++編寫,將以下內容翻譯為中文:在刪除陣列的一部分後,計算K個陣列的最小公共和的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文轉載於:tutorialspoint.com。如有侵權,請聯絡admin@php.cn刪除