交换悖论解析

1. 介绍 交换悖论(Exchange Paradox)或称双信悖论,由 Christensen and Utts 提出。 描述了一个情景:你面前有两个信封,你唯一知道的信息是里面一封装的钱是另一封的两倍。这时你拿起了一个信封,拆开看见其中有 x 元。而另一个人拿起了另一个信封。这时他问你:是否愿意交换信封? 悖论描述:当然应该换,原因在于对方的信封内有 50% 概率是 …

全文交换悖论解析

B树算法解析

主要梳理一下B树的插入和删除的方法和原理。 1. B树简介 又称多路平衡排序树 B树需要满足几个要求 节点的最多子树数量为B树的阶,通常用m表示 对每个节点,子树数量 = 关键字数量 – 1 每个节点至多有 m 棵子树,节点内的排列为 …

全文B树算法解析

求图的关键路径

1. 工程和时间说明 一个工程可以由多个活动和里程碑构成。活动可能对里程碑存在依赖性。在活动可并行的情况下,可以通过每个活动所需要的时间和依赖关系,计算出完成整个项目所需要的时间。 如以节点为里程碑,箭头为活动,一个项目的数据如下: 可以从一个入度为0的节点开始宽度优先顺序计算时间,也可以通过拓扑排序顺序进行计算,得到 比较容易得到每个里程碑的最早完成时间。 2. 关键路径说明 仅知道每个事件的可以的完成时间往往并不足够。工程中还想知道更多的关键信息,如: 哪些活动可以随意延期而不影响项目总进度? 哪些活动必须重点关注,一旦延期会拖延整个项目进度? 如果想提前整个项目的完成时间,可以最小地压缩哪几个活动? 这种问题在工程或者项目管理中非常常见,也因此引入了关键路径这个概念: 关键路径上的活动影响着整个项目的进度 …

全文求图的关键路径

红黑树C语言实现

1. 红黑树理解和推导详见 2. C语言代码 由于加了不少代码用于打印树和增改中的Log,所以整体会略长。 3. 测试运行结果 相关文章 KMP推导与C语言实现 红黑树理解和推导 Centos8中用Podman搭建 WordPress B树算法解析 数据结构重点-学习笔记

红黑树理解和推导

0. 前言 直接背红黑树的算法会比较难(由于情况较多),所以本文尝试用引导思路的方式去聊一聊红黑树,希望能在需要的时候,即使忘记也能将算法完整推导出来。 推导出来的代码和情况划分可能会有一些差异,但只要大思路一致,代码看着不同,执行效率上差异通常不大,这也是没必要强记各种情况的原因之一。 其实个人认为红黑树包含不少有趣的思维模式如递推、奇偶性、对称等等,知道其思想以后有可能也有助于其他问题的理解。 1.为什么要用红黑树 红黑树是二叉搜索树的一种。而二叉搜索树用于解决快速搜索的同时保持较高的改动效率(相对于有序数组)。 二叉搜索树也有很多种,相对来说最直观容易理解的是平衡二叉树,其整棵树或任意子树的左右子树深度差异不超过一。但为了这样的平衡,需要一点点代价:每次增删可能会要求更多的调整次数(具体为旋转)。并且为了提升增删的效率,往往需要为每个节点多记录一个深度值(通常这是小事)。 而红黑树则以牺牲绝对的平衡为代价,只要求其中的黑色节点完全平衡即可,以此换取了一些调整的便捷性空间,以此达到更高效的增删效率。 2.红黑树的要求 红黑树有几条要求(或者叫性质)。第一次看见往往都会一脸懵逼。但我们一条一条分析,就能知道每一条的意义。 (注:个人不把空的叶子结点视作叶子结点,能省一条对叶子结点的要求) 要求1 每个节点要不红黑要不黑色 …

全文红黑树理解和推导

KMP推导与C语言实现

0.说明 由于大部分文章直接从算法入手,即使配合丰富的动图,理解起来也有一些难度。在自己理解和实现后,用推导的思路聊一聊KMP。 当进行子字符串查找时,最简单的方法是尝试将母字符串的每一位依次看作首位,和目标字符串进行逐字符对比。这样非常易懂,但效率偏低。 如果母字符串长度为m,目标字符串长度为n,算法时间复杂度可能达到m*n。在基因工程等(字符集较少,相对容易大段重复,且目标串和母串都非常长)特殊情况下这样的时间复杂度是较难接受的。这时非常需要思考如何进行优化。 1.寻找可跳过的场景 相对容易想到(其实也很难)的一个方向是跳过一些无需重复的检查的场景,那我们先找一找有哪些场景可以跳过。 当我们有 开始,进行逐字符比较,从 对比至 发现不一致了。按最简单的做法,我们需要改变首字符位置重新匹配,如下 周而复始,可以发现迟早我们将对比至 而这个场景和当初场景1时的 是多么的相似啊(都将需要对比abc,且都能匹配上)。如果我们能跳过刚才这里已经对比过的abc。如果能避免重复对比,直接进行 至少能省下对比abc的时间。嗯,虽然看起来优化价值不大,如果能很低成本做,到至少还是稍有价值的(省了三次对比)。 …

全文KMP推导与C语言实现

游戏中策略性设计的坑

1.从一种常见的设计思路说起 由于策略往往是SLG的一个重点设计内容,相信大家对策略的思考应该不少。 而前段时间和一些策划聊关于策略的设计思路,却让我产生了一些疑惑。 比如当问及其自豪的设计时,不少策划会说增加了某某机制使游戏或系统更具策略性。例如在一个以梦幻模拟战玩法为基础的项目,进一步设计装备搭配、地形、天气等影响战斗的元素,使玩家能有更丰富多元的策略空间,并以此为亮点。 而一旦进一步询问为什么一定要更多元的策略?很策划都给不出进一步的理由,而是简单地将策略性奉为圭臬。但我却很怀疑策略性本身的价值,本文也将就这个问题展开讨论。 首先,策略是什么?可以简单的规约为对于“怎么做”的尝试和总结。详细一些,可以看作基于特定的目标,对特定的情境,寻找策略,得到特定可执行方案,且通过结果总结和重复优化策略。于是可以将策略抽象为一簇函数,是特定目标下,情景空间到方案空间的映射。 还可以把策略分为寻找和应用:寻找更像个泛函或者优化问题;应用相对比较简单,基于策略计算出方案就行。 比如对于德州扑克,其策略通常可以看作:基于最大化长期EV的目标,对特定手牌和公共牌各方形象和行为,用策略计算后得到诈唬或弃牌或价值注等特定执行方案,并通过实践结果加学习思考不断优化此策略。 如果我们这样理解策略,很明显,策略不应限于游戏:解谜题、解微分方程、优化神经网络、买房子亦或租房子、开车是否加塞、根据需求想案子、根据案子码开发。生活工作中几乎处处都需要寻找和使用策略,但显然,大部分对策略的寻找和应用过程并不让人开心,否则人人都应很容易且乐于成为学霸或沉迷于996。 理解为什么这样很容易,大脑消耗能量占了全身的20%,思考类工作占用的不仅是时间,还有体力。这是通常办公室工作也类似搬砖的生物学依据(误)。如此能耗,岂能随意思考挥霍,君不见浪费能量的生物已大批作死在了冰河世纪,而偏爱睡觉的考拉,喜欢吃糖的人类才苟且到了现代世界。由此可见懒很正常,懒可以是我们减少精力浪费的可能性(虽然也有副作用)。但看见数学就容易走神,捧起奶茶就停不下嘴,或许正是进化的体现。 基于这些理解对策略的理解,将游戏中的策略空间变多元变复杂,加大玩家的理解难度和计算成本显然是反人性的事,也和“策略越多元越有趣”的思路大相径庭。 2.策略设计的目的 策略设计在游戏中非常常见,但如果策略本身真不足以成为当今的亮点,那为什么那么多游戏要有策略呢?以及为什么确实又有不少玩家愿意花费时间和脑力进行游戏的策略研究总结和分享呢? 我们可以把策略相关行为的动机和行为本身分开进行理解。正如背单词通常比较难受,但是有比如原版书籍阅读目标,或单纯考试的驱动,则能使大家将本身负体验行为进行下去,并通过软件里的单词统计、考试成绩提升、读了感兴趣的原版书等外部正反馈内容反馈至背单词本身。 …

全文游戏中策略性设计的坑

Centos8中用Podman搭建 WordPress

1. 简单介绍 1.1 Podman Podman 是使用上非常类似 Docker 的容器工具,可以快捷管理镜像(带系统的Time Machine),快捷由镜像创建容器环境(类似虚拟机,但不模拟硬件层),也可以快速由容器制作出镜像进行保存或者分享。 由此非常适合我这样的新手基于 Podman 或 Docker 折腾和学习各种其他内容 …

全文Centos8中用Podman搭建 WordPress

公共知识与共有知识

1.经典问题 陶哲轩教授在多年前贴出过一道经典的蓝眼睛棕眼睛问题,后被广为流传为“红眼睛蓝眼睛问题”。 1.1 问题描述 一个岛上有100个人,其中5个人是红眼睛,95个人是蓝眼睛。每个人都无限聪明,且都遵守一系列规矩:不允许交流眼睛颜色,一旦知道自己眼睛颜色是红色则当晚必须自杀。同时岛上没有任何其他方式可以获悉自己眼睛的颜色,如反射等等。 有一天岛上来了一个游客,在离开的前一天,岛上所有人一起办了一场聚会。聚会期间游客不小心说了一句“没想到能在这里遇见红色眼镜的人”,说完后所有人都安静了下来。游客也很慌张,第二天匆匆离开。 离开后游客心想“岛上有红眼睛的人”这件事他们每个人早就知道,不应该有任何影响才对,于是放下了心。 没想到仅过了5天,岛上的5个红眼睛都自杀了。为什么? 1.2 传统分析 假设岛上只有一个红眼睛的人,因目光所及无红眼睛的其他人,显然会自知红眼且在第一晚自杀。 假设岛上有两个红眼睛的人,任意一人能且仅能看见一个红眼睛的人。如果假设自己不是红眼睛,则根据刚才的分析,应知对方会在第一夜自杀,如果没有,则知自己是红眼睛,且在第二晚自杀。 假设岛上有三个红眼睛的人,用类似上方所述逻辑,如果第二晚没有发现人自杀,则会在第三晚自杀。 … …

全文公共知识与共有知识