definverseNum(nums): sum=0 iflen(nums)==1: return0 for i inrange(1,len(nums)): if nums[0]>nums[i]:#判断num[0]相对数组是否有逆序数，有着sum+1 sum=sum+1 returnsum+inverseNum(nums[1:])#递归 nums=[1,2,3,4,5,4,3] print(inverseNum(nums))
defmaxGap(nums): max=nums[0] min=nums[0] for i inrange(0,len(nums)):#找到数组的最大值与最小值 if nums[i]>max: max=nums[i] if nums[i]<min: min=nums[i] iflen(nums)==2:#如果数组长度为2，返回2值之差 returnabs(nums[0]-nums[1]) length=(max-min)/(len(nums)-1)#将最大值与最小值之间平均分为n-1个范围 low,high,count={},{},{} for j inrange(0,len(nums)-1): low[j]=max+1#将每个范围的左坐标赋值为数组max+1 high[j]=min-1#将每个范围的右坐标赋值为数组min-1 count[j]=0#count用来记录数组中的值落在范围中的个数 for i inrange(0,len(nums)):#对数组中每个数遍历，找到每个数应该在哪个范围 index=(nums[i]-min)//length#index表示数在第index+1个范围内 if index==len(nums)-1: #当index为n-1时，表示该数为最大值，index-1,分在第index+1即第n-1个范围内 index-=1 if nums[i]<low[index]: #low[index]最开始赋值为max+1，即第一次落在该范围内的数赋给low[index] #之后落在该范围内数如果比low[index]小，即将该数赋给low[index] low[index]=nums[i] if nums[i]>high[index]: #high[index]最开始赋值为min+1，即第一次落在该范围内的数赋给high[index] #之后落在该范围内数如果比high[index]大，即将该数赋给high[index] high[index]=nums[i] count[index]+=1#第index+1个范围内每落入一个数，count[index]+1 i=0 maxgap=0 for i inrange(1,len(nums)-1): #因为除了min和max还有n-2个数，放入到n-1个范围内，必至少有一个范围内没有数放入 #且易知没有数的范围两边的范围内的数之间的间距比在同一范围内的数的间距大 #因此数组最大间距必是相邻范围内差距 if count[i]==0: #当范围内没有放入数时，该范围最小值与最大值都设为左边的范围的最大值 low[i]=high[i-1] high[i]=low[i] if low[i]-high[i-1]>maxgap: #求2个范围之间的差距，差距最大值即为数组的最大差距 maxgap=low[i]-high[i-1] return maxgap nums=[1,2,3,5,6,4,4,9] print('最大间隙为',end='') print(maxGap(nums))
defchess(tr,tc,pr,pc,size):#tr，tc为左上角在棋盘中的位置，pr，pc为特殊棋子的位置，size为棋盘大小 global mark global table if size==1: return mark+=1#每次新的递归当size大于1时，用新的l型方块填，即mark+1 count=mark#为count赋值mark half=size//2#half为size大小的一半 if pr<tr+half and pc<tc+half:#如果特殊棋子的位置小于初始位置+half，即特殊棋子在左上角，则在左上角棋盘递归 chess(tr,tc,pr,pc,half) else:#如果特殊棋子不在左上角，则在右下角用count型覆盖，并使右下角定义为特殊棋子，再递归左上角 table[tr+half-1][tc+half-1]=count chess(tr,tc,tr+half-1,tc+half-1,half) if pr<tr+half and pc>=tc+half:#如果特殊棋子在右上角 chess(tr,tc+half,pr,pc,half) else: table[tr+half-1][tc+half]=count chess(tr,tc+half,tr+half-1,tc+half,half) if pr>=tr+half and pc<tc+half:#如果特殊棋子在左下角 chess(tr+half,tc,pr,pc,half) else: table[tr+half][tc+half-1]=count chess(tr+half,tc,tr+half,tc+half-1,half) if pr>=tr+half and pc>=tc+half:#如果特殊棋子在右下角 chess(tr+half,tc+half,pr,pc,half) else: table[tr+half][tc+half]=count chess(tr+half,tc+half,tr+half,tc+half,half) defshow(table): n=len(table) for i inrange(n): for j inrange(n): print('%2s'%table[i][j],end=' ') print('') mark=0 n=8 table=[[-1for x inrange(n)] for y inrange(n)]#初始化table chess(0,0,2,5,n) show(table)
import math import random minDitsance=float("inf") defdistance(x,y):#求出x，y两点间的距离 h=math.sqrt((x[0]-y[0])**2+(x[1]-y[1])**2) #print(x,y) return h defmin_between(left,right,minDitsance):#找到左右各取一点的距离的最小值 x=float("inf") mini=left[-1][0]-minDitsance#比较范围最小值为左边最右点的x值减去已知最小距离 maxi=left[-1][0]+minDitsance#比较范围最大值为左边最右点的x值加上最小距离 #print(minDitsance) for i in left:#取左边的点 if (mini<i[0]<maxi):#当左边点x轴在离左边最右点一个最小距离内时 for j in right: if ((mini<j[0]<maxi)andabs(i[1]-j[1])<minDitsance): #当i，j的y值也在左边最右点y值一个最小距离内时求出这些点的最小距离 x=min(x,distance(i,j)) return x defdivide(list):#递归法求最小距离 global minDitsance if (len(list)==2):#列表长度为2是返回两点距离 return distance(list[0],list[1]) if (len(list)<2):#长度小于2返回inf returnfloat("inf") else: i=int(len(list)/2) left = list[0:i] right = list[i:]#长度大于2时，将已经按x轴排序的点分割为左一半元素,右一半元素,左右分别求最近点 s1=divide(left)#且用递归对分开的2边继续分直到找到最近点 s2=divide(right) #print(left) #print(right) s3=min_between(left,right,minDitsance) s=min(s1,s2,s3)#最后进行比较,将左，右两边的最近距离与左右各取一点的最短距离比较取最短 minDitsance=min(s,minDitsance) return minDitsance defminDistancePoints(point,minDistance):#求出取最短距离的两点 for i in point: for j in point: if distance(i,j)==minDistance and i[0]>=j[0]: print('最短距离的两点为',end='') print(i,j) n=10 point = [(random.randint(0, 50), random.randint(0, 50)) for i inrange(0, n)] point.sort() print(point) minDistance=divide(point) minDistancePoints(point,minDistance) print(minDistance)
