11

私はこのコードを実装しようとしています:

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

x の値が大きい場合に有効になるように、big.Int として。

以下は、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
}

Go Playground のこのコード: 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)格納されるためです。resultn

この問題を回避するために書き直されたコードは次のとおりです。

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 に答える