Fibonacci ต่ำกว่า 4 ล้าน [ซ้ำกัน]

สิ่งที่ซ้ำกันที่เป็นไปได้:
Python โปรแกรมหาอนุกรมฟีโบนัชชี วิธี Pythonic เพิ่มเติม

เฮ้ ฉันกำลังพยายามเขียนสคริปต์ที่รวมพจน์เลขคู่ทั้งหมดใน "ลำดับฟีโบนัชชี" ให้ต่ำกว่า 4 ล้าน

Fibonacci1 = 1
Fibonacci2 = 2
a = 2
i = 4
for i in range(1,4000000):
 Fibonacci1 = Fibonacci1 + Fibonacci2
 if Fibonacci1 % 2 == 0:
  a = a + Fibonacci1
 Fibonacci2 = Fibonacci1 + Fibonacci2
 if Fibonacci2 % 2 == 0:
  a = a + Fibonacci2
print a
raw_input()

น่าจะใช้เวลาไม่ถึงหนึ่งนาที แต่ใช้เวลาทั้งคืนและมันก็ไม่ได้รับการแก้ไข !

แก้ไข: ขออภัยเพื่อนๆ ฉันเข้าใจผิดปัญหา ฉันคิดว่ามันหมายความว่าฉันต้องรวมเงื่อนไขเลขคู่ทั้งหมดให้ได้มากถึง 4 ล้าน! แต่วิธีแก้คือรวมพจน์เลขคู่ทั้งหมดจนถึง 4 ล้าน

รหัสการทำงาน (เสร็จสิ้นภายในเวลาไม่ถึงหนึ่งวินาที):

Fibonacci1 = 1
Fibonacci2 = 2
a = 2
while a < 4000000:
 Fibonacci1 = Fibonacci1 + Fibonacci2
 if Fibonacci1 % 2 == 0:
  a = a + Fibonacci1
 Fibonacci2 = Fibonacci1 + Fibonacci2
 if Fibonacci2 % 2 == 0:
  a = a + Fibonacci2
print a
raw_input()

python sequence
person Mahmoud K.    schedule 17.07.2010    source แหล่งที่มา
comment
@che - นี่มีกลิ่นเหมือนโปรเจ็กต์ออยเลอร์สำหรับฉัน   -  person Bwmat    schedule 17.07.2010
comment
คุณอาจต้องการเพิ่มคณิตศาสตร์และแท็กฟีโบนัชชี   -  person Robert William Hanks    schedule 17.07.2010

คำตอบ (9)


arrow_upward
2
arrow_downward

เงื่อนไขการวนซ้ำไม่ถูกต้อง ควรเป็นดังนี้:

while True:
    Fibonacci1 = Fibonacci1 + Fibonacci2
    if Fibonacci1 % 2 == 0:
        if a + Fibonacci1 > 4000000:
            break
        a = a + Fibonacci1
    Fibonacci2 = Fibonacci1 + Fibonacci2
    if Fibonacci2 % 2 == 0:
        if a + Fibonacci2 > 4000000:
            break
        a = a + Fibonacci2
person Philipp    schedule 17.07.2010

arrow_upward
25
arrow_downward

รหัสของคุณมีปัญหาสองสามประการ:

  • คุณกำลังวนซ้ำสี่ล้านครั้งแทนที่จะวนซ้ำจนกว่าเงื่อนไขจะเป็นจริง
  • คุณมีโค้ดซ้ำในเนื้อหาของลูป

คนส่วนใหญ่เมื่อพวกเขาเริ่มเรียนรู้ Python จะเรียนรู้เฉพาะการเขียนโปรแกรมที่จำเป็นเท่านั้น ไม่น่าแปลกใจเพราะ Python เป็นภาษาที่จำเป็น แต่ Python ยังรองรับการเขียนโปรแกรมเชิงฟังก์ชันในระดับหนึ่ง และสำหรับแบบฝึกหัดประเภทนี้ วิธีการเขียนโปรแกรมเชิงฟังก์ชันนั้นให้ความกระจ่างมากกว่าในความคิดของฉัน

ขั้นแรกให้กำหนดตัวสร้างที่สร้างตัวเลขฟีโบนัชชีทั้งหมด:

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

หากต้องการใช้ตัวสร้างนี้ เราสามารถนำเข้าฟังก์ชันที่มีประโยชน์บางอย่างจาก itertools ได้ หากต้องการพิมพ์ตัวเลขสองสามตัวแรก ให้ใช้ islice:

from itertools import ifilter, islice, takewhile

for x in islice(fib(), 5):
    print x

1
1
2
3
5

หากต้องการค้นหาเฉพาะเลขคู่ เราสามารถใช้ ifilter เพื่อสร้างค่าใหม่ เครื่องกำเนิดไฟฟ้า:

def is_even(x):
    return x % 2 == 0

evenfibs = ifilter(is_even, fib())

for x in islice(evenfibs, 5):
    print x

2
8
34
144
610

หากต้องการดึงตัวเลขจากตัวสร้างจนกระทั่งตัวเลขเกินสี่ล้าน ให้ใช้ take While : :

for x in takewhile(lambda x: x < 4000000, evenfibs):
    print x

เพื่อแก้ปัญหาคุณสามารถใช้ผลรวม:

sum(list(takewhile(lambda x: x < 4000000, evenfibs)))

ฉันหวังว่านี่จะแสดงให้เห็นว่าวิธีการเขียนโปรแกรมเชิงฟังก์ชันนั้นไม่ใช่เรื่องยากและเป็นวิธีการแก้ปัญหาบางประเภทที่หรูหรากว่า

person Mark Byers    schedule 17.07.2010
comment
+1 ดีมาก! โดยปกติฉันคิดว่าการโพสต์รหัสสำหรับคำถามดังกล่าวไม่ได้ช่วย OP แต่คุณอธิบายได้ดีมาก! - person Felix Kling; 17.07.2010

arrow_upward
3
arrow_downward

คุณแน่ใจหรือว่า i คุณต้องการน้อยกว่า 4 ล้าน?

person user11977    schedule 17.07.2010

arrow_upward
3
arrow_downward

คุณอาจสนใจที่จะทราบเกี่ยวกับ สารานุกรมออนไลน์ของลำดับจำนวนเต็ม!

คุณสามารถค้นหาข้อมูลตามชื่อหรือตามลำดับ

หากคุณค้นหา 0,2,8,34 หรือ 'Even Fibonacci' คุณจะถูกเปลี่ยนเส้นทางไปยังลำดับ A014445

คุณจะพบข้อมูลมากมายรวมถึงสูตรต่างๆ
จากนั้น การสร้างโค้ดให้กับเครื่องกำเนิดไฟฟ้าที่ให้ผลลัพธ์เป็นเลขฟีโบนัชชีคู่โดยตรงนั้นเป็นเรื่องง่าย

def evenfib():
    """ Generates the even fibonacci numbers """
    a, b = 2, 0
    while True:
        a, b = b, a+4*b
        yield a
person Robert William Hanks    schedule 17.07.2010

arrow_upward
2
arrow_downward

ในปัจจุบัน คุณรวมตัวเลขฟีโบนักชีเลขคู่ 2 ล้านตัวแรกทั้งหมด

แต่นั่นไม่ใช่หน้าที่ คุณต้องรวมเลขฟีโบนัชชีทั้งหมดที่ต่ำกว่า 4 ล้าน

person Felix Kling    schedule 17.07.2010

arrow_upward
2
arrow_downward

หมายเหตุ: สิ่งนี้ได้รับการแก้ไขอย่างมากเพื่อตอบคำถามจริง

นี่เป็นอีกวิธีหนึ่ง (และวิธีที่เร็วมาก แต่ยังไม่ทดลอง) ขึ้นอยู่กับคุณสมบัติบางประการ:

  1. หมายเลขฟีโบนักชีแต่ละตัวสามารถคำนวณได้โดยตรงเป็นค่าพื้น( pow( phi, n ) + 0.5 ) (ดูการคำนวณโดยการปัดเศษใน http://en.wikipedia.org/wiki/Fibonacci_number ) ในทางกลับกัน ดัชนีของจำนวนฟีโบนัชชีที่ใหญ่ที่สุดที่น้อยกว่า i กำหนดโดย floor( log(i*sqrt(5)) / log(phi) )
  2. ผลรวมของหมายเลขฟีโบนักชี N ตัวแรกคือหมายเลขฟีโบนักชี N+2 ลบ 1 (ดูรหัสประจำตัวที่สองในหน้าวิกิพีเดียเดียวกัน)
  3. เลขฟีโบนัชชีคู่คือเลขที่สามทุกตัว (ดูลำดับ mod 2 แล้วผลลัพธ์ก็ไม่สำคัญ)
  4. ผลรวมของเลขฟีโบนัชชีคู่คือครึ่งหนึ่งของผลรวมของเลขฟีโบนัชชีคี่จนถึงจุดเดียวกันในลำดับ (ตามมาจากข้อ 3. และสมบัติที่ F(3N) = F(3N-1) + F(3N-2) ดังนั้น F(3N-2) + F(3N-1) + F(3N) = 2 F (N) .. แล้วสรุปทั้งสองข้าง

ดังนั้นแปลงค่าสูงสุดของเราที่ 4000000 ให้คำนวณดัชนีของเลขฟีโบนัชชีสูงสุดที่น้อยกว่าค่านั้น

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

33 หารด้วย 3 ลงตัว มันจึงเป็นเลขฟีโบนัชชีคู่ ถ้าไม่ใช่ เราก็ต้องปรับแบบนี้

n = (n/3)*3

ผลรวมของตัวเลขฟีโบนัชชีทั้งหมดจนถึงจุดนี้หากระบุโดย

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

ผลรวมของเลขคู่ทั้งหมดคือครึ่งหนึ่งของค่านี้:

sum_even = 4613732

สิ่งที่ดีเกี่ยวกับเรื่องนี้ก็คือมันเป็นอัลกอริธึม O(1) (หรือ O(log(N)) หากคุณรวมต้นทุนของอัลกอริธึม pow/log และทำงานเป็นสองเท่า .. เพื่อให้เราสามารถคำนวณผลรวมสำหรับค่าที่มีขนาดใหญ่มาก

person Michael Anderson    schedule 17.07.2010

arrow_upward
0
arrow_downward

ฉันไม่เข้าใจอัลกอริธึมของคุณแน่ชัด แต่ดูเหมือนว่าสเมอร์ริแมนจะมีประเด็น หมายเลขลำดับฟีบอนนาชี่ 4000000 ตัวจะเติบโตเหนือ 4M อย่างแน่นอน ฉันเดาว่าวิธีที่เร็วกว่าคือการสร้างลำดับสูงสุด 4M จากนั้นบวกลำดับเลขคู่เข้าด้วยกัน

person che    schedule 17.07.2010

arrow_upward
0
arrow_downward

มีเทคนิคอื่นๆ ที่ทำให้วิธีนี้มีประสิทธิภาพมากกว่าแค่การคำนวณรายการหมายเลขฟีโบนัชชีทั้งหมด แล้วรวมเลขคู่ในรายการ

ถ้าเป็นผมเองที่พยายามแก้ปัญหานี้ ผมจะทำรายการเลขฟีโบนัชชีคู่ มีลักษณะที่น่าสนใจของรายการนั้นหรือไม่? คุณสามารถโน้มน้าวตัวเองได้ว่ารูปแบบนี้เป็นจริงโดยทั่วไปหรือไม่?

ต่อไป ฉันอาจมองหาวิธีคำนวณสมาชิกของรายการนั้น และเฉพาะองค์ประกอบที่จำเป็นเท่านั้น ฉันอาจดูว่ามีสูตรใดบ้างที่ให้ผลรวมของลำดับฟีโบนัชชี

แน่นอนว่า ทั้งหมดนี้จะใช้เวลาของคุณเองมากกว่าการเขียนโค้ดโซลูชันแบบ Brute Force แต่ Project Euler มุ่งเน้นไปที่การค้นหาโซลูชันที่สวยงามมากกว่าโซลูชันแบบ Brute Force ท้ายที่สุดแล้ว หากคุณได้เรียนรู้บางอย่างเกี่ยวกับคณิตศาสตร์ หรือการคำนวณ คุณก็จะได้รับสิ่งนั้น

person Community    schedule 17.07.2010

arrow_upward
0
arrow_downward

เอาน่า วิธีที่ดีที่สุดในการคำนวณลำดับฟีโบนัชชีคือการใช้ 2 เทคนิค:

แก้ไขแล้ว ขออภัยสำหรับข้อผิดพลาดก่อนหน้านี้

1:

N =|2 0 0|
   |1 0 0|
   |0 0 0|

M =|3 2 1|
   |2 1 0|
   |0 0 1|

เมทริกซ์ N*M^(n/3) มีผลรวมของตัวเลข n ฟีโบนัชชีตัวแรก (กรองเฉพาะเลขคู่) เป็นองค์ประกอบมุมขวาบน

2:

คุณสามารถใช้ http://en.wikipedia.org/wiki/Exponentiation_by_squaring ได้ เนื่องจากการคูณเมทริกซ์ คือแหวน

ดังนั้นคุณสามารถแก้ปัญหาของเราได้ใน O(log n)

person Alistra    schedule 17.07.2010
comment
การเพิ่มประสิทธิภาพนี้ไม่ได้ช่วยอะไร เนื่องจากคุณต้องคำนวณหมายเลขฟีโบนัชชีทุกตัวอยู่ดี - person ; 17.07.2010
comment
ไม่ได้สังเกตเห็นคำผลรวมนั้น - person Alistra; 17.07.2010
comment
เขาต้องการผลรวมของเลขฟีโบนัชชีคู่เท่านั้น - person Mark Byers; 17.07.2010