11

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

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

作为 big.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

4

4 回答 4

13

Go 包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

于 2013-10-10T23:46:43.287 回答
8

在你的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

于 2012-06-30T00:59:51.477 回答
1

例如，

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))
}

输出：

5040
于 2012-06-30T01:31:18.040 回答
0

非递归版本：

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
}

playground

于 2014-09-12T17:39:01.257 回答