最小生成树
算法步骤Prim Kruskal 代码123456789101112131415161718192021222324clc,clear% matlab中，不存在的边设置成0% 6个顶点，初始化定义6x6的全零矩阵作为邻接矩阵a = zeros(6);% 注意，最小生成树是针对无向图的，每条边权重只需要设一次。1到2和2到1是同一条边% 因此，可仅使用邻接矩阵的上三角矩阵来构造图Ga(1,[2 3])=[14 18]; % 顶点1到顶点2、3的边的权重a(2,[3:5])=[13 18 16]; % 顶点2到顶点3、4、5的边的权重a(3,[4 5])=[12 16]; % 同上。因为写过1到3，和2到3的边的权重，无需重复设a(4,[5 6])=[14 19]; a(5,6)=10;s=cellstr(strcat('城市',int2str([1:6]')));G=graph(a,s,'upper'); % 仅使用 A...
最短路径
算法步骤Floyd算法参考CSDN文章 Dijkstra Floyd 代码12345678910111213141516171819202122232425262728293031% 定义图的边和权重s = [9 9 1 1 3 3 3 2 2 5 5 7 7 8]; % 起始节点编号t = [1 2 2 3 4 6 7 4 5 4 7 6 8 6]; % 终止节点编号w = [4 8 3 8 2 7 4 1 6 6 2 14 10 9]; % 边的权重% 创建一个图形对象 GG = graph(s,t,w);% 绘制图形 G，并将边的权重添加到图形上% G.Edges.Weight 表示图形对象 G 中所有边的权重值，'EdgeLabel' 表示在图形上显示这些权重值plot(G, 'EdgeLabel', G.Edges.Weight, 'linewidth', 2)% 隐藏图形的坐标轴set( gca, 'XTick', [], 'YTick', [] );%...
排序算法的复杂度
各类排序算法的复杂度 任何需要交换相邻元素进行排序的排序算法平均都需要Ω（N^2）时间证明：
离散数学中的其中几种证明题
（1） 结论： （2） （3）
证明无向图是连通图或者它的补图是连通图
补图的定义补图的数学定义为：对于一个给定的图G=(V,E)，其补图G'=(V,E')是一个具有相同顶点集V的图，其中**E'是V中未出现在E中的所有可能边的集合**。换句话说，G'中的边是G中不存在的边。 例题： 证明过程要证明对于任何无向图G，要么G是连通的，要么它的补图G’是连通的，我们可以使用反证法。 定义： 一个无向图G=(V,E)是连通的，如果对于任意两个顶点u, v ∈ V，存在一条从u到v的路径。 无向图G的补图G’=(V,E’)，其中E’包含所有不属于E的边，即如果(u,v) ∉ E，则(u,v) ∈ E’。 证明： 假设给定一个无向图G，它既不是连通图，其补图G’也不是连通图。这意味着在G中存在至少两个连通分量C1和C2，在G’中也存在至少两个连通分量C1’和C2’。 考虑G中的两个连通分量C1和C2，因为它们是不同的连通分量，所以不存在直接连接C1和C2中顶点的边，即对于所有的u ∈ C1和v ∈ C2，(u,v) ∉ E。根据补图的定义，这些不在E中的边都应该出现在E’中，即对于所有的u ∈ C1和v ∈...
哈夫曼树和哈夫曼编码
哈夫曼编码是一种用于数据压缩的编码方式，它使用变长编码来表示数据源中的符号。频率较高的符号用较短的编码，频率较低的符号用较长的编码，从而达到减少总编码长度的目的。 编码过程 例子： 对字母进行哈夫曼编码时的性质： 1.每个字母对应元素叶节点的值是该字母出现的次数 2.出现次数越多的字符编码越短 3.不出现歧义的情况下编出来的码长度最短 4.编码结果不唯一，字母编出来的码可能不一样，但是长度肯定一样 参考b站视频：哈夫曼树和哈夫曼编码, 看完秒懂！ 不会出现歧义原因：不存在任意一个元素节点出现在另一个元素节点的路径中 应用： 压缩文件 代码实现12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485#include <iostream>#include <queue>#include...
读公众号文章《小红书的一个用户救了我》有感，忆我与R星游戏
半佛仙人：小红书的一个用户救了我 文章的大致内容是在小红书有个叫做“小奈”的用户，因为她是被鉴定为智商二级，所以说话语言表达起来看着就像小孩子一样。她02年出生的，今年22岁，她在小红书发过很多篇笔记记录的都是自己攒钱想要买switch的经历。可能是被她坚持体现的童真所感动吧，大家在评论区里都很友善，都在积极地一起想要帮助小奈。看下来还是很令人感动的，评论区里大家都很友爱，小奈也很真诚，但是其实最令我有所感触的是当我看到小奈在幻想如果真的买到switch后会怎样，在那一刻我仿佛看到了小学和初中时的自己。 小学 在小学的时候我有一个iPad mini，我平时可以用它来看视频和玩游戏。小学时玩游戏外我还喜欢在爱奇艺上面看作者们上传的游戏视频，有一天我偶然地刷到了一个与gta5有关的游戏视频，我已经忘记了作者是谁了，反正当我看到游戏内容和游戏画面时马上就沦陷了，我被gta5的玩法和游戏画质所深深地吸引住了。于是我开始迷上了在爱奇艺里刷各种各样与gta5有关的游戏视频，我记得当时我最爱看一个叫“裴小峰”的游戏主播...
第七章 排序（堆排序）
说明 堆排序（Heap Sort）是一种基于二叉堆数据结构的比较型排序算法。它是一种选择排序，其最坏情况下的时间复杂度为O(n log n)**，其中 n 是待排序元素的数量。堆排序不是稳定排序，但是原地排序（只需要常数级别的额外空间）**。堆排序的基本思想是将待排序的序列构造成一个最大堆或最小堆，这样就可以方便地取出最大值或最小值，然后将其与末尾元素交换，最后对剩下的 n-1 个元素重新调整成堆，重复这个过程直到所有元素都被排序。 在堆排序中，我们通常使用最大堆（大顶堆），即每个父节点的值都大于或等于其子节点的值。最小堆（小顶堆）则是每个父节点的值都小于或等于其子节点的值。 代码这里假设堆数组元素下标从0开始 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include <iostream>#include <vector>//这里假设堆数组元素下标从0开始void...
博客搭建参考教程
在win10系统中利用阿里云服务器搭建个人博客Win10环境下基于Hexo的静态博客环境搭建，及其阿里云部署 | 阿汤笔迹 butterfly博客主题配置Butterfly 文檔(三) 主題配置 | Butterfly 公安备案如何填写公安联网备案公安联网备案信息指南_备案(ICP Filing)-阿里云帮助中心 Markdown官方教程 Markdown 官方教程
《博弈论的诡计》提及的几种博弈
囚徒困境囚徒困境（Prisoner’s Dilemma）是博弈论中的一个经典问题，用来描述两个个体在面对合作或背叛选择时的策略互动。它展示了为什么即使双方合作可以得到更好的结果，但在某些情况下，个人可能会选择不合作的行为。 囚徒困境的基本设定：假设有两个犯罪嫌疑人被警方逮捕，并分别关押审讯，无法沟通。警方没有足够的证据定罪他们所涉嫌的主要犯罪，但有足够的证据以较轻的罪名给他们定罪。为了鼓励两人自首，警方给出以下条件： 如果两人都保持沉默（合作），则他们会因为较小的罪行各被判1年监禁。 如果一方揭发（背叛）另一方而另一方保持沉默，则揭发者将被释放，而保持沉默的一方将被判5年监禁。 如果两人都互相揭发（互相背叛），那么他们都会因中等程度的罪行被判3年监禁。 用支付矩阵表示就是： 合作 (沉默) 背叛 (揭发) 合作 -1, -1 -5, 0 背叛 0, -5 -3,...
