3

我正在解决Project Euler 问题 16，我最终得到了一个可以在逻辑上解决它的代码，但由于我认为它溢出或其他原因而无法处理？我尝试用 int64 代替 int，但它只打印 0,0。如果我将电源更改为低于 30 的任何值，它可以工作，但高于 30 它不起作用，谁能指出我的错误？我相信它无法计算 2^1000。

// PE_16 project main.go
package main

import (
    "fmt"
)

func power(x, y int) int {
    var pow int
    var final int
    final = 1
    for pow = 1; pow <= y; pow++ {
        final = final * x
    }
    return final
}

func main() {
    var stp int
    var sumfdigits int
    var u, t, h, th, tth, l int
    stp = power(2,1000)
    fmt.Println(stp)
    u = stp / 1 % 10
    t = stp / 10 % 10
    h = stp / 100 % 10
    th = stp / 1000 % 10
    tth = stp / 10000 % 10
    l = stp / 100000 % 10
    sumfdigits = u + t + h + th + tth + l
    fmt.Println(sumfdigits)
}
4

3 回答 3

8

您解决此问题的方法需要大小高达 1000 位的精确整数数学。但是您使用int的是 32 位或 64 位。math/big.Int可以处理这样的任务。我故意不提供现成的解决方案，big.Int因为我假设您的目标是自己学习，我相信这是 Project Euler 的意图。

于 2013-04-23T08:59:54.383 回答
1

正如@jnml 所指出的，ints 不够大；如果你想在 Go 中计算 2^1000，big.Int这里 s 是一个不错的选择。请注意，它math/big提供了Exp()方法，该方法比将power函数转换为big.Ints 更容易使用。

大约一年前，我解决了一些 Project Euler 问题，在 Go 中完成这些问题以了解该语言。我不喜欢需要big.Ints 的那些，它们在 Go 中不太容易使用。对于这个，我“作弊”并在一行 Ruby 中做到了：

删除是因为我记得展示一个可行的解决方案被认为是不好的形式，即使是用不同的语言。

无论如何，我的 Ruby 示例展示了我从 Go 的 s 中学到的另一件事：有时将它们转换为字符串并使用该字符串比使用它本身big.Int更容易。这个问题让我印象深刻，就是其中之一。big.Int

将我的 Ruby 算法转换为 Go，我只big.Int在一行上使用 s，然后很容易使用字符串并在几行代码中得到答案。

于 2013-04-23T18:38:22.740 回答
1

你不需要使用math/big. 下面是一个小学生数学加倍十进制数的方法作为提示！

xs以最低有效的第一顺序保存十进制数字。传入一个指向数字 ( pxs) 的指针，因为切片可能需要变得更大。

func double(pxs *[]int) {
    xs := *pxs
    carry := 0
    for i, x := range xs {
        n := x*2 + carry
        if n >= 10 {
            carry = 1
            n -= 10
        } else {
            carry = 0
        }
        xs[i] = n
    }
    if carry != 0 {
        *pxs = append(xs, carry)
    }
}
于 2013-04-24T19:17:25.173 回答