离散数学算法.pptVIP

第1页，共35页，星期日，2025年，2月5日本讲内容算法简介算法例子算法分析递归算法第2页，共35页，星期日，2025年，2月5日算法－一组有限的指令集合输入：算法接受输入。输出：算法产生输出。精确性：步骤被精确描述。确定性：每步执行的结果是惟一的，且只依赖于输入和前面步骤执行的结果。有限性：算法可以终止，也就是在执行有限多条指令后停止。正确性：算法生成的输出结果是正确的，也就是算法可以正确地求解问题。一般性：算法适应于一组输入。第3页，共35页，星期日，2025年，2月5日算法示例－三数排序1.large=a.2.Ifblarge,thenlarge=b.3.Ifclarge,thenlarge=c.这个算法的思想是对这些数一个一个地检查，将所见的最大数赋值给变量large。在算法停止时，large就等于这三个数中最大的了第4页，共35页，星期日，2025年，2月5日跟踪a=1,b=5,c=3a=1,b=5,c=91.large=a.2.Ifblarge,thenlarge=b.3.Ifclarge,thenlarge=c.x=第5页，共35页，星期日，2025年，2月5日算法正确性证明算法描述：在数列s1,...,sn中找出最大的一个。输入：s,n输出：large（序列s中的最大值）max(s,n){large=s1fori=2tonif(silarge)large=sireturnlarge}第6页，共35页，星期日，2025年，2月5日算法正确性证明（二）循环不变式：在循环的每次迭代前后均为真的谓词 large=max{s1,...,sn}第7页，共35页，星期日，2025年，2月5日算法正确性证明（三）－归纳平凡情况（i=1）large是序列中的最大值。假设large是子序列s1,...,si中的最大值。假如in成立，i变成i+1。 （1）si+1large，赋值large＝si+1； （2）si+1≤large，算法不改变large的值。 因此，large=max{s1,...,sn}是一个循环不变量。for循环在i=n时结束，算法正确。第8页，共35页，星期日，2025年，2月5日文本有哪些信誉好的足球投注网站假设给定一个文本t（例如一个文档），在t中找出特定词组p首次出现的位置。ABCABCDEAD……EDCEDCEDCEDC第9页，共35页，星期日，2025年，2月5日text_search(p,m,t,n){ fori=1ton-m+1{ j=1; while(ti+j-1==pj){ j=j+1; if(jm)returnj; } } return0}第10页，共35页，星期日，2025年，2月5日插入排序假设插入排序的输入是s1,...,sn，目标是按非递减顺序将数据排序。在插入排序的第i次迭代后,序列的前一部分s1,...,si会被重新安排使得它有序。插入排序接下来将si+1插入s1,...,si，使得s1,...,si,si+1也是有序的。第11页，共35页，星期日，2025年，2月5日第12页，共35页，星期日，2025年，2月5日时空分析在插入排序算法中，for循环执行n-1次，但是对于一个特定的i值，while循环执行的次数依赖于输入。例如，如果输入的序列已经按非递减顺序排列，valsj总是false，while的循环体永远不被执行，称这个时间为最好情形执行时间；另外，如果这个序列是按递减顺序排序的，valsj，总是true，while的循环体执行最大次数。（当第i次迭代时for循环中while循环执行i-1次）。称这个时间为最坏情形执行时间。第13页，共35页，星期日，2025年，2月5日随机算法一个随机算法（randomizedalgorithm）并不要求每一步的执行中间结果被惟一决定且只依赖于输入和前面步骤的执行结果。根据定义，当执行一个随机算法时，在某些点上，算法做出随机选择。第14页，共35页，星期日，2025年，2月5日随机算法（二） rand(i,j)：返回在整数i和j之间的（包含i和