一，LoadingBalance问题描述：有m台相同的机器及n个作业，其中m={M(1),M(2),……M(m)}、n={J(1),J(2),……J(n)}。每个作业都有一个处理时间，记为t。如，;t(j)表示作业J(j)的处理时间。任意机器在某个时刻只能处理一个作业；一旦某个作业被调度到机器上处理，它就不能被抢占，直至它被处理完才能处理下一个作业。问：如何分配作业，使得处理完所有的作业所需的时间最少？由于该问题是NPC的，因此很难找到该问题的最优解（精确解），下面用贪心算法求解一个近似解。二，LoadingBalance问题的两倍贪心近似解贪心策略：总是优先给当前机器中负载最小的机器分配作业设BS(bestsolution)为LoadingBalance问题的最优解。BS表示处理完所有的作业所需的最少时间，则：1）BS>=max{t(1),t(2)……t(n)}     耗时最长的作业总会在某台机器上执行，BS一定比某个单一作业的执行时间要长（可...

参考《算法导论第二版P222页）一，如何把现实的问题转变成数学问题？即数学建模的思路？1，问题描述：现有一组相互竞争的活动，如何调度能够找出一组最大的活动（活动数目最多）使得它们相互兼容？2，问题转化：首先，按活动的结束时间单调递增进行排序。那么，为什么要按结束时间排序呢？这个问题留到后面解释。其次，定义合适的问题子空间，即定义集合S(i,j)。问题子空间描述的是现实生活中的问题，而集合S(i,j)则是数学概念，通过某种方式定义一个合适的集合将问题子空间的解转化为集合的解（即求出集合中符合某种条件的所有元素）。3，那么问题来了，怎样才能让定义的这个集合问题能够描述现实问题呢？----a，将S(i,j)中元素表示成与活动a(i)、a(j)兼容的活动b，将活动a(1)、a(2)……a(i)、a(i+1)、……a(j)、a(j+1)……a(n)按照结束时间单调递增排序！每个集合元素有一个特征：有开始时间和结束时间。这就是为什么要按结束时间单调递增排序的原因，因为只有这样，才能够成功的建模，将现实问题转化成数学...

1，对元素进行排列时，元素之间需要进行比较，因此需要实现Comparable<T>接口。即，<TextendsComparable<T>>.更进一步，如果允许待比较的类型可以和它的父类型进行比较，则需要写成：<TextendsComparable<?superT>，其中<?superT>表示T的任意超类。2，InsertionSortArray.java类实现了从小到大顺序以插入排序的方式对数据进行排序。3，insertionSort方法负责对每一个元素进行排序，insertInOrder方法将待排序的元素插入到合适的位置，相当于执行具体的操作。具体代码如下：publicclassInsertionSortArray{publicstatic<TextendsComparable<?superT>>voidinsertSort(T[]a,intn){insertionSort(a,0,n-1);//对序列a进行排序，其起始索引为0，最后元素的索引为n-1}//从索引first到last执行插入排序...

1，采用选择排序对元素进行排列时，元素之间需要进行比较，因此需要实现Comparable<T>接口。即，<TextendsComparable<T>>.更进一步，如果允许待比较的类型可以和它的父类型进行比较，则需要写成：<TextendsComparable<?superT>，其中<?superT>表示T的任意超类。2，SelectionSortArray.java实现了选择排序的迭代形式和递归形式。具体代码如下：publicclassSelectionSortArray{/**Task:将数组中前n个对象按升序排列*@paramaComparable对象的数组*@paramn大于0的整数，表示数组的长度*/publicstatic<TextendsComparable<?superT>>voidselectionSort(T[]a,intn){for(intindex=0;index<n-1;index++){intindexOfNextSmallest=getIndexOfSmalles...

【算法总结】图论-拓扑排序一、概念设有一个有向无环图（DAG图），对其进行拓扑排序即求其中结点的一个拓扑序列，对于所有的有向边（U，V）（由U指向V），在该序列中结点U都排列在结点V之前。满足该要求的结点序列，被称为满足拓扑次序的序列。求这个序列的过程，被称为拓扑排序。由满足拓扑次序序列的特征我们也能得出其如下特点：若结点U经过若干条有向边后能够到达结点V，则在求得的序列中U必排在V之前。在了解了拓扑次序的定义以后，我们就知道了前文中为什么将拓扑排序限定在一个有向无环图上。若图无向，则边的两个顶点等价，不存在先后关系；若图为有向图，但存在一个环路，则该环中所有结点无法判定先后关系（任意结点间都能通过若干条有向边到达）。二、拓扑排序的方法首先，所有有入度（即以该结点为弧头的弧的个数）的结点均不可能排在第一个。那么，我们选择一个入度为0的结点，作为序列的第一个结点。当该结点被选为序列的第一个顶点后，我们将该点从图中删去，同时删去以该结点为弧尾的所有边，得到一个新图。那么这个新图的拓扑序列即为原图的拓扑序列中除去第一个结点后剩余的序列。同样的，我们在新图上选择一个入度为0的结点，将其作为原图...

【算法总结】图论-最短路径一、概念最短路径问题。即寻找图中某两个特定结点间最短的路径长度。所谓图上的路径，即从图中一个起始结点到一个终止结点途中经过的所有结点序列，路径的长度即所经过的边权和。 二、Floyd算法用邻接矩阵保存原图，那么此时邻接矩阵中edge[i][j]的值即表示从结点i到结点j，中间不经过任何结点时距离的最小值(若它们之间有多条边，取最小权值保存至邻接矩阵；也可能为无穷，即不可达)。假设结点编号为1到N，我们再考虑从结点i到结点j中间只能经过编号小于等于1的结点（也可以不经过）时最短路径长度。与原始状况相比，在中间路径上可以经过的结点增加了编号为1的结点。我们又知道，最短路径上的结点一定不会出现重复（不考虑存在负权值的情况）。那么，某两个结点间若由于允许经过结点1而出现了新的最短路径，则该路径被结点1分割成两部分：由i到结点1，同时中间路径上不经过结点1的第一段路径；由结点1到j，中间路径上同样不经过结点1的第二段路径，其路径总长度为edge[i][1]+edge[1][j]。要确定该路径是否比不允许经过结点1时更短，我们比较edge[i][1]+edge[...

【算法总结】图论-最小生成树一、概念在一个无向连通图中，如果存在一个连通子图包含原图中所有的结点和部分边，且这个子图不存在回路，那么我们称这个子图为原图的一棵生成树。在带权图中，所有的生成树中边权的和最小的那棵（或几棵）被称为最小生成树。定理：在要求解的连通图中，任意选择一些点属于集合A，剩余的点属于集合B，必定存在一棵最小生成树包含两个顶点分别属于集合A和集合B的边（即连通两个集合的边）中权值最小的边。 二、Kruskal算法1.初始时所有结点属于孤立的集合。2.按照边权递增顺序遍历所有的边，若遍历到的边两个顶点仍分属不同的集合（该边即为连通这两个集合的边中权值最小的那条）则确定该边为最小生成树上的一条边，并将这两个顶点分属的集合合并。3.遍历完所有边后，原图上所有结点属于同一个集合则被选取的边和原图中所有结点构成最小生成树；否则原图不连通，最小生成树不存在。如步骤所示，在用Kruskal算法求解最小生成树的过程中涉及到大量的集合操作，我们恰好可以使用上一节中讨论的并查集来实现这些操作。例5.3还是畅通工程解题思路在给定的道路中选取一些，使所有的城市直接或间接连通且使道路的...

【算法总结】图论-并查集一、概念：并查集并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能用并查集来描述。并查集是一种树型的数据结构，用于处理一些不相交集合（DisjointSets）的合并及查询问题，如表示集合信息，用以实现如确定某个集合含有哪些元素、判断某两个元素是否存在同一个集合中、求集合中元素的数量等等。常常在使用中以森林来表示。二、并查集的原理1.表示：双亲结点表示法来表示一棵树，即每个结点保存其双亲结点。使用的数据结构为数组。即我们在数组单元i中保存结点i的双亲结点编号，若该结点已经是根结点则其双亲结点信息保存为-1。有了这样的存储结构，我们就能通过不断地求双亲结点来找到该结点所在树的...

【算法总结】图论-预备知识 邻接矩阵：用一个二维数组来表示图的相关信息，如edge[i][j]表示结点i和结点j之间的关系（以及权重）——在表示的图为稠密图，且频繁地判断特定结点对是否相邻时，使用邻接矩阵较为适宜。邻接链表：链式存储结构，为图的每个顶点建立一个单链表，第i个单链表中保存与结点相邻的所有结点（无向图）或所有以结点Vi为弧尾的弧指向的结点（有向图）及其有关信息——当应用中存在大量遍历邻接结点的操作而较少判断两个特定结点关系时，选用邻接链表较为适宜。邻接链表的数据结构表示：vector1.定义一个结构体，包括邻接结点和边权值，用来表示一条边。structEdge{intnextNode;//下一个结点编号intcost;//该边的权重};2.为每一个结点建立一个单链表来保存与其相邻的边权值和结点的信息。建立一个大小为N的数组，保存元素即为vector对象，edge[i]表示为结点i建立的单链表。vector<Edge>edge[N];3.单链表初始化，利用vector::clear()操作清空这些单链表fo...

【算法总结】高精度整数我们首先明确高精度整数的保存形式，我们常用如下结构体来保存一个高精度整数structbiginteger{intdigit[1000];//保存大整数中若干位的数字，暂且使用每4位为一个单位保存intsize;//size是digit数组中第一个我们还未使用的数组单元，即digit数组下一个存储单元的角标};一、高精度加法例4.11a+bAC代码#include<cstdio>#include<cstring>structbiginteger//高精度整数结构体{intdigit[1000];//保存大整数中若干位的数字，暂且使用每4位为一个单位保存intsize;//size是digit数组中第一个我们还未使用的数组单元，即digit数组下一个存储单元的角标voidinit()//对结构体的初始化{for(inti=0;i<1000;i++)digit[i]=0;//所有数位清0size=0;//没有一个单元被使用}voidset(charstr[])//从字符串中提取整数存入大数数组,单元内顺序，单元外倒序存储{init();//...

【算法总结】素数素数即只能被自身和1整除的大于1的正整数。一、素数判定怎样确定一个数是素数？我们可以用所有大于1小于其本身的整数去试着整除该数，若在该区间内存在某个数能整除该数则该数不是素数；若这些数都不能整除它，则该数为素数。这一朴素的算法思想时间复杂度为O（n），n为我们要测试的数字。但其实，我们并不用测试到n-1为止，我们只需测试到不比sqrt（n）（对n开根号）大的整数即可，若到这个整数为止，所有正整数数均不能整除n，则可以断定，n为素数。模板booljudge(intx)//判断一个数是否为素数{if(x<=1)returnfalse;intbound=(int)sqrt(x);//计算枚举上界，枚举到sqrt(x)下取整即可，因为sqrt(x)若本来就是整数，x一定不是素数for(inti=2;i<=bound;i++)if(x%i==0)returnfalse;returntrue;}例4.6素数判定AC代码#include<cstdio>#include<cmath>booljudge(intx)//判断一个数是否为素数{if(x&l...

【算法总结】最大公约数和最小公倍数一、最大公约数（GCD：greatest common divisor）欧几里得算法：若a、b全为零则它们的最大公约数不存在；若a、b其中之一为零，则它们的最大公约数为a、b中非零的那个；若a、b都不为零，则使新a=b；新b=a%b，然后重复该过程。 例4.4最大公约数递归代码#include<cstdio>intgcd(inta,intb){if(b==0)returna;//若b为零则最大公约数为aelsereturngcd(b,a%b);//否则改为求b和a%b的最大公约数}intmain(){inta,b;while(scanf("%d%d",&a,&b)!=EOF)printf("%d",gcd(a,b));return0;}非递归代码#include<cstdio>intgcd(inta,intb){while(b!=0){intt=a%b;a=b;b=t;}returna;}intmain(){inta,b;while(scanf("%d%d",&a,&...

【算法总结】%运算符与取余运算取余套路：对取得的余数加上除数后，再对该和求除数的模，即可解决符号问题，保证取余结果恒正。（这里b是绝对值，恒大于0）ans=(r+b)%b一、数位拆解数位拆解即把一个给定的数字（如3241）各个数位上的数字拆开，即拆成3、2、4、1。例4.1特殊乘法AC代码（数学方法）#include<cstdio>intmain(){inta,b;//保存两个整数的变量while(scanf("%d%d",&a,&b)!=EOF)//输入两个整数{intbuf1[20],buf2[20],size1=0,size2=0;//用buf1,buf2分别保存从两个整数中拆解出来的数位数字，其数量由size1,size2表示while(a!=0)//数位拆解，只要a>0就不断重复拆解过程{buf1[size1++]=a%10;//取得个位数字a/=10;//数位移动}while(b!=0)//拆解第二个数字{buf2[size2++]=b%10;b/=10;}intans=0;for(inti=0;i<size1;i++)for(int...

【算法总结】二叉排序树二叉排序树是一棵特殊的二叉树，它是一棵二叉树但同时满足如下条件：对于树上任意一个结点，其上的数值必大于等于其左子树上任意结点数值，必小于等于其右子树上任意结点的数值。二叉排序树的存储方式与二叉树保持一致，我们更多的关注它独有的操作。我们从二叉树的插入开始了解其建树方式，对二叉排序树插入数字x：1.若当前树为空，则x为其根结点。2.若当前结点大于x，则x插入其左子树；若当前结点小于x，则x插入其右子树；若当前结点等于x，则根据具体情况选择插入左右子树或者直接忽略。以插入4、2、6、1、3为例，其二叉排序树变化情况如下图。由于各个数字插入的顺序不同，所得到的二叉排序树的形态也很可能不同，所以不同的插入顺序对二叉排序树的形态有重要的影响。但是，所有的二叉排序树都有一个共同的特点：若对二叉排序树进行中序遍历，那么其遍历结果必然是一个递增序列，这也是二叉排序树名字的来由，通过建立二叉排序树就能对原无序序列进行排序，并实现动态维护。 insert函数的返回值是Node指针这一点非常重要，因为要往前拱就必须“生长”左右子结点。例3.5二叉排序树...

【算法总结】二叉树我们从二叉树的遍历谈起。众所周知，在对二叉树的遍历过程中，根据遍历每一个结点的左子树、结点本身、右子树的顺序不同可将对二叉树的遍历方法分为前序遍历、中序遍历、后序遍历。我们摒弃数据结构教科书上复杂的遍历方式，而是使用我们在上一章所重点讨论过的递归程序来简单的实现它。假设二叉树结点由以下结构体表示： structNode{Node*lchild;//指向其左儿子结点的指针，当其不存在左儿子时为NULLNode*rchild;//指向其右儿子结点的指针，当其不存在右儿子时为NULL/***其他节点信息的操作*/};我们以中序遍历为例，给出其遍历方法。 voidinOrder(Node*Tree){if(Tree->lchild!=NULL)inOrder(Tree->lchild);//递归遍历左子树/***对当前根结点做遍历操作*/if(Tree->rchild!=NULL)inOrder(Tree->rchild);//递归遍历右子树return;}如上所见,用递归方式编写的二叉树遍历代码较原始使用堆栈来编写的相同功能代码，...