第四章 递归

代码粗糙，望大佬指出方便改进

#4.1 front为头指针，rear为尾指针 def recursion(li,front,rear): if front==rear or front+1==rear: return max(li[rear],li[front]) return max(recursion(li,front,int((front+rear)/2)),recursion(li,int((front+rear)/2)+1,rear)) print('空间复杂度为n;\n时间复杂度为log2(n^2)\n'+ '过程：log2(n)+log2(n/2)+log2(n/2/2)+···\n'+ '=log2(n)*(1/2+1/2/2+1/2/2/2+···)\n' '=log(n)*lof(n)') #4.6 def text6(n): if n==1: return 1 return text6(n-1)+1/n #4.7 f为头指针，r为尾指针 def text7(s,f,l): if f==l: return 0 return text7(s,f+1,l)+int(s[f])*10**(l-f-1) #4.8 def text8(): print('n/2+n/2/2+···+n/(2^logn)\n=(n/2)*(1+1/2+1/4+1/(2^logn))\n=n/2*log(logn)\n=nlogn') #4.9 f为头指针，r为尾指针 def text9(li,f,r): if f==r or f+1==r: return max(li[f],li[r]),min(li[f],li[r]) front,rear=text9(li,f,int((f+r)/2)),text9(li,int((f+r)/2+1),r) return max(front[0],rear[0]),min(front[1],rear[1]) #4.10 def text10(num,res=0): if num==1: return res return text10(num//2,res+1) #4.11 def text11(li,f,m,r): if f==r: return True elif m==r+1: return text11(li,f+1,f+2,r) elif li[f]==li[m]: return False else: return text11(li,f,m+1,r) #4.12 def text12(m,n): if n==1: return m t=text12(m,n//2) if n%2==1: return t+t+m else: return t+t #4.13 def text13_(m): if m==0: return 0 a=text13_(m-1)+m #用来计算当前长度 print('-'*m) b=text13_(m-1) #用来进入英式尺的下半部分 #print(a,b) return a+b def text13(c): print(text13_(c),2**(c+1)-c-2) #4.14 def text14(n,a,b,c): if n==1: print(a,'-->',c) else: text14(n-1,a,c,b) text14(1,a,b,c) text14(n-1,b,a,c) #4.15 lis为元素，res为结果返回字典，r为长度，floor为当前处理的子集长度 def text15(lis,res,r,floor=1): if floor == r+1: return res elif floor==1: res[floor]=lis return text15(lis,res,r,floor+1) else: temp=[] for i in res[floor-1]: if i[-1]!=lis[-1]: for j in range(lis.index(i[-1])+1,r): temp.append(i+lis[j]) res[floor]=temp return text15(lis,res,r,floor+1) def text15_(): a=dir() print(list(text15(['1','2','3','4','5'],a,5))) #4.16 s为字符串，n为长度 def text16(s,n): if n==0: return '' return text16(s,n-1)+s[-n] #4.17 n为长度-1 def text17(s,n): if n==len(s)//2-1: return True if s[len(s)-n-1]!=s[n]: return False return text17(s,n-1) #4.18 n为字符串长度-1 f为辅音元素个数，y为原音元素个数 def text18(s,n,f=0,y=0): if n==0: return f<y elif s[n] in ['a','e','i','o','u','A','E','I','O','U']: return text18(s,n-1,f,y+1) else: return text18(s,n-1,f+1,y) #4.19 s为列表，n为长度-1 res为字典 def text19(s,n,res=dir()): if n==-1: return res if s[n]%2==1: res['r'].append(s[n]) else: res['f'].append(s[n]) return text19(s,n-1,res) #4.20 l为列表 k为指定数值，n为长度-1 f，r默认 #时间复杂度为n def text20(l,k,n,f=[],r=[]): if n==-1: return f+r if l[n]<=k: f.append(l[n]) else: r.append(l[n]) return text20(l,k,n-1,f,r) #4.21 '''先分半查询，找到二倍元素值大于所需要的值然后在这些值中向前找小数''' # li为答案序列，key为目标值,其它为默认值 # 时间复杂度为O(n)：首先找到中间值，为logn然后遍历中间值的前部分n/2 # 所以时间复杂度为 logn+n/2=O(n) def text21(li,key,f=0,l=0,sec=True,res=[]): if f==len(li): return res if li[f]*2<=key: return text21(li,key,(f+len(li)-1)//2+1,f,sec,res)#后移 elif li[f]*2>key and li[f-1]*2>key and sec: return text21(li,key,(f+l)//2,l,sec,res)#前移 elif li[f]*2>key and li[f-1]*2<=key and sec: return text21(li,key,f,f-1,False,res)#结束寻找 else: for i in range(l,-1,-1): if li[f]+li[i]==key: res.append((li[f],li[i])) return text21(li,key,f+1,i,False,res) elif li[f]+li[i]<key: return text21(li,key,f+1,i,False,res) #4.22 def text22(num,p): li=[] su=num if p==0: print(0) return 0 while p!=1: temp=p//2 li.append(p-temp*2) p=temp for i in range(-1,-(len(li)+1),-1): su*=su su*=(num**li[i]) print(su) #4.23 def text23(p,t=0): import os if os.path.isdir(p): print(' '*t+'#'+p)# #为文档 for filename in os.listdir(p): chilepath=os.path.join(p,filename)#拼接路径函数 text23(chilepath,t+1) else: print(' '*t+'*'+p)#*为文档 #4.24 #使用set在U上防止出错 def text24(k,L,U): for i in U: L.append(i) U.remove(i) text24(k,L,U) if k==L: print(L) return L.remove(i) U.add(i) #4.25 c为数字 def text25(c): if c==1: print('-') else: li=[] for i in range(1,c+1): li.append(i) li.extend(li[:-1]) for i in li: print('-'*i) #4.26 def text26(n,a,b,c): if n==1: print(a,'->',c) else: text26(n-1,a,c,b) text26(1,a,b,c) text26(n-1,b,a,c) #4.27 #题目要求不是很清楚，按照理解作出代码 def text27(p): import os l1=[] l2=[] for i in os.listdir(p): if os.path.isdir(p+'/'+i): l1.append(i) else: l2.append(i) return p,l1,l2

仅供参考，并非标准答案，标准答案只提供给教师，学者难以获取

如有问题可留言或私信，大家一起学习