问题去大。用递归的因子

我正在尝试实现这段代码：

func factorial(x int) (result int) {
  if x == 0 {
    result = 1;
  } else {
    result = x * factorial(x - 1);
  }
  return;
}

作为一个大的.Int，以使其对较大的x值有效。

以下为fmt.Println（factorial（r））返回值0

阶乘7应该是5040？

关于我做错的任何想法？

package main

import "fmt"
import "math/big"

func main() {
        fmt.Println("Hello, playground")

    //n := big.NewInt(40)
    r := big.NewInt(7)

    fmt.Println(factorial(r))

}

func factorial(n *big.Int) (result *big.Int) {
    //fmt.Println("n = ", n)
    b := big.NewInt(0)
    c := big.NewInt(1)

    if n.Cmp(b) == -1 {
        result = big.NewInt(1)
    }
    if n.Cmp(b) == 0 {
        result = big.NewInt(1)
    } else {
        // return n * factorial(n - 1);
        fmt.Println("n = ", n)
        result = n.Mul(n, factorial(n.Sub(n, c)))
    }
    return result
}

这个代码在去游乐场： http://play.golang.org/p/yNlioSdxi4

3951

2018-06-30 00:38

起源

答案:

在你的 int 版本，每一个 int 很明显。但在你的 big.Int 版本，你实际上在分享 big.Int 值。所以，当你说

result = n.Mul(n, factorial(n.Sub(n, c)))

表达方式 n.Sub(n, c) 实际上存储 0 回到 n，所以什么时候 n.Mul(n, ...) 被评估，你基本上是在做 0 * 1 然后你回来了 0 结果是。

记住，结果 big.Int 操作不只是返回它们的值，它们还将它们存储到接收器中。这就是你在表达中看到重复的原因 n.Mul(n, c)，例如为什么需要 n 再次作为第一个参数。因为你也可以这么说result.Mul(n, c) 并且你会得到相同的值，但它会存储在 result 代替 n。

以下是您重写的代码以避免此问题：

func factorial(n *big.Int) (result *big.Int) {
    //fmt.Println("n = ", n)
    b := big.NewInt(0)
    c := big.NewInt(1)

    if n.Cmp(b) == -1 {
        result = big.NewInt(1)
    }
    if n.Cmp(b) == 0 {
        result = big.NewInt(1)
    } else {
        // return n * factorial(n - 1);
        fmt.Println("n = ", n)
        result = new(big.Int)
        result.Set(n)
        result.Mul(result, factorial(n.Sub(n, c)))
    }
    return
}

这是一个稍微清理/优化的版本（我试图删除无关的分配 big.IntS）： http://play.golang.org/p/feacvk4P4O

2018-06-30 00:59

谢谢！是的那些big.Int操作的结果确实有点棘手。 - Greg

@Greg：这是一个更紧凑这意味着跳过递归并直接转换为for循环。 - Kevin Ballard

太好了！这也有效。 - Greg

答案:

在你的 int 版本，每一个 int 很明显。但在你的 big.Int 版本，你实际上在分享 big.Int 值。所以，当你说

result = n.Mul(n, factorial(n.Sub(n, c)))

表达方式 n.Sub(n, c) 实际上存储 0 回到 n，所以什么时候 n.Mul(n, ...) 被评估，你基本上是在做 0 * 1 然后你回来了 0 结果是。

以下是您重写的代码以避免此问题：

func factorial(n *big.Int) (result *big.Int) {
    //fmt.Println("n = ", n)
    b := big.NewInt(0)
    c := big.NewInt(1)

    if n.Cmp(b) == -1 {
        result = big.NewInt(1)
    }
    if n.Cmp(b) == 0 {
        result = big.NewInt(1)
    } else {
        // return n * factorial(n - 1);
        fmt.Println("n = ", n)
        result = new(big.Int)
        result.Set(n)
        result.Mul(result, factorial(n.Sub(n, c)))
    }
    return
}

这是一个稍微清理/优化的版本（我试图删除无关的分配 big.IntS）： http://play.golang.org/p/feacvk4P4O

2018-06-30 00:59

谢谢！是的那些big.Int操作的结果确实有点棘手。 - Greg

@Greg：这是一个更紧凑这意味着跳过递归并直接转换为for循环。 - Kevin Ballard

太好了！这也有效。 - Greg

去打包 math.big 具有 func (*Int) MulRange(a, b int64)。在第一个参数设置为1的情况下调用时，它将返回b！：

package main

import (
    "fmt"
    "math/big"
)

func main() {
    x := new(big.Int)
    x.MulRange(1, 10)
    fmt.Println(x)
}

会生产

3628800

2017-10-10 23:46

那是 x.MulRange不是 x.mulRange。 - Attila O.

低估的答案在这里。大多数用法可能不需要big.Int作为阶乘方法的输入，仅作为返回类型（因为只有答案非常大）。如果是这种情况，MulRange会更简单（也更快）。 - TM.

例如，

package main

import (
    "fmt"
    "math/big"
)

func factorial(x *big.Int) *big.Int {
    n := big.NewInt(1)
    if x.Cmp(big.NewInt(0)) == 0 {
        return n
    }
    return n.Mul(x, factorial(n.Sub(x, n)))
}

func main() {
    r := big.NewInt(7)
    fmt.Println(factorial(r))
}

输出：

2018-06-30 01:31

非递归版本：

func FactorialBig(n uint64) (r *big.Int) {
    //fmt.Println("n = ", n)
    one, bn := big.NewInt(1), new(big.Int).SetUint64(n)
    r = big.NewInt(1)
    if bn.Cmp(one) <= 0 {
        return
    }
    for i := big.NewInt(2); i.Cmp(bn) <= 0; i.Add(i, one) {
        r.Mul(r, i)
    }
    return
}

操场

2017-09-12 17:39

问题 去大。用递归的因子

答案:

答案:

热门问题

问题去大。用递归的因子