算法分析总复习

优选文档算法解析总复习考试题型：填空、简答、编程、计算。算法的定义：依照某种机械步骤获得问题结果的办理过程。算法的3要素：操作、控制结构、数据结构。算法的3个结构：序次结构、选择结构、循环结构。算法的基本性质：目的性、分布性、有序性、有限性、操作性。算法的基本特点：有穷性、确定性、可行性、输入性、输出性。(前3个是最主要的)算法的(质量)指标：正确性、可读性、庄重性、高效率与低储藏量需求。算法的抽象描述：算法=控制结构+原操作算法的表示方式包括：自然语言、流程图、盒图、PAD图、伪代码、程序设计语言。算法解析的任务：利用数学工具，谈论算法的复杂度。谈论算法的标准：算法实现所耗资的时间；算法实现所耗资的储藏空间；算法应易于理解、易于编码、易于调试。算法复杂度：算法的时间复杂度与算法的空间复杂度的统称。算法时间复杂度的估计：算法的执行时间=v原操作的执行次数X原操作的执行时间算法时间复杂度的数量级的形式：①0(L)称为常数级；②O(Logn)称为对数级；③0(n)称为线性级；④0(nc)称为多项式级；⑤0(Cn)称为指数级；⑥0(n!)称为阶乘级;判断时间复杂度的数量级：1)序次结构的算法的时间复杂度是0(L)；2)循环结构的算法的时间复杂度是0(nx)(x:循环的层数)；算法时间复杂度的最坏情况：可操作性最好的，且最有实质价值的，是最坏情况下的时间复杂性。算法的储藏量包括：1)输入数据所占空间；2)算法自己所占空间；3)辅助变量所占空间。NP完好问题：多项式复杂程度的非确定性问题，是图灵机在P时间内解决的问题，是世界7大数学优选文档优选文档难题之一。递归算法设计：就是把一个大型复杂的问题层层转变成一个与原问题相似的规模较小的问题，渐渐求解小问题后，再返回获得大问题的解。递归与非递归的比较程序可读性代码量大小时间占用空间使用范围设计难度递归易小长大广易非递归难大短小窄难算法与数据结构：1）计算机办理的问题种类:数值计算问题、非数值性问题。2）算法设计的实质：对实责问题要办理的数据选择一种合适的储藏结构，并在选定的储藏结构上设计一个好的算法，实现对数据的办理。好的算法在很大程度上取决于问题中数据所采用的数据结构。3）常用的数据结构的分类：连续储藏、链式储藏。4）连续储藏和链式储藏的优缺点比较：①基于储藏的考虑：序次表的储藏空间是静态分配的，早先必定明确规定其储藏规模；链表不用早先估计储藏规模，但储藏密度较低。②基于运算的考虑：运算若挨次号接见数据元素，则序次表优于链表；若是比较操作，则链表优于序次表。③基于环境的考虑：序次表简单实现；链表的操作是基于指针的。总之，平时较牢固的线性表选择序次储藏；而动向性较强的线性表宜选择链式储藏。选学生会主席问题（P70）的算法解析：先为5个候选人设置5个计数器，尔后依照选票分别对5个计数器累加1。即数组用于储藏统计结果，而其下标则是输入的原始信息。编程统计身高问题（P71）的算法解析：由于多数统计区间的大小都固定为5,这样用“身高/5?29”做下标，只须开辟8个元素的数组，对应8个统计品位，即可达成统计工作。统计3科全及格的学生问题（P71）的算法解析：从语文名单中逐一抽出及格学生学号，先在代数名单中查找，若有该学号，则代数也及格了，再在外语名单中查找，看该学号可否外语也及格了，若仍在，则该学号学生3科全及格，否则最少有一科不及格。语文名单中没有的学号，不可以能3科全及格，所以，语文名单办理完后算法就可以结束了。数字编号翻译成英文编号问题（P73）的算法解析：将英文的“zero?nine”储藏在数组中，对应下标为“0?9”。经过求余、取整运算，可以取到编号的各个位数字。用这个数字作下标，正好能找到对应的英文数字。高精度数据X长整数问题（P78）的算法解析：一个高精度数据与一个自然数的乘法运算过程，用一重循环来实现，循环变量i代表当前参加运算的数组下标，d表示储藏进位。统计50个学生中最少有3门成绩高于90分的人数问题（P91）的算法解析：优选文档优选文档对每个同学，先计算其成绩高于90分的课程科目，若高出3,则累加到满足条件的人数中。用二重循环实现以上过程，外层循环模拟50个同学，内层循环模拟5门课程。开灯问题（P92）的算法解析：定义有n个元素的a数组，它的每个下标变量a[i]视为一灯，i表示其编号。a[i]=1表示第i盏灯处于打开状态，a[i]=0表示第i盏灯处于关闭状态。经过算术运算a[i]=1-a[i]，就能很好地模拟开关灯的操作。数字圆圈问题（P93）的算法解析：数组定义为a[n]，则有a[0]?a[n-1]共n个元素。用i代表下标，题目就是序次将a（i-1）与a（i+1）相乘，经过求余运算求出乘积的最大值和最小值。任意3个数的最小公倍数问题（P97和P136）的算法解析：用蛮力法最方便，但运算时间最长。警察抓小偷问题（P99）的算法解析：将a、b、c、d4个人进行编号，号码分别是1、2、3、4。接着用列举法来解决。老师展望数学竞赛问题（P100）的算法解析：利用三重循环把所有的情况列举出来即可。找次品问题（P102）的算法解析：1?10号箱取产品的件数分别为20?29件，尔后称量，就可以很简单地找到次品。数学模型的定义：数学模型是利用数学语言模拟现实的模型。把现实模型抽象、简化为某种数学结构是数学模型的基本特点。上楼梯问题（P114）的算法解析：设n阶台阶的走法数位f（n）,则：仁n=1f(n)=2.................................................n=2f(n-1)f(n-2)n2迭代法的定义：也称辗转法，是一种不断用变量的旧值推出新值的解决问题的方法。兔子生殖问题（P124）的算法解析：把a,b表示成每个月的前2个月和前1个月的兔子的对数，它们的初值均为1,这样3月兔子的对数c=a+b;求4月兔子的对数时，先将4月前2个月和前1个月兔子的对数储藏在变量a,b中，即a=b,b=c,再将4月份兔子的对数连续保留在变量c中，即c=a+b+当然，在变量中的数据被覆盖从前应先行输出已求解的结果。main（）{inti,a=1,b=1;printf（%d%d",a,b）;fot（i=1;i<=10;i++）{c=a+b;printf（“%d”,c）;a=b;b=c;优选文档优选文档}}倒推法的定义：是对某些特别问题，所采用的从后向前推解的方法。杨辉三角(限制用1个一维数组达成)问题(P)的算法解析：从每一行第i个元素倒着向前计算，则可防备这种情况出现迭代表达式以下：A[1]=A[i]=1;A[j](i行)=A[j](i-1行)+A[j-1](i-1行)j=i-1,i-2,,2;穿越沙漠问题(P128)的算法解析：倒着累加储油点间的距离，并计算各储油点的储油量，直到总距离高出1000千米，求解距出发点近来的一个储油点的地址及储油量，问题就得以解决。牛顿迭代法的定义：又称切线法，第一，选择一个凑近f(X)零点的X。，计算相应的f(Xo)的切线斜率f'(Xo);尔后，依照牛顿迭代公式Xn.1=Xn-f,(Xn)求得x1。该方法拥有更高收敛速度。f(Xn)二分逼近法的定义：a。+b0f(X)在区间[a,b]上连续，f(a)*f(b)<0。令[a。,bo]=[a,b],c000，若f(0)=0,2则C为f(X)=0的根；否则，若f(a)与f(c)异号，则令[a1,b]=[a,c];若f(b)与0°°1°°°f(q)异号，则令[a1,b1]=[C0,b0]。依此做下去，当发现f(Cn)=0时或区间[a*,bn]足够小，就认为找到了方程的根。列举法的定义：是蛮力策略的一种表现形式，它依照问题中的条件将可能的情况一一列举出来，逐一尝试从中找出满足问题条件的解。蛮力法的典型模范：(P136)1)最小公倍数问题；2)狱吏问题。分治法的设计思想：将一个难以直接解决的大问题，切割成一些规模较小的几个相似问题，以便分而治之，各个击破。与递归算法相似。分治法的基本步骤：1)分解；2)解决；3)合并。大整数乘法问题(P146)的算法解析：将两个乘数及其积都按由低位到高位的序次，逐位储藏到数组元素中。储藏好两个高精度数据后，模拟竖式乘法，让两个高精度数据的按位交织相乘，并渐渐累加，即可获得精确的计算结果。用二重循环即可控制两个数的各位数字按位交织相乘的过程。贪心算法的定义：优选文档优选文档又叫登山法，其根本思想是渐渐获得最优解，是解决最优化问题时的一种简单但适用范围有限的策略。“贪心”可以理解为以渐渐的局部最优，达到最后的全局最优。埃及分数问题(P160)的算法解析：找最小的n,使分数f>1/n;输出1/n;计算f=f-1/n;若此时的f是埃及分数，输出f,否则返回第一步。贪心算法的基本思路：从问题的某一个初始解出发渐渐逼近给定的目标，每一步都作一个不可以回溯的决策，尽可能地求得最好的解。动向规划的基本思想：把求解的问题分成好多阶段或多个子问题，尔后按序次求解各子问题。前一子问题的解，为后一子问题的求解供应了适用的信息。在求解任一子问题时，列出各种可能的局部解，经过决策保留那些有可能达到最优的局部解，扔掉其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。不同样算法策略特点总结：1、贪心法：“经过局部最优获得全局最优”2、递推法：由当前问题的渐渐解决从而获得整个问题的解，多用于计算。3、递归法：利用大问题与其子问题间的递推关系来解决问题。4、列举法：逐一试一试问题的所有可能的解，从而找出真切的解，多用于决策类问题。5、递归回溯法：经过递归试一试遍历问题各个可能解得的通路，当发现此路不通时，回溯到上一步连续试一试其他通路。6、分治法：把一个大问题分解成若干个简单解决的子问题，分而治之，尔后把子问题的解合成，获得大问题的解，多用于较复杂的问题。7、动向规划法：经过多阶段决策过程来解决问题。每个阶段决策的结果是一个决策结果序列，这个结果序列的最优结果，取决于今后每个阶段的决策。搜寻算法的定义：有目的地列举一个问题的部分或所有的可能情况，从而找到问题的解。显示图的常用方法：）毗邻矩阵法：毗邻矩阵是表示极点之间相邻关系的矩阵。）毗邻表法：对于图G中的每个结点vi，该方法把所有毗邻于vi的极点vj链成一个单链，这个单链表就称为极点vi的毗邻表。毗邻表由极点表和边表两部分组成。广度优先搜寻算法的基本思路：经过搜寻图的过程中进行相应的操作，从而解决问题，主要用于解决在显式图中搜寻某一方案的问题。）毗邻表表示图的广度优先搜寻算法：intvisited[n];bfs（intk,graphhead[]）{intI;queueQ;优选文档优选文档edgenode*p;InitQueue(Q);print(“visitvertex”,k);visited[k]=1;EnQueue(Q,k);while(notQueueEmpty(Q)){i=DeQueue(Q);p=head[i].firstedge;while(p<>null){if(visited[p->adjvex]=0){print(“visitertex”,p->adjvex);visited[p->adjvex]=1;EnQueue(Q,p->adjvex);}p=p->next;}}}2)毗邻矩阵表示的图的广度优先搜寻算法：brsm(intk,graphg[][100],intn){inti,j;queueQ;InitQueue(Q);print(“visitvertex”,k);visited[k]=1;EnQueue(Q,k);while(notQueueEmpty(Q)){i=DeQueue(Q);for(j=0;j<n;j++)if(g[i][j]=1andvisited[j]=0){print(“visitvertex”,j);visited[j]=1;EnQueue(Q,j);}}}选路径问题(P198)的算法解析：运用广度优先搜寻，逐层搜寻正好可以赶忙找到一个结点与另一个结点相对而言最直接的路径。走迷宫问题(P200)的算法解析：运用广度优先搜寻，从入口开始广度优先搜寻所有可到达的方格入队，再扩展队首的方格，直到搜寻到出口时算法结束。优选文档优选文档深度优先搜寻算法的基本思路：深度优先搜寻和广度优先搜寻的基本思路同样。由于深度优先搜寻的E结点是分多次进行扩展的，所以它可以搜寻到问题所有可能的解决方案。)用毗邻表储藏图的搜寻算法以下：intvisited[n];graphhead[100];dfs(intk){edgenode*ptr;visited[k]=1;print(“接见”,k);ptr=head[k].firstedge;while(ptr<>null){if(visited[ptr->vertex]=0)dfs(ptr->vertex)ptr=ptr->nextnode;}})用毗邻矩阵储藏图的搜寻算法以下：intvisited[n];graphg[][100],intn;dfsm(intk){intj;print(“接见”,k);visited[k]=1;for(j=1;j<=n;j++)if(g[k][j]=1andvisited[j]=0)dfsm(g,j);}走迷宫问题(P204)的算法解析：深度优先搜寻，就是素来向着可通行的下一个方格进行，直到搜寻到出口就找到一个解。若行不通，则返回上一个方格，连续搜寻其他方向。七巧板问题(P206)的算法解析：在深度优先搜寻极点时，其实不加入任何涂色的策略，可是对每一个极点逐一试一试4种颜色，检查当前顶优选文档优选文档点的颜色可否与前面已确定的相邻极点的颜色发生矛盾，若不矛盾，则连续以同样的方法办理