本篇文章我们来介绍一下常用算法
1.贪心算法
贪心算法(Greedy Algorithm)是一种解决问题的策略,它在每一步都做出当前看来最优的选择,而不考虑全局最优解。(局部最优解得到整体最优解)贪心算法通常适用于满足"贪心选择性质"和"最优子结构性质"的问题。
贪心算法使用条件:
贪心算法适用的条件包括两个性质:贪心选择性质和最优子结构性质。
贪心选择性质(Greedy Choice Property):通过每一步的局部最优选择,能够得到全局最优解。也就是说,在每一步选择中,都做出当前看起来最好的选择,而不考虑对后续步骤的影响。
最优子结构性质(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.递归算法
递归算法是一种通过调用自身来解决问题的算法。它将一个大问题分解为一个或多个相同或类似的子问题,并通过逐级求解子问题来达到最终解决整个问题的目的。
递归算法通常包含以下两个重要组成部分:
基本情况(Base Case):确定递归算法何时停止,不再进行递归调用。基本情况应该是最简单的情况,无需进一步递归求解即可得到结果。
递归调用(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
函数返回了一个二维数组,其中每个元素代表一种合法的八皇后布局。回溯算法的关键在于
isValid
和backtrack
函数。isValid
函数用于判断当前位置是否可以放置皇后,而backtrack
函数用于递归地尝试所有可能的选择,并生成符合要求的解。
总结:本篇文章讲了一些常用的数据结构算法 如贪心算法 回溯法 递归算法 等 掌握,每一个算法的精髓 才行 根据不同的场景使用不同的算法 能达到意想不到的效果
好了 本篇文章就到这里 在这里小编想向大家推荐一个课程 课程质量杠杠的文章来源:https://www.toymoban.com/news/detail-835846.html
https://xxetb.xetslk.com/s/2PjJ3T文章来源地址https://www.toymoban.com/news/detail-835846.html
到了这里,关于C++古老算法介绍的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!