Fibonacci genap angka

Terinspirasi oleh komentar di bawah pos Fibonacci untuk wawancara . Pengguna pavellyzhin menyebutkan tugas wawancara berikut ( komentar ):

Lebih dari setahun yang lalu, "php-programmer" merespons lowongan itu, mereka mengirim TK dan ada tugas dari Fibonacci: pilih semua bahkan angka Fibonacci dalam kisaran 1 hingga 10.000 . Memutuskan menggunakan loop (untuk). Di sana, juga diperlukan untuk membuat kueri SQL untuk memilih ulang tahun pengguna terdekat, untuk membuat sesuatu, saya tidak ingat dan menulis semacam fungsi. Saya melakukan segalanya, mengirimkannya. Mereka mengirim jawaban: "sesuai dengan hasil tugas tes Anda tidak diterima." Apa yang sebenarnya tidak mereka sukai tidak tertulis. Sekarang saya duduk dan berpikir, mungkin karena Fibonacci saya terbang ... :)

Dalam posting ini saya akan menunjukkan bagaimana mungkin untuk menyelesaikan masalah ini secara efektif, dan mungkin bahkan secara efisien, tetapi ini tidak akurat. Pada saat yang sama saya akan menunjukkan beberapa ribuan fakta yang terbukti tentang angka Fibonacci.

Berteori

Cara terbaik untuk memulai adalah melihat melalui mata angka Fibonacci N pertama dan mencoba menemukan pola dalam pengaturan angka genap.

$$

$$1.1, {\ bf 2}, 3.5, {\ bf 8}, 13.21, {\ bf 34}, 55.89, {\ bf 144}, \ ldots$$

Angka genap ditandai dalam urutan, karena Anda dapat melihat setiap angka Fibonacci ke-3 genap dan, mungkin, semua angka genap berada di posisi kelipatan 3. Ini akan menjadi perkiraan kami, sekarang kami perlu mengonfirmasinya dan menyusun algoritma perhitungan.

Bukti terbaik adalah sederhana, jadi terima kasih kepada AllexIn untuk ide sederhana yang awalnya saya lewatkan. Setiap angka Fibonacci berikutnya adalah jumlah dari dua sebelumnya, jika dua angka sebelumnya ganjil, maka yang berikutnya akan genap, jika dalam dua angka sebelumnya satu ganjil dan yang lain genap, maka yang berikutnya akan ganjil. Pada prinsipnya, ide ini saja sudah cukup untuk "secara intuitif meraba-raba" fakta yang telah terbukti. Buktinya dengan induksi sudah jelas, tapi saya tidak bisa menolak, agar tidak membawanya

Kami membuktikan bahwa "setiap angka Fibonacci ketiga adalah genap, dan dua yang mendahului setiap angka tersebut adalah ganjil."

• Induksi dasar . Dua angka fibonacci pertama $$$1,1$ - aneh, nomor ketiga $$$2$ - bahkan
• Hipotesis . Misalkan hingga beberapa angka Fibonacci kelipatan 3, memang benar bahwa setiap sepertiga adalah genap, dan dua angka sebelumnya adalah aneh.
• Langkah induksi . Angka yang mengikuti angka genap terakhir dari hipotesis adalah ganjil, karena itu diperoleh dari jumlah ganjil dengan genap, mengikuti angka yang sudah juga ganjil, karena itu diperoleh dari jumlah genap dengan yang ganjil, dan selanjutnya setelah genap, karena dua yang sebelumnya baru saja diterima untuknya aneh, dengan konstruksi nomornya adalah kelipatan 3, itu genap, dan dua yang sebelumnya aneh.

Ini adalah bagaimana kita dapat membuktikan dugaan kita tanpa menggunakan perhitungan matematis. Anda dapat memformalkan ide ini, pada saat yang sama mendapatkan formula untuk menghitung setiap angka Fibonacci ketiga $$$F_ {n + 3}$ dari $$$F_n$ dan $$$F_ {n + 1}$ . Menggunakan hubungan rekursif $$$F_ {n + 2} = F_ {n + 1} + F_ {n}$ kami mendapatkan:

$$

$$F_ {n + 3} = F_ {n + 2} + F_ {n + 1} = 2 F_ {n + 1} + F_n$$

Jadi jika $$$F_n$ - bahkan saat itu $$$F_ {n + 3}$ juga bahkan berdasarkan formula ini. Mengingat itu $$$F_3 = 2$ , maka setiap angka Fibonacci ketiga benar-benar genap, yang menegaskan bagian dari perkiraan kami. Di sini Anda perlu memastikan bahwa kami tidak kehilangan nomor genap lainnya, yaitu bahwa mereka semua memiliki kelipatan 3. Terima kasih kepada janatem untuk idenya yang sederhana, karena dari rumus di atas untuk $$$F_ {n + 3}$ itu juga mengikuti bahwa jika $$$F_n$ - aneh kalau begitu $$$F_ {n + 3}$ juga aneh, jadi kami mendapatkan angka itu dengan angka $$$3k-2,3k-1, k \ in \ mathbb {N}$ - aneh (dengan induksi, mulai dengan $$$F_1 = F_2 = 1$ - aneh), dan $$$3k, k \ in \ mathbb {N}$ - even, yang mencakup semua angka Fibonacci, yang artinya kita benar-benar mencakup semua angka genap.

Ada cara lain, karena mungkin untuk menunjukkan bahwa tidak ada angka genap lainnya. Misalkan ada nomor $$$F_m$ - bahkan dan $$$0 \ tidak \ equiv m \ mod 3$ lalu $$$m = 3k - 1$ atau $$$m = 3k + 1$ dimana $$$k$ - semacam alami.

Mari kita beralih ke representasi matriks angka Fibonacci dari pos asli

$$

$$\ begin {pmatrix} 0 & 1 \\ 1 & 1 \ end {pmatrix} ^ n = \ begin {pmatrix} F_ {n-1} & F_n \\ F_n & F_ {n + 1} \ end {pmatrix}$$

Menghitung penentu kedua bagian, kita dapatkan

$$

$$(-1) ^ n = F_ {n + 1} F_ {n-1} -F_n ^ 2$$

Oleh karena itu pembagi angka $$$F_ {n + 1}, F_n$ dan $$$F_ {n-1}, F_n$ pembagi pertandingan $$$(- 1) ^ n$ , yaitu angka-angka Fibonacci tetangga saling sederhana. Ini juga berarti kesederhanaan dan angka yang saling menguntungkan $$$F_ {3k}, F_ {3k-1}$ dan $$$F_ {3k}, F_ {3k + 1}$ , yaitu $$$F_ {3k}$ dan $$$F_m$ . Tetapi dengan asumsi $$$F_m$ - bahkan, dan $$$F_ {3k}$ - bahkan seperti yang telah dibuktikan sebelumnya. Jadi nomor genap lainnya $$$F_ {3k}$ dimana $$$k \ in \ mathbb {N}$ dalam deret Fibonacci tidak ada. Dan kami juga menetapkan fakta menarik bahwa angka-angka Fibonacci yang berdekatan saling sederhana.

Akhirnya, kami menunjukkan setidaknya satu cara lagi untuk membuktikan dugaan kami: gunakan teorema Lukas.

Teorema Lukas . Membagi bilangan bulat $$$F_m$ , dan $$$F_n$ , jika dan hanya jika itu adalah pembagi $$$F_d$ dimana $$$d = \ gcd (m, n)$ khususnya

$$

$$\ gcd (F_m, F_n) = F _ {\ gcd (m, n)}$$

Di sini $$$\ gcd$ Merupakan faktor umum terbesar. Jika dimasukkan $$$m = 3$ lalu $$$\ gcd (2, F_n) = F _ {\ gcd (3, n)}$ . Jika $$$F_n$ - bahkan, maka sisi kiri adalah 2, sehingga sisi kanan juga sama dengan 2, perlu itu $$$n$ dibagi 3 dan pada saat yang sama kebalikannya benar. Jadi, kita mendapatkan apa yang ingin kita buktikan.

Jadi, setiap angka Fibonacci ketiga adalah genap, dan setiap angka genap memiliki kelipatan tiga. Kami telah membuktikan ini dengan hati-hati dan tidak ada yang berani meragukannya sekarang.

Algoritma

Dan sekarang masih muncul dengan sebuah algoritma. Anda tentu saja dapat melakukan apa yang pavellyzhin awalnya lakukan, tetapi bukannya memeriksa $$$0 \ equiv F_n \ mod 2$ kita bisa periksa $$$0 \ equiv n \ mod 3$ , ini memelintir! Benar, ini tidak mempengaruhi jumlah iterasi dari algoritma, karena kami baru saja mengubah filter urutan. Lebih baik segera menghasilkan nomor Fibonacci berikutnya dengan properti yang kita butuhkan (paritas), jadi cara lain yang jelas adalah dengan menggunakan rumus Binet

$$

$$F_n = \ kiri \ lfloor \ frac {\ varphi ^ n} {\ sqrt {5}} \ kanan \ rceil, \ qquad n \ dalam \ {3,6, \ ldots, 3k \ ldots \}$$

Ada kesulitan dengan efisiensi perhitungan, lebih lanjut tentang ini di pos asli. Karena itu, saya mengusulkan yang terbaik, menurut saya, metode - perhitungan iteratif $$$F_ {n + 3}$ , ini bisa dilakukan, seperti yang kami tunjukkan sebelumnya, dengan formula $$$F_ {n + 3} = 2F_ {n + 1} + F_n$ . Untuk membangun transisi berulang dalam algoritma, kita perlu menghitung $$$F_ {n + 4}$ Semuanya serba sederhana

$$

$$F_ {n + 4} = F_ {n + 3} + F_ {n + 2} = 2F_ {n + 1} + F_n + F_ {n + 1} + F_n = 3F_ {n + 1} + 2F_n$$

Ngomong-ngomong, secara umum, mudah untuk membuktikannya

$$

$$F_ {n + m} = F_mF_ {n + 1} + F_ {m-1} F_n$$

Kemudian secara formal algoritma ditulis sebagai berikut (angka Fibonacci bahkan saat ini $$$F_n$ diikuti oleh angka Fibonacci $$$F_ {n + 1}$ , $$$M$ Apakah batas atas untuk angka yang diberikan dalam kondisi masalah):

1. $$$F_n \ leftarrow F_3 = 2, \ quad F_ {n + 1} \ leftarrow F_4 = 3$
2. Jika $$$F_n> M$ , lalu selesaikan, jika tidak tambahkan hasilnya $$$F_n$
3. $$$(F_n, F_ {n + 1}) \ leftarrow (2F_ {n + 1} + F_n, 3F_ {n + 1} + 2F_n)$ lanjut ke langkah 2.

Algoritma ini cukup sepele - kita cukup melompat ke setiap nomor Fibonacci ketiga dan mencetaknya (jika tidak lebih $$$M$ ) Kompleksitas algoritma masih linier, tetapi jumlah pengulangan langkah 2 persis sama dengan jumlah angka Fibonacci bahkan dalam kisaran $$$1 \ ldots M$ , untuk perbandingan, algoritma sederhana dengan penyaringan membutuhkan iterasi 3 kali lebih banyak (untuk setiap yang ditemukan, akan ada 2 yang dibuang).

Algoritma ada di atas kertas, apa wawancara, PHP? Nah, akhirnya mengungkap berarti PHP

function evenfibs($ubound) { $result = []; [$evenf, $nextf] = [2, 3]; while($evenf <= $ubound) { array_push($result, $evenf); [$nextf, $evenf] = [ 3 * $nextf + 2 * $evenf, 2 * $nextf + $evenf]; } return $result; } 

Catatan : Metode ini selalu dapat ditingkatkan, seperti, misalnya, pengguna hunroll menunjukkan. Idenya adalah bahwa untuk perhitungan kita tidak perlu sesuatu yang berlebihan, kecuali untuk hasil yang diperoleh sebagian, yaitu kita bisa menghitung bilangan genap hanya dengan menggunakan bilangan Fibonacci genap sebelumnya.

$$

$$F_ {n + 3} = 2F_ {n + 1} + F_ {n} = 3F_n + 2F_ {n-1} = 3F_n + F_ {n-1} + F_ {n-1} = \\ 3F_n + ( F_ {n-1} + F_ {n-2}) + F_ {n-3} = 4F_n + F_ {n-3}$$

 function evenfibs($ubound) { if($ubound < 2) return []; $evens = [2]; $next = 8; for($i = 1; $next <= $ubound; $i++) { $evens[$i] = $next; $next = $evens[$i]*4 + $evens[$i-1]; } return $evens; } 

Generalisasi

Kami menyebutkan di sini teorema Lukas, yang menyatakan itu $$$\ gcd (F_m, F_n) = F _ {\ gcd (m, n)}$ . Sebagai akibatnya, kita bisa mendapatkan angka Fibonacci $$$F_n$ kelipatan dari $$$F_m$ , jika dan hanya jika jumlahnya $$$n$ beberapa ke nomor $$$m$ . Yaitu setiap angka 4 Fibonacci dibagi 3, setiap 5 dengan 5, setiap 6 dengan 8, dll.

Kemudian, dengan cara yang sederhana, kita memperoleh algoritma untuk menghitung urutan Fibonacci, di mana unsur-unsurnya adalah kelipatan dari beberapa angka yang diberikan $$$F_m$ . Menggunakan fakta itu

$$

$$F_ {n + m} = F_mF_ {n + 1} + F_ {m-1} F_n \\ F_ {n + m + 1} = F_ {m + 1} F_ {n + 1} + F_mF_n$$

Algoritma sebelumnya berubah menjadi

1. $$$F_n \ leftarrow F_m, \ quad F_ {n + 1} \ leftarrow F_ {m + 1}$
2. Jika $$$F_n> M$ , lalu selesaikan, jika tidak tambahkan hasilnya $$$F_n$
3. $$$(F_n, F_ {n + 1}) \ leftarrow (F_mF_ {n + 1} + F_ {m-1} F_n, F_ {m + 1} F_ {n + 1} + F_mF_n)$ lanjut ke langkah 2.

Dimana $$$F_ {m-1}, F_m, F_ {m + 1}$ dapat diatur sebagai konstanta.

Ringkasan catatan . Seperti yang benar-benar diperhatikan oleh pengguna, dalam kasus umum, juga dimungkinkan untuk membuat algoritma yang hanya menggunakan angka dari hasil sebagian.

$$

$$F_ {n + 1} = F_n + F_ {n-1} \\ F_ {n + 2} = 3F_ {n} - F_ {n-2} \\ F_ {n + 3} = 4F_ {n} + F_ {n-3} \\ F_ {n + 4} = 7F_ {n} - F_ {n-4} \\ F_ {n + 5} = 11F_ {n} + F_ {n-5} \\ \ cdots \\ F_ {n + t} = (F_t + 2F_ {t-1}) F_n + (-1) ^ {t-1} F_ {nt}$$

Mari kita buktikan dengan metode induksi matematika, untuk t = 1 dan t = 2, pemenuhannya jelas. Misalkan tahan hingga beberapa t; lalu

$$

$$F_ {n + t + 1} = F_ {n + t} + F_ {n + t-1} = \\ (F_t + 2F_ {t-1}) F_n + (-1) ^ {t-1} F_ {nt} + \\ (F_ {t-1} + 2F_ {t-2}) F_n + (-1) ^ {t-2} F_ {n-t + 1} = \\ (F_t + F_ { t-1} + 2 (F_ {t-1} + F_ {t-2})) F_n + (-1) ^ {t-1} (F_ {nt} -F_ {n-t + 1}) = \\ (F_ {t + 1} + 2F_t) F_n + (-1) ^ {t-1} (F_ {nt} -F_ {nt} -F_ {nt-1}) = \\ (F_ {t + 1} + 2F_t) F_n + (-1) ^ tF_ {nt-1}$$

Sesuatu seperti total

Tugas tentu saja sepenuhnya sintetik, jumlah iterasi sangat kecil (untuk $$$M = $ 10.00$ jawabannya hanya berisi 6 angka, mis. 6 iterasi akan selesai, dan algoritma "head-on" yang asli akan membutuhkan 18), tetapi dengan cara ini pengguna yang menemukan sesuatu yang baru di sini sekarang dapat menunjukkan sedikit pengetahuan matematika yang lebih dalam pada angka-angka Fibonacci pada wawancara.

Sunting: Terima kasih kepada pengguna janatem dan AllexIn untuk bukti sederhana, saya memasukkannya ke dalam “Teoriisasi”, serta hunroll untuk algoritme hanya dengan menggunakan angka genap yang telah diperoleh dalam perhitungan dan kepada pengguna yang tidak tahu untuk menggeneralisasikannya.