欧拉16号项目-帮助解决该问题

问题描述：

I'm solving Project Euler problem 16, I've ended up with a code that can logically solve it, but is unable to process as I believe its overflowing or something? I tried int64 in place of int but it just prints 0,0. If i change the power to anything below 30 it works, but above 30 it does not work, Can anyone point out my mistake? I believe its not able to calculate 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)
}

答

Your approach to this problem requires exact integer math up to 1000 bits in size. But you're using int which is 32 or 64 bits. math/big.Int can handle such task. I intentionally do not provide a ready made solution using big.Int as I assume your goal is to learn by doing it by yourself, which I believe is the intent of Project Euler.

答

As noted by @jnml, ints aren't large enough; if you wish to calculate 2^1000 in Go, big.Ints are a good choice here. Note that math/big provides the Exp() method which will be easier to use than converting your power function to big.Ints.

I worked through some Project Euler problems about a year ago, doing them in Go to get to know the language. I didn't like the ones that required big.Ints, which aren't so easy to work with in Go. For this one, I "cheated" and did it in one line of Ruby:

Removed because I remembered it was considered bad form to show a working solution, even in a different language.

Anyway, my Ruby example shows another thing I learned with Go's big.Ints: sometimes it's easier to convert them to a string and work with that string than to work with the big.Int itself. This problem strikes me as one of those cases.

Converting my Ruby algorithm to Go, I only work with big.Ints on one line, then it's easy to work with the string and get the answer in just a few lines of code.

答

You don't need to use math/big. Below is a school boy maths way of doubling a decimal number as a hint!

xs holds the decimal digits in least significant first order. Pass in a pointer to the digits (pxs) as the slice might need to get bigger.

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

欧拉16号项目-帮助解决该问题

相关推荐