透過交換相鄰數字（差值為奇數）來最小化給定數字

---

本文旨在實現一個程式，透過交換相鄰數字（差值為奇數）來最小化給定數字。

目標是確定僅使用字元“1”、“2”和“3”透過任意次數交換相鄰字元，從表示整數的長度為 N 的字串中可以建立的最小值。

眾所周知，在 C 語言程式設計中，字串是一組以空字元“\0”結尾的字元。C 字串中的字元儲存在一個字元陣列中。C 字串與字元陣列的區別在於它以特殊的字元“\0”結尾。

示例 1

Let the Input string be,
S = “211323”
Output obtained here is: 112233

示例 2

Let the Input string be,
S = “112323”
Output obtained here is: 112233

示例 3

Let the Input string be,
S = “231213”
Output obtained here is: 223113

示例 4

Let the Input string be,
S = “123123”
Output obtained here is: 122313

問題陳述

實現一個程式，透過交換相鄰數字（差值為奇數）來最小化給定數字

方法

解決這個問題並獲得一個程式來最小化給定數字的方法，該程式透過交換相鄰數字（差值為奇數）來實現。

透過以下見解，可以使用貪心演算法來解決這個問題：

貪心演算法究竟是什麼？

貪心演算法逐段構建解決方案，始終選擇提供最明顯和直接好處的元件作為下一步。因此，貪心演算法非常適合於選擇區域性最優解也能導致全域性最優解的問題。

在這種情況下，由於 1 和 3 之間的差是 2（偶數），因此它們不能交換。

由於 1 和 2 之間的差是 1（奇數），因此 2 和 3 之間的差也是如此。

由於 1 和 2 之間的差是 1（奇數），因此 2 和 3 之間的差也是如此。

演算法

下面給出了實現程式的演算法，該程式透過交換相鄰數字（差值為奇數）來最小化給定數字

• 步驟 1 - 定義一個函式來交換相鄰數字（如果差值為奇數），以獲得與給定字串匹配的最小數字。

• 步驟 2 - 查詢給定字串的長度

• 步驟 3 - 宣告一個整型變數來儲存 3 的第一次出現位置

• 步驟 4 - 宣告變數來跟蹤字串中 2 的總數和第一個 3 之前的 1 的計數

• 步驟 5 - 現在，遍歷字串時，計算第一個 3 之前的 1 的數量和 2 的總數。

• 步驟 6 - 將第一個 3 出現之前的所有 1 都新增到結果中

• 步驟 7 - 將每個 2 都新增到結果中

• 步驟 8 - 將剩餘的 3 和 1 以與給定字串相同的順序新增到結果中

• 步驟 9 - 最後，列印輸出結果。

示例：C 程式

以下是上述演算法的 C 語言程式實現，該程式透過交換相鄰數字（差值為奇數）來最小化給定數字

#include <stdio.h>
#include <string.h>
void findMinimumString(char S[]){
   int N = strlen(S);
   int pos = -1;
   int count1 = 0, count2 = 0;
   for (int i = 0; i < N; i++) {
      if (pos == -1 && S[i] == '1')
         count1++;
      else if (pos == -1 && S[i] == '3')
         pos = i;
      else if (S[i] == '2')
         count2++;
   }
   while (count1--)
      printf("1");
   while (count2--)
      printf("2");
   if (pos != -1) {
      while (pos < N) {
         if (S[pos] != '2')
            printf("%c", S[pos]);
         pos++;
      }
   }
}
int main(){
   char S[] = "211323";
   findMinimumString(S);
   return 0;
}

輸出

112233

結論

同樣，我們可以得到一個程式，透過交換相鄰數字（差值為奇數）來最小化給定數字。“透過交換相鄰數字（差值為奇數）來最小化給定數字”這一挑戰已在本文中得到解決。

本文提供了 C 語言程式碼以及實現程式的演算法和方法，該程式透過交換相鄰數字（差值為奇數）來最小化給定數字。