发布于：2019-06-17
冒泡排序——Bubble Sort 算法原理 它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。 算法描述 比较相邻的元素。如果第一个比第二个大，就交换它们两个； 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数； 针对所有的元素重复以上的步骤，除了最后一个； 重复步骤1~3，直到排序完成。 package main import "fmt" func main() { arr := []int{1, 3, 45, 32, …...
发布于：2015-06-02
问题 假设一个工程分为若干阶段，每个阶段需要耗费一定的天数，有些工程的开始必须以其他一个和多个工程的结束为前提。假设每次只能同时进行一个阶段，问如何安排执行工程的阶段确保工程能顺利的完成。 解决问题的思路 用一个有向图表示一个工程的各子工程及其相互制约的关系，其中以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向图为顶点表示活动的网，简称AOV (Activity On Vertex network)网。 在AOV网没有回路的前提下，我们将全部活动排列成一个线性序，使得若AOV网中有弧<i,j>存在，则在这个序列中,，i一定排在j的前面，具有这种性质的线性序列称为拓扑有序序 …...
发布于：2015-05-13
问题 假设要给5位工人分配不同的5项工作，每位工人都能完成这5项工作，但是每一位工人完成不同工作能带来的效益是不一样的，如何分配工作能使得总效益达到最大值。 解决问题的思路 对于这个问题最容易想到的解决思路是请举所有的排列组合，然后计算总的效益后取最大值即可。上述问题的因子是5，5求全排列一共有120种组合，对于计算机而言，循环求120次求解不是很难的问题，效率也高，但是一旦问题变大，例如因子变为20，那么时间复杂度和空间复杂度都会呈现几何级数级别的上升。 上述问题可定义为寻找带权二分图最佳匹配，解决这个问题的著名算法是KM算法。 对KM算法的描述，基本上可以概括成以下几个步骤： 初始化可行 …...
发布于：2015-05-07
问题 假设某一婚介单位要给10位男生和10位女生安排1对1相亲，每个男生都有自己喜好的几位女生（喜好程度假设相同）。问如何进行男女匹配使得男生最大限度的能和自己喜好的女生进行约会，即使得能安排到喜好女生的男生数目最大。 解决问题的思路 此问题实质上是经典的二分图最大匹配问题，求解二分图最大匹配问题的一个算法是匈牙利算法。 匈牙利算法是由匈牙利数学家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall定理中充分性证明的思想，它是部图匹配最常见的算法，该算法的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法。 二分图以及匹配相关概念 二分图 简单来说，如果图中点可以被分 …...
发布于：2015-03-09
问题 有三个和尚（或传教士）和三个妖怪（或食人怪）过河，只有一条能装下两个人（和尚或妖怪）的船，在河的任何一方或者船上，如果妖怪的人数大于和尚的人数，那么和尚就会有被吃掉的危险。你能不能找出一种安全的渡河方法呢？ 解决问题的思路 题目的初始条件是三个和尚和三个妖怪在河的一边（还有一条船），解决问题后的终止条件是三个和尚和三个妖怪安全地过到河的对岸，如果把任意时刻妖怪和和尚的位置看作一个“状态”，则解决问题就是找到一条从初始状态变换到终止状态的路径。 从初始状态开始，每选择一批妖怪或和尚过河（移动一次小船），就会从原状态产生一个新的状态，如果以人类思维解决这个问题，每次都会选择最佳的妖怪与和尚组 …...
发布于：2015-03-05
问题 有一个容积为8升的水桶里装满了水，另外还有一个容积为3升的空桶和一个容积为5升的空桶，如何利用这两个空桶等分8升水？附加条件是三个水桶都没有体积刻度，也不能使用其它辅助容器。 解决问题的思路 如果我们把某一时刻三个水桶中存水的容积称为一个状态，则问题的初始状态是8升的水桶装满水，求解的解出状态（最终状态）是8升水桶中4升水，5升水桶中4升水。穷举法的实质就是把从初始状态开始，根据某种状态变化的规则搜索全部可能的状态，每当找到一个从初始状态到最终状态的变化路径，就可以理解为找到了一种答案。 这样的状态变化搜索的结果通常是得到一棵状态搜索树，根节点是初始状态，叶子节点可能是最终状态，也可能是 …...