Scala尾递归方法具有除法和余数误差 [英] Scala tail recursive method has an divide and remainder error

问题描述

我目前正在通过在Scala中编写尾递归来计算两个自然数的二项式系数.但是我的代码在除数方面存在问题，像我那样将整数除以k会给您一个非零的余数，从而导致舍入误差.那么谁能帮我弄清楚，如何解决?

I'm currently computing the binomial coefficient of two natural numbers by write a tail recursion in Scala. But my code has something wrong with the dividing numbers, integer division by k like I did as that will give you a non-zero remainder and hence introduce rounding errors. So could anyone help me figure it out, how to fix it ?

 def binom(n: Int, k: Int): Int = {
    require(0 <= k && k <= n)
    def binomtail(n: Int, k: Int, ac: Int): Int = {
      if (n == k || k == 0) ac
      else binomtail(n - 1, k - 1, (n*ac)/k)
    }
    binomtail(n,k,1)
  }

推荐答案

通常，它保持:

binom(n, k) = if (k == 0 || k == n) 1 else binom(n - 1, k - 1) * n / k

如果要在线性时间内进行计算，则必须确保每个中间结果都是整数.现在，

If you want to compute it in linear time, then you have to make sure that each intermediate result is an integer. Now,

binom(n - k + 1, 1)

肯定是整数(只是 n-k + 1 ).从这个数字开始，然后将两个参数都增加一个，您可以通过以下中间步骤到达 binom(n，k):

is certainly an integer (it's just n - k + 1). Starting with this number, and incrementing both arguments by one, you can arrive at binom(n, k) with the following intermediate steps:

binom(n - k + 1, 1)
binom(n - k + 2, 2)
...
binom(n - 2, k - 2)
binom(n - 1, k - 1)
binom(n, k)

这意味着您必须以正确的顺序累积"，从 1 到 k ，而不是从 k 到 1 -那么可以保证所有中间结果都对应于实际的二项式系数，因此是整数(而不是分数).这是尾递归函数的样子:

It means that you have to "accumulate" in the right order, from 1 up to k, not from k down to 1 - then it is guaranteed that all intermediate results correspond to actual binomial coefficients, and are therefore integers (not fractions). Here is what it looks like as tail-recursive function:

def binom(n: Int, k: Int): Int = {
  require(0 <= k && k <= n)
  @annotation.tailrec 
  def binomtail(nIter: Int, kIter: Int, ac: Int): Int = {
    if (kIter > k) ac
    else binomtail(nIter + 1, kIter + 1, (nIter * ac) / kIter)
  }
  if (k == 0 || k == n) 1
  else binomtail(n - k + 1, 1, 1)
}

小小的视觉测试:

val n = 12
for (i <- 0 to n) {
  print(" " * ((n - i) * 2))
  for (j <- 0 to i) {
    printf(" %3d", binom(i, j))
  }
  println()
}

打印:

                           1
                         1   1
                       1   2   1
                     1   3   3   1
                   1   4   6   4   1
                 1   5  10  10   5   1
               1   6  15  20  15   6   1
             1   7  21  35  35  21   7   1
           1   8  28  56  70  56  28   8   1
         1   9  36  84 126 126  84  36   9   1
       1  10  45 120 210 252 210 120  45  10   1
     1  11  55 165 330 462 462 330 165  55  11   1
   1  12  66 220 495 792 924 792 495 220  66  12   1

好吧，如果需要，可以将其与此进行比较

Looks ok, compare it with this, if you want.

这篇关于Scala尾递归方法具有除法和余数误差的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！