最新消息:欢迎光临 魔力 • Python!大家可以点开导航菜单中的【学习目录】,这个目录类似图书目录,更加方便学习!

两道关于递归的练习题

Python教程 小楼一夜听春语 3064浏览 0评论

递归能够锻炼我们的逻辑能力和抽象能力。

递归过程中的每一次计算方法都是一样的。

以下是两道网友提出的问题,对于递归的练习非常有帮助。

第一道题目:

list = [{‘name’:’小红’,sub’:[{‘name’:’小明’,’sub’:[{‘name’:’小花’}]},{’name‘:’小黑’}]}]

这是一个嵌套列表,但是嵌套的可能有n层,如何运用递归函数得到列表中所有的“name”值,并且有层级关系的名字需要拼接起来,得到的结果是“[‘小红’,’小红’/’小明,’小红’/’小明/’小花’, ‘小红’/’小黑’]” 。

解题思路:

因为外层的名字要与内层名字拼接,所以每次获取外层的名字,都要作为参数传入内层,最外层参数默认为空字符串;每一次将外层名字与当前层名字拼接后,都判断是否存在下一层,如果存在则将下一层的列表和当前层的拼接结果作为参数进行递归,并将递归结果与当前结果列表合并。

示例代码:

lst = [{'name': '小红', 'sub': [{'name': '小明', 'sub': [{'name': '小花'}]}, {'name': '小黑'}]}]


def fun(lst, name=''):  # 参数“name”为已从字典中取出的键值
    result = []  # 每次递归的结果列表
    for dic in lst:  # 从列表获取字典
        if name:  # 如果有上一次递归结果
            names = name + '/' + dic['name']  # 上一次递归结果连接当前字典“name”键的值
        else:
            names = dic['name']  # 直接将当前字典“name”键的值存入
        result.append(names)  # 结果列表中添加当前递归结果
        sub = dic.get('sub', None)  # 获取子级列表
        if sub:  # 如果存在子级列表
            result = result + fun(sub, names)  # 当前结果列表与子级结果列表合并
    return result  # 返回每次递归结果列表


print(fun(lst))

第二道题目:

写出python程序,一定要利用递归函数,尽量不用for循环、while循环。

输入整数B代表进制数,再输入两个B进制的数,用列表list_a和list_b表示,输出list_a+list_b的B进制数结果,也可以用列表来表示。

例如,B=16,输入list_a=[10,9,9]和list_b=[9,9],相加后的十六进制结果是[11,3,2];如果B=11,相加后的结果是[1,0,8,7]。

解题思路:

要注意两点,一点是列表长度可能不一致,另外一点是相加之后大于进制数时需要进位1。

每一次递归,我们都取出两个列表的最后一个元素和进位数一起进行求和。

因为列表元素数量可能不一致,当只有一个列表有元素时,只取出有元素的列表最后一位与进位数求和。

如果列表都为空,存在进位数时,直接返回进位数,否则,返回空列表。

对于每一次递归计算出的和,分别获取进位数和余数,并将余数与外层递归结果合并,将进位数作为参数传入下一次递归。

示例代码:

list_a = [10, 9, 9]
list_b = [9, 9]
mod = 11


def fun(mod, lst_a, lst_b, carry=0):  # carry为进位数
    result = []  # 每次递归的计算结果列表
    if lst_a and lst_b:  # 如果列表均不为空
        sum = lst_a[-1] + lst_b[-1] + carry  # 取出每个列表最后一个元素与上一层传入的进位数相加求和
        lst_a.pop(-1)  # 从列表中去除最后一个元素
        lst_b.pop(-1)  # 从列表中去除最后一个元素
    elif lst_a:  # 如果只有lst_a列表不为空
        sum = lst_a[-1] + carry  # 列表最后一位元素与上一层传入的进位数相加求和
        lst_a.pop(-1)  # 从列表中去除最后一个元素
    elif lst_b:  # 如果只有lst_b列表不为空
        sum = lst_b[-1] + carry  # 列表最后一位元素与上一层传入的进位数相加求和
        lst_b.pop(-1)  # 从列表中去除最后一个元素
    else:  # 如果列表均为空
        if carry:  # 如果有进位数
            return [carry]  # 返回进位数
        else:  # 否则
            return []  # 返回空列表
    carry = sum // mod  # 计算当前和按进制计算后的进位数
    remainder = sum % mod  # 计算当前和按照进制计算后的余数
    result = [remainder] + result  # 余数以列表形式与外层递归列表合并
    return fun(mod, lst_a, lst_b, carry=carry) + result  # 进行下一层递归

转载请注明:魔力Python » 两道关于递归的练习题

头像
发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网站 (可选)

网友最新评论 (1)

  1. 头像
    看得懵逼了
    搓小灰9个月前 (04-02)回复