Fibonacci di bawah 4 juta [duplikat]

Kondisi loopnya salah, seharusnya seperti ini:

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

Ada beberapa masalah dengan kode Anda:

• Anda mengulang empat juta kali, bukannya sampai suatu kondisi benar.
• Anda telah mengulangi kode di badan loop Anda.

Kebanyakan orang ketika mereka mulai belajar Python hanya mempelajari pemrograman penting. Hal ini tidak mengherankan karena Python adalah bahasa yang sangat penting. Tetapi Python juga mendukung pemrograman fungsional sampai batas tertentu dan untuk latihan semacam ini, pendekatan pemrograman fungsional lebih mencerahkan menurut saya.

Pertama tentukan generator yang menghasilkan semua angka Fibonacci:

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

Untuk menggunakan generator ini kita dapat mengimpor beberapa fungsi berguna dari itertools. Untuk mencetak beberapa angka pertama gunakan islice:

from itertools import ifilter, islice, takewhile

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

1
1
2
3
5

Untuk menemukan bilangan genap saja kita dapat menggunakan ifilter untuk menghasilkan bilangan baru generator:

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

Untuk mengambil nomor dari generator hingga jumlahnya melebihi empat juta, gunakan take while :

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

Untuk mengatasi masalah ini Anda dapat menggunakan penjumlahan:

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

Saya harap ini menunjukkan bahwa pendekatan pemrograman fungsional tidaklah sulit dan merupakan cara yang lebih elegan untuk menyelesaikan jenis masalah tertentu.

Apakah Anda yakin i ingin kurang dari 4 juta?

Anda mungkin tertarik untuk mengetahui tentang Ensiklopedia On-Line Barisan Integer!

Anda dapat mencari informasi berdasarkan nama atau urutan.

Jika Anda mencari 0,2,8,34 atau 'Fibonacci Genap', Anda akan diarahkan ke urutan A014445

Di sana Anda akan menemukan banyak informasi termasuk rumus,
dari sana untuk membuat kode generator yang akan menghasilkan bilangan fibonacci genap secara langsung sangatlah mudah.

def evenfib():
    """ Generates the even fibonacci numbers """
    a, b = 2, 0
    while True:
        a, b = b, a+4*b
        yield a  

Saat ini, Anda menjumlahkan semua 2 juta angka Fibonacci genap pertama.

Namun bukan itu tugasnya. Anda harus menjumlahkan semua angka Fibonacci genap yang dibawah 4 juta.

CATATAN: Ini telah banyak dimodifikasi untuk menjawab pertanyaan sebenarnya

Inilah metode alternatif (dan sangat cepat, namun belum teruji). Itu bergantung pada beberapa properti:

1. Setiap bilangan Fibonacci dapat dihitung secara langsung sebagai floor( pow( phi, n ) + 0.5 ) (Lihat Perhitungan dengan Pembulatan di http://en.wikipedia.org/wiki/Fibonacci_number ). Sebaliknya indeks bilangan Fibonacci terbesar kurang dari i diberikan oleh floor( log(i*sqrt(5)) / log(phi) )
2. Jumlah bilangan Fibonacci N pertama adalah bilangan fibonacci N+2 dikurangi 1 (Lihat Identitas Kedua di halaman wikipedia yang sama)
3. Angka Fibonacci genap adalah setiap angka ketiga. (Lihat urutan mod 2 dan hasilnya sepele)
4. Jumlah bilangan Fibonacci genap adalah setengah dari jumlah bilangan Fibonacci ganjil sampai titik yang sama pada barisan tersebut. (Ini mengikuti dari 3. dan sifat bahwa F(3N) = F(3N-1) + F(3N-2) jadi F(3N-2) + F(3N-1) + F(3N) = 2 F (N) .. lalu menjumlahkan kedua ruasnya.

Jadi konversikan nilai maksimum kita sebesar 4000000, hitung indeks angka Fibonacci tertinggi yang kurang dari itu.

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

33 habis dibagi 3 jadi bilangan Fibonacci genap, kalau tidak kita perlu sesuaikan n seperti ini.

n = (n/3)*3

Jumlah semua bilangan Fibonacci sampai saat ini jika diberikan oleh

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

Jumlah semua bilangan genap adalah setengahnya:

sum_even = 4613732

Hal yang menyenangkan tentang ini adalah ini merupakan algoritma O(1) (atau O(log(N)) jika Anda memasukkan biaya pow/log), dan bekerja pada ganda.. sehingga kita dapat menghitung jumlah untuk nilai yang sangat besar.

Saya tidak begitu memahami algoritme Anda, tetapi tampaknya smerriman ada benarnya, 4000000 bilangan deret Fibonnacci pasti akan tumbuh di atas 4M. Saya kira pendekatan yang lebih cepat adalah dengan menghasilkan urutan hingga 4M, lalu menjumlahkannya.

Ada trik lain yang membuat hal ini lebih efisien daripada sekadar menghitung daftar lengkap angka Fibonacci, lalu menjumlahkan angka genap dalam daftar tersebut.

JIKA saya yang mencoba memecahkan masalah ini, saya akan membuat daftar bilangan Fibonacci genap. Apakah ada ciri-ciri menarik dari daftar itu? Bisakah Anda meyakinkan diri sendiri bahwa pola ini berlaku secara umum?

Selanjutnya, saya mungkin mencari cara untuk menghitung anggota daftar itu, dan hanya elemen-elemen yang diperlukan. Saya bahkan mungkin melihat apakah ada rumus yang bisa ditemukan yang menghasilkan jumlah deret angka Fibonacci.

Tentu saja, semua ini akan memakan lebih banyak waktu Anda daripada sekadar mengkodekan solusi brute force, namun Project Euler adalah tentang menemukan solusi yang bagus daripada solusi brute force. Pada akhirnya, jika Anda telah mempelajari sesuatu tentang matematika, tentang komputasi, maka Anda telah memperolehnya.

Yuk, cara menghitung deret Fibonacci yang optimal adalah dengan menggunakan 2 trik:

EDIT, maaf atas kesalahan sebelumnya

1:

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

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

Matriks N*M^(n/3) memiliki jumlah n bilangan fibonacci pertama (difilter hanya ke bilangan genap) adalah elemen kanan atas.

2:

Anda dapat menggunakan http://en.wikipedia.org/wiki/Exponentiation_by_squaring, karena perkalian matriks adalah sebuah cincin.

Jadi Anda bisa menyelesaikan masalah kita di O(log n)