Chương trình Python để tìm chuỗi số. Thêm Pythonic way

Question

Có một chuỗi khác để thảo luận về loạt Fibo trong Python. Điều này là để tinh chỉnh mã thành nhiều pythonic hơn. How to write the Fibonacci Sequence in Python

Tôi yêu chương trình này mà tôi đã viết để giải quyết Dự án Euler Q2. Tôi mới được viết mã bằng Python và vui mừng mỗi lần tôi làm theo cách Pythonic! Bạn có thể đề xuất một cách tốt hơn Pythonic để làm điều này?

Project Euler Q2. Tìm tổng của tất cả các thuật ngữ có giá trị trong dãy Fibonacci không vượt quá bốn triệu.

fib=[] 
def fibo(a=-1,b=1,upto=4000000): 
    if a+b>=upto: 
     return 
    else: 
     a,b=b,a+b 
     fib.append(b) 
     fibo(a,b) 

fibo() 
even=[i for i in fib if not i%2] 
print sum(even) 

Answer 1

Trước tiên tôi muốn làm fibo() như một máy phát điện:

def fibo(a=-1,b=1,upto=4000000): 
    while a+b<upto: 
     a,b = b,a+b 
     yield b 

Sau đó tôi d cũng chọn cho sự đồng đều như một máy phát điện chứ không phải là một danh sách hiểu.

print sum(i for i in fibo() if not i%2) 

Answer 2

Có một điều, tôi đề nghị tổng hợp các thuật ngữ khi bạn tính chúng thay vì lưu trữ chúng trong một mảng và tổng hợp mảng sau đó, vì bạn không cần làm bất kỳ điều gì thêm chúng lên. (Đó là cảm giác tính toán chỉ tốt trong bất kỳ ngôn ngữ)

Answer 3

tôi sẽ làm cho những thay đổi sau:

• Sử dụng lặp thay vì đệ quy
• Chỉ cần giữ một số hoạt động thay vì giữ một danh sách của tất cả các số Fibonacci và sau đó tìm thấy tổng số tiền ngay cả sau một số sau

Ngoài ra, nó là hợp lý Pythonic.

def even_fib_sum(limit): 
    a,b,sum = 0,1,0 
    while a <= limit: 
     if a%2 == 0: 
      sum += a 
     a,b = b,a+b 
    return sum 

print(even_fib_sum(4000000)) 

Answer 4

Sử dụng máy phát điện là một cách Pythonic để tạo chuỗi dài trong khi vẫn giữ bộ nhớ:

def fibonacci(): 
    a, b = 0, 1 
    while True: 
    yield a 
    a, b = b, a + b 

import itertools 
upto_4000000 = itertools.takewhile(lambda x: x <= 4000000, fibonacci()) 
print(sum(x for x in upto_4000000 if x % 2 == 0)) 

Answer 5

Tôi muốn sử dụng máy phát điện fibonacci như trong @constantin' answer nhưng biểu thức máy phát điện có thể được thay thế bằng một đồng bằng for loop:

def fibonacci(a=0, b=1): 
    while True: 
     yield a 
     a, b = b, a + b 

sum_ = 0 
for f in fibonacci(): 
    if f > 4000000: 
     break 
    if f % 2 == 0: 
     sum_ += f 

print sum_ 

Answer 6

Dưới đây là một phương pháp trực tiếp thay thế Nó dựa trên một vài thuộc tính:

1. Mỗi số Fibonacci có thể được tính trực tiếp dưới dạng sàn (pow (phi, n) + 0.5) (Xem tính toán bằng cách làm tròn trong http://en.wikipedia.org/wiki/Fibonacci_number). Ngược lại chỉ số của số Fibonacci lớn nhất nhỏ hơn i được cho bởi sàn (log (i * sqrt (5))/log (phi))
2. Tổng của N số Fibonacci đầu tiên là số N + 2 1 (Xem Nhận dạng thứ hai trên cùng trang wikipedia)
3. Các số Fibonacci đều là số thứ ba. (Nhìn vào chuỗi thứ tự 2 và kết quả là tầm thường)
4. Tổng của các số Fibonacci thậm chí bằng một nửa tổng các số Fibonacci lẻ tới cùng một điểm trong chuỗi.

Point 4 có thể được nhìn thấy từ này:

Sum of first 3N fibonacci numbers 
    =(F(1) + F(2))+ F(3) +(F(4) + F(5))+ F(6) + ... +(F(3N-2) + F(3N-1))+ F(3N) 
    =  F(3) + F(3) +  F(6) + F(6) + ... +  F(3N)  + F(3N) 
    = 2(F(3) + F(6) + ... + F(3N)) 
    = 2 (Sum of odd fibonacci numbers up to F(3N)) 

Vì vậy, chuyển đổi giá trị lớn nhất của chúng ta về 4000000 tính toán chỉ số của các số Fibonacci cao nhất ít hơn nó.

int n = floor(log(4000000*sqrt(5))/log(phi)); // (= 33) 

33 chia hết cho 3 vì vậy đây là số Fibonacci ngay cả khi chúng tôi không cần điều chỉnh n như thế này.

n = (n/3)*3; 

Tổng số tất cả các số Fibonacci đến thời điểm này nếu do

sum = floor(pow(phi, n+2) + 0.5) - 1; // (= 9227464) 

Tổng của tất cả các số chẵn là một nửa của này:

sum_even = sum/2; // (= 4613732) 

đẹp điều về việc này là rằng nó là một O (1) (hoặc O (log (N)) nếu bạn bao gồm các chi phí của pow/log) thuật toán, và hoạt động trên đôi ... vì vậy chúng tôi có thể tính toán tổng cho các giá trị rất lớn.

LƯU Ý: Tôi đã chỉnh sửa và chuyển câu trả lời này từ bản sao đã đóng của câu hỏi này. Fibonacci under 4 millions

Answer 7

Trong Python 3 ít nhất nếu bạn cung cấp cho một máy phát điện đến chức năng sum nó sẽ lazily đánh giá nó vì vậy không cần phải tái tạo lại bánh xe.

Đây là những gì @Constantin đã làm và chính xác.

Tested bằng cách so sánh việc sử dụng bộ nhớ của việc sử dụng máy phát điện:

sum(range(9999999))

so với không làm như vậy:

sum(list(range(9999999)))

Một với các máy phát điện không gây ra ngoại lệ bộ nhớ với cao số.

Answer 8

print ("Fibonacci Series\n") 

a = input ("Enter a nth Term: ") 

b = 0 

x = 0 

y = 1 

print x,("\n"), y 

while b <=a-2: 

    b = b+1 

    z = x + y 

    print z 

    x = y 

    y = z 

Answer 9

def main(): 
    a = 1 
    b = 2 
    num = 2 

    while b < 4000000: 
     a, b = b, a+b 
     num += b if b % 2 == 0 else 0 

    print num 

if __name__ == '__main__': 
    main()