走向零还是无穷大?科特林

Question

在CodeWars上真是太棒了。 我从双倍开始，但在阶乘 30 之后！应该使用大十进制。200！我改进了我的代码，但时间问题

执行超时(16000 毫秒)

卡塔描述

零或无穷大描述图像

请帮助我改进我的代码，以快速计算超过200！

我的代码(工作到 200！Siple测试通过还行，但在随机测试中超过200！我有时间问题。在我的 Idea IDE 中计算没有问题，但服务器代码大战无法计算。

fun going(n: Int): Double {
val factorial = factorial(n)
val zeroField = zero(factorial)
val infiniteField = infinite(n)
val beforeRound = zeroField.multiply(infiniteField)
return beforeRound.setScale(6, RoundingMode.DOWN).toDouble()
}
fun factorial(n: Int): BigDecimal{
if (n<=1) return BigDecimal.ONE
return BigDecimal(n).multiply(factorial(n-1))
}
fun infinite(n: Int): BigDecimal {
var sumFact = BigDecimal(0)
var factCounter = 1
repeat(n){
sumFact += factorial(factCounter)
factCounter++
}
return sumFact
}
fun zero(factorial: BigDecimal): BigDecimal{
return BigDecimal.ONE.divide(factorial, MathContext.DECIMAL128)
}

---

在提示 k314159 之后，我尝试使用 hashMap 来兑现我的阶乘结果。它一直工作到n<1000。当 n> ~5800 -> 线程"main"中的异常 java.lang.StackOverflowError

我需要计算非常大的数字，例如阶乘 10_000 ！

我的代码与哈希地图

val myFactorialHash = mutableMapOf<Int, BigDecimal>(1 to BigDecimal.ONE)

fun going(n: Int): Double {

println(n)
val factorial = factorial(n)
val zeroField = zero(factorial)
val infiniteField = infinite(n)
val beforeRound = zeroField.multiply(infiniteField)
return beforeRound.setScale(6, RoundingMode.DOWN).toDouble()
}
fun factorial(n: Int): BigDecimal{
if (n<=1){
return myFactorialHash[1]!!
}
if (myFactorialHash.containsKey(n)){
return myFactorialHash[n]!!
} else {
myFactorialHash[n] = BigDecimal(n).multiply(factorial(n-1))
}
return myFactorialHash[n]!!
}
fun infinite(n: Int): BigDecimal {
var sumFact = BigDecimal(0)
var factCounter = 1
repeat(n){
sumFact += factorial(factCounter)
factCounter++
}
return sumFact
}
fun zero(factorial: BigDecimal): BigDecimal{
return BigDecimal.ONE.divide(factorial, MathContext.DECIMAL128)
}

---

关于递归的 tailrec 一点点

在实际实验中，尾部与无尾部没有区别

n == 7027 ->一切正常 n == 7028 -> 堆栈溢出异常

我在下面的实验代码

fun main(){
println(factorial(7027))
}
tailrec fun factorial(n: Int): BigDecimal{
if (n<1) return BigDecimal.ONE
return BigDecimal(n).multiply(factorial(n-1))
}

<小时 />

好的，5小时后... 在最大堆栈容量上初始化我的哈希

val myFactorialHash = mutableMapOf<Int, BigDecimal>(1 to BigDecimal.ONE)
fun going(n: Int): Double {
initHash()
val factorial = factorial(n)
val zeroField = zero(factorial)
val infiniteField = infinite(n)
val beforeRound = zeroField.multiply(infiniteField)
return beforeRound.setScale(6, RoundingMode.DOWN).toDouble()
}
fun factorial(n: Int): BigDecimal{
if (n<=1){
return myFactorialHash[1]!!
}
var counter = n
if (myFactorialHash.containsKey(n)){
return myFactorialHash[n]!!
} else {
myFactorialHash[n] = BigDecimal(n).multiply(factorial(n-1))
}
return myFactorialHash[n]!!
}
fun infinite(n: Int): BigDecimal {
var sumFact = BigDecimal(0)
var factCounter = 1
repeat(n){
sumFact += factorial(factCounter)
factCounter++
}
return sumFact
}
fun zero(factorial: BigDecimal): BigDecimal{
return BigDecimal.ONE.divide(factorial, MathContext.DECIMAL128)
}
fun initHash(){
repeat(7000){
myFactorialHash[it] = factorial(it)
}
}

谢谢k314159。我使用 BigDecimal 的哈希传递了这个。 当我找到解决解决方案中此kata的简单方法时，我的头利用

了))))我不明白它是如何工作的，但它是 1 行代码

fun going(n: Int): Double = if (n == 0) 0.0 else 1 + going(n - 1) / n

Answer 1

让我们简化表达式

(1/n!) * (1! + 2! + 3! + ... + n!) = 1!/n! + 2!/n! + ... + n!/n!

现在让我们为n = k-1和n = k编写这个表达式：

• n = k-1：1!/(k-1)! + 2!/(k-1)! + ... + (k-1)!/(k-1)!
• n = k：1!/k! + 2!/k! + ... + (k-1)!/k! + k!/k!

您可以注意到第二个表达式是一个总和，这个总和等于1。所有其他求和都变小了k倍，因为k! = (k-1)! * k.因此，如果我们现在得到n = k-1的答案，那么我们需要做的就是计算n = k的答案，就是除以k并加1。我们可以简单地循环完成：

result = 0
for every k in [1, n]
result /= k
result += 1