Tổng số từ Fibonacci dùng hàm Swift

Question

Tôi đang cố gắng tìm hiểu hàm Swift và bắt đầu thực hiện một số bài tập từ Project Euler.

Ngay cả các số Fibonacci Bài toán 2 Mỗi thuật ngữ mới trong chuỗi Fibonacci được tạo bằng cách thêm hai cụm từ trước đó. Bằng cách bắt đầu với 1 và 2, 10 từ đầu tiên sẽ là:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Bằng cách xem xét các điều khoản trong chuỗi Fibonacci có giá trị không vượt quá bốn triệu, tìm tổng các thuật ngữ có giá trị.

thực hiện một chức năng Fibonacci memoized, theo WWDC tiến video Swift:

func memoize<T:Hashable, U>(body: ((T)->U,T) -> U) -> (T)->U { 
    var memo = [T:U]() 
    var result: ((T)->U)! 
    result = { x in 
    if let q = memo[x] { return q } 
    let r = body(result,x) 
    memo[x] = r 
    return r 
    } 
    return result 
} 

let fibonacci = memoize { (fibonacci:Int->Double,n:Int) in n < 2 ? Double(n) : fibonacci(n-1) + fibonacci(n-2) } 

và thực hiện một lớp phù hợp với Sequence giao thức

class FibonacciSequence: SequenceType { 
    func generate() -> GeneratorOf<Double> { 
     var n = 0 
     return GeneratorOf<Double> { fibonacci(n++) } 
    } 

    subscript(n: Int) -> Double { 
     return fibonacci(n) 
    } 
} 

đầu tiên (không có chức năng) giải pháp của vấn đề:

var fib = FibonacciSequence().generate() 
var n:Double = 0 
var sum:Double = 0 
while n < Double(4_000_000) { 
    if n % 2 == 0 { 
    sum += n 
    } 
n = fib.next()! 
} 

println(sum) 

Thứ hai, giải pháp thêm chức năng, sử dụng ExSwift cho nó takeWhile chức năng

let f = FibonacciSequence() 
println((1...40).map { f[$0] } 
       .filter { $0 % 2 == 0 } 
       .takeWhile { $0 < 4_000_000 } 
       .reduce(0, combine: +)) 

Tôi muốn cải thiện về giải pháp này, vì 1...40 loạt tại cầu xin đó là tính toán quá nhiều điều khoản không có lý do. Lý tưởng nhất là tôi muốn để có thể có một số loại phạm vi vô hạn, nhưng cùng lúc đó chỉ tính toán các điều khoản cần thiết đáp ứng các điều kiện trong takeWhile

Bất kỳ lời đề nghị?

Answer 1

Có chức năng filter() có tham số là một đối số:

func filter<S : SequenceType>(source: S, includeElement: (S.Generator.Element) -> Bool) -> [S.Generator.Element] 

nhưng kể từ khi giá trị trả về là một mảng , đây không phải là thích hợp nếu bạn muốn để làm việc với một chuỗi "vô hạn". Nhưng với

lazy(FibonacciSequence()).filter ({ $0 % 2 == 0 }) 

bạn nhận được chuỗi "số vô hạn" của các số Fibonacci.Bạn không thể gọi phương thức ExSwift .takeWhile() của ExSwift trên chuỗi đó vì .takeWhile() chỉ được xác định cho struct SequenceOf và không cho chuỗi chung. Nhưng

TakeWhileSequence(
    lazy(FibonacciSequence()).filter ({ $0 % 2 == 0 }), 
    { $0 < 4_000_000 } 
) 

hoạt động và cung cấp chuỗi các số Fibonacci dưới 4.000.000. Sau đó,

let sum = reduce(TakeWhileSequence(
    lazy(FibonacciSequence()).filter ({ $0 % 2 == 0 }), 
    { $0 < 4_000_000 }), 0, +) 

cho kết quả mong muốn và chỉ tính các số Fibonacci "cần thiết" .

Lưu ý rằng không có nhu cầu thực tế để ghi nhớ số Fibonacci tại đây vì chúng được truy cập tuần tự. Ngoài ra (như @Matteo đã được nhận thấy), tất cả các số Fibonacci là số nguyên. Vì vậy, bạn có thể xác định trình tự đơn giản hơn như

struct FibonacciSequence : SequenceType { 

    func generate() -> GeneratorOf<Int> { 
     var current = 1 
     var next = 1 
     return GeneratorOf<Int>() { 
      let result = current 
      current = next 
      next += result 
      return result 
     }; 
    } 
} 

và tính toán trên không vẫn làm việc.

Answer 2

Ở đây tôi tạo chuỗi đã dừng khi đạt đến giá trị tối đa. Sau đó, bạn chỉ cần giảm mà không cần lọc, chỉ cần cộng 0 khi n là lẻ.

func fibonacciTo(max: Int) -> SequenceOf<Int> { 
    return SequenceOf { _ -> GeneratorOf<Int> in 
     var (a, b) = (1, 0) 
     return GeneratorOf { 
      (b, a) = (a, b + a) 
      if b > max { return nil } 
      return b 
     } 
    } 
} 


let sum = reduce(fibonacciTo(4_000_000), 0) {a, n in (n % 2 == 0) ? a + n : a } 

Là một thay thế, nếu bạn muốn giữ lại fibonacci một hàm tổng quát hơn bạn có thể mở rộng SequenceOf với takeWhile và reduce1 lấy cái gì mà giống thành phần chức năng:

extension SequenceOf { 
    func takeWhile(p: (T) -> Bool) -> SequenceOf<T> { 
     return SequenceOf { _ -> GeneratorOf<T> in 
      var generator = self.generate() 
      return GeneratorOf { 
       if let next = generator.next() { 
        return p(next) ? next : nil 
       } 
       return nil 
      } 
     } 
    } 

    // Reduce1 since name collision is not resolved 
    func reduce1<U>(initial: U, combine: (U, T) -> U) -> U { 
     return reduce(self, initial, combine) 
    } 
} 


func fibonacci() -> SequenceOf<Int> { 
    return SequenceOf { _ -> GeneratorOf<Int> in 
     var (a, b) = (1, 0) 
     return GeneratorOf { 
      (b, a) = (a, b + a) 
      return b 
     } 
    } 
} 

let sum2 = fibonacci() 
    .takeWhile({ $0 < 4_000_000 }) 
    .reduce1(0) { a, n in (n % 2 == 0) ? a + n : a} 

Hope this helps

Answer 3

Bạn có thể nhận được khá gần với những gì bạn muốn bằng cách sử dụng trình tự lười biếng của Swift. Nếu bạn mang máy phát điện của bạn số fibonacci (đây là một trong những Tôi đang sử dụng :)

var (a, b) = (1, 0) 

var fibs = GeneratorOf<Int> { 

    (b, a) = (a, b + a) 

    return b 

} 

Bạn có thể bọc nó trong lười biếng():

var (a, b) = (1, 0) 

var fibs = lazy(

    GeneratorOf<Int> { 

    (b, a) = (a, b + a) 

    return b 

    } 
) 

nào cho thấy nó để lọc() như là một chức năng lười biếng. Bộ lọc này() trả về:

LazySequence<FilterSequenceView<GeneratorOf<Int>>> 

Bây giờ, để có được chức năng takeWhile() của bạn, bạn cần phải mở rộng LazySequence:

extension LazySequence { 

    func takeWhile(condition: S.Generator.Element -> Bool) 
    -> LazySequence<GeneratorOf<S.Generator.Element>> { 

    var gen = self.generate() 

    return lazy(GeneratorOf{ gen.next().flatMap{ condition($0) ? $0 : nil }}) 

    } 
} 

Vì vậy mà nó trả về nil (dừng máy phát điện) nếu một trong hai trình tự cơ bản kết thúc, hoặc điều kiện không hài lòng.

Với tất cả điều đó, dãy Fibonacci của bạn dưới một số lượng nhất định trông rất giống những gì bạn muốn:

fibs 
    .filter {$0 % 2 == 0} 
    .takeWhile {$0 < 100} 

//2, 8, 34 

Nhưng, vì giảm không phải là một phương pháp trên LazySequence, bạn phải chuyển sang một mảng :

fibs 
    .filter {$0 % 2 == 0} 
    .takeWhile {$0 < 100}.array 
    .reduce(0, combine: +) 

//44 

Bạn có thể làm một phần mở rộng nhanh chóng và dơ bẩn để LazySequence để có được giảm():

extension LazySequence { 

    func reduce<U>(initial: U, combine: (U, S.Generator.Element) -> U) -> U { 

    var accu = initial 

    for element in self { accu = combine(accu, element) } 

    return accu 

    } 
} 

Và bạn có thể viết những điều cuối cùng như thế này:

fibs 
    .filter {$0 % 2 == 0} 
    .takeWhile {$0 < 100} 
    .reduce(0, combine: +) 

//44 

Tất cả những chuỗi có được để tồn tại trong sự lười biếng của họ - fibs là vô hạn, vì vậy họ sẽ không thực sự làm việc khác. Trong thực tế, không có gì được tính toán cho đến khi giảm: đó là tất cả các khối cho đến khi đó.

Answer 4

Trong Swift 3.1, đây là một iterator mà tạo ra con số Fibonacci mãi mãi, và một dãy vô hạn bắt nguồn từ nó:

class FibIterator : IteratorProtocol { 
    var (a, b) = (0, 1) 

    func next() -> Int? { 
     (a, b) = (b, a + b) 
     return a 
    } 
} 

let fibs = AnySequence{FibIterator()} 

Bạn có thể lấy tổng của các điều khoản số chẵn dưới bốn triệu như thế này:

fibs.prefix{$0 < 4000000}.filter{$0 % 2 == 0}.reduce(0){$0 + $1} 

Được cảnh báo rằng filter và map là theo mặc định và sẽ chạy vĩnh viễn trên một Chuỗi vô hạn. Trong ví dụ trên, điều này không quan trọng vì prefix chỉ trả về một số giá trị hữu hạn. Bạn có thể gọi số .lazy để có một Trình tự lười biếng trong đó filter và map sẽ hoạt động không nghiêm chỉnh. Ví dụ: dưới đây là 5 số Fibonacci đầu tiên:

> print(Array(fibs.lazy.filter{$0 % 2 == 0}.prefix(5))) 
[2, 8, 34, 144, 610]