我想知道在Scala中,是否有任何方法可以计算二项式系数,从n中选择k,或者从一组n个元素中选择k个组合的数量。对于n=1000和k=35,即使使用Long,在Scala中计算35!时也可能会遇到溢出问题。谢谢你,谢谢
n=1000
k=35
35!
cbeh67ev1#
使用BigInt和BigDecimal处理不适合Int/Long/Float/Double的数字。
BigInt
BigDecimal
def permutations(n: Int): BigInt = (1 to n).map(BigInt(_)).foldLeft(BigInt(1))(_ * _) def combinations(n: Int, k: Int): BigInt = permutations(n) / (permutations(k) * permutations(n - k)) combinations(1000, 35) // res23: BigInt = 53007599712421378893801108296363791932591235151324218238066214600
字符串
fumotvh32#
你不需要计算大因子。如果n >= k >= 1,则C(n,k)= C(n-1,k-1)* n / k这个怎么样?
def choose(n:Int,k:Int):BigInt = { if (k == 1) BigInt(n) else if (n == k) BigInt(1) else if (k == 0) BigInt(1) else choose(n-1, k-1) * n / k }
2条答案
按热度按时间cbeh67ev1#
使用
BigInt
和BigDecimal
处理不适合Int/Long/Float/Double的数字。字符串
fumotvh32#
你不需要计算大因子。
如果n >= k >= 1,则C(n,k)= C(n-1,k-1)* n / k
这个怎么样?
字符串