木有BUG!站点正常运行(ノ゚▽゚)ノ | 最近更新:欧拉路径与哈密顿路径 | 更新时间:2024-02-27

有关于C++的基础教程,该教程建立在学习过C语言的基础上,进行对比学习,了解不同的特性和更多新内容,学习设计类和面向对象程序设计

注:该教程建立在学习过 C 语言的基础上,因此很多提过的细节会忽略,主要学习一些 C 语言没有或不同的特性,建议先学习C 语言基础教程

本文中没有特殊重申的,大多语句和特性都与 C 语言相同,C++是 C 的超集,兼容了 C 的大多数特性


开始


章节概要:编写一个简单的 C++程序;初识输入输出;使用 C++ 版本的 C 标准库头文件;类简介

阅读更多
C++基础语法

学习欧拉路径、欧拉回路与哈密顿路径的特点,学习 Fleury 算法和 Hierholzer 算法

欧拉路径与哈密顿路径


  • 欧拉路

    1、欧拉路径:从某一点出发经过一条不间断的路径这条路径刚好访问整个图的所有边一次且仅一次(一笔画问题)。一个图可能有多条欧拉路径
    2、欧拉回路:一条首尾相接欧拉路径(首尾相接的一笔画问题)。一个图可能有多条欧拉回路
    3、欧拉图:具有欧拉回路的图。特点为:无向图中所有顶点的度都是偶数有向图中所有顶点的入度和出度都相等
    4、半欧拉图:具有欧拉路径但不具有欧拉回路的图。特点为:无向图有且仅有两个顶点度为奇数,这两个顶点分别为起点和终点有向图有且仅有一个顶点出度 - 入度 = 1,另有且仅有一个顶点入度 - 出度 = 1,这两个顶点分别为起点和终点
    5、推论:欧拉图的所有欧拉路径都是欧拉回路,所以计算欧拉回路欧拉路径的算法完全一样

阅读更多
C++数学欧拉路径哈密顿路径FleuryHierholzer

学习动态规划中更多常用的DP,如线性DP、区间DP、树形DP、存在DP、计数DP、数位DP、状压DP、概率DP

线性 DP-最长上升子序列


  • 最长上升子序列

    1、最长上升子序列(easy):给定一个长度为 n数组 a(n 不超过 1000),求其最长上升子序列(非降)的长度。注意:子序列不一定是连续的
    2、对于线性 DP,通常用dp[i]表示以 i 结尾到 i 为止,如果有对应的代价,通常用dp[i][j]表示到 i 为止花费 j 的代价价值最值(见背包问题)
    3、确定状态:令dp[i]表示以 i 结尾的最长上升子序列长度
    4、确定转移:对于输入的每一个a[i],可知都有两种情况:一种是它作为最长上升子序列的起点,另一种是它接续在其他上升子序列之后。对于a[i]作为起点dp[i] = 1;对于a[i]作为接续,应向左搜寻小于等于 i 的元素 jdp[i] = max(dp[i], dp[j] + 1)遍历取最大值
    5、易知,该算法复杂度为 O(n2),只能处理小规模数据,仍需优化

阅读更多
C++DP动态规划

学习动态规划中典型的背包问题,通过动态规划的思想不重不漏地表达整个集合,推导出线性的状态转移方程

01 背包-采药


  • 采药

    1、采药:输入 T 和 M 分别表示拥有的总时间药材种类(T 不超过 1000,M 不超过 100),对于每种药材,输入 t 和 v(都不超过 100),表示采摘该药材需要的时间药材的价值,每种药材只可采摘一次。可能输入多组数据,直到 T 和 M 都为 0 结束。对于每组数据,输出其规定时间内能采摘的药材价值之和的最大值
    2、对于每种药材都可以用 0 或 1 标记状态(是否被选择),是一个01 背包问题。运用动态规划的思想,先确定状态:令dp[i][j]表示到第 i 个物品为止用了 j 的时间所获得的最大价值
    3、再确定转移,对于当前的dp[i][j],有两种情况:如果没选择当前第 i 个物品,则dp[i][j] = dp[i-1][j](没有花费时间,没有增加价值,和上一个——到第 i-1 个物品的状态相同);如果选择了当前第 i 个物品,则dp[i][j] = dp[i-1][j-t[i]] + v[i](当前状态等同于dp[i-1][j-t[i]]上一个物品的价值 + 当前物品价值,其中因为当前dp[i][j]花费的总时间为 j,所以上一个物品的时间应为j-t[i])
    4、最后确定初始化和边界初始化dp[0][i] = 0(到第 0 个物品无论花费多少时间,价值为 0);边界为 i <= M, j <= T

阅读更多
C++动态规划背包问题

学习通过递推法或公式法求组合数 C(n, m)

递推求组合数


  • 递推求组合数

    1、组合数中有C(n, m) = C(n-1, m-1) + C(n-1, m)。其中C(n, m)意为从 n 个元素中选出 m 个元素有多少种不同组合,其总的可能可划分为组合中选了第一个组合中没选第一个两种。如果组合中选了第一个,那么剩下的方案数还有C(n-1, m-1)种(从剩余元素中选 m-1 个);如果组合中没选第一个,那么剩下的组合中还有C(n-1, m)种;这两种结果互斥,因此相加便可得到总的方案
    2、这种方法运用了递推DP的思想,上面的等式状态转移方程。其中,C(n, m)新状态,通过方程将其转移为两个老状态的和。此外,需要确定起始点边界起始点C(i, 0) = 1(从任意多的元素中选 0 个,有 1 种方案——不选);边界C(i, j)(其中 0 <= j <= i,i <= n)

阅读更多
C++数学组合数

学习基于点的 Prim 最小生成树和基于边的 Kruskal 最小生成树

Prim 最小生成树(朴素)


  • 生成树 与 MST

    1、在无向连通图中,找出一个节点最多子连通图(有 n 个点,n-1 条边),这样的子连通图一定是,称为生成树最小生成树指各边权值之和最小生成树,称为 MST(Minimum Spanning Tree)
    2、如下图,便是一幅无向连通图,该图的最小生成树为图中红色所示子连通图(有 5 个点,4 条边),其权值和为 10
    3、对于最小生成树的生成,可以通过基于点的 Prim 最小生成树基于边的 Kruskal 最小生成树完成

阅读更多
C++PrimKruskal

学习 Dijkstra 单源带权最短路和 Floyd 多源带权最短路

Dijkstra 单源带权(朴素)


  • Dijkstra 朴素算法

    1、最短路 1:给定 n 个点 m 条边的有向图(n 不超过 103),输出点 1 到 n最短距离。对于 m 条边,每次输入 u、v、w,表示存在一条从 u 到 v权值为 w 的有向边。如果不存在路径,输出 -1
    2、先前在图与回溯中介绍过权值相等最短路(无权最短路),现在有了权值,需要做一个结构体保存。Dijkstra还使用一个数组d[]d[i]表示从起点 st 到 i 的最短距离
    3、Dijkstra 思路如下图:起始时,建图,标记所有d[i]无穷大,以 1 为起点,向外走一层将经过的边松弛(用边的权值更新所到点的d[i]d[i]取较小值);接下来,比较得到最小的d[i]以该点为当前起点(图中为点 2),先前的点已经可以忽略,继续向外走一层将经过的边松弛(注意,d[3]取较小值更新为 3);以此类推,以 4 为当前起点发现点 4 没有出点返回以 3 为当前起点,走到终点,更新d[5]为 6,所以最短路为 6
    4、该算法结合了贪心DP的思想,每个点只拓展一次,且拓展时已为最短距离

阅读更多
C++DijkstraFloyd