Wawancara fibonacci

Penghitungan seri Fibonacci adalah tugas algoritmik klasik, karena sering diberikan pada wawancara ketika mereka ingin memverifikasi bahwa kandidat, pada prinsipnya, setidaknya dapat melakukan algoritma. Misalkan Anda adalah kandidat yang sama. Anda diberi tugas: dalam JavaScript, tulis fungsi fib(n) yang mengembalikan nomor Fibonacci n. Kami menganggap bahwa angka Fibonacci nol adalah nol. Validasi argumen tidak diperlukan. Pilihan apa yang Anda miliki?

1. Agar lebih mudah, dan orang-orang akan meraih Anda.

Solusi paling sederhana adalah siklus dangkal.

 const fib = n => { let prev = 0, next = 1; while(n-- && (next = prev + (prev = next))); return prev; } 

Lelucon. Tentu saja, Anda tidak perlu menulis seperti itu - kecuali, tentu saja, Anda tidak diwawancarai untuk posisi obfuscator penuh waktu.

 const fib = n => { let prev = 0, next = 1; for(let i = 0; i < n; i++){ next = prev + next; prev = next - prev; } return prev; } 

Apakah Anda kehabisan kupon variabel? cypok

Oke, oke, untuk keterbacaan yang lebih besar, mari kita tulis ini:

 const fib = n => { let prev = 0, next = 1; for(let i = 0; i < n; i++){ let temp = next; next = prev + next; prev = temp; } return prev; } 

Ini adalah pilihan klasik, sederhana dan elegan. Tapi mungkin Anda ingin menunjukkan pengetahuan Anda tentang beberapa konsep lain? Misalnya ...

2. Untuk memahami rekursi, Anda harus memahami rekursi

Sebagai contoh, ya, Anda dapat menunjukkan bahwa Anda dapat melakukan rekursi. Misalnya, seperti ini:

 const fib = n => { if(n <= 1){ return n; }else{ return fib(n - 1) + fib(n - 2); } } 

Ingat opsi ini. Ini tidak layak dilakukan. Seharusnya tidak. Itu tidak mungkin. Tidak pernah. Ini lebih buruk daripada menendang anak anjing, dan sebanding dengan holocaust kecil.

Anda mungkin bertanya mengapa. Dalam hal ini, jalankan saja kode ini dan coba untuk menghitung, katakanlah, angka Fibonacci Lima Puluh. Saya pikir Anda akan merasakan penundaan tertentu. Lelucon. Saya percaya bahwa jika Anda menjalankan kode ini bukan pada superkomputer, maka Anda tidak akan menunggu hasilnya. Terlepas dari kenyataan bahwa kode sederhana, non-rekursif dari contoh sebelumnya akan menghitung anggota kelima puluh dari urutan Fibonacci lebih cepat daripada Anda punya waktu untuk mengatakan kata "fifty" atau suku kata apa pun.

Disajikan dalam bahasa kasar notasi-O, solusi semacam itu memiliki kompleksitas waktu O (e ⁿ ). Artinya, waktu eksekusi fungsi ini tumbuh secara eksponensial dengan meningkatnya n. Yaitu, ketika n bertambah, waktu eksekusi bertambah. Secara kasar, jika fib(45) Anda harus menunggu satu jam, maka fib(46) Anda akan menunggu dua jam, fib(47) - 4 jam, dan seterusnya. Saya mengunyah dengan sangat rinci sehingga setiap pembaca, bahkan seorang juru ketik yang pertama kali mencoba menulis skrip, dapat menyadari kengerian situasi ini.

Ini benar, tetapi terlalu kasar. Anda bisa mendapatkan perkiraan jumlah panggilan fungsi yang lebih akurat ~ (1 + sqrt (5)) fib (n) dan komentar indah “Untuk menghitung angka Fibonacci menggunakan metode rekursif naif, Anda membutuhkan panggilan fungsi 3,2 kali lebih banyak daripada angka Fibonacci itu sendiri.” Taus

Dan kami mendapatkan metode lain untuk menghitungnya. Anda hanya perlu menjalankan metode rekursif naif, menghitung jumlah panggilan fungsi dan membaginya dengan 3,2! Cerberuser

Jika Anda diharuskan untuk memecahkan masalah ini secara rekursif selama wawancara, ini kemungkinan besar adalah jebakan. Rekursi "benar" yang bekerja dalam waktu linier mungkin terlihat, misalnya, seperti ini:

 const fib2 = n => { if(n == 0){ return [0, 1]; }else{ const [prev, next] = fib2(n - 1); return [next, prev + next]; } } const fib = n => fib2(n)[0]; 

Untuk meringkas: terlepas dari kenyataan bahwa angka-angka Fibonacci adalah klasik, contoh rekursi buku teks, pada kenyataannya ini bukan kasus yang paling nyaman untuk menerapkan rekursi. Tetapi Anda bisa mencoba memamerkan lebih banyak pengetahuan.

3. Fungsi peringatan

Ada cara ajaib yang mengubah solusi yang sangat tidak efektif dari paragraf terakhir menjadi solusi yang berpotensi sangat cepat (walaupun bukan tanpa masalah). Namanya adalah memoisasi. Dan jika Anda berbicara bahasa Rusia - kami hanya mengingat hasil panggilan sebelumnya alih-alih menghitungnya lagi.

Pada dasarnya, kita bahkan tidak dapat mengubah apa pun di dalam solusi itu - cukup tambahkan fungsi memoize wrapper. Di sini, untuk kejelasan, saya menggunakan versi yang disederhanakan untuk fungsi dengan satu argumen.

 //   ,       ,     const oldFib = n => { if(n <= 1){ return n; }else{ return oldFib(n - 1) + oldFib(n - 2); } } const memoize = f => { const cache = {}; return arg => cache[arg] || (cache[arg] = f(arg)); } const fib = memoize(oldFib); 

Voila! Sekarang fungsi fib memiliki akses ke objek cache melalui penutupan. Jika dipanggil dengan argumen yang belum pernah ditemukan sebelumnya, nilai yang dihitung disimpan dalam cache . Dengan pemanggilan fungsi baru dengan argumen yang sama, nilainya tidak harus dihitung ulang, itu hanya akan diambil dari cache. Masalah utama dari fungsi fib lama "buruk" adalah bahwa nilai yang sama di dalamnya dihitung ulang beberapa kali. Sebagai contoh, untuk menghitung fib(45) perlu untuk menghitung f(44) satu kali, dua kali f(43) , tiga kali f(42) , lima kali f(41) , dan seterusnya.


Jadi, sekarang nilai-nilai sebelumnya akan dihitung sekali, dan ketika diminta kembali - baru saja diambil dari cache. Bisakah Anda bayangkan seberapa cepat kita sekarang dapat menghitung angka Fibonacci empat puluh lima? Serius, jam berapa menurutmu?

Bahkan - sedikit lebih lambat. Saya sengaja membuat kesalahan klasik, sering dibuat ketika memotret fungsi rekursif. Ketika fib(45) disebut “under the hood”, oldFib(45) dipanggil, yang memanggil oldFib(44) dan oldFib(43) untuk kebutuhannya ... Apakah Anda merasakan tangkapan? Selanjutnya, sudah ada panggilan ke fungsi biasa, yang tidak memo. Tentu saja, ketika memanggil fib(45) lagi, kami langsung mendapatkan hasil dari cache - namun, panggilan pertama tidak mempercepat sama sekali. Untuk memperbaiki ini, Anda masih harus mendapatkan oldFib bawah kunci pas:

 const oldFib = n => { if(n <= 1){ return n; }else{ return fib(n - 1) + fib(n - 2); } } const memoize = f => { const cache = {}; return arg => cache[arg] || (cache[arg] = f(arg)); } const fib = memoize(oldFib); 

Hebat! Sekarang panggilan pertama ke fib(45) bekerja pada kecepatan yang sebanding dengan versi dengan loop. Dan tantangan lebih lanjut umumnya akan bekerja dalam waktu yang konstan ... Ups! Lagi-lagi tertipu. Memperoleh nilai properti objek dengan kunci adalah operasi cepat, tapi tetap saja O (1) hanya rata-rata, dalam kasus terburuk ia bisa terdegradasi ke O (n). Untuk membuatnya sangat baik, dalam kasus kami, kami dapat mengubah jenis cache dari objek ke array.

Tentu saja, orang tidak boleh lupa bahwa memoisasi membutuhkan memori. Dan sementara kita mengurangi kompleksitas waktu, kompleksitas memori tumbuh dari O (1) menjadi O (n).

Bagaimana lagi yang bisa kita pamerkan? Misalnya, menunjukkan pengetahuan matematika Anda yang mendalam

4. Tuan Binet

Ada ilmu khusus yang luar biasa tentang cara mengubah hubungan perulangan menjadi formula eksplisit. Di sini kita tidak akan membahas perinciannya. Kami hanya akan mengatakan bahwa untuk bilangan Fibonacci, menggunakan argumen yang cukup sederhana, kita dapat memperoleh rumus berikut, yang dikenal sebagai rumus Binet:

$$

$$F_n = \ frac {\ kiri (\ frac {1 + \ sqrt5} {2} \ kanan) ^ n - \ kiri (\ frac {1 - \ sqrt5} {2} \ kanan) ^ n} {\ sqrt5}$$

Namun, ini bahasa yang cukup matematis, kami menulisnya dalam JavaScript:

 const fib = n => { const a = (1 + 5 ** 0.5) / 2; const b = (1 - 5 ** 0.5) / 2; return (a ** n - b ** n) / 5 ** 0.5; } 

Mari kita simak beberapa angka pertama. Hebat, semuanya sepertinya bekerja. Ini 13, di sini 21, di sini 34, di sini ... 54,9999999999999999?

Ya, tentu saja, hasil seperti itu masuk akal. Rumus Binet akurat secara matematis, tetapi komputer beroperasi dengan fraksi akurasi terbatas, dan kesalahan dapat menumpuk ketika bekerja dengan mereka, yang terjadi dalam kasus ini. Namun, kami dapat memperbaikinya. Mengetahui bahwa yang dikurangkan dalam pembilang akan selalu kecil dalam besarnya, kita dapat menyederhanakan rumus ke status berikut:

$$

$$F_n = \ kiri \ lfloor \ frac {\ kiri (\ frac {1 + \ sqrt5} {2} \ kanan) ^ n} {\ sqrt5} \ kanan \ rceil$$

Di sini tanda kurung kotak yang belum selesai yang aneh berarti bilangan bulat terdekat, yaitu pembulatan. Tulis ulang kode kami:

 const fib = n => { const a = (1 + 5 ** 0.5) / 2; return Math.round(a ** n / 5 ** 0.5); } 

Ya, itu jauh lebih baik. Kita bisa melihat 55 dan 89, dan bahkan angka Fibonacci favorit saya adalah 144 (yang saya suka karena sama dengan dua belas kuadrat). Semuanya akan baik-baik saja hingga angka 76. Yang seharusnya sama dengan 3416454622906707, dan fungsi kami akan menghitung 3416454622906706. Karena masalah keakuratan terbatas dari angka pecahan belum hilang, kami hanya mendorongnya lebih dalam dan berharap tidak akan muncul. Seperti yang ditunjukkan contoh ini, mereka berharap dengan sia-sia.

Faktanya, kita dapat melakukan sesuatu yang lain untuk menyimpan metode ini. Tetapi lebih lanjut tentang itu di bawah ini. Sementara itu - lelucon samping. Mari kita bicara tentang metode yang keras, hardcore, dan brutal.

5. Ikuti kelinci putih.

Mereka mengatakan bahwa jika Anda memiliki masalah dan muncul ide bahwa Anda dapat menyelesaikannya dengan ekspresi reguler, sekarang Anda memiliki dua masalah. Matriks adalah ekspresi reguler sebaliknya. Banyak masalah, jika dirumuskan ulang dalam bahasa matriks, diselesaikan dengan sendirinya.

Adapun angka-angka Fibonacci, bagi mereka dalam bahasa matriks Anda dapat menulis identitas yang jelas ini:

$$

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

Yaitu, jika kita mengambil sepasang angka Fibonacci berturut-turut dan mengalikannya dengan matriks langsung, kita mendapatkan pasangan berikut. Dan kesimpulan logis berikut dari ini: jika kita mengambil sepasang angka Fibonacci nol dan pertama, yaitu, nol dan satu, dan mengalikannya dengan matriks ini ke kekuatan n, kita mendapatkan sepasang n dan en ditambah Fibonacci pertama. Yaitu, berbicara secara manusiawi:

$$

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

Anda dapat menyederhanakan ini sedikit lebih dengan meninggalkan vektor. Bahkan, semua nilai yang diperlukan terkandung dalam matriks itu sendiri:

$$

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

Bagus bukan? Masih harus dipahami, untuk apa harmoni keledai, jika ia bukan seorang philharmonic. Maksud saya - mengapa kesulitan seperti itu tiba-tiba. Dan jawabannya sederhana - eksponensial cepat.

Berapa banyak perkalian dasar yang diperlukan untuk menghitung, katakanlah, 2 ¹⁰ ? Orang normal akan mengatakan sembilan. Dua dua empat. Dua kali empat - delapan. Dua kali delapan adalah enam belas. Dan sebagainya. Seseorang yang licik akan mengatakan itu empat.

$$

$$2 \ cdot 2 = 4 \\ 4 \ cdot 4 = 16 \\ 2 \ cdot 16 = 32 \\ 32 \ cdot 32 = 1024$$

Programmer akan berkata. bahwa dia mengingat angka ini dengan hati, dan tidak ada yang perlu dikalikan. Namun, kami membahas masalah memoisasi di atas.

Jadi, eksponensial cepat juga berlaku untuk matriks, dan dengan demikian memungkinkan kita untuk mengurangi kompleksitas waktu asimptotik dari fungsi kita dari O (n) menjadi O (log n). Dan ini sangat keren - kecuali, tentu saja, kompleksitas ini sangat penting bagi kita. Mari kita menulis kodenya:

 //    ,          const mul = ( [ [a1, a2], [a3, a4] ], [ [b1, b2], [b3, b4] ]) => [ [a1 * b1 + a2 * b3, a1 * b2 + a2 * b4], [a3 * b1 + a4 * b3, a3 * b2 + a4 * b4] ]; const matrix = [ [0, 1], [1, 1] ]; // ,   const id = [ [1, 0], [0, 1] ] const fib = n => { let result = id; const bits = n.toString(2); //        for(const bit of bits){ result = mul(result, result); if(bit == "1"){ result = mul(result, matrix); } } return result[1][0]; } 

Jadi kami mendapatkan algoritma tercepat di Wild West. Dan itu, tidak seperti kebanyakan yang sebelumnya, dapat ditunjukkan tanpa ironis pada sebuah wawancara. Dan di beberapa tempat matematika-luas itu akan diharapkan dari Anda.

PS

Saya menjanjikan komentar tentang cara menyimpan metode berdasarkan rumus Binet. Jawabannya ada di artikel saya ini. Di sana, untuk kebutuhan ekonomi nasional, saya menulis kelas khusus, akar dari lima bilangan rasional, yang, tanpa kehilangan keakuratan, dapat menyimpan hasil operasi aritmatika pada bilangan bulat dan akar lima. Anda dapat mengambil kelas ini, menambahnya dengan metode pembulatan dan menggunakannya untuk mencari angka Fibonacci menggunakan rumus Binet. Dan kemudian menyuntikkan nitro oksida dengan menerapkan eksponensial cepat.

Dan apa yang paling menarik: jika Anda dengan cermat melihat angka apa yang akan diperoleh dalam proses, operasi mana yang akan dilakukan, akan menjadi jelas bahwa metode ini merupakan perkalian matriks yang sama, hanya di bawah fasad yang berbeda. Satu-satunya perbedaan adalah apakah kita menyimpan angka dalam array dua dimensi atau dalam bidang objek kelas khusus.

Itu saja. Jika Anda berpikir bahwa saya telah melewatkan beberapa cara menarik lainnya untuk menemukan nomor yang tidak diperlukan, pastikan untuk menuliskannya di komentar.

Ada juga metode seperti penggandaan cepat . Ia bekerja seperti perkalian matriks dalam O (log), tetapi dengan konstanta yang lebih kecil dalam asimptotik (dan dalam praktiknya). Secara singkat, maka dua formula digunakan di sana, dengan mengandalkan yang mana dapat dengan cepat memutar kembali ke indeks dua kali lebih rendah secara rekursif:

F _2n = F _n * (2 * F _{n + 1} - F _n )
F _{2n + 1} = F _n ² + F _{n + 1} ²

Implementasinya, omong-omong, cukup kompak.

Perbandingan kecepatan berbagai metode

just_maksim