FIBONANCY

DERET FIBONACCI
Proses pencarian dan menemukan data kembali (retrieval) merupakan hal yang amat penting dalam suatu kegiatan komputasi. Banyak teknik yang dapat digunakan dalam proses pencarian, yaitu 1. Teknik Sequential/ LinierSearching, 2. Teknik Binary, 3. Teknik D and C, 4. Teknik StraitMaxMin, dan 5. Teknik Deret Fibonancy.
Dalam hal ini, proses yang akan penulis coba sampaikan adalah pencarian dengan Teknik Fibonancy. Teknik ini dalam proses pencariannya menggunakan pendekatan dengan Deret Fibonancy, sehingga sebelum kita melakukan aplikasi, terlebih dahulu harus mengetahui bagaimana deret fibonancy sendiri.
Deret Fibonancy merupakan suatu deret yang diperoleh dari penjumlahan dua bilangan sebelumnya, dimana bilangan dasar/pokoknya adalah 0 dan 1. sehingga deret yang terbentuk adalah 0,1,1,2,3,5,8,13,21,34,….
Jika deret sudah diketahui maka proses pencarian sudah dapat dilakukan dengan langkah-langkah kegiatan sebagai berikut:
1. Menentukan nilai yang akan dicari, disimpan pada variabel X
2. Menentukan angka pertambahan, dengan rumus FK + M = N + 1
M = (N + 1) - FK
FK = Angka fibonancy terdekat dengan jumlah data
M = Nilai pertambahan
N = Jumlah data
3. Menentukan nilai fibonancy FK-1, FK-2, FK-3
4. Menyimpan nilai fibonancy dalam suatu variabel
I = FK-1
P = FK-2
Q = FK-3
5. Lakukan algoritma untuk:
Jika X > K(I) maka I = I + M, jika tidak I = I,
6. Lakukan algoritma untuk:
Apakah nilai I ≠ 0, jika tidak maka proses SELESAI dan data tidak ditemukan, jika ya maka lakukan pengulangan dengan fungsi CASE OF.
Case of :
1. X < K(I)
Jika Q = 0 maka I = 0
Jika Q ≠ 0 maka I = I - Q, t = P, P = Q, Q = t – Q
2. X = K(I)
Pencarian sukses, data ditemukan
3. X > K(I)
Jika P = 1 maka I = 0
Jika P ≠ 1 maka I = I + Q, P = P – Q, Q = Q – P
Contoh :
1. Diketahui suatu kumpulan data sebanyak 10 buah yaitu : 16,13,18,11,14,19,12,17,20,15 dan akan cari nilai 13 dengan cara teknik fibonancy
Jawab :
a. Mengurutkan data secara Ascending
11 12 13 14 15 16 17 18 19 20
b. Menentukan nilai yang dicari
X = 13
c. Menentukan deret fibonancy
0 1 1 2 3 5 8 13 21 34 55 ……
d. Menentukan angka pertambahan (M)
N = 10
FK = 8 (angka 8 pada deret fibonancy merupakan nilai yang terdekat terhadap jumlah data yang 10, sedangkan 13 menjauh dari nilai 1o)
M = (N + 1) – FK
= (10 + 1) – 8
M = 3
e. Menentukan nilai fibonancy FK-1, FK-2, FK-3
Lihat deret fibonancy :
FK-3
FK-2
FK-1
FK
0
1
1
2
3
5
8
13
21
…..
Jadi
FK = 8
FK-1 = 5
FK-2 = 3
FK-3 = 2
f. Menyimpan nilai fibonancy dalam suatu variabel
I = FK-1 = 5
P = FK-2 = 3
Q = FK-3 = 2
g. Lakukan algoritma untuk:
Apakah X > K(I)
K(I) merupakan urutan data yang ke-I
Apakah X > K(I)
Apakah X > K(5), K(5) = 15
Apakah 13 > 15, karena kondisi bernilai salah maka I = I = 5
h. Lakukan algoritma untuk:
Apakah I ≠ 0
Apakah 5 ≠ 0, maka lakukan pengulangan pada Case of
Pada Case of ada 3 pilihan yaitu : X < x =" K(I),"> K(I), karena nilai X < K(I), maka pilihan no 1 dikerjakan yaitu
Nilai I=5, P=3, Q=2, maka Q ≠ 0 sehingga I = I - Q, t = P, P = Q, Q = t - Q, yaitu:
I = I - Q = 5 - 2 = 3
t = P = 3
P = Q = 2
Q = t - Q = 3 – 2 = 1
Kembali ke langkah h .
h. Lakukan algoritma untuk:
Apakah I ≠ 0
Apakah 3 ≠ 0, maka lakukan pengulangan pada Case of
Pada Case of ada 3 pilihan yaitu : X < x =" K(I),"> K(I), karena nilai X = K(I), maka pilihan no 2 dikerjakan yaitu “Pencarian Sukses”, nilai data ditemukan.
2. Diketahui suatu kumpulan data sebanyak 10 buah yaitu : 16,13,18,11,14,19,12,17,20,15 dan akan cari nilai 17 dengan cara teknik fibonancy
Jawab :
a. Mengurutkan data secara Ascending
11 12 13 14 15 16 17 18 19 20
b. Menentukan nilai yang dicari
X = 17
c. Menentukan deret fibonancy
0 1 1 2 3 5 8 13 21 34 55 ……
d. Menentukan angka pertambahan (M)
N = 10
FK = 8 (angka 8 pada deret fibonancy merupakan nilai yang terdekat terhadap jumlah data yang 10, sedangkan 13 menjauh dari nilai 1o)
M = (N + 1) – FK
= (10 + 1) – 8
M = 3
e. Menentukan nilai fibonancy FK-1, FK-2, FK-3
Lihat deret fibonancy :
FK-3
FK-2
FK-1
FK
0
1
1
2
3
5
8
13
21
…..
Jadi
FK = 8
FK-1 = 5
FK-2 = 3
FK-3 = 2
f. Menyimpan nilai fibonancy dalam suatu variabel
I = FK-1 = 5
P = FK-2 = 3
Q = FK-3 = 2
g. Lakukan algoritma untuk:
Apakah X > K(I)
K(I) merupakan urutan data yang ke-I
Apakah X > K(I)
Apakah X > K(5), K(5) = 15
Apakah 17 > 15, karena kondisi bernilai benar maka I = I + M
I = 5 + 3 = 8.
h. Lakukan algoritma untuk:
Apakah I ≠ 0
Apakah 8 ≠ 0, maka lakukan pengulangan pada Case of
K(I) = K(8) = 18
Pada Case of ada 3 pilihan yaitu : X < x =" K(I),"> K(I), karena nilai X < K(I), X < K(8), 17 < 18 maka pilihan no 1 dikerjakan yaitu
Nilai I=8, P=3, Q=2, maka Q ≠ 1 sehingga I = I-Q, t = P, P = Q, Q = t-Q, yaitu:
I = I - Q = 8 - 2 = 6
t = 3
P = 2
Q = t - Q = 3 – 2 = 1
Kembali kelangkah h.
h. Lakukan algoritma untuk:
Apakah I ≠ 0
Apakah 6 ≠ 0, maka lakukan pengulangan pada Case of
K(6) = 16
Pada Case of ada 3 pilihan yaitu : X < x =" K(I),"> K(I), karena nilai X > K(I), X > K(6), 17 > 16 maka pilihan no 3 dikerjakan yaitu :
Nilai I=6, P=2, Q=1, maka P ≠ 0 sehingga I = I+Q, P = P-Q, Q = Q-P, yaitu:
I = I + Q = 6 - 1 = 7
P = P - Q = 2 – 1 = 1
Q = Q - P = 1 – 1 = 0
Kembali ke langkah h.
h. Lakukan algoritma untuk:
Apakah I ≠ 0
Apakah 7 ≠ 0, maka lakukan pengulangan pada Case of
K(7) = 17
Pada Case of ada 3 pilihan yaitu : X < x =" K(I),"> K(I), karena nilai X = K(I), X = K(7), 17 = 17 maka pilihan no 2 dikerjakan yaitu “Pencarian Sukses”, data ditemukan.