XYZ - 默认分类
type: channel
link: https://xyzshare.xyz/index.php/category/default
description: 只是一个默认分类
items: 戏说清朝十二帝
items: 网络协议的趣谈
items: 俄罗斯方块：“富贵险中求”算法
items: 小学二年级数学题，震惊了～
items: 趣味图论：哥德堡七桥问题
items: 如何看懂UML类图
items: 谈谈Go语言：Map-Reduce
items: 背包问题的变形二：限制背包（Bounded Knapsack）
items: 背包问题的变形一：无限制背包（Unbounded Knapsack）

戏说清朝十二帝
type: item
date: 2024-09-14T07:26:00+00:00
description: 引言清朝，作为中国历史上最后一个封建王朝，从1616年努尔哈赤建立后金政权开始，到1912年末代皇帝宣统帝退位，历经近300年的风雨。从一统天下的辉煌到内忧外患的衰落，清朝的兴衰历程不仅是中国历史的重要篇章，也是世界历史中一段波澜壮阔的经历。清朝的建立与发展，无疑是中国封建王朝历史中的一个重要转折点。努尔哈赤和他之后的皇帝们通过军事征服、政治谋略和文化融合，成功地将一个起初弱小的女真部落发展为一个横跨东北、华北、华中以及西北广大地区的庞大帝国。清朝在康熙、雍正、乾隆三位帝王的治理下，达到顶峰，创造了中国历史上著名的“康乾盛世”。然而，随着统治时间的推移，清朝也逐渐暴露出其自身的弱点和问题。自道光帝时期开始，内忧外患接踵而至。鸦片战争、太平天国运动、以及列强的干涉，使得清朝政府疲于应对，国家财政状况恶化，社会矛盾也日益尖锐。清末的改革尝试，如光绪帝的“百日维新”，也因保守势力的强大阻力而未能成功。清朝的十二位皇帝，每一位都在这个历史的舞台上留下了自己的印迹。他们或开创基业，或励精图治，或力挽狂澜，或无奈收场。通过他们的治国策略、政策措施以及个人性格，我们可以更全面地理解清朝这个封建王朝的全貌，以及其从辉煌走向衰落的必然性。本文将以清朝十二位皇帝为线索，深入探讨他们的生平及其治国理念，揭示他们在清朝历史中的重要性和影响力。希望通过这段历史的回顾，能够为读者提供一些有益的启示，帮助我们更好地理解历史，并从中汲取经验教训。一、清太祖努尔哈赤：开疆拓土的奠基者清朝的开创者努尔哈赤（1559-1626），其出身于建州女真部落，祖籍为今辽宁省新宾县赫图阿拉村。他的家族世代为建州女真部落的领袖，在一个相对分散、纷争不断的环境中成长。努尔哈赤幼时丧父，家庭背景并不显赫，但他凭借卓越的军事才能和政治智慧，逐步崛起为女真各部的领袖。努尔哈赤早年即展示出卓越的军事和政治才能。他通过征战、联姻和外交手段，逐步统一了建州女真。在1583年，努尔哈赤发动一系列攻势，击败了邻近的女真部落以及汉族军队，不断扩大其统治范围。努尔哈赤在1593年的九部联军之战中，以少胜多，彻底巩固了自己在女真各部中的霸主地位。努尔哈赤于1616年建立后金，定都赫图阿拉，正式称汗。这标志着女真部落从一个松散的联盟逐渐转变为一个中央集权的国家。为了进一步巩固其统治，努尔哈赤进行了多项改革。他实行八旗制度，将女真各部编入八个军事单位中，八旗不仅是军事组织，也是行政管理单位，有效提高了军事和行政效率。此外，他还注重发展农业和手工业，鼓励开垦荒地，增加粮食生产，以支持日益扩张的军事需求。在外交方面，努尔哈赤积极与明朝、大明周边的蒙古各部和朝鲜进行互动，既有征战，也有联姻和贸易。他的战略目标不仅限于统一女真各部，更是要与明朝争夺东北的统治权。1618年，努尔哈赤发布“七大恨”檄文，正式对明朝宣战，开启了长达数十年的明清战争。在努尔哈赤的领导下，后金军队屡次在战场上击败明军，逐步控制了辽东大片地区，为后来的入关奠定了基础。努尔哈赤的历史功绩不仅在于他建立了后金，统一了女真各部，更在于他为大清帝国的建立和发展奠定了坚实基础。他所创立的八旗制度、军事战略和行政管理模式，被其后继者保留并发扬光大，对清朝的巩固和扩张起到了至关重要的作用。努尔哈赤去世后，其子皇太极继位，继续推动后金向大清帝国的转变，最终完成了对中原的统一。努尔哈赤的一生充满了战斗与智慧，他那不屈不挠的精神和卓越的领导才能，使他成为一位名副其实的开疆拓土的奠基者，为清朝的辉煌奠定了基石。二、清太宗皇太极：缔造大清帝国的基础皇太极，原名爱新觉罗·皇太极，是清朝的第二位皇帝，也是清朝的奠基者之一。作为努尔哈赤的第八子，皇太极在其父去世后继位，继续推进满洲的统一和扩张。他在位期间，不仅从后金转变为大清，更是在经济、军事和文化方面进行了一系列的改革，为大清帝国的稳固和发展奠定了坚实的基础。从后金到大清在努尔哈赤去世后，皇太极继位于1626年。当时的后金虽然已经占据了辽东大部分地区，但内部仍需进一步整合，外部也面临明朝的强大压力。皇太极深知，要想建立一个持久稳固的政权，仅靠武力是不够的，还需要在制度和文化上进行深远的变革。1636年，皇太极正式改国号为“大清”，并自称“皇帝”，宣告了一个全新帝国的诞生。这一举措不仅增强了后金统治集团的凝聚力，还为未来的入关和统一全国做好了准备。经济改革为了增强国家的经济实力，皇太极推行了一系列重大改革。首先，他倡导农业生产，鼓励满洲人学习汉族的农业技术，提高粮食产量，以解决军粮供应问题。其次，他重视商业发展，尤其是东北地区的皮毛、药材等特产贸易，通过与蒙古、西伯利亚等地的互市，增加了清朝的经济收入。此外，皇太极还注重财政管理，通过严格的税收制度，确保了国家财政的稳定。军事改革在军事方面，皇太极延续了努尔哈赤的八旗…

网络协议的趣谈
type: item
date: 2024-09-13T11:21:00+00:00
description: 引子：网络协议究竟是什么？我们每天通过互联网进行各种活动：购物、聊天、刷视频，但你是否想过这些数据是如何传输的？在这一章，我们将揭开网络协议的神秘面纱，用通俗易懂的语言解释其基本概念和重要性。首先，想象一下你在现实生活中给朋友打电话。你需要知道对方的电话号码，拨号，然后等待接通。这个过程中有很多规则：比如你要先拿起电话，听到拨号音后再拨号码，接通后要等对方接听才能开始对话。这一系列规则确保了你能顺利找到对方并进行交流。网络协议就像这些规则一样，是计算机网络中进行信息交换的标准和规范。它们定义了数据如何在网络上进行发送、接收和解释。没有这些协议，就像没有电话通话的规则，我们的计算机将无法相互理解和通信。你可能会问，为什么需要这么多协议？想象一下我们日常的网络活动：发送邮件、浏览网页、观看视频、在线购物……每一种活动都涉及不同类型的数据和不同的传输要求。为了满足这些多样化的需求，互联网发展出了多种网络协议，每种协议负责特定类型的通信。例如，浏览网页时最常用的协议是HTTP（超文本传输协议），它定义了浏览器和服务器之间交换网页内容的方式。发送和接收电子邮件则主要依靠SMTP（简单邮件传输协议）和POP3/IMAP（邮局协议/互联网消息访问协议）。这些协议各有其特定的功能和工作原理，但共同确保了数据在互联网中可以可靠地传输和接收。网络协议的重要性不言而喻，它们是互联网的基石，使得不同设备、不同平台之间能够互相通信，构建出一个全球性的网络。在接下来的章节中，我们将深入探讨一些关键的网络协议，用生动的例子和通俗的语言帮你理解这些看似复杂但实际上非常有趣的技术细节。准备好了吗？让我们一起踏上这段网络协议的探索之旅吧！第一章：TCP/IP - 守护互联网的隐形英雄在互联网的世界里，TCP/IP协议就像是交通规则，指引着数据包的正确方向。你可以把它们想象成邮局的工作人员，负责把信件（数据包）从一个地点送到另一个地点。尽管这些信件要经过错综复杂的路线，但TCP/IP协议确保它们最终能够准确无误地到达目的地。TCP：可靠的传输保障首先，让我们认识一下TCP（Transmission Control Protocol），它是保证数据可靠传输的关键人物。可以把TCP想象成一辆运送贵重包裹的快递车，它不仅要保证包裹送达，还要确保包裹的完整性。三次握手：确保连接稳固TCP最著名的特性之一是“三次握手”机制。想象一下你在打电话，第一次拨号就是请求连接，对方接听并回应表示可以接通，这就是第一次握手；你确认收到回应，并再次确认连接状态，这就是第二次握手；对方收到你的确认并最终确认连接成功，这就是第三次握手。通过这三次握手，TCP确保双方都准备好进行数据传输。分段和重传：确保数据完整TCP还负责将数据分成小片发送，并在接收端重新组装这些数据片。如果有任何数据片在传输过程中丢失，TCP会自动重传。好比邮局会分批次运送你的包裹，并在丢失时重新发送。IP：寻找最佳路径有了TCP的可靠传输保障，还需要IP（Internet Protocol）来负责找路。IP就像是地图导航系统，它决定数据包通过哪条路线才能最快最安全地到达目的地。IP地址：互联网的门牌号每一台连接到互联网的设备都有一个独一无二的IP地址，就像每个房子都有一个门牌号。IP地址分为IPv4和IPv6两种，IPv4是由四组数字组成的，例如192.168.1.1，而IPv6则是为了应对互联网设备数量爆发式增长而设计的，它由八组16进制数字组成，如2001:0db8:85a3:0000:0000:8a2e:0370:7334。路由选择：智能导航IP协议不仅负责地址管理，还要选择最佳路径。每个数据包在传输过程中会经过多个路由器，这些路由器就像是高速公路上的每个路口，决定数据包的下一跳。如果一个路口堵车了，IP协议会智能地选择其他可行路径，确保数据包能顺利到达。小故事：快递小哥的冒险假设你要给远方的朋友寄一份生日礼物，过程中你会先把礼物交给快递公司（就像数据由应用层交给传输层），快递公司会把大件礼物拆成多个小包裹（数据分段），并用快递单号（序列号）标记。每个小包裹会通过不同的路线送往朋友家（路由选择），快递公司会确保每一个包裹都安全送达。如果某个包裹丢失，快递公司会重新发送（重传机制）。最终，朋友会收到所有包裹并把它们重新组装成一份完整的礼物（数据重组）。通过这个小故事，你应该对TCP/IP协议有了更直观的理解。它们是互联网数据传输的无名英雄，确保我们每天都能顺畅地上网、通讯和获取信息。在接下来的章节中，我们将继续探索更多有趣且重要的网络协议，敬请期待！第二章：HTTP和HTTPS - 网站通信的语言在互联网世界中，HTTP和HTTPS就像是网站之间的语言翻译官，帮助我们与远程服务器进行有效的沟通。那么，这两位“翻译官”…

俄罗斯方块：“富贵险中求”算法
type: item
date: 2022-07-12T10:22:00+00:00
description: 导语作为80后，小时候一定玩过一款经典游戏，俄罗斯方块，英文名称Tetris。玩的画面在脑海中已是“上古”时期的事情，但也并不陌生，因为刷视频时，偶尔还能看到顶尖世界高手对决，他们玩的俄罗斯方块难度极大，游戏模式是对决，比谁的分数高，有些比赛到最后不仅自己消砖块得分，而且还可以通过得分不停给对手制造麻烦。看到鹅厂组织的一次极客挑战赛，主题就是俄罗斯方块游戏，当然游戏名称叫“鹅”罗斯方块，蛮鹅厂风格的，可可爱爱。我比较感兴趣，当时也报名参加了，最后是在2000+入场选手排名在9位，比赛结束后，我又花了点时间调试了自己的算法参数，最终比赛分数可以刷进TOP3。谨以此文，记录自己的所思所想。如何活着第一步想到的是，如何“活着”，就和当前经济形势下，各行各业都得考虑先“活着”，能不能得到高分其次，先得“不死”。我自己写了一个俄罗斯方块的游戏界面，和传统俄罗斯方块游戏一样，如何拼搭这些小图形，让高度不超过游戏规定的高度，满行就会消除，消除的行数有4种情况1行、2行、3行和4行。针对如何活着的俄罗斯方块AI算法比较多了，全网比较有名的是Pierre Dellacherie算法。我这里搜索到一篇El-Tetris – An Improvement on Pierre Dellacherie’s Algorithm，大家可以参考下。首先，分析下俄罗斯方块中方块的种类，一共有7种图形：上面图中有7种不同的形状，我在代码里面的表示为坐标法，以(0, 0)为原点，标示周围那几个点对应图形需要占用。BrickShapes = [ # I [[[-2, 0], [-1, 0], [0, 0], [1, 0]], [[0, -1], [0, 0], [0, 1], [0, 2]]], # L [[[-2, 0], [-1, 0], [0, 0], [0, 1]], [[0, 0], [0, 1], [0, 2], [1, 0]], [[0, -1], [0, 0], [1, 0], [2, 0]], [[-1, 0], [0, -2], [0, -1], [0, 0]]], # J [[[-2, 0], [-1, 0], [0, -1], [0, 0]], [[-1, 0], [0, 0], [0, 1], [0, 2]], [[0, 0], [0, 1], [1, 0], [2, 0]], [[0, -2], [0, -1], [0, 0], [1, 0]]], # T [[[0, -1], [0, 0], [0, 1], [1, 0]], [[-1, 0], [0, -1], [0, 0], [1, 0]], [[-1, 0], [0, -1], [0, 0], [0, 1]], [[-1, 0], [0, 0], [0, 1], [1, 0]]], # O [[[-1, 0], [-1, 1], [0, 0], [0, 1]]], # S [[[-1, 0], [-1, 1], [0, -1], [0, 0]], [[-1, -1], [0, -1], [0, 0], [1, 0]]], # Z [[[-1, -1], [-1, 0], [0, 0], [0, 1]], [[-1, 0], [0, -1], [0, 0], [1, -1]]] ]比如竖棍“I”的图形，有两种rotation，所以有两组坐标的标示方式，其他图形类似，只不过rotation数量不同： # I, two rotations [[[-2, 0], [-1, 0], [0, 0], [1, 0]], [[0, -1], [0, 0], [0, 1], [0, 2]]], El-Tetris算法是传统AI人工智能，不要因为人工智能，就觉得很复杂，其实不论传统的AI算法还是目前深度学习的人工算法，一般都不会很复杂，深度学习AI算法不在此文讨论范围。基本上传统AI算法就是列举所有的可能性，通过计算预先建模的公式，评估最优秀的一个局面，做出选择，一直循环往复，直到游戏结束。我们看下El-Tetris算法的公式：f(x) = b0x0+b1x1+b2x2...bnxn其中x0,x1,x2...xn都是一些特征，b0,b1,b2...bn是一些系数（通过数学方法或者机器学习方法等手段推算出的经验值），对应特征和系数相乘相加之后，得到的就是当前局面+此选择的局面评估分数，是不是很简单，看上去是一个线性公式，但是效果出奇的好，原因还是在于每一个特征x的合理性以及系数b的合理性。系数b不需要我们实现，就是一组常数字，作者说是通过particle swarm optimization寻找到的，具体怎么找，我也不太清楚，先拿来用吧。另外要提一下，算法可以通常可以考虑当前图形+下一个图形，也可以只考…

小学二年级数学题，震惊了～
type: item
date: 2022-06-17T14:07:00+00:00
description: 上海疫情封在家中有三个月，辅导了小孩子功课，每每小孩遇到不会做的题目，比她更着急。有时也会想起自己学生时代的样子，遇到难题，心中升起必须克服难题的决心，现在自己娃，怎么没有我当年的风采了。哈哈，扯远了，这两天网上看到一道小学二年级的题目，其实我之前做过类似的题目，但是当下还是震惊了，怎么现在小学二年级题目有这么难？题目是这样的：配合网友的回复，我马上想到了之前类似的问题，说是25匹马，5个赛道，至少比几场保证找出最快的2匹马。赛马这题答案我记得很清楚7场比赛，先分组进行小组赛：首先一个虚线框就是一场比赛，上来25匹马，分5组，进行5场预赛。5组比赛会得到组内的名次，比如A组，A1->A2->A3->A4->A5，每组第一名就是A1，B1，C1，D1和E1，然后第一名之间安排一场决赛：假设结果就是A1->B1->C1->D1->E1(真正结果不重要，不管怎么样，总能推理出最后的结论)，这时候我们就通过4场比赛，知道了第一名是A1，那第二名是谁呢，是不是B1，不一定哦，有可能是在小组赛中被A1淘汰的A2，所以安排场附加赛吧，A2 vs B1：附加赛之后，就能知道前两名了。话说回小学二年级赛车这道题目，其实思路一模一样，就是通过小组赛->决赛->附加赛，完成前两名的确认，也就是说赛车的话，通过至少5场比赛，保证找出前两名的赛车。作为小学二年级的题目很变态了吧，但是出题的人还多问了一句，怎么证明这件事情呢，为什么通过4场比赛一定不能保证找出前两名呢？这个证明难倒我了，抓耳挠腮半天，没想出来。然后我就看了下出题老师的分析，茅塞顿开，原来还可以使用图论+反正法来证明。大致的过程如下：首先把每一辆赛车想象成点，那么我们一共有9辆赛车，一共9个点，每场比赛，只能进行3辆赛车的比拼，每次比拼完，我们会有一个名次，紧挨着的前后两名之间，使用一条有向边连接，这个我文字讲得有点绕口，一图解千愁：圆圈表示赛车，1号比2号快，2号比3号快，所以每次比赛，我们仅仅能得到2条有向边，如果进行4场比赛，那么总共的有向边数量是4*2 = 8条，而赛车的数量是9，也就是节点数量是9，8条边，9个点，如果要保证所有边都连接到一张图中，不能出现环，否则边的数量不够。出现环就意味着9个点形成了若干个分开的子图，上面图中9个节点，分为了两个子图，那么就会有一个问题，第一名都不知道是谁，为什么？因为在1～8节点所在的图中，1号赛车最快，9号赛车单独成子图，9号赛车和谁都没有比过，那么到底9号和1号赛车谁快呢？不知道。所以8条边，安排的比赛结果，划分为多个子图，这样是无法确认前两名的。那我们4场比赛的结果，如何是可以前两名的图形呢，如下：左边就是分3场比赛（1、4、7，2、5、8和3、6、9分别比赛），得到结果后，4、2、3比一次，结果是4->2->3，转化这张单图，得到右侧的结果，其实就是一个树形的图，那么前两名就是1、4号赛车。这样我们很容易举出反例，你不是就8条边么，我最后4、2、3的结果是2->4->3，图就变成非树形图，如下：这样又回到之前多个子图的问题，我们是没法确认1号赛车和2号赛车谁快的，也就没法真正确认前两名是哪两辆赛车。OK，至少5场比赛，而非4场比赛保证找出最快的2辆赛车得证。是不是挺难的，至少我是没有想出来，通过图论+反证法证明这个数据结论，由衷发出感慨，活学活用好难啊，能做到的大佬，真的太强了。

趣味图论：哥德堡七桥问题
type: item
date: 2022-04-05T13:31:00+00:00
description: 导语最近因为上海的疫情，被关在家里，有点闷坏了，小区里的快递或者外卖，也不允许下楼取，由小区保安统一配送，保安还需要定时去巡查，看看小区有没有违规下楼，小区有没有人在随意走动，我们小区有8栋楼，虽然不大，但楼宇间有绿化带阻隔，加上小区保安人手有限，怎样合理规划路径（保证所有路径都经过，又不重复走），倒是一个有趣的图论问题。我突然想到了哥尼斯堡七桥经典问题，相传18世纪初普鲁士的哥尼斯堡，有一条河穿过，河上有两个小岛，有七座桥把两个岛与河岸联系起来（如下图）。有个人提出一个问题：一个步行者怎样才能不重复、不遗漏地一次走完七座桥，最后回到出发点。自己画的图有点丑，但应该比较好理解，A、D是两个小岛，B、C是两边的陆地。哥尼斯堡的七座桥1736年29岁的欧拉向圣彼得堡科学院递交了《哥尼斯堡的七座桥》的论文，在解答问题的同时，开创了数学的一个新的分支——图论与几何拓扑，也由此展开了数学史上的新历程。欧拉的名声如雷贯耳，往往成功的大师，都是有心人，对生活中遇到的问题，愿意进行深入的分析和思考。在论文中，欧拉对哥尼斯堡的七座桥问题进行了抽象与转换，他认为岛和两边的河岸都是点，桥就是连接点的边，那么能否不重复地走过所有的桥，又不重复，就转换为能否一笔画出对应的图（点和边组成的图），并且没有重复的笔画。首先，我们来了解下关键的一个概念：度数，即每个点连接的边数量。那么可以把点分为：奇点：点的度数为奇数的点，即连接此点的边数量为奇数；偶点：点的度数为偶数的点，即连接此点的边数量为偶数；我们使用一笔画出一个图来，如下图所示，红色的点就是偶点，蓝色的点就是奇点，落笔的点就是奇点之一，另外一个奇点就是收笔的点。中间的所有点都是偶点，一进一出，必然度数是2、4、6、8等情况。而奇点有2个，分别是落笔的点和收笔的点，不可能出现第三个奇点。如果把落笔点和收笔点连接起来，理解为两个奇点连接起来，那么图中所有的点都是偶点。如下图所示：在1736年，大数学家欧拉提出了一个图如果一笔不重复地画出来，需要的充要条件是，该图只有0个或者2个奇点，如果存在0个奇点，图中存在欧拉回路，如果存在2个奇点，图中存在欧拉路径。回到哥尼斯堡七桥问题，抽象出来的图如下：可以看到4个点都是奇点，所以欧拉说，不可能做到不重复、不遗漏地一次走完七座桥。既然这个图不能一笔画出来，那么究竟几笔能画出来，欧拉也给了答案。图的奇点总是成对出现的，因为有一个落笔点，必然会有一个收笔点，如果一张图有2k(k >= 1)个奇点，那么欧拉认为有以下3个推论：此图可以通过k笔画出添加k-1条边，保证存在欧拉路径添加k条边，保证存在欧拉回路回到我们小区送东西的场景，简化为下图：一共8栋楼，如果小区保安走一遍，保证每条路径都要走到，又不能重复，存在这样的路径，比如：很幸运，我们小区还是有这样一条路径，可以保证保安巡查时不走重复路的，但又走遍了所有的角落。有些实际生活中的场景，也适合使用欧拉回路来规划，比如在旅游景区的线路规划（游客都不希望走回头路，但又希望每一条路都走一遍），也比较适合。如上图，怎么添加线路，使得可以保证旅游景区存在欧拉回路，是不是特别有意思和实用？结束语图论中有很多有趣的问题，显然300多年前，欧拉打开了一扇图论的大门，还有一些问题，比如需要走遍图中所有点一次（但不能重复经过点），边不需要都走，有没有合适的判定方法或者算法，显然欧拉回路或者路径是不适用的，这个也有相应的图论算法，叫哈密尔顿回路/路径，单独写文章介绍，在此不详述了。

如何看懂UML类图
type: item
date: 2022-03-14T03:20:00+00:00
description: 导语作为程序员，时常在一些技术书中看到这些UML类图表示，大部分能看懂意思，但那些箭头和标记很容易混淆。其实UML类图是一门精准的语言，每个符号都是有着精确的程序语义的，在这篇文章中，通过自己整理的一个例子，举例说明，帮助自己加深理解。UML类图例子其实多看多用就熟悉了，举一个例子，来看这样一幅图，其中就包括了常见UML类图的基本图示法。首先看“交通工具”矩形框，它就代表一个类(Class)。类图分三层，第一层显示类的名称，如果是抽象类，则就用斜体显示。第二层是类的特性，通常就是字段和属性。第三层是类的操作，通常是方法或行为。注意前面的符号，‘+’表示public，‘-’表示private，‘#’表示protected。然后注意左下角的“翻越”，它表示一个接口图，与类图的区别主要是顶端有<<interface>>显示。第一行是接口名称，第二行是接口方法。接口还有另一种表示方法，俗称棒棒糖表示法，比如图中的警车类就是实现了“鸣笛”的接口。interface ICross { // 翻越 void Cross(); } interface IWhistle { // 鸣笛 void Whistle(); } 接下来就可以看下类与类，类与接口之间的关系了。可以观察交通工具、车、轿车、卡车、越野车和警车之间的关系，他们都是继承关系，用空心三角形加上实线来表示。例子中的几种车中，越野车是可以翻越小山丘的，我让它实现了翻越接口，实现接口就用空心三角形加上虚线来表示。、再看卡车和法规（这个例子可能不是特别恰当，但是我想不当更合适的），卡车一般都是运送货物，需要遵守政府的货运相关的法规，限重多少，和卡车能否上路行驶息息相关，卡车司机需要“知道”政府法规，当一个类‘知道’另一个类时，可以用关联（association）。关联关系用实线箭头来表示。越野车队和越野车这两个类，生活中，开越野车的车友喜欢加入俱乐部，参加越野车活动，一个车队可以有多辆车，所以它们之间就满足聚合（Aggregation）关系。聚合表示一种弱的‘拥有’关系，体现的是A对象可以包含B对象，但B对象不是A对象的一部分。聚合关系用空心的菱形+实线箭头来表示。合成（Composition，也有翻译成‘组合’的）是一种强的‘拥有’关系，体现了严格的部分和整体的关系，部分和整体的生命周期一样，在这里车和轮胎就是合成（组合）关系，因为它们是部分和整体的关系，并且轮胎和车的生命周期是相同的。合成关系用实心的菱形+实线箭头来表示。另外，你会注意到合成关系的连线两端还有一个数字‘1’和数字‘2’，这被称为基数。表明这一端的类可以有几个实例，很显然，一辆车应该有5个轮胎（算上备胎）。如果一个类可能有无数个实例，则就用‘n’来表示。关联关系、聚合关系也可以有基数的。交通工具的几大特征，比如类型，路上、水上还是空中的交通工具，交通工具都需要燃料驱动，需要机油保养，他们之间是依赖关系（Dependency），用虚线箭头来表示。abstract class Vehicle { // 增加能源 void Fill(Energy energy); // 保养 void Maintain(EngineOil oil); } 结论编程是一门技术，更加是一门艺术，不能只满足于写完代码运行结果正确就完事，时常考虑如何让代码更加简练，更加容易维护，容易扩展和复用，只有这样才可以真正得到提高。写出优雅的代码真的是一种很爽的事情。UML类图也不是一学就会的，需要有一个慢慢熟练的过程。所谓学无止境，其实这才是理解面向对象的开始呢。

谈谈Go语言：Map-Reduce
type: item
date: 2022-01-03T14:05:00+00:00
description: 导语函数式编程的中非常重要的Map、Reduce、Filter的三种操作，这三种操作可以让我们非常方便灵活地进行一些数据处理——我们的程序中大多数情况下都是在到倒腾数据，尤其对于一些需要统计的业务场景，Map/Reduce/Filter是非常通用的玩法。例子Map示例下面的程序代码中，我们写了两个Map函数，这两个函数需要两个参数：一个是字符串数组 []string，说明需要处理的数据一个字符串另一个是一个函数func(s string) string 或 func(s string) intfunc MapStrToStr(arr []string, fn func(s string) string) []string { var newArray = []string{} for _, it := range arr { newArray = append(newArray, fn(it)) } return newArray } func MapStrToInt(arr []string, fn func(s string) int) []int { var newArray = []int{} for _, it := range arr { newArray = append(newArray, fn(it)) } return newArray } 整个Map函数运行逻辑都很相似，函数体都是在遍历第一个参数的数组，然后，调用第二个参数的函数，然后把其值组合成另一个数组返回。于是我们就可以这样使用这两个函数：var list = []string{"Hao", "Chen", "MegaEase"} x := MapStrToStr(list, func(s string) string { return strings.ToUpper(s) }) fmt.Printf("%v\n", x) //["HAO", "CHEN", "MEGAEASE"] y := MapStrToInt(list, func(s string) int { return len(s) }) fmt.Printf("%v\n", y) //[3, 4, 8] 我们可以看到，我们给第一个 MapStrToStr() 传了函数做的是 转大写，于是出来的数组就成了全大写的，给MapStrToInt() 传的是算其长度，所以出来的数组是每个字符串的长度。我们再来看一下Reduce和Filter的函数是什么样的。Reduce示例func Filter(arr []int, fn func(n int) bool) []int { var newArray = []int{} for _, it := range arr { if fn(it) { newArray = append(newArray, it) } } return newArray } var intset = []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10} out := Filter(intset, func(n int) bool { return n%2 == 1 }) fmt.Printf("%v\n", out) out = Filter(intset, func(n int) bool { return n > 5 }) fmt.Printf("%v\n", out) Filter示例func Filter(arr []int, fn func(n int) bool) []int { var newArray = []int{} for _, it := range arr { if fn(it) { newArray = append(newArray, it) } } return newArray } var intset = []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10} out := Filter(intset, func(n int) bool { return n%2 == 1 }) fmt.Printf("%v\n", out) out = Filter(intset, func(n int) bool { return n > 5 }) fmt.Printf("%v\n", out) 下图是一个比喻，其非常形象地说明了Map-Reduce是的业务语义，其在数据处理中非常有用。业务示例通过上面的一些示例，你可能有一些明白，Map/Reduce/Filter只是一种控制逻辑，真正的业务逻辑是在传给他们的数据和那个函数来定义的。是的，这是一个很经典的“业务逻辑”和“控制逻辑”分离解耦的编程模式。下面我们来…

背包问题的变形二：限制背包（Bounded Knapsack）
type: item
date: 2021-08-27T23:27:00+00:00
description: 导语有了之前两篇关于背包问题文章的积累，《一文搞懂经典0-1背包问题》和《背包问题的变形一：无限制背包（Unbounded Knapsack）》，今天讨论的背包问题另一个变形问题，限制背包（Bounded Knapsack）就容易理解得多了。限制背包的意思是每样物品不是只有一件，也不是无限数量，给定一个限制数量，求取装满背包获得的最大价值。那么这个问题利用之前积累的知识很容易解决。背包问题可以由浅入深，而且层层递进，经过这次的学习，我发现迷上了这个经典的NPC问题。限制背包（Bounded Knapsack Problem）最容易想到的还是把每件物品按照数量限制（naive），一件件取出，然后更新之前定义的dp数组（见《一文搞懂经典0-1背包问题》），OK，源代码修改下之前无限制背包问题的，也很简单：func knapsackBounded1(w []int, v []int, m []int, W int) int { n := len(w) dp := make([]int, W+1) for i := 0; i < n; i++ { for j := 0; j < m[i]; j++ { knapsack01(dp, w[i], v[i]) } } r := 0 for i := 0; i <= W; i++ { if dp[i] > r { r = dp[i] } } return r }数组m给出的是物品的数量限制。算法时间复杂度O(NW*Sigma(m[i]))，空间复杂度O（W）（已经通过滚动数组优化）。如果要进行优化，自然想到了之前smarter的方式，按2的幂次方去组合出虚拟物品来，这样考虑的物品数量大大降低了，但是恶心的是，不像无限制背包，我们每件物品都可以随便取，直到超过重量上限。这里，我们需要按两种方式考虑，如果m[i]w[i] >= W，OK，那直接使用knapsackComplete更新dp数组即可，如果m[i]w[i] < W，那么我们尝试尽可能拆分虚拟物品，比如m[i] = 19，那么可以拆出的虚拟物品组合为（1, 2, 4, 8)倍原来的物品，剩下19-(1+2+4+8)=4倍物品，我们单独考虑。代码如下，稍微复杂些，仔细看，应该不难理解：func knapsackBounded2(w []int, v []int, m []int, W int) int { n := len(w) dp := make([]int, W+1) for i := 0; i < n; i++ { if m[i] * w[i] >= W { knapsackComplete(dp, w[i], v[i]) continue } left := m[i] for k := 0; k < math.Ilogb(float64(m[i])); k++ { knapsack01(dp, w[i] * 1<<k, v[i] * 1<<k) left -= 1<<k } for j := 0; j < left; j++ { knapsack01(dp, w[i], v[i]) } } r := 0 for i := 0; i <= W; i++ { if dp[i] > r { r = dp[i] } } return r }算法时间复杂度O(NW*Sigma(m[i]))，空间复杂度O（W）（已经通过滚动数组优化）。性能测评参数设置，W=100000，w取值[11, 220]，长度10001，v取值[7, 33]，m取值[5, 100]，测试性能如下：knapsackUnbounded3=281800, time_cost=778.899197ms knapsackBounded2=195626, time_cost=16.464975377s knapsackBounded1=195626, time_cost=1m27.138384055s 看上去这个参数下，基本上算法耗时都很高了，相当于有10w件不同的商品，虚拟一下，knapsackBounded2的商品数量达到了200w左右，然后通过动态规划计算（重复子问题其实没那么高），如果可以大部分进入到m[i] * w[i] >= W，性能会比较好些，试了下面这组参数，W=100000，w取值[1000, 2000]，长度10001，v取值[7, 33]，m取值[1000, 2000]，性能结果如下：knapsackUnbounded3=3168, time_cost=769.803021ms knapsackBounded2=3168, time_cost=1.718676383s knapsackBounded1废了，算不出结果到此为止，背包问题的讨论蛮多了，我感觉自…

背包问题的变形一：无限制背包（Unbounded Knapsack）
type: item
date: 2021-08-21T14:01:00+00:00
description: 导语之前写过一篇《一文搞懂经典0-1背包问题》，n个物品放入包中，每件只能选择放一次，放过之后就不能再放了。当时分析了三种算法，一个是递归搜索（在n<20，W特别大时适用），一种是记忆化递归，最后是动态规划算法，记忆化递归和动态规划都依赖于子问题有重复，否则，最糟糕的情况下，每件物品都是不同的2的幂次方重量，就会退化到递归搜索。今天要再深入讨论两个变形题目，一个是无限制的背包问题，一个是有限制的背包问题，今天先讨论下无限制的背包问题。无限制背包（Unbounded Knapsack Problem）简单说每件物品没有数量限制，随便放入包中。关于这个算法，有三种解法。基本思路都是虚拟出所有的物品，因为有总重量限制，每件物品放入背包中的数量总是有上限的。先看下0-1背包问题动态规划实现方法的源码：func knapsack01D(w []int, v []int, W int) int { n := len(w) dp := make([]int, W+1) for i := 0; i < n; i++ { for j := W; j >= w[i]; j-- { dp[j] = max(dp[j-w[i]]+v[i], dp[j]) } } r := 0 for i := 0; i <= W; i++ { if dp[i] > r { r = dp[i] } } return r } 这里把更新dp数组的部分，包装成一个函数knapsack01，如下：func knapsack01(dp []int, w int, v int) { W := len(dp) for j := W-1; j >= w; j-- { dp[j] = max(dp[j-w]+v, dp[j]) } } 第一种方法，是把每件东西可以选择数量都虚拟出来（naive），比如第i件重量w[i]，那么第i件东西最多有W/w[i]件，然后就变成每件虚拟的物品扔给knapsack01更新dp数组的部分。func knapsackUnbounded1(w []int, v []int, W int) int { n := len(w) dp := make([]int, W+1) for i := 0; i < n; i++ { m := W/w[i] for j := 0; j < m; j++ { knapsack01(dp, w[i], v[i]) } } r := 0 for i := 0; i <= W; i++ { if dp[i] > r { r = dp[i] } } return r }算法时间复杂度为O(NW^2)，空间复杂度O(W)（已经通过滚动数组优化）。第二种方法，控制虚拟出的物品数量更少（smart），以不同的2的幂次方虚拟出物品，对于第i件物品，最多能放W/w[i]件，第i件物品的虚拟物品为，w[i]2^0、w[i]2^1、w[i]2^2……w[i]2^logW/w[i]，代码如下：func knapsackUnbounded2(w []int, v []int, W int) int { n := len(w) dp := make([]int, W+1) for i := 0; i < n; i++ { m := math.Ilogb(float64(W)/float64(w[i])) for k := 0; k <= m; k++ { knapsack01(dp, w[i] << k, v[i] << k) } } r := 0 for i := 0; i <= W; i++ { if dp[i] > r { r = dp[i] } } return r }算法时间复杂度为O(NWlogW)，空间复杂度O(W)（已经通过滚动数组优化）。第三种方法，实现上是最简单的，但也是最难想到的，原先我们做dp更新时，故意将j的迭代顺序从W最大值逆向迭代到当前物品重量w，其实我们只需要改为顺向迭代即可，更新dp函数knapsack01改为knapsackComplete，代码如下：func knapsackComplete(dp []int, w int, v int) { W := len(dp) for j := w; j < W; j++ { dp[j] = max(dp[j-w]+v, dp[j]) } } 整体的背包问题代码变为：func knapsackUnbounded3(w []int, v []int, W int) int { n := len(w) dp := make([]int, W+1) for i := 0; i < n; i++ { knapsackComplete(dp, w[i], v[i]) } r := …