要零还是无限？科特林

Question

在Codewars，这是惊人的Kata。 我是从双人开始的，但是在阶乘30之后！应该使用bigdecimal。在200！我改进了代码，并在时间

执行时遇到问题（16000 ms）

零或Infinity说明图像

请帮助我改善代码以计算超过200个！快速。

我的代码（用于200个！）SIPL测试可以通过，但是在随机测试中有200多个测试！我有时间有问题。在我的想法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＆lt; 1000。N＆GT; 〜5800 - ＆gt;线程“ main” java.lang.stackoverflowerror中的例外，

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

我的hashmap的代码

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，

之间没有区别

tailRec或没有tailrec n == 7027 - ＆gt 。一切都很好 n == 7028-＆gt; stackoverflow异常

我的实验代码在下面

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-1）！ * k。因此，如果我们现在的答案n = k-1我们需要做的一切来计算n = k的答案，就是通过k 并添加1。我们可以简单地循环做到这一点：

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