代码收藏家 湖南大学Python头歌实训-实验14：递归与二分法
第4章算法思维4.3.1 二分搜索
第1关：不重复序列二分搜索
#Student start
def findx(A,x):
l,r = 0,len(A)-1
while l<=r:
mid = (l+r)//2
if A[mid] == x:
break
elif A[mid] < x:
l = mid+1
elif A[mid] > x:
r = mid - 1
if A[mid] != x:
return -1
return mid
#Student End
Y = input().split() #输入格式[1,2,3,4,5] 4
A = eval(Y[0])
x = eval(Y[1])
ind = findx(A,x)
print(ind)
第2关：重复序列的二分搜索
#Student start
def findx(A,x):
l,r = 0,len(A)-1
if A[0]==x:
return 0
while l<=r:
mid = (l+r)//2
if A[mid] == x:
break
elif A[mid] < x:
l = mid+1
elif A[mid] > x:
r = mid - 1
if A[mid] != x:
return -1
while A[mid] == x:
mid -= 1
return mid+1
#Student End
Y = input().split()
A = eval(Y[0])
x = eval(Y[1])
A.sort()
ind = findx(A,x)
print(ind)
有点说法，注意第一个数可能就是目标值
第3关：重复序列二分搜索2
#Student start
def findx(A,x):
l,r = 0,len(A)-1
while l<=r:
mid = (l+r)//2
if A[mid] == x:
break
elif A[mid] < x:
l = mid+1
elif A[mid] > x:
r = mid - 1
if A[mid] != x:
return -1
while A[mid] == x:
mid += 1
if mid == len(A):
break
return mid-1
#Student End
Y = input().split()
A = eval(Y[0])
x = eval(Y[1])
A.sort()
ind = findx(A,x)
print(ind)
第4关：重复序列二分搜索3
#Student Start
l= input().split()
li,target = eval(l[0]),eval(l[1])
# print(len(li),target)
def s(li,target):
l,r = 0,len(li)-1
while l<=r:
mid = (l+r)//2
if li[mid] == target:
break
elif li[mid] < target:
l = mid+1
elif li[mid] > target:
r = mid - 1
# print(mid)
if li[mid] != target:
print(f"{target}不在列表中")
return -1
while li[mid] == target:
mid -= 1
if mid<0:
print(f"{target}已经是列表中最小的数")
return -1
return mid
t = s(li,target)
if t!=-1:
print(f"比{target}小的最大的数是{li[t]}最后出现的下标位置为{t}")
#Student End第4章算法思维4.3.2 二分法求方程的根
第1关：给定方程给定单调上升区间方程的根
def f(x):
return x**2-10*x+3
#Student Start
for i in range(7,13):
if f(i)==0:
print("i"+".0000")
elif f(i)*f(i+1)<0:
l,r = i,i+1
while r-l>1e-4:
m = (l+r)/2
if f(m)*f(r)<0:
l = m
else:
r = m
print(f"{m:.4f}")
########## end ##########
#Student End
一招鲜吃遍天
第2关：给定方程给定单调下降区间方程的根
def f(x):
return x**2-10*x+3
#Student Start
for i in range(-2,2):
if f(i)==0:
print("i"+".0000")
elif f(i)*f(i+1)<0:
l,r = i,i+1
while r-l>1e-4:
m = (l+r)/2
if f(m)*f(r)<0:
l = m
else:
r = m
print(f"{m:.4f}")
#def findroot(a,b,eps):路径依赖了已经
第3关：给定方程给定区间内所有方程的根（可能多个）
def f(x):
return x**2-10*x+3
#Student Start
for i in range(-2,12):
if f(i)==0:
print("i"+".0000")
elif f(i)*f(i+1)<0:
l,r = i,i+1
while r-l>1e-4:
m = (l+r)/2
if f(m)*f(r)<0:
l = m
else:
r = m
print(f"{m:.4f}")有难一点的题目可能步长要更小一点
第四章-算法思维-4.2 递归函数
第1关：递归算法求n！
def factorial(n):
if n == 1:
return 1
return n*factorial(n-1)
x = eval(input())
print(f"{x}!={factorial(x)}")第2关：累加和的递归算法
#请用递归算法实现
def s(n):
if n==1:
return 2
return 2**(n)+s(n-1)
x = eval(input())
print(s(x)+1)第3关：汉诺塔问题
#请实现函数
def Hanoi(n,source,auxiliary,target):
if n==1:
print(f"{source} -> {target}")
else:
Hanoi(n-1,source,target,auxiliary)
Hanoi(1,source,auxiliary,target)
Hanoi(n-1,auxiliary,source,target)
n = eval(input())
Hanoi(n,"A","C","B")画图试试吧，或者b站上找个视频看看，入门递归真的很合适
第4关：计算黄金分割
#请在下面输入代码
def b(n):
if n==0:
return 1
else:
return 1+1/b(n-1)
x = eval(input())
if x<=0:
print("请输入正整数")
else:
print(f"{b(x)-1:.6f}")
第5关：集合表示自然数
#请在下面输入代码
def F(n,mem):
def S(n,f,mem):
a = []
if mem[n][0]:
return mem[n][0]
for i in range(n):
a.append(f(i,mem))
mem[n][0] = ",".join(a)
return mem[n][0]
if n == 0:
return "{}"
return "{"+S(n,F,mem)+"}"
x = eval(input())
mem = [[0] for _ in range(x+1)]
a = F(x,mem)
print(a)
博主当时写了一个小时，逗号一直加不对。。。
总结：
递归期末不考大题，但是是学习很多算法的基础，感兴趣的同学可以多了解
作者：湖大方脸
