3

我正在尝试定义一个过程，该过程采用 columnc和 row ，从三角形中该点的数字开始r计数并返回：0

def pascal(c: Int, r: Int): Int = {
    if (c <= 0) 1
    else
        println(pascal(r, c-1) * (r-c)/c)
        pascal(r, c-1) * (r-c)/c
}

当我运行我的代码时：

>>>pascal(1,3)

我有以下错误：

pascal: (c: Int, r: Int)Int
java.lang.StackOverflowError

我该如何解决？

谢谢。

4

6 回答 6

9

要获得帕斯卡三角形的一个元素，您只需添加上一行的 2 个元素。

以下代码将正确执行此操作。

def pascal(c: Int, r: Int): Int = {
    if (c <= 0 || c == r) 1
    else pascal(c, r-1) + pascal(c-1, r-1)
}
于 2014-09-22T09:13:02.570 回答
3

我不认为你应该pascal在你的 中再次调用函数println，你也应该使用花括号。我稍微改写了一下：

def pascal(c: Int, r: Int): Int = {
  var p = 1
  if (c > 0) {
    p = pascal(r, c-1) * (r-c)/c 
    println(p)
  }
  p
}

这打印为pascal(1,3)：

-1
-2

更新：我很想写一个正确的解决方案，这就是我最终得到的：

  def fact(n: Int, r: Int=1): Int = if (n==0) r else fact(n-1, n*r)

  def pascal(c: Int, r: Int): Int = {
    fact(c) / (fact(r) * fact(c-r))
  }

  def main(a: Array[String]) { 
    println(pascal(3, 2))
  }

唯一的问题（我知道）是坐标必须是正确的，索引从 0 开始。任何超出帕斯卡三角形范围的东西都会导致除以零，这包括 OP 给出的示例pascal(1,3)- 只有两个数字第 1 行。

于 2013-09-24T10:19:15.690 回答
3

你可以试试这个版本，它计算与帕斯卡三角形的条目相同的二项式系数：

  def pascal(col: Int, row: Int): Int = {

    val l = if (col > row / 2) col else row - col
    @tailrec
    def go(i: Int, acc: Int): Int = {
      if (i == l + 1) acc
      else go(i + 1, acc * (row - l + i) / i)
    }
    return go(1, 1);
  }

该解决方案使用尾递归，因此 StackOverflowError 在这里不是威胁。

于 2013-09-24T11:46:00.913 回答
2

你的帕斯卡三角算法是不正确的，但可能你还没有写完，所以我不会告诉你如何写一个正确的算法，只是告诉你如何阻止堆栈溢出。

编辑：maksimov 是对的，因为忘记将else序列包装在大括号中，您只是使第一个表达式有条件，这意味着第二个表达式总是被评估并无限循环到堆栈溢出中。但是，添加大括号只会将堆栈溢出的 100% 概率更改为堆栈溢出的可能性，因为对pascal函数的调用不在尾部位置。要消除堆栈溢出的风险，您必须进行进一步的修改，如下所述...

递归函数可以通过使用尾递归来避免堆栈溢出。但是，要使其正常工作，递归调用必须位于tail 位置。也就是说，递归调用必须是函数返回之前要执行的最终表达式，并且它的值必须不加修改地返回，一直返回堆栈到第一次调用。由于您的计算使用pascal(r, c-1) * (r-c)/c，因此您总是在返回修改后的结果之前修改返回的值，因此调用不在尾部位置。您需要修改您的函数，以便当它最终返回时，它无需修改即可给出正确的结果。最终结果应该有这个基本的形状......

def pascal(c: Int, r: Int): Int = {
  ...
  if (c <= 0) 1 else pascal(..., ...)
}

你会发现这样做的唯一方法是在你的 pascal 函数中定义一个局部函数并让它进行递归......

def pascal(c: Int, r: Int): Int = {
  def loop(...): Int = ... match {
    case ... => 1
    case ... => x + y
    case ... => loop(...)
    case _ => loop(...)
  }
  ...
  if (c <= 0) 1 else loop(...)
}

这是因为递归函数必须检查状态以确定它是否解决了最终问题或问题中的子任务。状态可以是传递给的额外参数loop或在顶层定义的本地变量pascal

只有将递归安全地移动到本地函数中，才能安全地执行 maksimov 建议的操作

var p = if (c <= 0) 1 loop(...)
println(p)
p

您可以安全地执行此操作，因为递归调用都发生在内部loop并且都（如果您使用我的模板）在尾部位置。

需要明确的是：连续两次调用您的pascal函数不是溢出的原因。代码中的两个顶级调用是连续的，不会相互干扰；如果一个完成，另一个也将完成。如果第一个失败，第二个也会失败（删除第一个不会阻止第二个失败）。

于 2013-09-24T10:49:58.220 回答
0

这是整个代码的示例：

object Main {

  def main(args: Array[String]) {
  println("Pascal's Triangle")

 for (row <- 0 to 10) {
  for (col <- 0 to row)
    print(pascal(col, row) + " ")

    println()
  }
 }


def pascal(c: Int, r: Int): Int = {
 if ( c <= 0 || c == r ){
    return 1
  }

  return pascal(c, r - 1) + pascal(c - 1, r -1)
}

}
于 2015-12-29T23:30:42.557 回答
-1

纯函数式编程

def printPascalsTriangle(n: Int): Unit ={

    // n=1 print 1
    // n=2 print 1 1
    // n=3 print 1 2 1   List(prev(0),prev(0+1),prev(1))
    // n=4 print 1 3 3 1 List(prev.head,prev(0+1),prev(1+2),prev.reverse.head)

    def combine(oldList: List[Int], newList: List[Int]) = List(oldList.head) ::: newList ::: List(oldList.reverse.head)

    def g(prevList:List[Int],v:Int) = List(prevList(v-1), prevList(v))

    def pascalLine(prevList: List[Int], n: Int): List[Int] =
    {
      if(n>0)
      prevList match {
        case Nil => {println(List(1));pascalLine(List(1),n-1)}
        case List(1) => {println(List(1,1));pascalLine(List(1,1),n-1)}
        case _ => {
          val newList=combine(prevList,(1 to prevList.length-1).map(x => g(prevList,x)).map(y=>y.sum).toList)
          println(newList)
          pascalLine(newList,n-1)
        }

      }
      else
        Nil
    }
    pascalLine(Nil,n)
}
于 2017-04-08T23:47:17.370 回答