C++古老算法介绍

简介: C++古老算法介绍

本篇文章我们来介绍一下常用算法

1.贪心算法

贪心算法(Greedy Algorithm)是一种解决问题的策略,它在每一步都做出当前看来最优的选择,而不考虑全局最优解。(局部最优解得到整体最优解)贪心算法通常适用于满足"贪心选择性质"和"最优子结构性质"的问题。

贪心算法使用条件:

贪心算法适用的条件包括两个性质:贪心选择性质和最优子结构性质。

  1. 贪心选择性质(Greedy Choice Property):通过每一步的局部最优选择,能够得到全局最优解。也就是说,在每一步选择中,都做出当前看起来最好的选择,而不考虑对后续步骤的影响。
  2. 最优子结构性质(Optimal Substructure):问题的最优解包含了子问题的最优解。换句话说,通过求解子问题的最优解,可以推导出原问题的最优解。

当一个问题满足这两个性质时,可以考虑使用贪心算法来求解。但需要注意,并非所有问题都满足这两个性质,所以不能盲目地应用贪心算法。

代码实例:

以下是一个使用贪心算法解决找零钱问题的示例(经典):

假设有面额为1元、5元、10元、25元的硬币,现在要找零给定金额的钱数,求最少需要多少个硬币。

#include <iostream>
#include <vector>
std::vector<int> greedyCoinChange(int amount, std::vector<int>& coins) {
    std::vector<int> result;
    for (int i = coins.size() - 1; i >= 0; i--) {
        while (amount >= coins[i]) { // 尽可能多地选择当前面额的硬币
            result.push_back(coins[i]);
            amount -= coins[i];
        }
    }
    return result;
}
int main() {
    int amount = 48;
    std::vector<int> coins = {25, 10, 5, 1};
    std::cout << "Amount: " << amount << std::endl;
    std::cout << "Coins used: ";
    
    std::vector<int> result = greedyCoinChange(amount, coins);
    for (int coin : result) {
        std::cout << coin << " ";
    }
    
    std::cout << std::endl;
    return 0;
}

这段代码中,我们从最大面额的硬币开始选择,如果当前金额仍然大于等于当前面额的硬币,则选择该硬币,并减去相应的金额。重复这个过程直到金额变为0。

贪心算法在此问题中能够得到最优解,因为每次选择都是局部最优的。但需要注意的是,贪心算法并不适用于所有问题,有些问题可能需要动态规划等其他方法来求解。在使用贪心算法时,需要仔细分析问题性质,并确保它满足贪心选择性质和最优子结构性质。

2.递归算法

递归算法是一种通过调用自身来解决问题的算法。它将一个大问题分解为一个或多个相同或类似的子问题,并通过逐级求解子问题来达到最终解决整个问题的目的。

递归算法通常包含以下两个重要组成部分:

  1. 基本情况(Base Case):确定递归算法何时停止,不再进行递归调用。基本情况应该是最简单的情况,无需进一步递归求解即可得到结果。
  2. 递归调用(Recursive Call):在算法中使用相同的函数来解决规模更小的子问题。通过反复调用自身,将大问题转化为规模较小且相同性质的子问题。

在编写递归算法时,需要注意以下几点:

  • 确保每次递归调用都能使问题规模减小,否则可能会导致无限循环。
  • 保证基本情况被正确处理,确保最终可以终止递归过程。
  • 尽量避免重复计算和重复工作,利用已经计算过的结果进行缓存或剪枝操作。

斐波那契数列

#include <iostream>
int fibonacci(int n) {
    if (n <= 0) {
        return -1; // 错误情况,返回负数表示错误
    } else if (n == 1 || n == 2) {
        return 1; // 基本情况,斐波那契数列的第一项和第二项为1
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2); // 递归调用求解前两个斐波那契数之和
    }
}
int main() {
    int n = 6;
    int result = fibonacci(n);
    
    std::cout << "第 " << n << " 个斐波那契数是:" << result << std::endl;
    return 0;
}

回溯法:

回溯法(Backtracking)是一种解决问题的算法思想,通常用于求解在给定约束条件下的所有可能解。它通过尝试所有可能的选择,并逐步构建出候选解,如果当前构建的部分无法满足问题的限制条件,就会回溯到上一个状态进行其他选择。

八皇后问题

#include <iostream>
#include <vector>
using namespace std;
bool isValid(vector<int>& board, int row, int col) {
    for (int i = 0; i < row; ++i) {
        if (board[i] == col || abs(board[i] - col) == abs(i - row)) {
            return false;
        }
    }
    return true;
}
void backtrack(vector<vector<string>>& res, vector<int>& board, int row, int n) {
    if (row == n) {
        vector<string> solution(n, string(n, '.'));
        for (int i = 0; i < n; ++i) {
            solution[i][board[i]] = 'Q';
        }
        res.push_back(solution);
    } else {
        for (int col = 0; col < n; ++col) {
            if (isValid(board, row, col)) {
                board[row] = col;
                backtrack(res, board, row + 1, n);
                board[row] = -1;
            }
        }
    }
}
vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> res;
    vector<int> board(n, -1);
    backtrack(res, board, 0, n);
    return res;
}
int main() {
    int n = 4;
    vector<vector<string>> solutions = solveNQueens(n);
    
    for (const auto& solution : solutions) {
        for (const auto& row : solution) {
            cout << row << endl;
        }
        cout << "----------------" << endl;
    }
    
    return 0;
}

在这个示例中,我们通过回溯法解决了八皇后问题。solveNQueens 函数返回了一个二维数组,其中每个元素代表一种合法的八皇后布局。

回溯算法的关键在于 isValidbacktrack 函数。isValid 函数用于判断当前位置是否可以放置皇后,而 backtrack 函数用于递归地尝试所有可能的选择,并生成符合要求的解。

总结:本篇文章讲了一些常用的数据结构算法    如贪心算法 回溯法 递归算法 等   掌握,每一个算法的精髓 才行 根据不同的场景使用不同的算法 能达到意想不到的效果

好了 本篇文章就到这里 在这里小编想向大家推荐一个课程 课程质量杠杠的

https://xxetb.xetslk.com/s/2PjJ3T

相关文章
|
4月前
|
存储 监控 算法
基于 C++ 哈希表算法实现局域网监控电脑屏幕的数据加速机制研究
企业网络安全与办公管理需求日益复杂的学术语境下,局域网监控电脑屏幕作为保障信息安全、规范员工操作的重要手段,已然成为网络安全领域的关键研究对象。其作用类似网络空间中的 “电子眼”,实时捕获每台电脑屏幕上的操作动态。然而,面对海量监控数据,实现高效数据存储与快速检索,已成为提升监控系统性能的核心挑战。本文聚焦于 C++ 语言中的哈希表算法,深入探究其如何成为局域网监控电脑屏幕数据处理的 “加速引擎”,并通过详尽的代码示例,展现其强大功能与应用价值。
103 2
|
5月前
|
存储 算法 C++
Windows共享文件:探秘C++实现的B树索引算法奇境
在数字化时代,Windows共享文件的高效管理至关重要。B树算法以其自平衡多路搜索特性,在文件索引与存储优化中表现出色。本文探讨B树在Windows共享文件中的应用,通过C++实现具体代码,展示其构建文件索引、优化数据存储的能力,提升文件检索效率。B树通过减少磁盘I/O操作,确保查询高效,为企业和个人提供流畅的文件共享体验。
|
6月前
|
存储 负载均衡 算法
基于 C++ 语言的迪杰斯特拉算法在局域网计算机管理中的应用剖析
在局域网计算机管理中,迪杰斯特拉算法用于优化网络路径、分配资源和定位故障节点,确保高效稳定的网络环境。该算法通过计算最短路径,提升数据传输速率与稳定性,实现负载均衡并快速排除故障。C++代码示例展示了其在网络模拟中的应用,为企业信息化建设提供有力支持。
171 15
|
6月前
|
运维 监控 算法
解读 C++ 助力的局域网监控电脑网络连接算法
本文探讨了使用C++语言实现局域网监控电脑中网络连接监控的算法。通过将局域网的拓扑结构建模为图(Graph)数据结构,每台电脑作为顶点,网络连接作为边,可高效管理与监控动态变化的网络连接。文章展示了基于深度优先搜索(DFS)的连通性检测算法,用于判断两节点间是否存在路径,助力故障排查与流量优化。C++的高效性能结合图算法,为保障网络秩序与信息安全提供了坚实基础,未来可进一步优化以应对无线网络等新挑战。
|
6月前
|
存储 算法 数据处理
公司局域网管理中的哈希表查找优化 C++ 算法探究
在数字化办公环境中,公司局域网管理至关重要。哈希表作为一种高效的数据结构,通过哈希函数将关键值(如IP地址、账号)映射到数组索引,实现快速的插入、删除与查找操作。例如,在员工登录验证和设备信息管理中,哈希表能显著提升效率,避免传统线性查找的低效问题。本文以C++为例,展示了哈希表在局域网管理中的具体应用,包括设备MAC地址与IP分配的存储与查询,并探讨了优化哈希函数和扩容策略,确保网络管理高效准确。
|
2月前
|
存储 监控 算法
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表(Skip List)是一种基于概率的数据结构,适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作,时间复杂度为 $O(\log n)$,优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色,具备实现简单、支持范围查询等优势,是企业网络监控中动态数据管理的理想选择。
77 0
|
3月前
|
存储 机器学习/深度学习 算法
基于 C++ 的局域网访问控制列表(ACL)实现及局域网限制上网软件算法研究
本文探讨局域网限制上网软件中访问控制列表(ACL)的应用,分析其通过规则匹配管理网络资源访问的核心机制。基于C++实现ACL算法原型,展示其灵活性与安全性。文中强调ACL在企业与教育场景下的重要作用,并提出性能优化及结合机器学习等未来研究方向。
96 4
|
4月前
|
监控 算法 数据处理
基于 C++ 的 KD 树算法在监控局域网屏幕中的理论剖析与工程实践研究
本文探讨了KD树在局域网屏幕监控中的应用,通过C++实现其构建与查询功能,显著提升多维数据处理效率。KD树作为一种二叉空间划分结构,适用于屏幕图像特征匹配、异常画面检测及数据压缩传输优化等场景。相比传统方法,基于KD树的方案检索效率提升2-3个数量级,但高维数据退化和动态更新等问题仍需进一步研究。未来可通过融合其他数据结构、引入深度学习及开发增量式更新算法等方式优化性能。
139 17
|
3月前
|
机器学习/深度学习 存储 算法
基于 C++ 布隆过滤器算法的局域网上网行为控制:URL 访问过滤的高效实现研究
本文探讨了一种基于布隆过滤器的局域网上网行为控制方法,旨在解决传统黑白名单机制在处理海量URL数据时存储与查询效率低的问题。通过C++实现URL访问过滤功能,实验表明该方法可将内存占用降至传统方案的八分之一,查询速度提升约40%,假阳性率可控。研究为优化企业网络管理提供了新思路,并提出结合机器学习、改进哈希函数及分布式协同等未来优化方向。
87 0
|
5月前
|
存储 监控 算法
基于 C++ 哈希表算法的局域网如何监控电脑技术解析
当代数字化办公与生活环境中,局域网的广泛应用极大地提升了信息交互的效率与便捷性。然而,出于网络安全管理、资源合理分配以及合规性要求等多方面的考量,对局域网内计算机进行有效监控成为一项至关重要的任务。实现局域网内计算机监控,涉及多种数据结构与算法的运用。本文聚焦于 C++ 编程语言中的哈希表算法,深入探讨其在局域网计算机监控场景中的应用,并通过详尽的代码示例进行阐释。
115 4

热门文章

最新文章