資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究透過交換相鄰的奇偶對獲得可能的最小數字
“奇偶對”是指兩個連續整數的配對，一個為偶數，另一個為奇數。例如，奇偶對包括 (2,3)、(4,5)、(6,7) 等。
這些配對通常用於基於數字變化的演算法和程式設計練習中。當對一組數字進行重複操作時，例如，可能只想對偶數或奇數執行操作。當這種情況發生時，使用奇偶對可以透過減少所需的條件語句數量來幫助簡化程式碼。
方法
透過交換附近的奇偶對，您可以應用以下策略來確定可能的最小數字 -
氣泡排序方法
貪心演算法
方法 1：氣泡排序方法
從數字開始，我們必須使用氣泡排序後續演算法來解決手頭的難題。從一開始，我們必須仔細檢查每對相鄰數字。如果對的左成員是奇數，而右成員是偶數，則我們交換它們的位置。然後，在處理完最後兩個數字後，該過程將繼續處理後續的數字。如果在完整遍歷期間發生任何更改，我們必須重新開始整個過程。
語法
為了透過交換附近的奇偶對獲得最小數字，請按照以下關於如何在 C++ 中構建氣泡排序演算法的分步教程 -
建立整數陣列並填寫要排序的數字。
int q[] = {6, 4, 2, 5, 7, 1};
計算陣列的大小或長度。
int p = sizeof(q) / sizeof(q[0]);
應用氣泡排序演算法。
for (int r = 0; r < p - 1; r++) {
for (int j = 0; j < p - r - 1; j++) {
if (q[j] % 2 == 0 && q [j + 1] % 2 != 0) {
swap(q[j], q [j + 1]);
}
}
}
輸出排序後的陣列。
for (int r = 0; r < p; r++) {
cout << q[r] << " ";
}
演算法
透過交換相鄰的奇偶對找到可能的最小數字的氣泡排序方法的分步演算法 -
步驟 1 - 開始獲取需要排序的一組數字作為輸入。
步驟 2 - 建立一個迴圈，該迴圈在整個陣列中重複，直到所有元素都排序完畢。
步驟 3 - 然後在第一個迴圈內出現第二個迴圈，該迴圈遍歷陣列中每對相鄰元素。
步驟 4 - 查詢每對相鄰元素中第一個元素是否為奇數，第二個元素是否為偶數。如果是，則交換元素。
步驟 5 - 如果陣列中有前一個元素，則將其與新交換的成員進行比較。如有必要，用較小的元素替換先前交換的元素。
步驟 6 - 繼續迭代遍歷陣列，直到驗證和排序每對元素。
步驟 7 - 如果在任何迭代期間未執行任何交換，則認為陣列已排序，並且可以結束外部迴圈。
步驟 8 - 排序完成後，列印已排序的陣列。
示例 1
為了透過交換相鄰的奇偶對獲得最小數字，以下是在 C++ 中實現氣泡排序方法的一個示例 -
在此實現中，使用向量，輸入數字透過應用氣泡排序演算法（透過 bubble Sort 函式）進行排序。swapped 變數跟蹤內部迴圈中的交換。如果在不進行任何交換的情況下完成了一次遍歷，則演算法停止操作，利用列表已經排序的事實。
在內部迴圈中，我們比較每對相鄰數字。只有當第一個數字為奇數且第二個數字為偶數，或者當奇偶性匹配且第一個數字更大時，我們才會修改數字。偶數在奇數之前的順序為奇偶對建立升序。
使用 for 迴圈，列印輸出包含排序後的數字。如果在相鄰數字之間對奇偶對進行了更改，則結果將生成可能的最小序列 2 7 5 8 9 10 1 12。
#include <iostream>
#include <vector>
using namespace std;
void bubbleSort(vector<int>& nums) {
int n = nums.size();
bool swapped;
for (int i = 0; i < n-1; i++) {
swapped = false;
for (int j = 0; j < n-i-1; j++) {
if ((nums[j] % 2 == 0 && nums[j+1] % 2 != 0) || (nums[j] % 2 == nums[j+1] % 2 && nums[j] > nums[j+1])) {
swap(nums[j], nums[j+1]);
swapped = true;
}
}
if (!swapped) break;
}
}
int main() {
vector<int> nums = {7, 2, 5, 9, 12, 10, 8, 1};
bubbleSort(nums);
for (int num : nums) {
cout << num << " ";
}
cout << endl; // Output: 2 7 5 8 9 10 1 12
return 0;
}
輸出
1 5 7 9 2 8 10 12
方法 2：貪心演算法
另一種策略是始終用其後最大的奇數替換最左邊的偶數。這稱為貪心演算法。找到最左邊的偶數右側最大的奇數。在這種情況下，交換這兩個數字並繼續執行下一步，從交換後的偶數開始。如果當前偶數的右側沒有更大的奇數，則應使用下一個偶數。
語法
以下是如何使用 C++ 程式碼實現貪心演算法，以透過交換相鄰的奇偶對找到可能的最小數字 -
定義一個函式，用於交換字串中兩個相鄰字元 -
void swapAdjacentChars(string& s, int i) {
char temp = s[i];
s[i] = s[i+1];
s[i+1] = temp;
}
初始化字串
string s = "98167375";
迴圈遍歷字串，交換相鄰的奇偶對
for (int o = 0; o < s.l () - 1; o++) {
if ((s[o] - '0') % 2 == 0 && (s[o+1] - '0') % 2! = 0) {
swap Adjacentn Chars (s, o);
break;
}
}
列印結果
cout << s << endl; }
演算法
可以使用以下步驟實現透過交換相鄰奇偶對找到可能的最小數字的貪心演算法 -
步驟 1 - 將給定的數字轉換為數字陣列。
步驟 2 - 從左到右遍歷陣列，對於每個偶數，搜尋其右側最小的奇數。
步驟 3 - 如果找到較小的奇數，則交換偶數和奇數，並中斷迴圈。
步驟 4 - 如果未找到較小的奇數，則繼續下一個偶數。
步驟 5 - 將數字陣列轉換為單個數字似乎是一項具有挑戰性的任務。但是，對問題應用交換演算法可以提供 O(n^2) 的時間複雜度，其中 n 表示初始數字中的數字個數。幸運的是，所需的交換次數通常很少；因此，該解決方案既高效又快速。
示例 2
以下是一個 C++ 示例，其中我們交換相鄰的奇偶對以獲得可能的最小整數 -
在此示例中，我們建立了一個名為 smallest number 的函式，該函式以字串 num 作為輸入，並返回可以透過交換相鄰奇偶對建立的最小數字。該方法第一次遍歷字串時，它會確定當前索引是否為偶數，以及該點的數字是否為奇數。在這種情況下，它會在字串中查詢下一個偶數並將其與奇數交換。該函式最終返回修改後的字串。
#include <iostream>
#include <string>
using namespace std;
string smallestNumber(string num) {
int n = num.length();
// Iterate over the string and swap adjacent even-odd pairs
for (int i = 0; i < n - 1; i++) {
if (i % 2 == 0 && num[i] % 2 != 0) {
// Swap the current odd digit with the next even digit
for (int j = i + 1; j < n; j++) {
if (j % 2 != 0 && num[j] % 2 == 0) {
swap(num[i], num[j]);
break;
}
}
}
}
return num;
}
int main() {
string num = "2145367";
cout << "Original number: " << num << endl;
cout << "Smallest number possible: " << smallestNumber(num) << endl;
return 0;
}
輸出
Original number: 2145367 Smallest number possible: 2145637
結論
從最左邊的數字開始，我們可以將其與相鄰的數字進行比較，以找到透過更改相鄰的奇偶對可以獲得的最小值。為了建立這個最小數字，如果左側數字為偶數，右側數字為奇數，則我們將這兩個數字交換。此過程持續到最右邊的數字。使用此方法，我們可以確保較小的數字首先出現在數字中，使其成為可以實現的最小數字。如果存在多個具有相同值的奇偶對，則我們必須首先考慮最靠近最左邊數字的對。
404 次檢視
