英文:
Go big.Int factorial with recursion
问题
我正在尝试实现这段代码:
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
}
这段代码在Go Playground上: http://play.golang.org/p/yNlioSdxi4
英文:
I am trying to implement this bit of code:
func factorial(x int) (result int) {
if x == 0 {
result = 1;
} else {
result = x * factorial(x - 1);
}
return;
}
as a big.Int so as to make it effective for larger values of x.
The following is returning a value of 0 for fmt.Println(factorial(r))
The factorial of 7 should be 5040?
Any ideas on what I am doing wrong?
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
}
This code on go playground: <http://play.golang.org/p/yNlioSdxi4>
答案1
得分: 16
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
英文:
Go package math.big
has func (*Int) MulRange(a, b int64)
. When called with the first parameter set to 1, it will return b!:
package main
import (
"fmt"
"math/big"
)
func main() {
x := new(big.Int)
x.MulRange(1, 10)
fmt.Println(x)
}
Will produce
> 3628800
答案2
得分: 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.Int
分配):http://play.golang.org/p/feacvk4P4O
英文:
In your int
version, every int
is distinct. But in your big.Int
version, you're actually sharing big.Int
values. So when you say
result = n.Mul(n, factorial(n.Sub(n, c)))
The expression n.Sub(n, c)
actually stores 0
back into n
, so when n.Mul(n, ...)
is evaluated, you're basically doing 0 * 1
and you get back 0
as a result.
Remember, the results of big.Int
operations don't just return their value, they also store them into the receiver. This is why you see repetition in expressions like n.Mul(n, c)
, e.g. why it takes n
again as the first parameter. Because you could also say result.Mul(n, c)
and you'd get the same value back, but it would be stored in result
instead of n
.
Here is your code rewritten to avoid this problem:
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
}
And here is a slightly more cleaned-up/optimized version (I tried to remove extraneous allocations of big.Int
s): http://play.golang.org/p/feacvk4P4O
答案3
得分: 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
英文:
For example,
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))
}
Output:
5040
答案4
得分: 0
func FactorialBig(n uint64) (r *big.Int) {
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
}
英文:
Non-recursive version:
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
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论