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文章来源地址https://www.toymoban.com/news/detail-835846.html

到了这里,关于C++古老算法介绍的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++基础-介绍·数据结构·排序·算法

    C++是一门风格严谨又不失自由的开发语言,提供了完整的内存管理、支持函数式编程和面向对象编程,支持模板、多继承、多实现、重载、重写等多态特性。 优势在于目前90%的操作系统、数据库、应用基础架构、硬件嵌入式等都是使用C/C++制作的,而C++是对C的标准扩展,掌握

    2024年02月03日
    浏览(43)
  • 【每日一题】补档 CF487B. Strip | 数据结构杂烩 -> 单调队列 | 困难

    原题链接 给定一个长度为 n n n 的数组,将这个数组进行拆分成若干个连续子数组, 使得每个子数组的最大值减去最小值小于等于 s s s , 且每个子数组的长度大于等于 l e n len l e n 。 问最少可以拆分成多少个连续子数组,如果不可以,则输出 − 1 -1 − 1 1 ≤ n , l e n ≤ 1 0

    2024年02月06日
    浏览(49)
  • 【C++】数据结构与算法:常用排序算法

    😏 ★,° :.☆( ̄▽ ̄)/$: .°★ 😏 这篇文章主要介绍常用排序算法。 学其所用,用其所学。——梁启超 欢迎来到我的博客,一起学习,共同进步。 喜欢的朋友可以关注一下,下次更新不迷路🥞 排序算法是计算机科学中常见的一类算法,用于将一组数据按照特定的顺序进行排

    2024年02月14日
    浏览(46)
  • 数据结构与算法复杂度介绍

    目录 一、基本概念 二、时间复杂度 【2.1】时间复杂度概念 【2.2】大O的渐进表示法 【2.3】举例时间复杂度计算 三、空间复杂度 数据结构 :相互之间存在一种或者多种特定关系的数据元素的集合。在逻辑上可以分为线性结构,散列结构、树形结构,图形结构等等。 算法 :

    2024年02月10日
    浏览(36)
  • 算法 数据结构分类 数据结构类型介绍 数据结构线性非线性结构 算法合集 (一)

     数据结构分为:                            a.线性结构                            b.非线性结构  a.线性结构:                       数据与结构存在一对一的线性关系; a . 线性结构 存储 分为:                                   顺序存储

    2024年02月10日
    浏览(49)
  • 【数据结构与算法C++实现】3、排序算法

    原视频为左程云的B站教学 外层循环 :n个数需要冒n-1个泡上去,剩下的一个必然是最小的。所以外层循环执行n-1轮 内层循环 :比大小,第1个泡需要比n-1次,第2个泡,比较n-2次… 选择: 每次从待排序序列中选择 最小的一个 放在已排序序列的后一个位置 原理类似于对扑克牌

    2024年02月11日
    浏览(56)
  • C++数据结构与算法——哈希表

    C++第二阶段——数据结构和算法,之前学过一点点数据结构,当时是基于Python来学习的,现在基于C++查漏补缺,尤其是树的部分。这一部分计划一个月,主要利用代码随想录来学习,刷题使用力扣网站,不定时更新,欢迎关注! 给定两个字符串 s 和 t ,编写一个函数来判断

    2024年02月19日
    浏览(56)
  • 【C++图解专栏】手撕数据结构与算法,探寻算法的魅力

    ✍个人博客:https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343 📣专栏定位:为 0 基础刚入门数据结构与算法的小伙伴提供详细的讲解,也欢迎大佬们一起交流~ 📚专栏简介:在这个专栏,我将带着大家一起用 C++ 手撕基础的数据结构与算法,每一讲都有详细的讲解,29 篇文章共

    2024年02月09日
    浏览(57)
  • C++数据结构与算法——双指针法

    C++第二阶段——数据结构和算法,之前学过一点点数据结构,当时是基于Python来学习的,现在基于C++查漏补缺,尤其是树的部分。这一部分计划一个月,主要利用代码随想录来学习,刷题使用力扣网站,不定时更新,欢迎关注! 给你一个数组 nums 和一个值 val,你需要 原地

    2024年02月20日
    浏览(38)
  • C++数据结构与算法——栈与队列

    C++第二阶段——数据结构和算法,之前学过一点点数据结构,当时是基于Python来学习的,现在基于C++查漏补缺,尤其是树的部分。这一部分计划一个月,主要利用代码随想录来学习,刷题使用力扣网站,不定时更新,欢迎关注! 请你仅使用两个栈实现先入先出队列。队列应当

    2024年02月20日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包