Scala 尾递归方法具有除法和余数错误

Question

我目前正在通过在 Scala 中写入尾递归来计算两个自然数的二项式系数。但是我的代码在除数方面有问题，像我所做的那样将整数除以 k 会给你一个非零余数，因此会引入舍入错误。那么谁能帮我弄清楚，如何解决它？

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)
}

Answer 1

一般来说，它包含：

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

如果要以线性时间计算它，则必须确保每个中间结果都是整数。现在

binom(n - k + 1, 1)

当然是一个整数(它只是n - k + 1(。从这个数字开始，并将两个参数递增 1，您可以通过以下中间步骤得出binom(n, k)：

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- 然后保证所有中间结果对应于实际的二项式系数，因此是整数(不是分数(。下面是它看起来像尾递归函数：

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

看起来还行，如果你愿意，可以和这个比较一下。

Answer 2

Andrey Tyukin的优秀例子在更大的n(比如binom(10000,2((中会失败，但可以很容易地适应使用BigInt。

def binom(n: Int, k: Int): BigInt = {
require(0 <= k && k <= n)
@annotation.tailrec 
def binomtail(nIter: Int, kIter: Int, ac: BigInt): BigInt = {
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, BigInt(1))
}