数据结构
网络
关系数据库管理系统
操作系统
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 次查看
