python算法设计和分析

计算机解决问题的关键：设计出合适的算法算法设计和分析算法的质量评价正确性：算法应能正确地实现预定的功能；易读性：算法应易于阅读和理解，以便于调试、修改和扩充；稳健性：当环境发生变化（如遇到非法输入）时，算法能适当地做出反应或进行处理，不会产生不正确的运算结果；高效率：具有较高的时间和空间性能。Outline:§10.1枚举法（查找问题）§10.2递归程序设计§10.3排序问题§10.4可计算性问题枚举法问题求解中常用的一种算法设计方法。给定问题P，如果知道P的可能解构成一个有限集合S={s1,s2,s3,…,sn}，则可以逐一例举每个si，检验它是否确实是P的解。“百钱白鸡”问题：假设公鸡每只5元，母鸡每只3元，小鸡每3只1元。用100元钱买100只鸡，问公鸡、母鸡和小鸡各买了多少只？x+y+z=1005x+3y+z/3=100枚举法应用一、不定方程的求解代码：forxinrange(100):foryinrange(100):forzinrange(100):t=x+y+zm=5*x+3*y+z/3ift==100andm==100:print"x=",x,"y=",y,"z=",zforxinrange(100):foryinrange(100):forzinrange(100):t=x+y+zm=5*x+3*y+z/3

ift==100andm==100andz%3==0:print"x=",x,"y=",y,"z=",zx=0y=25z=75x=3y=20z=77x=4y=18z=78x=7y=13z=80x=8y=11z=81x=11y=6z=83x=12y=4z=84x=0y=25z=75x=4y=18z=78x=8y=11z=81x=12y=4z=84枚举法应用二、查找问题问题描述：在一个列表中查找某个值.defsearch(x,nums): #nums为一数值列表,x是一个数

#如果找到,返回x在列表中的位置

#否则返回-1Python本身就提供有关的功能:判断：xinnums求位置：nums.index(x)>>>nums=[3,1,4,2,5]>>>x=4>>>search(4,nums)2>>>nums.index(4)2>>>nums.index(100)Traceback(mostrecentcalllast):File"<pyshell#3>",line1,in<module>nums.index(100)ValueError:100isnotinlistSuperprogrammer：自己来完成类似的功能，而且在寻找的数不在数列中时返回-1.（1）无序表的查找：一维表中的线性查找逐个检查列表中的数据.defsearch(x,nums):foriinrange(len(nums)):ifnums[i]==x:returnireturn–1nums=[3,1,4,2,5]>>>nums=[3,1,4,2,5]>>>x=4>>>search(4,nums)2>>>search(4,[10,11,12,13])-1无序表的查找：二维表中的线性查找defsearch2D(matrix,row,col,x):foriinrange(row):forjinrange(col):ifmatrix[i][j]==x:return(i+1,j+1)return-1

>>>search2D([[1,2,3],[4,5,6]],2,3,6)(2,3)>>>search2D([[1,2,3],[4,5,6]],2,3,7)-1特点:容易实现适合无序数据列表不适合大数据量补充：二维列表的初始定义列表初始定义的两种方法（初始值和多维）：myList=[0]*10#定义一个初始值皆为0的长度为10的列表myList=[[0]*5]*6#定义一个初始值皆为0的6行*5列的二维列表myList=[0forxinrange(10)]

#定义一个初始值皆为0的长度为10的列表myList=[[0forcolinrange(10)]forrowinrange(9)]#定义一个初始值皆为0的9行*10列的二维列表两种定义方法本质上不同：第一种（紫色）的定义是浅拷贝，第二种（蓝色）的定义是深拷贝。浅拷贝（shallowcopy）是指源对象与拷贝对象共用一份实体，仅仅是引用的变量不同（名称不同）。对其中任何一个对象的改动都会影响另外一个对象。所以只在不改变对象值的情况下可用。深拷贝（deepcopy）是指源对象与拷贝对象互相独立，其中任何一个对象的改动都不会对另外一个对象造成影响。myList=[[0]*5]*6#定义一个初始值皆为0的6行*5列的二维列表foriinrange(5):myList[0][i]=iforiinrange(6):forjinrange(5):printmyList[i][j],printforiinrange(5):myList[2][i]=9foriinrange(6):forjinrange(5):printmyList[i][j],printmyList=[[0forcolinrange(5)]forrowinrange(6)]012340123401234012340123401234999999999999999999999999999999012340000000000000000000000000012340000099999000000000000000（2）

有序表的查找：二分查找猜数字：1-100（二分查找的思想）二分查找：

假设查找范围为（low，high）

循环查找：

查看有序列表的中点数据nums[(low+high)/2]

找到：退出

else：根据情况接着找较大一半或较小一半，

即更新查找范围（low、high）

循环退出条件：找到或未找到（此时low和high什么关系——终止条件）defsearch(x,nums):low,high=0,len(nums)-1

whilelow<=high:mid=(low+high)/2ifx==nums[mid]:returnmid

elifx<nums[mid]:high=mid-1else:low=mid+1return-1二分法——分而治之，特点就是把一个问题的规模不断缩小。#performbinarysearchforxinrangenums[low]tonums[high]mid=(low+high)/2iflow>high：xisnotinnumselifx<nums[mid]：performbinarysearchforxinrangenums[low]tonums[mid-1]else：

performbinarysearchforxinrangenums[mid+1]tonums[high]将一个大问题简化为同样形式的较小问题第13章算法分析与设计§13.1枚举法§13.2递归程序设计§13.3排序问题§13.4可计算性问题递归用途递归程序设计：将一个大问题简化为同样形式的较小问题。在一个递归求解中，分解的子问题与最初的问题具有一样的形式作为处理问题的工具，递归技术是一种非常有力的工具。利用递归不但可以使得书写复杂度降低，而且使程序看上去更加美观递归调用：在一个函数中直接或间接地调用函数本身递归条件必须有递归终止的条件函数有与递归终止条件相关的参数，在递归过程中，决定终止条件的参数有规律地递增或递减

递归的标准模式有可对函数的入口（参数）进行测试的基本情况

if(条件)return(不需要递归的简单答案);elsereturn(递归调用同一函数)；基本情况典型的递归函数—阶乘函数n!=1*2*3*4*…*(n-1)*n(n-1)!递归形式：递归终止条件计算阶乘的递归函数deffact(n):ifn==0:return1else:returnn*fact(n-1)二分查找的递归算法二分查找的思想：在范围list[low]到list[high]之间查找x取当前范围的中间数据m；如果m等于x或者m不存在则算法结束；如果x<m则在范围list[low]到list[mid-1]之间查找x，否则在范围list[mid+1]到list[high]之间查找x。涉及几乎相同的操作二分查找的递归算法defBinSearch(x,nums,low,high):iflow>high:return-1#没找着mid=(low+high)/2ifx==nums[mid]

returnmid

#找到了

elifx<nums[mid]:

returnBinSearch(x,nums,low,mid-1)

else:

returnBinSearch(x,nums,mid+1,high)defsearch(x,nums):#递归函数的调用

returnBinSearch(x,nums,0,len(nums)-1)切记不要忘了“return”递归函数的补充--数字旋转方阵（蛇阵）数字旋转方阵如右图所示。编程输出任意n*n的蛇阵。120191817162213231301532233362914423343528135242526271267891011初始矩阵的建立myList=[[0forcolinrange(n)]forrowinrange(n)]000000000000000000000000000000000000用递归的观点看问题先填最外圈，然后再填内部的，填法同上，也是先填最外圈，再填内部。根据上述思想，可以设计一个递归函数fill。该函数先填外圈，然后递归调用自己填内部。函数接口：

fill(number,begin,size)number：表示要填入的起始数据

begin：表示要填的起始位置size：蛇阵的规模要生成一个6*6的蛇阵只要调用：fill(1,0,6)120191817162213231301532233362914423343528135242526271267891011Fill函数的设计思路：自上而下填最左列自左而右填最下行自下而上填最右列自右而左填最上行递归调用fillfill(number,begin,size)关键问题：参数怎么变化（number,begin,size)

递归终止条件120191817162213231301532233362914423343528135242526271267891011关键问题：

（1）递归终止条件

（2）参数怎么变化（number,begin,size)（1）递归终止条件：size==0:函数结束size==1：填写最后一个数字，函数结束（2）参数变化：

规模减2，起始位置为原来的下一行下一列，填入的起始数字为填入一圈后的第一个数字。begin=begin+1size=size-2number在填写数字时随着改变120191817162213231301532233362914423343528135242526271267891011deffill(number,begin,size):

ifsize==0:return

elifsize==1:

myList[begin][begin]=numberreturnelse:foriinrange(begin,begin+size):#setthevalueofthecolfromtoptodown

myList[i][begin]=numbernumber=number+1foriinrange(begin+1,begin+size):#setthevalueoftherowfromlefttoright

myList[begin+size-1][i]=numbernumber=number+1foriinrange(begin+size-2,begin-1,-1):#setthevalueofthecolfromdowntotop

myList[i][begin+size-1]=numbernumber=number+1foriinrange(begin+size-2,begin,-1):#setthevalueoftherowfromrighttoleft

myList[begin][i]=numbernumber=number+1fill(number,begin+1,size-2)#开始填内圈120191817162213231301532233362914423343528135242526271267891011递归vs迭代(循环)递归算法设计容易易读效率略低迭代算法：用循环设计困难有的问题没有直观的迭代算法效率高用迭代能实现的算法基本都能用递归来实现，反之亦然，当然也有例外，如汉诺塔问题递归经典之作——汉诺塔问题

印度古神庙中有三根柱子，第一根柱子上有64个直径大小不同的金盘子，按照由大到小的次序排列。要求借助于第二根柱子将盘子全部移到第三根柱子。整个移动过程符合三条规则：每次只能移动一个盘子盘子只能在三根柱子之间移动在移动过程，三根柱子上的盘子必须保持大盘在下，小盘在上天神说：“当这64个盘子全部移到第三根柱子上时，世界末日就要到了”Hanoi塔问题ABC目标：利用辅助杆C，将A上的盘子全部移到B上规则：每次只能移动一个盘子不允许大盘子放在小盘子上Hannoi塔n＝4（最开始的情况）n＝4（完成情况）ABCABC

srcdstaux

srcdstauxHannoi塔第1步：从开始的杆到辅助杆（src到aux）第2步：从开始杆到目的杆（src到dst）srcdstauxABCABCHannoi塔第3步：从辅助杆到目的杆（aux到dst）第4步：从开始的杆到辅助杆（src到aux）ABCABCHannoi塔第5步：从目的杆到开始杆（dst到src）第6步：从目的杆到辅助杆（dst到aux）ABCABCHannoi塔第7步：从开始杆到目的杆（src到dst）第8步：从开始杆到目的杆（src到dst）ABCsrcdstauxABC

auxdstsrc1-8步就实现了两个关键功能：

(1)把3个圆盘借助B杆从A移到C(2)最后一个盘从A移到B接下去的工作应该是：（3）把C杆上的3个盘借助A移到B整个过程中，盘的个数不断减少，杆子的作用会发生变化，其余处理形式一样——递归解题思路最简单的情况，只有一个盘子：将盘子直接从A移到B大于一个盘子的情况：将除了最下面一个盘子外的所有盘子借助B杆从A移到C将最下面的盘子从A移到B将C上的盘子移到B终止条件ABCdef

moveTower(n,source,dest,temp):ifn==1:print“Movediskfrom”,source,“to”,dest,“.“#搬else:#3步走#先把n-1个塔转移到辅助杆（temp）上，借助的是目标杆（dest）

moveTower(n-1,source,temp,dest)#然后移动最底下那根杆

moveTower(1,source,dest,temp)#把辅助杆上的移动到目标杆上

moveTower(n-1,temp,dest,source)第二个参数:盘子原始栖息地第三个参数:盘子最终栖息地第四个参数:盘子借过的地方38Hanoi塔moveTower函数的应用

defhanoi(n):

moveTower(n,"A","C","B")

>>>hanoi(3)

MovediskfromAtoC.

MovediskfromAtoB.

MovediskfromCtoB.

MovediskfromAtoC.

MovediskfromBtoA.

MovediskfromBtoC.

MovediskfromAtoC.第10章算法分析与设计§10.1查找问题§10.2递归程序设计§10.3分治法（排序问题）§10.4贪心法分治法思想是将难以处理的较大问题分解为若干个较小的子问题，然后分别解决这些子问题，并从子问题的解构造出原问题的解。“分”是指将原问题分解，“治”是指解决问题。“分治”除了分而治之的过程，还有另一个特点——递归。当我们将大问题分解成子问题后，经常会发现子问题与大问题本质上是相同的问题，因此可以利用递归方法来设计算法。所以，分治法常常与递归法结合起来使用。分治法与排序问题（1）选择排序每次从剩下的数据中选择最小值与剩余数据中的最前面一个值交换

[31,41,59,26,53,58,97,93]选择排序实例31415926535897939397585331594126已正确定位9397585341593126已正确定位9397585359413126已正确定位主要任务：循环找最小值交换朴素策略：选择排序def

selSort(nums):n=len(nums)

forbottominrange(n-1):

#循环n-2次

mp=bottom#初始bottom为迄今最小的索引位置

foriinrange(bottom+1,n):

#考虑其他值

ifnums[i]<nums[mp]:

mp=i

#新的迄今最小值的索引位置

nums[bottom],nums[mp]=nums[mp],nums[bottom]易实现，大数据量时效率低3141592653589793

(2)冒泡排序法从头到尾比较相邻的两个元素，将小的换到前面，大的换到后面。经过一趟比较，就把最大的元素交换到了最后一个位置。然后再从头开始到倒数第二个元素进行第二趟气泡……5730421968待冒泡的元素5304217689待冒泡的元素3042156789待冒泡的元素0321456789待冒泡的元素0213456789待冒泡的元素0123456789待冒泡的元素冒泡过程如果在一次起泡中没有发生交换，则表示数据都已排好序，不需要再进行起泡for(i=1;i<n;++i){

从元素0到元素n-i进行起泡，最大的泡放入元素n-i；

if（没有发生过数据交换）break;}怎么表示？defbubbleSort(nums):

n=len(nums)foriinrange(n-1):#对冒泡次数的循环

flag=False#每次循环flag被设为false，只要一次交换，flag就被设为true

forjinrange(n-1-i):

#内循环，控制待冒泡的元素进行两两比较

ifnums[j]>nums[j+1]:nums[j],nums[j+1]=nums[j+1],nums[j]flag=True#一旦发生过两两交换，就置为Trueifflag==False:break

#一趟冒泡中没有发生交换，排序结束

defmain():myList=[45,67,76,54,34,55,90,23]bubbleSort(myList)printmyList冒泡排序源代码特点：很容易实现，但大数据量时效率低(3)合并排序人们在玩扑克牌的时候，经常将手上的牌排成特定的顺序，比如按花色或按大小排序。如果分到的牌不多，玩家一般用一只手将牌呈扇形握持，另一只手去整理排序。然而，如果玩的是用到两三副牌的游戏，每个玩家分到的牌很多，那么玩家就会有手不够大难以排序的烦恼。这时，如果旁边坐着个观战者，玩家可以请这个观战者帮着拿一些牌，两人分别将手中不多的牌进行排序，然后再合并两手牌以完成全部牌的排序。——合并排序的基本思想（大问题分解成小问题，分开排序，再合并）无序的初始扑克牌集合分成二组分解的过程排好序的扑克牌集合合并的过程合并算法：两个集合的最小值，较小者移出到新列表分治法：合并排序数据分成两组或更多组，分别对各组排序，再把已有序的各组合并(merge)成完整有序列表。合并（merge）：定义一个新列表，比较两组各自的第一个数据，小者输出到新列表，由该组的下一个数据顶上来继续比较。当某组没有数据，则将另一组整个输出到新列表。defmerge(lst1,lst2,lst3):合并lst1、lst2到lst3whilelst1和lst2两组都有数据:

输出两组第一个数据的较小者至lst3

更新该组的第一个数据

while某组没有数据了:

将另一组剩余数据输出至lst3分而治之：合并排序合并排序中的合并过程实现:defmerge(list1,list2,mergelist):

i,j,k=0,0,0#i,j为列表1和2的计数，k为列表3的计数n1,n2=len(list1),len(list2)whilei<n1andj<n2:#循环一直到某个列表为空iflist1[i]<list2[j]:#小者进列表3，该列表的下一个值进入下一次比较

mergelist[k]=list1[i]

i=i+1

else:

mergelist[k]=list2[j]

j=j+1

k=k+1

#列表3的下标值

whilei<n1:#列表1还有未合并元素

mergelist[k]=list1[i]

i=i+1k=k+1whilej<n2:#列表2还有未归并元素

mergelist[k]=list2[j]j=j+1k=k+1defmerge(list1,list2,mergelist):whilelen(list1)>0andlen(list2)>0:iflist1[0]<list2[0]:

mergelist.append(list1[0])dellist1[0]else:

mergelist.append(list2[0])dellist2[0]

mergelist.extend(list1)

mergelist.extend(list2)分而治之：合并排序的整体讨论数据分成两组或更多组，分别对各组排序，再把已有序的各组合并(merge)成完整有序列表。对各组排序可以利用递归：对每一组再次应用分而治之的归并排序。满足递归的前提条件:基本情形：组中只有一个数据时无需递归;每次分组都使列表变小，最终会到达基本情形。伪代码：

算法：对datalist执行合并排序

输入：无序的列表datalist

输出：有序的列表datalist

将datalist一分为二：list1，list2

对list1进行合并排序

对list2进行合并排序合并list1和list2，结果放入datalist

合并排序的递归实现：def

mergeSort(nums):n=len(nums)ifn>1:m=n/2nums1,nums2=nums[:m],nums[m:]#分割

mergeSort(nums1)#对nums1进行归并排序，返回排好序的列表

mergeSort(nums2)

#对nums2进行归并排序，返回排好序的列表

merge(nums1,nums2,nums)#合并两个排好序的列表，结果存于nums合并排序中的合并过程实现:defmerge(list1,list2,mergelist):

i,j,k=0,0,0n1,n2=len(list1),len(list2)whilei<n1andj<n2:iflist1[i]<list2[j]:

mergelist[k]=list1[i]

i=i+1

else:

mergelist[k]=list2[j]

j=j+1

k=k+1

whilei<n1:

mergelist[k]=list1[i]

i=i+1k=k+1whilej<n2:

mergelist[k]=list2[j]j=j+1k=k+1第10章算法分析与设计§10.1查找问题§10.2递归程序设计§10.3分治法（排序问题）§10.4贪心法问题的提出：需要在油库A和加油站B、C、D、E、F、G、H之间修建输油管道，图中的虚线表示可能的管道铺设路线，虚线旁标注的数值表示所需铺设的管道的长度（千米）显然没有必要在所有可能路线上铺设管道，而只需要各加油站直接或间接与油库连通即可。假设人手和资金比较紧张，工程只能分批分期进行，每期建设一条管道。我们该如何规划整个工程？图论——最小生成树方法（一）、尽可能快地使加油站投入使用，每一期工程都使一个加油站能够供油。第一期必须在油库A与某个加油站之间铺设管道。找最短路径。Prim算法：

从单一顶点开始，在加权连通图里搜索最小生成树。即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点，且其所有边的权值之和亦为最小。Prim算法：Step1、初始时所有地点标记为不可通达Step2、选择一个特定地点，标记为可通达Step3、重复下列步骤，直至所有地点都被标记为可通达：

选择距离最近的两点，其中一个地点是标记可通达，另一个地点是不可通达。然后将这两个点连接起来，并将原先不可通达的地点改为可通达_=float('inf')#正无穷defmain():

n=8#可让用户输入Vertex=['A','B','C','D','E','F','G','H']graph=[[0,35,_,_,_,_,_,_],[35,0,15,_,_,_,_,_],[_,15,0,5,_,_,25,_],[_,_,5,0,_,_,_,_],[_,_,_,_,0,40,_,_],[_,_,_,_,40,0,_,10],[_,_,25,_,_,_,0,20],[_,_,_,_,_,10,20,0],]

#返回一个标记两两之间是否联通的列表

C=prim(graph,n)#接着开始统计距离，打印线路

Result=[]

Total_dis=0foriinrange(n):forjinrange(n):if(1==C[i][j]):#两地点连通

Result.append((Vertex[i],Vertex[j],graph[i][j]))

Total_dis=Total_dis+graph[i][j]print'FinalResult(totaldistance):%d'%(Total_dis)print'(P1,P2,dis)'printforrinResult:printrdefprim(graph,n):#flagsdenotingwhetherthevertexinconnectedornotflag=[False]*nflag[0]=True#initialconnectionmapconnection=[[0forcolinrange(n)]forrowinrange(n)]fornode_iterinrange(n-1):#有n-1条通路c_i=0c_j=0min_dis=_foriinrange(n):if(flag[i]):#是可通达点

forjinrange(n):dis_ij=graph[i][j]if(not(flag[j])anddis_ij<min_dis):#j为非可通达点min_dis=dis_ijc_i=ic_j=jflag[c_j]=Trueconnection[c_i][c_j]=1returnconnection方法（二）、不追求各加油站尽快投入使用，只想以最小的投资完成工程。这时的指导思想是，每一期工程都尽可能选择当前所有线路中最短的线路来铺设管道，并确保最终能将油库和所有加油站连通起来。Kruskal算法：

在加权连通图里搜索最小生成树，从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。Kruskal实现_=float('inf')defkruskal(graph,n):

#initialconnectionmapconnection=[[0forcolinrange(n)]forrowinrange(n)]fornode_iterinrange(n-1):c_i=0c_j=0min_dis=_foriinrange(n):forjinrange(n):dis_ij=graph[i][j]if(0==connection[i][j]and0==connection[j][i]\anddis_ij<min_disandi!=j):min_dis=dis_ijc_i=ic_j=jconnection[c_i][c_j]=1returnconnectiondefmain():n=8Vertex=['A','B','C','D','E','F','G','H']graph=[[0,35,_,_,_,_,_,_],[35,0,15,_,_,_,_,_],[_,15,0,5,_,_,25,_],[_,_,5,0,_,_,_,_],[_,_,_,_,0,40,_,_],[_,_,_,_,40,0,_,10],[_,_,25,_,_,_,0,20],[_,_,_,_,_,10,20,0],]C=kruskal(graph,n)Result=[]

Total_dis=0foriinrange(n):forjinrange(n):if(1==C[i][j]):

Result.append((Vertex[i],Vertex[j],graph[i][j]))

Total_dis=Total_dis+graph[i][j]print'FinalResult(totaldistance):%d'%(Total_dis)print'(P1,P2,dis)'print

forrinResult:printr贪心算法Prim算法和Kruskal算法都属于贪心（贪婪）算法。贪心算法的特点:

在对问题求解时，总是做出在当前看来是最好的选择。不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最