用于查找二项式系数的 Bash 脚本

Question

我正在尝试为二项式系数生成一个函数。我正在为此使用 nCk=n!/(k!(nk)!) 公式。

我目前的代码是：

function factorial {
  typeset n=$1
  (( n < 2 )) && echo 1 && return
  echo $(( n * $(factorial $((n-1))) ))
}

function nCk {
  echo $((factorial $1/$(( factorial $2 *factorial $(($1-$2)) ))  ))
}

但是我遇到了错误，因为我可能会弄乱语法。

Answer 1

错误在您的nCk函数中：

nCk() {
    echo $(( $(factorial $1) / ( $(factorial $2) * $(factorial $(($1-$2))) )  ))
}

您需要小心地将每个子表达式括起来，$( )以免将 之类的内容*视为factorial函数的参数。请注意，我还更改了声明以使用更广泛兼容的函数语法。

正如@chepner 在您问题下方的评论中所建议的那样，这不是计算二项式系数的最佳方法。原因之一是您需要计算阶乘，它会非常快地变得非常大。我可以使用 bash 计算的最高阶乘是20!; 任何更高的值都会导致整数溢出：

$ factorial 20
2432902008176640000
$ factorial 21
-4249290049419214848

还有其他方法可以计算二项式系数，不需要阶乘。下面的函数实现了其中之一：

nCk2() {
    num=1
    den=1

    if (( $2 < $1 - $2 )); then
        k=$2
    else
        k=$(( $1 - $2 ))
    fi

    for ((i = 1; i <= k; ++i)); do
        ((num *= $1 + 1 - i)) && ((den *= i))
    done
    echo $((num / den))
}

使用这种方法，可以为更高的值计算系数，n而不会受到整数溢出的影响。作为一个令人愉快的副作用，该函数也比原始函数快得多，因为它不会多次调用递归函数。