2

我正在尝试解决 Project Euler 的第二个问题。问题如下：

斐波那契数列中的每个新项都是通过添加前两项来生成的。从 1 和 2 开始，前 10 项将是：1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... 通过考虑斐波那契数列中其值不超过的项四百万，求偶数项之和。

我想我已经写了一个解决方案，但是当我尝试运行我的代码时，它会导致我的 Swift 操场崩溃并给我这个错误消息：

Playground execution aborted：执行被中断，原因：EXC_BAD_INSTRUCTION (code=EXC_I386_INVOP, subcode=0x0)

var prev = 0
var next = 1
var num = 0
var sum = 0

for var i = 1; i < 400; i++ {
    num = prev + next
    if next % 2 == 0 {
        sum += next
    }
    prev = next
    next = num
}
print(sum)

奇怪的是，如果我将循环上的计数器设置为小于 93，它就可以正常工作。将变量名称显式设置为 Double 无济于事。有人知道这里发生了什么吗？

4

2 回答 2

4

There is nothing weird about this at all. Do you know how large the 400 fibonacci number is?

176023680645013966468226945392411250770384383304492191886725992896575345044216019675

Swift Int64 or UInt64 simply cannot handle that large of a number. The later can go up to 18446744073709551615 at max - not even close.

If you change your variables to be doubles it works but will be inaccurate:

var prev : Double = 0
var next : Double = 1
var num : Double = 0
var sum : Double = 0

will yield

2.84812298108489e+83

which is kind of close to the actual value of

1.76e+83

Luckily you do not need to get values that big. I would recommend not writing a for loop but a while loop that calculates the next fibonacci number until the break condition is met whose values do not exceed four million.

于 2016-01-10T16:08:30.367 回答
1

斐波那契数很快变得非常大。要计算大的斐波那契数，您需要实现某种BigNum. 这是一个在BigNum内部实现为数字数组的版本。例如，12345在内部实现为[1, 2, 3, 4, 5]. 这使得表示任意大的数字变得容易。

加法是通过使两个数组大小相同来实现的，然后map用于将元素相加，最后该carryAll函数将数组恢复为个位数。

例如12345 + 67：

[1, 2, 3, 4, 5] + [6, 7]            // numbers represented as arrays
[1, 2, 3, 4, 5] + [0, 0, 0, 6, 7]   // pad the shorter array with 0's
[1, 2, 3, 10, 12]                   // add the arrays element-wise
[1, 2, 4, 1, 2]                     // perform carry operation

这里是BigNum. 这也CustomStringConvertible使得可以将结果打印为String.

struct BigNum: CustomStringConvertible {
    var arr = [Int]()

    // Return BigNum value as a String so it can be printed
    var description: String { return arr.map(String.init).joined() }

    init(_ arr: [Int]) {
        self.arr = carryAll(arr)
    }

    // Allow BigNum to be initialized with an `Int`
    init(_ i: Int = 0) {
        self.init([i])
    }

    // Perform the carry operation to restore the array to single
    // digits
    func carryAll(_ arr: [Int]) -> [Int] {
        var result = [Int]()

        var carry = 0
        for val in arr.reversed() {
            let total = val + carry
            let digit = total % 10
            carry = total / 10
            result.append(digit)
        }

        while carry > 0 {
            let digit = carry % 10
            carry = carry / 10
            result.append(digit)
        }

        return result.reversed()
    }

    // Enable two BigNums to be added with +
    static func +(_ lhs: BigNum, _ rhs: BigNum) -> BigNum {
        var arr1 = lhs.arr
        var arr2 = rhs.arr

        let diff = arr1.count - arr2.count

        // Pad the arrays to the same length
        if diff < 0 {
            arr1 = Array(repeating: 0, count: -diff) + arr1
        } else if diff > 0 {
            arr2 = Array(repeating: 0, count: diff) + arr2
        }

        return BigNum(zip(arr1, arr2).map { $0 + $1 })
    }
}

// This function is based upon this question:
// https://stackoverflow.com/q/52975875/1630618

func fibonacci(to n: Int) {
    guard n >= 2 else { return }
    var array = [BigNum(0), BigNum(1)]
    for i in 2...n {
        array.append(BigNum())
        array[i] = array[i - 1] + array[i - 2]
        print(array[i])
    }
}

fibonacci(to: 400)

输出：

1
2
3
5
8
...
67235063181538321178464953103361505925388677826679492786974790147181418684399715449
108788617463475645289761992289049744844995705477812699099751202749393926359816304226
176023680645013966468226945392411250770384383304492191886725992896575345044216019675
于 2018-10-25T01:45:59.203 回答