Tolong jelaskan kode sederhana ini:
public int fibonacci(int n) {
if(n == 0)
return 0;
else if(n == 1)
return 1;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}
Saya bingung dengan baris terakhir terutama karena jika n = 5 misalnya, maka fibonacci (4) + fibonacci (3) akan dipanggil dan seterusnya, tetapi saya tidak mengerti bagaimana algoritma ini menghitung nilai pada indeks 5 dengan ini metode. Tolong jelaskan dengan banyak detail!
Jawaban:
Dalam urutan fibonacci setiap item adalah jumlah dari dua sebelumnya. Jadi, Anda menulis algoritma rekursif.
Begitu,
Sekarang kamu sudah tahu
fibonacci(1)==1 and fibonacci(0) == 0
. Jadi, Anda selanjutnya dapat menghitung nilai lainnya.Sekarang,
Dan dari deret fibonacci
0,1,1,2,3,5,8,13,21....
kita dapat melihat bahwa untuk5th element
deret fibonacci kembali5
.Lihat di sini untuk Tutorial Rekursi .
sumber
Ada 2 masalah dengan kode Anda:
Kode
fibonacci(n - 1) + fibonacci(n - 2)
ini sangat salah.
Masalahnya adalah bahwa ia memanggil fibonacci bukan 50 kali tetapi lebih.
Pada awalnya ia memanggil Fibre (49) + fibonacci (48),
Fibre (48) + Fibre (47) + Fibre (47) + Fibre (46)
Setiap kali menjadi Fibre (n) lebih buruk, jadi kompleksitasnya eksponensial.
Pendekatan kode non-rekursif:
sumber
2*fibonacci(n+1)-1
, sehingga ia tumbuh dengan kompleksitas yang sama dengan angka-angka fibonacci itu sendiri, yaitu 1,618 ^ n bukannya 2 ^ nDalam kode semu, di mana n = 5, berikut ini terjadi:
Ini dipecah menjadi:
Ini dipecah menjadi:
Ini dipecah menjadi:
Ini dipecah menjadi:
Ini menghasilkan: 5
Mengingat urutan fibonnacci adalah 1 1 2 3 5 8 ... , elemen ke-5 adalah 5. Anda dapat menggunakan metodologi yang sama untuk mencari iterasi lain.
sumber
Rekursi terkadang sulit untuk dipahami. Cukup evaluasi pada selembar kertas untuk sejumlah kecil:
Saya tidak yakin bagaimana Java sebenarnya mengevaluasi ini, tetapi hasilnya akan sama.
sumber
Anda juga dapat menyederhanakan fungsi Anda, sebagai berikut:
sumber
Poin penting yang perlu diperhatikan adalah algoritma ini eksponensial karena tidak menyimpan hasil angka yang dihitung sebelumnya. misal F (n-3) disebut 3 kali.
Untuk lebih jelasnya rujuk algoritma oleh dasgupta bab 0.2
sumber
Sebagian besar jawabannya baik dan menjelaskan bagaimana rekursi dalam fibonacci bekerja.
Berikut ini adalah analisis pada tiga teknik yang termasuk rekursi juga:
Ini kode saya untuk menguji ketiganya:
Inilah hasilnya:
Oleh karena itu kita dapat melihat memoisasi adalah waktu terbaik dan untuk pertandingan loop erat.
Namun rekursi memakan waktu paling lama dan mungkin Anda harus hindari dalam kehidupan nyata. Juga jika Anda menggunakan rekursi, pastikan Anda mengoptimalkan solusinya.
sumber
Ini adalah video terbaik yang saya temukan yang sepenuhnya menjelaskan rekursi dan deret Fibonacci di Jawa.
http://www.youtube.com/watch?v=dsmBRUCzS7k
Ini adalah kode untuk urutan dan penjelasannya lebih baik daripada yang bisa saya lakukan untuk mencoba mengetiknya.
sumber
Untuk solusi recursive fibonacci, penting untuk menyimpan output dari angka fibonacci yang lebih kecil, sambil mengambil nilai dari angka yang lebih besar. Ini disebut "Memoizing".
Berikut ini adalah kode yang menggunakan memoizing nilai fibonacci yang lebih kecil, sambil mengambil nomor fibonacci yang lebih besar. Kode ini efisien dan tidak membuat banyak permintaan dengan fungsi yang sama.
sumber
dalam urutan fibonacci , dua item pertama adalah 0 dan 1, setiap item lainnya adalah jumlah dari dua item sebelumnya. yaitu:
0 1 1 2 3 5 8 ...
jadi item ke-5 adalah jumlah item ke-4 dan ke-3.
sumber
Michael Goodrich et al memberikan algoritma yang sangat pintar dalam Struktur Data dan Algoritma di Jawa, untuk memecahkan fibonacci secara waktu linear secara linier dengan mengembalikan array [fib (n), fib (n-1)].
Ini menghasilkan fib (n) = fibGood (n) [0].
sumber
Inilah solusi O (1):
Formula nomor Fibonacci Binet digunakan untuk implementasi di atas. Untuk input besar
long
bisa diganti denganBigDecimal
.sumber
Urutan Fibbonacci adalah urutan yang menjumlahkan hasil angka ketika ditambahkan ke hasil sebelumnya dimulai dengan 1.
Setelah kita memahami apa itu Fibbonacci, kita dapat mulai memecah kode.
Statment if pertama memeriksa case dasar, di mana loop dapat keluar. Lain lagi jika pernyataan di bawah ini melakukan hal yang sama, tetapi bisa ditulis ulang seperti itu ...
Sekarang setelah kasus dasar ditetapkan, kita harus memahami tumpukan panggilan. Panggilan pertama Anda ke "fibonacci" akan menjadi yang terakhir untuk diselesaikan pada tumpukan (urutan panggilan) karena mereka menyelesaikan dalam urutan terbalik dari mana mereka dipanggil. Metode terakhir yang disebut resolves terlebih dahulu, lalu yang terakhir dipanggil sebelum itu dan seterusnya ...
Jadi, semua panggilan dilakukan terlebih dahulu sebelum semuanya "dihitung" dengan hasil tersebut. Dengan input 8, kami mengharapkan output 21 (lihat tabel di atas).
fibonacci (n - 1) terus dipanggil hingga mencapai base case, kemudian fibonacci (n - 2) dipanggil hingga mencapai base case. Ketika tumpukan mulai menjumlahkan hasil dalam urutan terbalik, hasilnya akan seperti ...
Mereka terus menggelegak (menyelesaikan mundur) hingga jumlah yang benar dikembalikan ke panggilan pertama di tumpukan dan itulah cara Anda mendapatkan jawaban Anda.
Karena itu, algoritma ini sangat tidak efisien karena menghitung hasil yang sama untuk setiap cabang yang dipecah dengan kode. Pendekatan yang jauh lebih baik adalah pendekatan "bottom-up" di mana tidak diperlukan Memoisasi (caching) atau rekursi (tumpukan panggilan yang mendalam).
Seperti ...
sumber
Sebagian besar solusi yang ditawarkan di sini berjalan dalam kompleksitas O (2 ^ n). Menghitung ulang node identik dalam pohon rekursif tidak efisien dan membuang siklus CPU.
Kita dapat menggunakan memoisasi untuk membuat fungsi fibonacci berjalan dalam waktu O (n)
Jika kita mengikuti rute Bottom-Up Dynamic Programming, kode di bawah ini cukup sederhana untuk menghitung fibonacci:
sumber
Mengapa jawaban ini berbeda
Setiap jawaban lainnya:
(selain: tidak ada yang benar-benar efisien; gunakan rumus Binet untuk langsung menghitung angka ke- n istilah )
Tail Recursive Fib
Berikut ini adalah pendekatan rekursif yang menghindari panggilan rekursif ganda dengan melewati kedua jawaban sebelumnya DAN yang sebelumnya.
sumber
Ini adalah urutan dasar yang menampilkan atau mendapatkan output 1 1 2 3 5 8 itu adalah urutan bahwa jumlah dari angka sebelumnya, angka saat ini akan ditampilkan berikutnya.
Cobalah untuk menonton tautan di bawah Tutorial urutan Fibonacci Recursive Java
Klik Di Sini Tonton Tutorial Java Recursive Fibonacci sequence untuk sendok makan
sumber
Saya pikir ini adalah cara sederhana:
sumber
Jawaban RanRag (diterima) akan berfungsi dengan baik tetapi itu bukan solusi yang dioptimalkan sampai dan kecuali dihafal seperti yang dijelaskan dalam jawaban Anil.
Untuk pertimbangan rekursif di bawah pendekatan, pemanggilan metode
TestFibonacci
minimalsumber
sumber
Dengan menggunakan ConcurrentHashMap internal yang secara teoritis memungkinkan implementasi rekursif ini beroperasi dengan baik di lingkungan multithreaded, saya telah mengimplementasikan fungsi fib yang menggunakan BigInteger dan Rekursi. Butuh sekitar 53ms untuk menghitung 100 bilangan fib pertama.
Kode tes adalah:
sumber
Berikut ini adalah satu baris febonacci rekursif:
sumber
Coba ini
sumber
Sebagai pelengkap, jika Anda ingin dapat menghitung angka yang lebih besar, Anda harus menggunakan BigInteger.
Contoh berulang.
sumber
http://en.wikipedia.org/wiki/Fibonacci_number lebih terinci
Jadikan sesederhana yang diperlukan tidak perlu menggunakan while dan loop lainnya
sumber
sumber
Gunakan
while
:Keuntungan dari solusi ini adalah mudahnya membaca kode dan memahaminya, berharap itu membantu
sumber
Urutan Fibbonacci adalah salah satu yang merangkum hasil angka kemudian kita tambahkan ke hasil sebelumnya, kita harus mulai dari 1. Saya mencoba mencari solusi berdasarkan algoritma, jadi saya membangun kode rekursif, perhatikan bahwa saya menyimpan nomor sebelumnya dan saya mengubah posisi. Saya mencari urutan Fibbonacci dari 1 hingga 15.
sumber
sumber
Fibonacci Sederhana
sumber
@ chro sangat tepat, tetapi dia tidak menunjukkan cara yang benar untuk melakukan ini secara rekursif. Inilah solusinya:
sumber