一、编程题
1、36.统计高分问题
小张在学习对分查找后，想利用该思路来实践一下，加深对该算法的理解。于是他按老师的要求，统计期末考试成绩，总分比他高的同学有多少个？
他的思路是，首先将全区所有学生的成绩降序排序，然后利用对分查找思想解决。他编写的代码如下，请完善划线处的代码。
cj =[654,643,621,612,609,606,...]#学生成绩存列表cj并已经降序排序
def dfsearch(key):
i =0; j=len(cj)-1
while i<=j:
m =(i+j)//2
if cj[m]>key:
①
else:
j-= 1
return ②
key = int(input('输入待查找的成绩'))
pos = ③
print('高于',key,'分的人数有',pos)
参考答案：1. ①处应填：i = m + 12. ②处应填：return j3. ③处应填：dfsearch(key)
解析：【喵呜刷题小喵解析】：
这道题目考查了对分查找算法的应用。小张想要统计全区成绩比自己高的学生数量，可以首先对成绩进行降序排序，然后利用对分查找的思想，从列表的中间位置开始查找，如果中间位置的成绩大于自己，那么说明自己之前的所有学生成绩都大于自己，只需要返回j（即中间位置）即可；如果中间位置的成绩小于自己，那么说明自己之前肯定没有比自己高的成绩，那么自己应该在中间位置之后的位置，于是可以将搜索范围缩小到中间位置的右边，重复以上步骤。
所以，根据以上思路，我们可以得出以下代码：
```python
cj =[654,643,621,612,609,606,...] #学生成绩存列表cj并已经降序排序
def dfsearch(key):
i =0; j=len(cj)-1
while i<=j:
m =(i+j)//2
if cj[m]>key:
i = m + 1 # 如果中间位置的成绩大于key，将搜索范围缩小到m的右边
else:
j-= 1 # 如果中间位置的成绩小于key，将搜索范围缩小到m的左边
return j # 最终返回j，即成绩大于key的最后一个位置，也就是成绩大于key的学生数量
key = int(input('输入待查找的成绩'))
pos = dfsearch(key)
print('高于',key,'分的人数有',pos)
```
其中，①处应填：i = m + 1，表示将搜索范围缩小到m的右边；
②处应填：return j，表示返回成绩大于key的最后一个位置，也就是成绩大于key的学生数量；
③处应填：dfsearch(key)，表示调用函数进行对分查找。
2、37.比岁数问题
有5个人坐在一起，问第五个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第3个人大2岁。问第三个人，又说比第2人大两岁。问第2个人，说比第一个人大两岁。
最后问第一个人，他说是10岁。请问第五个人多大？
请运用递归算法完成以下代码。
def age(n):
if ① :
c = 10
else:
c = ②
return c
print(age( ③ ))
参考答案：```pythondef age(n):if n == 1:c = 10else:c = age(n-1) + 2return cprint(age(5))```
解析：【喵呜刷题小喵解析】：
在这个问题中，第五个人比第四个人大2岁，第四个人比第三个人大2岁，以此类推。第一个人是10岁，这是已知的。我们需要找出第五个人的年龄。
在这个情况下，递归是一个很好的选择。递归函数会重复调用自己，每次调用时，参数的值都会改变，直到满足某个终止条件。在这个问题中，终止条件就是n等于1，因为第一个人是10岁。
在Python中，递归函数可以像这样编写：
```python
def age(n):
if n == 1:
c = 10
else:
c = age(n-1) + 2
return c
```
在这个函数中，如果n等于1，函数返回10（因为第一个人是10岁）。否则，函数返回age(n-1) + 2，其中age(n-1)是前一个人的年龄，加2是因为题目中说每个人都比前一个人大2岁。
最后，我们调用函数age(5)，打印出第五个人的年龄。
3、38.数学证明问题
上世纪中期，校园里流行一种数学游戏，其规则十分简单：任意取一个自然数，若它是奇数，则把它乘以3加上1，若它是偶数，则除以2。按此规则进行下去，经过若干步的计算就能得到自然数1。这个数学现象至今都没有得到完全的证明，但是可以编程来验证它的正确性。
实现上述功能的部分程序代码如下，请补充完成空白处的内容。
step = 1
midlist = []
def subwork(n):
global step
if n == 1:
return step
elif n % 2 == 0:
n = ①
midlist. append(n)
step += 1
subwork( ② )
return step
elif n % 2 != 0:
n = ③
midlist. ④
step += 1
subwork( ⑤ )
return step
cur_num = int(input("请输入一个数字："))
subwork(cur_num)
print(midlist)
print(step)
参考答案：① n = n / 2② n // 2③ n = 3 * n + 1④ append(n)⑤ n // 2
解析：【喵呜刷题小喵解析】：
根据题目描述，这是一个数学游戏，其规则是：任意取一个自然数，若它是奇数，则把它乘以3加上1，若它是偶数，则除以2。我们需要补充完成空白处的内容，以完成这个数学游戏的程序实现。
1. 对于偶数的处理：
* 偶数除以2得到一个新的偶数，所以需要补充的是`n = n / 2`。
* 将新的偶数添加到`midlist`列表中，即`midlist.append(n)`。
* 递归调用`subwork`函数，并传入新的偶数，即`subwork(n // 2)`。
2. 对于奇数的处理：
* 奇数乘以3再加上1得到一个新的奇数，所以需要补充的是`n = 3 * n + 1`。
* 将新的奇数添加到`midlist`列表中，即`midlist.append(n)`。
* 递归调用`subwork`函数，并传入新的奇数，即`subwork(n)`。
根据以上分析，我们补充了空白处的内容，完成了这个数学游戏的程序实现。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
