时间戳

首页 > 解决方案 > 递归算法，显示是否可以从整数列表中选择两个整数，使得它们的差等于给定值

python - 递归算法，显示是否可以从整数列表中选择两个整数，使得它们的差等于给定值

问题描述

完整问题：设计一个递归算法，该算法将显示是否可以从整数列表中选择两个整数，使得两者的差等于给定值。提示：您可能希望调用另一个算法（即函数），它接受更多执行递归的参数。提交一个 python 函数 is_diff_two(values,diff) ，它将一个列表和所需的差异作为一个非负整数并返回 true 或 false。您可以使用的唯一函数是：print、str、int、float、bool、len、list、range、abs、round、pow。我们不会扣除 str() 的使用，但您实际上并不需要它。不要导入库。

允许的关键字：if、elif、else、and、or、not、return、def、assert、

不允许使用关键字：for、while、in、import。

请注意，您不能使用切片（索引中的又名冒号）。

我在实现这个算法时遇到了麻烦；我不确定基本情况是什么，如何使用辅助方法，或者如何在不使用循环或 python 列表切片的情况下解决问题。我目前拥有的是一个名为 check_diff() 的辅助方法，它将一个列表作为参数，递归地遍历列表并将原始列表中值之间的所有可能差异附加到一个新列表中。然后我将在 is_diff_two() 方法中调用该方法，在一行中检查 diff 参数是否在列表中 - 如果是，它应该返回 true，如果不是则返回 false。到目前为止，这就是我的辅助方法所拥有的，但我无法弄清楚如何正确地遍历列表并获得所有可能的差异。

def check_diff(values):
    diff_list = []
    if len(values) == 1:
        return diff_list
    else:
        diff_list.append(values[0] - check_diff(values[1]))
        return values[0] - check_diff(values[1])

标签： pythonalgorithmrecursion

解决方案

您可以创建一个函数，该函数可选地采用给定列表的两个索引，并进行递归调用，第二个索引递增直到超出范围，此时进行递归调用，第一个索引递增直到超出范围，此时False如果在两个索引处没有发现与目标值不同的两个值，则点返回，或者True如果找到任何此类值，则返回：

def is_diff_two(values, diff, a=0, b=1):
    if a == len(values):
        return False
    if b == len(values):
        return is_diff_two(values, diff, a + 1, a + 2)
    return abs(values[a] - values[b]) == diff or is_diff_two(values, diff, a, b + 1)

所以is_diff_two([2, 4, 8], 3)返回False，然后is_diff_two([2, 4, 8], 4)返回True。

推荐阅读