C++试听课

引导学员进行算法实践的编程练习

C++算法实例

在C++中，标准库<algorithm>提供了大量的算法，如排序、查找、操作等，可以方便地应用于各种数据结构。以下是两个C++算法实例，一个使用排序算法对一组数进行排序，另一个使用查找算法在向量中查找元素。

实例一：使用排序算法（如 std::sort）

#include <iostream>  
#include <vector>  
#include <algorithm> // 包含排序算法的头文件  
  
int main() {  
    // 创建一个包含整数的向量  
    std::vector<int> numbers = {4, 2, 9, 6, 5, 1, 8, 3, 7};  
  
    // 使用 std::sort 对向量进行排序  
    std::sort(numbers.begin(), numbers.end());  
  
    // 输出排序后的向量  
    std::cout << "排序后的向量：" << std::endl;  
    for (int num : numbers) {  
        std::cout << num << " ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}

实例二：使用查找算法（如 std::find）

#include <iostream>  
#include <vector>  
#include <algorithm> // 包含查找算法的头文件  
  
int main() {  
    // 创建一个包含整数的向量  
    std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9};  
  
    // 要查找的元素  
    int valueToFind = 5;  
  
    // 使用 std::find 查找元素  
    auto it = std::find(numbers.begin(), numbers.end(), valueToFind);  
  
    // 检查元素是否找到  
    if (it != numbers.end()) {  
        std::cout << "找到元素 " << valueToFind << " 在位置 " << std::distance(numbers.begin(), it) << std::endl;  
    } else {  
        std::cout << "未找到元素 " << valueToFind << std::endl;  
    }  
  
    return 0;  
}

这两个例子展示了如何使用C++标准库中的算法。std::sort用于对向量中的元素进行排序，而std::find用于在向量中查找特定的元素。这些算法都是泛型算法，可以应用于任何支持相应迭代器类型的容器。

在实际应用中，你可能还需要考虑其他因素，比如性能优化、异常处理以及算法的选择（例如，对于大型数据集，可能需要使用更高效的排序算法，如快速排序或归并排序）。此外，对于复杂的搜索问题，可能还需要考虑使用更复杂的数据结构（如哈希表）和搜索算法（如二分搜索）。

实例一：计算最大公约数和最小公倍数

#include <iostream>  
  
// 计算最大公约数（GCD）  
int gcd(int a, int b) {  
    if (b == 0) return a;  
    return gcd(b, a % b);  
}  
  
// 计算最小公倍数（LCM）  
int lcm(int a, int b) {  
    return (a / gcd(a, b)) * b;  
}  
  
int main() {  
    int num1, num2;  
    std::cout << "请输入两个整数：";  
    std::cin >> num1 >> num2;  
  
    int result_gcd = gcd(num1, num2);  
    int result_lcm = lcm(num1, num2);  
  
    std::cout << "最大公约数（GCD）：" << result_gcd << std::endl;  
    std::cout << "最小公倍数（LCM）：" << result_lcm << std::endl;  
  
    return 0;  
}

实例二：使用迭代器遍历和修改容器元素

#include <iostream>  
#include <vector>  
#include <algorithm> // 包含迭代器算法的头文件  
  
int main() {  
    // 创建一个整数向量  
    std::vector<int> numbers = {1, 2, 3, 4, 5};  
  
    // 使用迭代器遍历并打印向量中的每个元素  
    for (std::vector<int>::iterator it = numbers.begin(); it != numbers.end(); ++it) {  
        std::cout << *it << " ";  
    }  
    std::cout << std::endl;  
  
    // 使用 std::for_each 和 lambda 表达式遍历并打印向量中的每个元素  
    std::for_each(numbers.begin(), numbers.end(), [](int n) {  
        std::cout << n << " ";  
    });  
    std::cout << std::endl;  
  
    // 使用 std::transform 将向量中的每个元素乘以2  
    std::transform(numbers.begin(), numbers.end(), numbers.begin(), [](int n) {  
        return n * 2;  
    });  
  
    // 再次遍历并打印修改后的向量  
    for (int num : numbers) {  
        std::cout << num << " ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}

实例三：查找算法——二分查找

#include <iostream>  
#include <vector>  
#include <algorithm> // 包含查找算法的头文件  
  
// 二分查找函数  
int binarySearch(const std::vector<int>& arr, int target) {  
    int left = 0;  
    int right = arr.size() - 1;  
    while (left <= right) {  
        int mid = left + (right - left) / 2;  
        if (arr[mid] == target) {  
            return mid; // 找到目标，返回其索引  
        } else if (arr[mid] < target) {  
            left = mid + 1; // 在右侧继续查找  
        } else {  
            right = mid - 1; // 在左侧继续查找  
        }  
    }  
    return -1; // 未找到目标  
}  
  
int main() {  
    // 创建一个已排序的整数向量  
    std::vector<int> sortedArray = {1, 3, 5, 7, 9, 11, 13, 15};  
    int targetValue = 9;  
  
    // 使用二分查找查找目标值  
    int index = binarySearch(sortedArray, targetValue);  
  
    if (index != -1) {  
        std::cout << "找到目标值 " << targetValue << " 在位置 " << index << std::endl;  
    } else {  
        std::cout << "未找到目标值 " << targetValue << std::endl;  
    }  
  
    return 0;  
}

这些实例展示了C++中一些常见的算法应用，包括数学运算、迭代操作以及查找算法。你可以根据实际需要，将这些算法结合数据结构，应用于更复杂的问题中。记得在使用算法时，要考虑数据的大小和特性，选择最合适的算法以提高效率。

0.060401s