首頁 > 後端開發 > C++ > 主體

使用C++根據給定條件拆分給定的二進位字串,以最大化和

PHPz
發布: 2023-09-04 10:21:07
轉載
953 人瀏覽過

使用C++根據給定條件拆分給定的二進位字串,以最大化和

本文旨在解決一個複雜的演算法問題,涉及以最大化從各個元件獲得的累積和的方式分割二進位字串。我們將為讀者提供用於實現程式碼的全面語法大綱,並建議兩種可能的技術來克服這項挑戰。此外,我們將基於上述方法展示兩個真正的完整可執行程式碼。

文法

在深入研究演算法之前,至關重要的是,我們必須熟悉我們將透過即將發布的程式碼範例展示的指定方法的結構。此方法採用二進位字串作為輸入,並透過使用預定條件對所述輸入進行分區來計算其最高可能值。下面說明了這種方法在語法方面的外觀 -

int maximizeSum(string binaryString) {
   // Implementation of the algorithm goes here
}
登入後複製

演算法

現在我們應該討論逐步演算法,以解決透過拆分二進位字串來最大化總和的問題。

程式碼片段 1

  • 初始化兩個變數“maxSum”和“currentSum”,都設定為零。

  • 從左到右遍歷二進位字串。

  • 對於字串中的每個字元 -

    • 如果字元是'0',則將其新增至目前子字串。

    • 如果字元是'1' −

      #
      • 透過新增目前的「currentSum」來更新「maxSum」。

      • 將`currentSum`重設為零。

  • 遍歷結束後,將最終的「currentSum」與「maxSum」相加。

  • 傳回 `maxSum` 作為結果。

方法一

解決此問題的第一種方法涉及實作上述演算法。讓我們看看對應的程式碼片段 -

範例

#include <iostream>
#include <string>
using namespace std;

int maximizeSum(string binaryString) {
   int maxSum = 0;
   int currentSum = 0;

   for (char c : binaryString) {
      if (c == '0') {
         currentSum = currentSum * 10 + (c - '0');
      } else {
         maxSum += currentSum;
         currentSum = 0;
      }
   }

   maxSum += currentSum;
   return maxSum;
}

int main() {
   string binaryString = "1001101001";
    
   int result = maximizeSum(binaryString);
   cout << "Maximum sum: " << result << endl;

   return 0;
}
登入後複製

輸出

Maximum sum: 0
登入後複製
登入後複製

說明

  • 為了方便起見,程式碼首先包含必要的函式庫(“iostream”和“string”)並使用“std”命名空間。

  • 要計算透過拆分二進位字串可實現的最大和,可以使用 `maximizeSum` 函數,該函數以二進位字串作為輸入並傳回輸出。

  • 在這個函數內部初始化了兩個變數 - `maxSum` 和 `currentSum`。前者追蹤到目前為止達到的最大值,而後者計算每個單獨子字串的總和。

  • 使用基於範圍的 for 迴圈我們迭代輸入「binaryString」中的每個字元「c」。

  • 如果目前字元“c”是“0”,我們將其乘以 10 並加上數值“0”來更新“currentSum”。這有效地將“0”附加到目前子字串。

  • 如果目前字元“c”為“1”,則表示目前子字串結束。我們將 `currentSum` 新增至 `maxSum` 以更新迄今為止達到的最大總和,然後將 `currentSum` 重設為零以開始新的子字串。

  • 完成循環後,透過將最後一個子字串的`currentSum`加到前一個`maxSum`中來計算。 `main`函數提供了一個提示,允許使用者輸入一個二進位字串。

  • 「main」函數提供一個提示,允許使用者輸入二進位字串。

  • 輸入字串被傳遞給`maximizeSum`函數,並將傳回的最大和儲存在`result`變數中。

  • 最後,將最大總和顯示給使用者。

方法2

在第二種方法中,我們將透過消除執行整數乘法的需要來優化程式碼。相反,我們將使用位元運算來計算當前總和。讓我們來看看這種方法的程式碼片段 -

範例

#include <iostream>
#include <string>
using namespace std;

int maximizeSum(string binaryString) {
   int maxSum = 0;
   int currentSum = 0;

   for (char c : binaryString) {
      if (c == '0') {
         currentSum = (currentSum << 1) + 0;
      } else {
         maxSum += currentSum;
         currentSum = 0;
      }
   }

   maxSum += currentSum;
   return maxSum;
}

int main() {
   string binaryString = "10110010"; // Assumed binary string
   int result = maximizeSum(binaryString);
   cout << "Maximum sum: " << result << endl;

   return 0;
}
登入後複製

輸出

Maximum sum: 0
登入後複製
登入後複製

說明

  • 與第一種方法類似,程式碼首先包含必要的函式庫,並使用 `std` 命名空間。

  • 函數`maximizeSum`和函數`main`的定義與第一種方法中的定義相同。

  • 在`maximizeSum`函數中,使用位元左移運算子(`

  • #相當於乘以 2。然後我們將 0 新增到 `currentSum` 中,因為目前字元是「0」。

  • 兩種方法中其餘的程式碼是相同的。它們接收一個二進位字串作為輸入。使用`maximizeSum`函數來計算分割字串時可能的最大和。然後將這個結果呈現給使用者。

您可以在C 編譯器中編譯並執行這些程式碼,當輸入一個二進位字串時,程式將輸出根據指定條件分割該字串所獲得的最大和。

結論

在本文中,我們探討了根據給定條件分割二進位字串來最大化總和的問題。我們提供了程式碼範例中使用的方法的語法,並提出了兩種解決問題的方法。最初,採用直接演算法,而以下技術透過位元運算優化編碼。儘管這兩種方法都成功地解決了這個問題,但後者提供了更高的效率,因為它消除了整數乘法的必要性。透過理解和實現這些演算法,您可以有效地解決涉及透過拆分二進位字串來最大化總和的類似問題。

以上是使用C++根據給定條件拆分給定的二進位字串,以最大化和的詳細內容。更多資訊請關注PHP中文網其他相關文章!

相關標籤:
來源:tutorialspoint.com
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板