Python数组加法递归

jhdbpxl9 于 2023-01-08 发布在 Python

关注(0)|答案(3)|浏览(107)

我在做coderbyte的挑战我有一个问题ArrayAdditionI，下面是问题的陈述：
'''使用Python语言，让函数ArrayAdditionI（arr）获取存储在arr中的数字数组，如果数组中的任意数字组合可以相加等于数组中的最大数字，则返回字符串true，否则返回字符串false。例如：如果arr包含[4，6，23，10，1，3]，则输出应返回true，因为4 + 6 + 10 + 3 = 23。数组将不为空，将不包含所有相同的元素，并且可能包含负数。“”“
因为我不能这样做，我研究了一个解决方案，我发现这一点：

def countFor(arr, m, s0):
  if len(arr) == 0:
    return False
  a0 = arr[0]
  ar = arr[1:]

  sw = s0 + a0
  if sw == m:
    return True
  if countFor(ar, m, sw):
    return True
  if countFor(ar, m, s0):
    return True
  return False

def ArrayAdditionI(arr): 

  m = max(arr)
  arr.remove(m)
  return str(countFor(arr, m, 0)).lower()

现在，我试着理解代码在每个循环中到底做了什么，我打印出了这个列表[4，6，23，10，1，3]的每个循环的输出：

Input:  [4, 6, 10, 1, 3] 23 0
a0:  4
ar:  [6, 10, 1, 3]
sw:  4
Input:  [6, 10, 1, 3] 23 4
a0:  6
ar:  [10, 1, 3]
sw:  10
Input:  [10, 1, 3] 23 10
a0:  10
ar:  [1, 3]
sw:  20
Input:  [1, 3] 23 20
a0:  1
ar:  [3]
sw:  21
Input:  [3] 23 21
a0:  3
ar:  []
sw:  24
Input:  [] 23 24
Input:  [] 23 21
Input:  [3] 23 20
a0:  3
ar:  []
sw:  23
True

然后我就能理解到底发生了什么，直到最后三个循环，我都不知道是哪部分代码让它从“Input：[] 23 24”改为“输入：[] 23 21”改为“输入：[3] 23 20”。

python

来源：https://stackoverflow.com/questions/38256375/python-array-addition-recursion

3条答案

按热度按时间

guz6ccqo1#

好了，下面是调用。儿童调用相对于其父母缩进：

呼叫countFor([4, 6, 10, 1, 3], 23, 0)
从第一个if调用countFor([6, 10, 1, 3], 23, 4)
从第一个if调用countFor([10, 1, 3], 23, 10)
从第一个if调用countFor([1, 3], 23, 20)
从第一个if调用countFor([3], 23, 21)
从第一个if调用countFor([], 23, 24)
从第二个if调用countFor([], 23, 21)
从第二个if调用countFor([3], 23, 20)

关键是countFor中的第二个递归调用不在elif中--它本身就是if，所以当我们回到调用堆栈后，第二个递归调用也可能发生。

赞(0）回复(0）举报 2023-01-08

wwtsj6pe2#

您还没有跟踪所有的逻辑，只是例程顶部的输入和更新。
在**[] 23 24**，让我们遵循逻辑：

if sw == m:

不...是24对23 ...

if countFor(ar, m, sw):

这将生成您的**[] 23 24行。由于数组有0个元素，调用将立即返回False**。

if countFor(ar, m, s0):

这将生成**[] 23 21行。同样，空数组立即得到False**。
我们再掉一行，并返回一个False到前一个调用。
生成此调用的调用是第一个countFor，调用时带有

if countFor([3], 23, 21):

其中，21是sw的值。我们转到第二个调用，即s0的调用。此时，s0为20，因此调用如下所示：

if countFor([3], 23, 20):

...并且 this 调用看到20+3 = 23 = m，所以它返回True。
你明白了吗？

赞(0）回复(0）举报 2023-01-08

bbuxkriu3#

只需使用包itertools.combinations：

from itertools import combinations

def arrayChallenge(numbers):
    expected_sum = max(numbers)
    numbers.remove(expected_sum)
    
    result = [seq for i in range(len(numbers), 0, -1)
          for seq in combinations(numbers, i)
          if sum(seq) == expected_sum]

    return len(result) > 0

print(arrayChallenge([4, 6, 23, 10, 1, 3]))

赞(0）回复(0）举报 2023-01-08

我来回答

Python数组加法递归

3条答案

相关问题

热门标签

最新问答