Python-教程-chapter13

算法设计与分析222查找问题问题:在一个列表中查找某个值.defsearch(x,nums):#nums为一数值列表,x是一个数#如果找到,返回x在列表中的位置#否则返回-1333查找问题Python本身就提供有关的功能–判断:xinnums–求位置:nums.index(x)defsearch(x,nums)try:returnnum.index(x)#如何实现？except:return-1444策略一:线性查找逐个检查列表中的数据defsearch(x,nums):foriinrange(len(nums)):ifnums[i]==x:returnireturn–1555策略一:线性查找特点:–适合无序数据列表–不适合大数据量使列表有序后,线性查找算法可略加改进(How?)666策略二:二分查找猜数游戏:可取的策略?二分查找:每次查看有序列表的中点数据,根据情况接着查找较大一半或较小一半defsearch(x,nums):low,high=0,len(nums)-1whilelow=high:mid=(low+high)/2ifx==nums[mid]:returnmidelifxnums[mid]:high=mid-1else:low=mid+1return-1算法的优劣比较经验分析–根据电脑上的运行时间比较–环境变化会影响结果抽象分析–分析算法解题所耗“步数”(时间)步数越少越好–步数又与问题难度/规模相关查找问题中,问题难度用数据量n衡量7888查找算法的比较策略一–步数与n成正比–称为线性时间算法策略二–步数与log2n成正比(如：16个元素的列表)–称为对数时间算法猜数游戏中:若数的范围是1~1000000,则–策略一:平均要猜50万次才能猜对最坏1百万次,最好1次–策略二:最坏也只需猜20次999查找算法的比较策略一–步数与n成正比–称为线性时间算法策略二–步数与log2n成正比(如：16个元素的列表)–称为对数时间算法ListSizeHalvings10214283164递归定义二分查找算法的另一表述:算法binarySearch:在nums[low]~nums[high]中查找xmid=(low+high)/2iflowhighx不在nums中elifxnums[mid]在nums[low]~nums[mid-1]中查找xelse在nums[mid+1]~nums[high]中查找x大问题的子问题仍是同样形式的问题,故仍用解决大问题的算法来解决子问题10递归定义的特征递归定义完全是合法的,数学里有很多递归定义的对象.如阶乘:–这不是循环定义，有”出口”111,当n=0;n!=n*(n–1)!,否则递归定义的特征递归定义的特征–有奠基情形,这种情形无需递归–每次递归都是针对较小情形–递归链最后终止于奠基情形12Python递归函数例如:计算阶乘的递归函数deffact(n):ifn==0:return1else:returnn*fact(n-1)13递归查找算法二分查找的递归版本:defrecBinSearch(x,nums,low,high):iflowhigh:return-1mid=(low+high)/2ifx==nums[mid]returnmidelifxnums[mid]:returnrecBinSearch(x,nums,low,mid-1)else:returnrecBinSearch(x,nums,mid+1,high)defsearch(x,nums):returnrecBinSearch(x,nums,0,len(nums)-1)14递归vs迭代递归算法–设计容易–易读–效率略低迭代算法:用循环–设计困难有的问题没有直观的迭代算法–效率高排序问题给定数据列表,将其数据重新排列,形成一个有序的(递增)列表回顾:Python列表类型提供了方法list.sort()–我们要学的是如何实现这个方法朴素策略:选择排序每次从剩下的数据中选择最小值输出–求列表中最小值的算法:参考前面的max算法defselSort(nums):n=len(nums)forbottominrange(n-1):#求nums[bottom]..nums[n-1]间的最小值mp=bottom#初始bottom为迄今最小foriinrange(bottom+1,n):#考虑其他值ifnums[i]nums[mp]:mp=i#新的迄今最小值nums[bottom],nums[mp]=nums[mp],nums[bottom]–大数据量时效率低分而治之:归并排序数据分成两组或更多组分别对各组排序再把已有序的各组归并(merge)成完整有序列表分而治之:归并排序归并:比较两组各自的第一个数据,小者输出,由该组的下一个数据顶上来继续比较–当某组没有数据,则将另一组整个输出.defmerge(lst1,lst2,lst3):while当lst1和lst2两组都有数据:输出两组第一个数据的较小者至lst3更新该组的第一个数据while某组没有数据了:将另一组剩余数据输出至lst3分而治之:归并排序(续)问题:如何对各组排序?似乎可以利用递归:–对每一组再次应用分而治之的归并排序–因为满足递归的前提条件:奠基情形:组中只有一个数据时无需递归;每次分组都使列表变小,最终会到达奠基情形分而治之:归并排序(续)利用递归defmergeSort(nums):n=len(nums)ifn1:m=n/2nums1,nums2=nums[:m],nums[m:]mergeSort(nums1)mergeSort(nums2)merge(nums1,nums2,nums)排序算法的比较难度和列表大小n有关选择排序–每次循环:从剩余数据中选择最小值,所需步数为剩余数据的个数–总的步数:n+(n-1)+...+1=n(n+1)/2称为n2算法排序算法的比较难度和列表大小n有关选择排序(n2算法)归并排序–作分组归并图示,可知每层归并都涉及n步(拷贝n个数据)共有log2n层故需nlog2n步,称为nlogn算法排序算法的比较难度和列表大小n有关选择排序(n2算法)归并排序(nlogn算法)可计算性与计算复杂性问题可划分为:–可计算的:存在确定的机械过程,一步一步地解决问题可计算,而且能有效解决可计算,但难度太大,不能有效解决–不可计算的:不存在明确的机械过程来求解该问题不可解,不可判定Hanoi塔问题体现递归威力的经典问题!–三条规则defmoveTower(n,source,dest,temp):ifn==1:printMovediskfrom,source,to,dest+.else:moveTower(n-1,source,temp,dest)moveTower(1,source,dest,temp)moveTower(n-1,temp,dest,source)Hanoi塔问题难度:需要2n−1步!–称为指数时间算法–属于难解(intractable)问题.–根据Hanoi塔的传说:有64个金盘.就算僧侣1秒移动一次,至少也要花264−1秒,大约等于5850亿年NumberofDisksStepsinSolution112337415531停机问题能否编一个终止性判定程序HALT?defHALT(prog,data)若prog(data)终止,则输出True;否则输出False.是不可解(unsolvable)问题!停机问题若有HALT,则歌德巴赫猜想可以迎刃而解:defgc():n=2whileTrue:if2*n不是两个素数的和,则返回Falsen=n+1–然后运行HALT(gc)即可哥德巴赫猜想主張每個大於等於4的偶數都是哥德巴赫數－可表示成兩個質數之和的數停机问题(续)说HALT不存在只能通过严格证明:假设存在HALT(prog,data).则编程序defstrange(p):result=HALT(p,p)ifresult==False:#即p(p)不终止returnelse:whileTrue:n=1运行strange(strange),结果如何?悖论“我正在说谎”。他是在说谎还是在说真话呢?如果他讲真话,那么他所说的是真,也就是他在说谎。我们得出结论如果他讲真话,那么他是在说谎另一方面,如果他是说谎,那么他说的是假;因为他承认他是说谎,所以他实际上是在说真话,我们得出结论如果他是说谎,那么他是讲真话。悖论悖论是自相矛盾的命题。即如果承认这个命题成立，就可推出它的否定命题成立；反之，如果承认这个命题的否定命题成立，又可推出这个命题成立Aparadoxisastatementorgroupofstatementsthatleadstoacontradictionorasituationwhichdefiesintuition1900年前后,在数学的集合论中出现了三个著名悖论:罗素悖论、康托尔悖论、布拉利—福尔蒂悖论。这些悖论特别是罗素悖论，在当时的数学界与逻辑界内引起了极大震动。触发了数学的第三次危机悖论例如比较有名的理发师(罗素)悖论：某乡村有一位理发师，一天他宣布：只给不自己刮胡子的人刮胡子。这里就产生了问题：理发师给不给自己刮胡子？如果他给自己刮胡子，他就是自己刮胡子的人，按照他的原则，他不能给自己刮胡子；如果他不给自己刮胡子，他就是不自己刮胡子的人，按照他的原则，他就应该给自己刮胡子。这就产生了矛盾考试2011-06-23第18周星期四18:00－20:00东上院103考试形式：开卷考试范围：上课所讲3535End