下载文档原格式
目录算法概论 (1)序言 (1)第一章 (2)乘法 (2)除法 (2)两数的最大公因数 (2)扩展 (2)RSA (3)第二章：分治算法 (3)整数相乘的分治算法 (3)递推式 (3)2.3合并排序 (3)第三章图的分解 (4)3.2.1寻找从给定顶点出发的所有可达顶点 (4)3.2.2 深度优先搜索 (4)第四章 (4)4.2、广度优先搜索 (4)4.4.1、dijkstra最短路径算法 (5)4.6.1、含有负边 (5)Bellman-Ford算法 (6)4.7、有向无环图的最短路径 (6)第五章贪心算法 (6)5.1 最小生成树 (6)算法概论序言Fibonacci数列：死板的算法：function Fib1(n)If n=0:return 0If n=1:return 1Return fib1(n-1)+fib1(n-2)(递归，很多计算是重复的，不必要)合理的算法：functionFib2(n)If n=0:return 0Create an array f[0…n]f[0]=0,f[1]=1fori=2…n:f[i]=f[i-1] + f[i-2]return f[n](随时存储中间计算结果，之后直接调用)大O符号：若存在常数c>0，使得f(n)<=c*g(n)成立，则f=O(g)。
f增长的速度慢于g。
第一章乘法：functionMultiply(x,y)If y=0:return 0z=multiply(x,y/2)//向下取整If y is even: //even---偶数return 2zelse:return x+2z除法：functionDivide(x,y)If x=0: return (q,r)=(0,0)(q,r)=divide( x/2 ,y) //向下取整q=2*q,r=2*rif x is odd:r=r+1if r>=y :r=r-y,q=q+1return (q,r)p22两数的最大公因数：function Euclid(a,b)if b=0: return areturn Euclid(b,a mod b)扩展：function extended-Euclide(a,b)if b=0: return (1,0,a)(x1,y1,d)=extended-Euclide(b,a mod b)retrun (y1,x1-a/b*y1,d)RSA:(X^e)^d ==X mod Nd=e^-1 mod(p-1)(q-1)N=pq第二章：分治算法整数相乘的分治算法：function multiply(x,y)input:n-bit positive integers x and youtput:their productif n=1:return xyxl,xr=leftmost n/2_^ ,rightmost n/2_v bits of x // _^表示向上取整，_v表示向下取整yl,yr=leftmost n/2_^ ,rightmost n/2_v bits of yp1=multiply(xl,yl)p2=multiply(xr,yr)p3=multiply(xl+xr,yl+yr)return p1*p2+(p3-p1-p2)*2^(n/2)+p22.2递推式：T(n)={ O(nd):d>logba|| O(n d *log n) :d=log b a|| O(n^(log b a)): d<log b a}2.3合并排序function mergersort(a[1…n])if n>1:return merge(mergesort( a[1…n/2]), a[n/2+1…n]))else:return afunction merge(x[1…k], y[1…L] )if k=0: return y[1…L]if L=0: return x[1…k]if x[1]<=y[1]:return x[1]＆merge(x[2…k],y[1…L])else:return y[1]&merge( x[1…k], y[2…L] )第三章图的分解3.2.1寻找从给定顶点出发的所有可达顶点：procedure explore(G,v)input:G=(V,E) is a graph; v ∈Voutput:visited(u) is set to true for all nodes u reachable from vvisited(v)=trueprevisit(v)for each edge(v,u)∈E:if not visited(u):explore(u)postvisit(v)3.2.2 深度优先搜索：proceduredfs(G)for all v ∈V:visited(v)=falsefor all v∈V:if not visited(v):explore(v)线性化序列：对图深度优先搜索，取post的降序序列。
用伪代码描述算法欧几里得算法算法：欧几里得算法 (Euclidean Algorithm)1.令a和b为两个输入的正整数2.如果a等于0，则返回b作为最大公约数3.如果b等于0，则返回a作为最大公约数4.令r为a除以b的余数5.将a的值更新为b，将b的值更新为r6.转到步骤4，直到r为07.返回b作为最大公约数下面是对这个算法的详细步骤解释。
算法详解：对于给定的两个正整数a和b，我们要找到它们的最大公约数。
步骤1：定义输入令a和b为两个输入的正整数。
步骤2、3：检查边界条件如果a等于0，说明b本身就是最大公约数，因为任何数与0的最大公约数都是本身。
因此，返回b作为最大公约数。
同理，如果b等于0，返回a作为最大公约数。
步骤4：计算余数令r为a除以b的余数。
步骤5：更新变量将a的值更新为b，并将b的值更新为r。
步骤6：重复直到余数为0重复步骤4和步骤5，直到r为0。
这是因为当余数为0时，说明a 能够整除b，即找到了最大公约数。
步骤7：返回结果返回b作为最大公约数。
伪代码实现：以下是用伪代码描述的欧几里得算法的完整实现：```function EuclideanAlgorithm(a, b)if a = 0 thenreturn belse if b = 0 thenreturn aelser = a mod bwhile r ≠ 0 doa=bb=rr = a mod bend whilereturn bend ifend function```这段伪代码描述了欧几里得算法的实现过程，其中使用了基本的算术运算符（加法，乘法和取模），以及控制结构（if-else语句和while循环）。
伪代码的写法伪代码（Pseudocode）是⼀种算法描述语⾔。
使⽤伪代码的⽬的是为了使被描述的算法可以容易地以任何⼀种编程语⾔（Pascal，C，Java，etc）实现。
因此，伪代码必须结构清晰、代码简单、可读性好，并且类似⾃然语⾔。
介于⾃然语⾔与编程语⾔之间。
它以编程语⾔的书写形式指明算法的职能。
相⽐于程序语⾔（例如Java, C++,C, Dephi 等等）它更类似⾃然语⾔。
它是半⾓式化、不标准的语⾔。
我们可以将整个算法运⾏过程的结构⽤接近⾃然语⾔的形式（这⾥，你可以使⽤任何⼀种你熟悉的⽂字，中⽂，英⽂等等，关键是你把你程序的意思表达出来）描述出来. 使⽤伪代码, 可以帮助我们更好的表述算法, 不⽤拘泥于具体的实现. ⼈们在⽤不同的编程语⾔实现同⼀个算法时意识到，他们的实现（注意:这⾥是实现,不是功能）很不同。
尤其是对于那些熟练于不同编程语⾔的程序员要理解⼀个(⽤其他编程语⾔编写的程序的)功能时可能很难，因为程序语⾔的形式限制了程序员对程序关键部分的理解。
这样伪代码就应运⽽⽣了。
当考虑算法功能（⽽不是其语⾔实现）时，伪代码常常得到应⽤。
计算机科学在教学中通常使⽤虚拟码，以使得所有的程序员都能理解。
综上，简单的说，让⼈便于理解的代码。
不依赖于语⾔的，⽤来表⽰程序执⾏过程，⽽不⼀定能编译运⾏的代码。
在数据结构讲算法的时候⽤的很多。
语法规则 例如，类Pascal语⾔的伪代码的语法规则是：在伪代码中，每⼀条指令占⼀⾏（else if，例外）。
指令后不跟任何符号（Pascal和C中语句要以分号结尾）。
书写上的“缩进”表⽰程序中的分⽀程序结构。
这种缩进风格也适⽤于if-then-else语句。
⽤缩进取代传统Pascal中的begin和end语句来表⽰程序的块结构可以⼤⼤提⾼代码的清晰性；同⼀模块的语句有相同的缩进量，次⼀级模块的语句相对与其⽗级模块的语句缩进。
算法的伪代码语⾔在某些⽅⾯可能显得不太正规，但是给我们描述算法提供了很多⽅便，并且可以使我们忽略算法实现中很多⿇烦的细节。
