Jawaban dan Penjelasan:

Bilangan/Deret Fibonacci

Bilangan/deret Fibonacci didefinisikan secara rekursif sebagai berikut:

Jadi:

f(2) = f(1) + f(0) = 1 + 0 = 1

f(3) = f(2) + f(1) = 1 + 1 = 2

f(4) = f(3) + f(2) = 2 + 1 = 3

f(5) = f(4) + f(3) = 3 + 2 = 5

dst.

Di bawah ini adalah algoritma Fibonacci secara iteratif (bukan rekursif) yang menampilkan semua bilangan Fibonacci hingga jumlah tertentu sesuai masukan pengguna.

ALGORITMA

Algoritma Secara Deskriptif

1. Meminta masukan jumlah bilangan fibonacci, dan disimpan dalam variabel n, atau deklarasi n dalam program.

2. Menyimpan nilai f(0) (= 0) ke variabel a.

3. Menyimpan nilai f(1) (= 1) ke variabel b.

4. Menampilkan a dan b.

5. Untuk i = 2 hingga n, f(i) diperoleh dengan perulangan:

• a. Menyimpan nilai variabel b [ = f(i-1) ] dalam variabel c.
• b. Melakukan penjumlahan b [ = f(i-1) ] dengan a [= f(i-2)], dan menyimpannya dalam variabel b. Saat ini, b adalah f(i).
• c. Menyimpan variabel c [ = f(i-1) ] dalam variabel a, sehingga a akan menjadi f(i-2) pada iterasi selanjutnya.
• d. Menampilkan nilai b [ = f(i) ].

Algoritma Dengan Pseudocode

KAMUS

   a, b, c, n, i: integer

ALGORITMA

   read n

   a = 0

   b = 0

   for i = 2 to n do

       c = b

       b = b+a

       a = c

   end for

Contoh Implementasi

(menggunakan C++)

#include <iostream>

using namespace std;

int main() {

   int a, b, c, n;

   cout << "n = ? ";

   cin >> n;

   a = 0;

   b = 1;

   cout << a << ", " << b;

   for (int i=2; i <= n; i++) {

       c = b;

       b += a;

       a = c;

       cout << ", " << b;

   }

}

Hasil eksekusinya (dengan masukan n = 20):

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765