帕斯卡三角形与递归

Question

好的,有人可以告诉我,我的当前代码是否可行.我必须使用输入创建pascals三角形而不使用任何循环.我一定会递归.

我花了3天时间,这是我能想到的最好的输出.它驱使我INSANE

def pascal(curlvl,newlvl,tri):

  if curlvl == newlvl:
    return ""

  else:

    tri.append(tri[curlvl])

    print(tri)
    return pascal(curlvl+1,newlvl,tri)


def triLvl():
  msg = "Please enter the number of levels to generate:"

  triheight = int(input(msg))

  if triheight < 1:
    print("\n Sorry, the number MUST be positive\n Please try again.")
    return triLvl()

  else:
    return triheight



def main():

   triangle = [1]

   curlvl = 0

   print("Welcome to the Pascal's triangle generator.")

   usrTri = triLvl()
   print(triangle)
   pascal(curlvl,usrTri,triangle)



main()

Answer 1

pascal我们可以使用辅助函数 来定义递归pairs。

\n

pascal将返回[[Int]]（Int 数组的数组）。例如，pascal(3)将返回

\n

[ [1],\n  [1, 1],\n  [1, 2, 1] ]\n

\n

好的，我将首先向您展示所有代码，然后我将逐步解释并解释某些部分。

\n

def pairs (xs):\n  if 2 > len(xs):\n    return []\n  else:\n    return [xs[0:2]] + pairs(xs[1:])\n\ndef pascal (n):\n  def compute (prev):\n    return [1] + [x + y for (x,y) in pairs(prev)] + [1]\n  def aux (m, prev):\n    if (m > n):\n      return []\n    else:\n      return [prev] + aux(m + 1, compute(prev))\n  return aux(1, [1])\n\n[print(line) for line in pascal(5)]\n# [1]\n# [1, 1]\n# [1, 2, 1]\n# [1, 3, 3, 1]\n# [1, 4, 6, 4, 1]\n

\n\n

解释

\n

我们真正关心的是pascal功能。我们所写的其他内容都是从我们的写作方式中诞生的pascal，所以我将首先回顾一下这一点。

\n

编写递归函数的一种非常常见的方法是使用内部辅助函数来跟踪计算的各种状态。我们将使用这种技术作为我们pascal函数的基础。

\n

def my_recursive_func (<parameters>):\n  def aux (<state_parameters>):\n    if (<base_condition>):\n      return <base_value>\n    else\n      return aux(<updated_state>)\n  return aux(<initial_state>)

\n

我们已经知道如何为我们的函数填写一些样板文件pascal：

\n

\n
• parameters应该只是n, 一个 Integer ，因为我们希望调用我们的函数，例如pascal(3)orpascal(5)等​​ \xe2\x80\x93 不应该接受其他参数
\n
• state_parameters\xe2\x80\x93 我们现在只知道两件事：1）我们需要一些m计数到 的值n，每次 \xe2\x80\x93 都会递增1；2）一些允许我们计算下一行的值；我们会这样称呼它，prev因为每个 pascal 行都是根据前一行计算的
\n
• base_condition\xe2\x80\x93 当m == n我们知道我们已经生成了我们需要的所有行时，这就是我们想要停止递归的时候
\n
• base_value\xe2\x80\x93 这是返回的最后一个值 \xe2\x80\x93 不太确定应该是什么
\n
• updated_state\xe2\x80\x93 我们将m使用更新m + 1，并且我们将使用某种数组串联来更新行 \xe2\x80\x93 在我们编写更多代码之前并不完全确定
\n
• initial_state\xe2\x80\x93 我们将从 开始m，1pascal 的第一行是[1]
\n

\n

好的，让我们填写目前为止的内容：

\n

def pascal (n):\n  def aux (m, prev):\n    if (m > n):\n      return ?\n    else:\n      return aux(m + 1, ?)\n  return aux(1, [1])

\n

我们希望建立pascal这样的结果：

\n

[[1]] + [[1, 1]] + [[1, 2, 1]] + [[1, 3, 3, 1]], ...]\n# => [ [1], [1 ,1], [1, 2, 1], [1, 3, 3, 1], ... ]\n

\n

因此，为了写入base_value和 更新后的状态prev，我们需要考虑此返回类型。我们想要返回[[Int]]，它是一个列表，因此 base_value可以简单地是空列表，[]。

\n

这意味着在每一步中，我们实际上都希望将其[prev]连接 ( +) 到递归结果......

\n

[prev] + aux(m + 1, <next_row>)

\n

我们现在已经非常接近了。让我们pascal再次更新看看我们需要完成什么：

\n

def pascal (n):\n  def aux (m, prev):\n    if (m > n):\n      return []\n    else:\n      return [prev] + aux(m + 1, <next_row>)\n  return aux(1, [1])

\n

好的，现在到了计算下一行的困难部分 \xe2\x80\x93 ，对吗？嗯，实际上还不错。

\n

# Given\n[1,2,1]\n\n# the next row is\n[1, (1 + 2), (2 + 1), 1]\n

\n

或者另一个例子

\n

# Given\n[1, 4, 6, 4, 1]\n\n# the next row is\n[1, (1 + 4), (4 + 6), (6 + 4), (4 + 1), 1]\n

\n

所以模式是这样的：创建一个以 开头的新数组1，然后对于前一行中的每对数字，将这两个数字相加并将每个总和附加到数组中，最后附加另一个1。我们可以在 Python 中使用列表推导式来表达这一点，如下所示：

\n

[1] + [x + y for (x,y) in pairs(prev)] + [1]\n

\n

现在我们只需要弄清楚这个pairs函数。pairs应有以下合同：

\n

pairs([])        => []\npairs([a])       => []\npairs([a,b])     => [[a,b]]\npairs([a,b,c])   => [[a,b],[b,c]]\npairs([a,b,c,d]) => [[a,b],[b,c],[c,d]]\n

\n

现在让我们实现它并验证我们的实现是否履行了合同。请注意，我在 之外实现此函数，因为pascal它是一个通用函数并且本身很有用。为了计算帕斯卡行，我们需要添加数字对，但是添加或如何获得这些数字对或数字不应该由函数本身负责pascal。

\n

def pairs (xs):\n  if 2 > len(xs):\n    return []\n  else:\n    return [xs[0:2]] + pairs(xs[1:])\n\nprint(pairs([]))        # []\nprint(pairs([1]))       # []\nprint(pairs([1,2]))     # [[1,2]]\nprint(pairs([1,2,3]))   # [[1,2],[2,3]]\nprint(pairs([1,2,3,4])) # [[1,2],[2,3],[3,4]]\n

\n

好的，现在我们已经很接近了。让我们pascal再次更新该函数，看看我们现在处于什么位置：

\n

def pascal (n):\n  def aux (m, prev):\n    if (m > n):\n      return []\n    else:\n      return [prev] + aux(m + 1, [1] + [x + y for (x,y) in pairs(prev)] + [1])\n  return aux(1, [1])

\n

圣烟！我们已经完成了。aux不过，对下一行进行内联计算的调用看起来有点忙。让我们在里面添加另一个助手pascal来compute清理东西。现在我们完成了！

\n

def pascal (n):\n  def compute (prev):\n    return [1] + [x + y for (x,y) in pairs(prev)] + [1]\n  def aux (m, prev):\n    if (m > n):\n      return []\n    else:\n      return [prev] + aux(m + 1, compute(prev))\n  return aux(1, [1])

\n\n

彻底

\n

如果您希望显示愚蠢的文本和提示，您可以编写main如下内容。这使得所有 I/O 与我们的pascal和pairs函数分开。在程序的早期考虑这种关注点分离和副作用管理非常重要，因为很难重用那些超出我们期望的功能的函数。

\n

def main ():\n  try:\n    print("Pascal triangle generator")\n    n = int(input("Pascal(x): x = "))\n    if n < 1: raise\n    [print(line) for line in pascal(n)]\n  except:\n    print("enter a non-zero positive integer")\n    main()\n\n# run program\nmain()\n

\n

继续跑步pascal(300)或者做一些其他的事情，以获得一些令人印象深刻的结果。

\n