斐波那契数列中的每个新术语都是通过添加
前两个词。从1和2开始，前10个术语将是：
1、2、3、5、8、13、21、34、55、89，...
通过考虑斐波那契数列中值不超过400万的项，找到偶值项的和。
是我的解决方案：
func swap(inout left: Any, inout right: Any) {
let swap = left
right = left
left = swap
}
func findNextEvenFibonacci(var firstFibonacci: Int = 0, var secondFibonacci: Int = 1) -> (Int, Int) {
do {
firstFibonacci += secondFibonacci
swap(&firstFibonacci, &secondFibonacci)
} while firstFibonacci % 2 != 0
return (firstFibonacci, secondFibonacci)
}
let maxFibonacci: Int = 4_000_000
var fibonacci: (first: Int, next: Int) = (0,1)
var sumOfEvenFibonnaccis: Int = 0
while fibonacci.next < maxFibonacci {
fibonacci = findNextEvenFibonacci(firstFibonacci: fibonacci.first, secondFibonacci: fibonacci.next)
sumOfEvenFibonnaccis += fibonacci.first
}
let answer = sumOfEvenFibonnaccis
#1 楼
以下内容与Flambino的方法类似，但是创建了一个SwiftSequenceType，因此您可以使用Swift库函数filter()和reduce()遍历元素：struct FibonacciSequence : SequenceType {
let upperBound : Int
func generate() -> GeneratorOf<Int> {
var current = 1
var next = 1
return GeneratorOf<Int>() {
if current > self.upperBound {
return nil
}
let result = current
current = next
next += result
return result
};
}
}
let fibseq = lazy(FibonacciSequence(upperBound: 4_000_000))
let sum = reduce(fibseq.filter { struct FibonacciSequence : SequenceType {
let upperBound : Int
func generate() -> AnyGenerator<Int> {
var current = 1
var next = 1
return anyGenerator {
if current > self.upperBound {
return nil
}
let result = current
current = next
next += result
return result
};
}
}
let fibseq = FibonacciSequence(upperBound: 4_000_000).lazy
let sum = fibseq.filter { q4312078q % 2 == 0 }.reduce(0) { q4312078q + }
% 2 == 0 }, 0) { q4312078q + }
有关序列和生成器的更多信息，请参见此处。
这个不错的应用程序使我真正了解了如何创建自己的序列。
lazy()创建了一个LazySequence，其filter()方法返回“按需”元素，例如根据需要进行总结。在开始求和之前，filter()函数将返回所有偶数斐波纳契数的数组。 （对@jtbandes的建议表示敬意）。 更新：由于Swift编程语言的重大变化，
以上代码不再使用当前的Swift 2.1 / Xcode 7进行编译。这是前一个更新版本任何人的便利：
q4312078q
评论
\ $ \ begingroup \ $
非常好。我认为会有某种内置的“生成器”类型，但我不知道（而且，当我[快速]看时，似乎找不到）
\ $ \ endgroup \ $
– Flaambino
2014年8月23日在19:47
\ $ \ begingroup \ $
@MartinR随时加入第二届Monitor的常客！
\ $ \ endgroup \ $
–syb0rg
2014年8月23日19:55
\ $ \ begingroup \ $
我真的很喜欢这个答案，因为生成序列似乎对于其余的Euler问题以及Euler之外的问题都非常有用-但是对于这个特定的问题，相对而言，这会不会很慢？我们生成所有斐波那契数，然后过滤到偶数，然后将偶数相加，而不是随便添加。
\ $ \ endgroup \ $
– nhgrif
2014年8月23日在22:11
\ $ \ begingroup \ $
您是否尝试过lazy（）？应该有一个懒惰的过滤器版本。
\ $ \ endgroup \ $
– jtbandes
2014年8月24日在17:12
\ $ \ begingroup \ $
@MartinR酷！我正在研究一种更通用的惰性解决方案，如果可以使用，我会在几分钟后发布。
\ $ \ endgroup \ $
– jtbandes
2014年8月24日17:32
#2 楼
我只能建议一种更快的*基于数学的算法：斐波那契数是：0、1、1、2、3、5、8、13、21、34等。
偶数为：索引0处的0，索引3处的2，索引6处的8，索引9处的34，依此类推。
这表明每个第三个斐波纳契数都是偶数（从0开始）。让我们尝试通过归纳法证明这一点：
警告数学先行
我们已经证明了一些基本情况：索引0和3甚至是斐波那契数。
假设
Fibonacci(3 * n)是偶数。Fibonacci(3 * (n + 1)) = Fibonacci(3n + 3)
= Fibonacci(3n + 2) + Fibonacci(3n + 1)
= 2 * Fibonacci(3n + 1) + Fibonacci(3n)
由于
2 * Fibonacci(3n + 1)是偶数，并且根据归纳假设，Fibonacci(3n)是偶数，这意味着总和也是偶数，并且所以Fibonacci(3 * (n+1))也必须是偶数。这样就完成了归纳，并且我们证明了每个第三个斐波那契数都是偶数。接下来，我们必须证明所有其他数字都不是偶数。由于我们知道
Fibonacci(1) = 1是奇数，因此使用与之前相同的逻辑，我们可以证明保证Fibonacci(3n + 1) = 2 * Fibonacci(3n - 1) + Fibonacci(3n + 1)是奇数。类似地，将对所有n = 2 mod 3都获得结果。算术结束是否，因为我们刚刚证明了它们是唯一的偶数斐波纳契数。
大约101000
评论
\ $ \ begingroup \ $
要明确，这只是消除了检查结果是否均匀的权利，对吧？
\ $ \ endgroup \ $
– nhgrif
2014年8月23日19:04
\ $ \ begingroup \ $
有趣。我怀疑平价存在一种模式，但是...数学很难（而且我很懒）：P
\ $ \ endgroup \ $
– Flaambino
2014年8月23日19:50
\ $ \ begingroup \ $
@nhgrif这是我的理解，尽管有一些方法可以单独生成看起来很有趣的序列中的第N个数字。当然，如果您使用的算法仍然产生整个序列，呃，依序查找第N个数字，那么沿途检查奇偶校验无疑会更简单
\ $ \ endgroup \ $
– Flaambino
2014年8月23日在19:51
\ $ \ begingroup \ $
@nhgrif的确是正确的。它节省了一些模数。就这些。
\ $ \ endgroup \ $
–mleyfman
14年8月24日，0：45
\ $ \ begingroup \ $
您甚至可以从公式\ $ \ gcd（F_m，F_n）= F _ {\ gcd（m，n）} \ $得出有关斐波那契数的陈述：\ $ \ gcd（F_m，2）= \ gcd（F_m，F_3）= F _ {\ gcd（m，3）} \ $是\ $ F_3 = 2 \ $或\ $ F_1 = 1 \ $，具体取决于\ $ m \ $是...的倍数3或没有。
\ $ \ endgroup \ $
–马丁R
2014年8月24日11:36
#3 楼
免责声明：这是我用Swift写过的最多的东西。换句话说，我几乎不知道自己在做什么。我的直觉是Swift还是没有Swift，
findNextEvenFibonacci函数本身过于具体。我可能还有另一个函数，它只能生成下一个斐波那契数-偶数或奇数。然后在汇总时检查其奇偶校验。此外，我也不知道如何看待元组。虽然这是一个简单，直接的解决方案，但元组也感觉有点不透明。鉴于struct在Swift中非常强大，因此完全声明的具有某些功能的struct可能会更好。当然，这是可以用一百种不同方式完成的任务-以上正是我首先想到的。
旁：其他一百种方式中的几种将完全在程序上没有任何功能或结构或其他类似的东西-仅
while循环和一些变量。但是我认为这里的想法也是与Swift合作。它足够基本，可以作为核心类型扩展通用，并且可以清理一下Int循环上方的一部分。斐波那契数生成器，它采用闭包。如果只有一个闭包可以isEven调用它的循环而不是返回布尔值...哦，好吧，struct FibonacciPair {
var current: Int
var previous: Int
// using the name successor, since that's what Int
// calls its next-in-sequence function
func successor() -> FibonacciPair {
return FibonacciPair(current: current + previous, previous: current)
}
}
var generator = FibonacciPair(current: 1, previous: 1)
var sum = 0
while generator.current < 4_000_000 {
if generator.current % 2 == 0 {
sum += generator.current
}
generator = generator.successor()
}
let answer = sum
while是一个可怕的Ruby，但是极限值也可以只是一个参数，这样可以避免布尔值返回：
extension Int {
func isEven() -> Bool {
return self % 2 == 0
}
}
我认为这可能是最好的，最直接的方法。
但是，无论哪种情况，其想法都是要有一种方法来获取常规的斐波那契数列，然后决定如何处理每个数字，而不是使用特定的“仅偶数斐波那契数”设备。当然，以上任何一种都可以成为这种设备的基础。
无论如何，通过Swift使用Project Euler是一个好主意-我可能会做同样的事情：）
评论
\ $ \ begingroup \ $
关于您的免责声明：我认为大多数Swift开发人员都可以这么说。
\ $ \ endgroup \ $
–syb0rg
2014年8月23日在16:48
\ $ \ begingroup \ $
@ syb0rg嗯，是的，我想是的。但是考虑到我很快就安装了Xcode beta，但是还没有真正使用它，尽管如此，我还是有些尴尬:)
\ $ \ endgroup \ $
– Flaambino
2014年8月23日在17:06
#4 楼
这是一种使用通用RecurrenceRelation结构的方法，该结构可用于编写任何重复项，而不仅仅是Fibonacci序列（Fibonacci序列由初始条件（1,1）和关系T[n] = T[n-1] + T[n-2]定义）。我还将takeWhile定义为LazySequence的扩展，因此功能不必内置于RecurrenceRelation中-Swift具有内置的prefix，但它似乎仅适用于随机访问集合。 struct RecurrenceRelation<E> : SequenceType {
let initialCondition: [E]
let relation: (T: [E], n: Int) -> E
init(_ initialCondition: [E], relation: (T: [E], n: Int) -> E) {
self.initialCondition = initialCondition
self.relation = relation
}
func generate() -> GeneratorOf<E> {
var memory = initialCondition
var i = 0
return GeneratorOf<E> {
if i < memory.count { return memory[i++] }
memory.append(self.relation(T: memory, n: memory.count))
memory.removeAtIndex(0)
return memory.last
}
}
}
extension LazySequence {
func takeWhile(pred: S.Generator.Element -> Bool) -> LazySequence<SequenceOf<S.Generator.Element>> {
return lazy(SequenceOf { () -> GeneratorOf<S.Generator.Element> in
var g = self.generate()
return GeneratorOf<S.Generator.Element> {
let n = g.next()
if n == nil || !pred(n!) { return nil }
return n
}
})
}
}
let fib = RecurrenceRelation([1, 1]) { (T, n) in T[n-1] + T[n-2] }
let n = reduce(lazy(fib).takeWhile { q4312078q < 4_000_000 }.filter { q4312078q % 2 == 0 }, 0, +)
评论
交换器是否已内置？从文档中引用：“ [...]您可以使用Swift的现有交换功能，而不必提供自己的实现。”哭，显然是这样。我只是注释掉了交换功能，它仍然可以正常工作。