Archive

Archive for the ‘Algorithm’ Category

Deret Bilangan Fibonacci Non-Rekursif

January 30, 2010 4 comments
Seperti sudah dibahas sebelumnya, deret bilangan Fibonacci adalah deret yang setiap sukunya dihasilkan dari penjumlahan dua suku sebelumnya. Jadi misalkan dua angka sebelumnya angka 0 dan 1, maka deret berikutnya adalah 0 + 1 = 1. Banyak sekali kegunaan dari bilangan fibonacci ini.
Dalam matematika, deret fibonacci didefinisikan sebagai berikut:

F(n) = F(n-1) + F(n-2)
F(0) = 0
F(1) = 1

Berbeda dengan sebelumnya, sekarang implementasi definisi matematika tadi akan kita terapkan dengan looping dengan algoritma yang lebih dinamis karena nilai setiap variabelnya akan terus selalu berubah sampai suatu kondisi yang ditentukan. Algoritmanya adalah seperti di bawah ini :

function Fibonacci (input n:integer) → integer
{fungsi untuk mencari deretan sebuah bilangan fibonacci}
kamus :
   i, a, b : integer
algoritma :
   a = 0
   b = 1
   for i = 1 to n do
      a = a + b
      b = a - b
   endfor
   Fibonacci ← a

Algoritma ini lebih susah dimengerti memang kelihatannya, tapi jika kita lihat lagi algoritma ini memiliki langkah pencarian yang lebih pendek daripada algoritma yang rekursif, jadi lebih efesien.

Categories: Algorithm Tags:

Deret Bilangan Fibonacci Rekursif

January 30, 2010 2 comments
Deret bilangan Fibonacci adalah deret yang setiap sukunya dihasilkan dari penjumlahan dua suku sebelumnya. Jadi misalkan dua angka sebelumnya angka 0 dan 1, maka deret berikutnya adalah 0 + 1 = 1. Banyak sekali kegunaan dari bilangan fibonacci ini.
Dalam matematika, deret fibonacci didefinisikan sebagai berikut:

F(n) = F(n-1) + F(n-2)
F(0) = 0
F(1) = 1

Dari definisi di atas cukup menjelaskan bagaimana bilangan fibonacci itu sebenarnya. Dalam dunia komputer dapat kita buat algoritmanya seperti berikut :

function Fibonacci (input n:integer) → integer
{fungsi untuk mencari deretan sebuah bilangan fibonacci}
algoritma :
   if n = 0 then
      Fibonacci ← 0
   else
      if n = 1 then
         Fibonacci ← 1
      else
         Fibonacci ← Fibonacci(n-1)+Fibonacci(n-2)
      endif
   endif

Algoritma ini sangat sederhana dan kelihatannya mudah dimengerti, tapi setelah coba dijalankan algoritma ini akan memberatkan kita karena resource yang diperlukannya sangat besar dan lama pula.

Categories: Algorithm Tags:

Rekursif

January 12, 2010 Leave a comment

Definisi rekursif adalah definisi yang menggunakan konsep atau sebagian dari definisi tersebut menjadi definisi yang komplit.

Misalnya : “keturunan” bisa berarti anak atau keturunan dari anak. “Kalimat” bisa berarti dua kalimat yang digabung dengan kata hubung “dan”. “Direktori” adalah bagian pada hard disk yang berisi file dan direktori. Dalam matematika, “himpunan” adalah koleksi elemen, di mana elemen tersebut bisa berupa himpunan. “Pernyataan” pada Java misalnya pernyataan while yang didalamnya terdapat kata while, kondisi bernilai boolean dan pernyataan lainnya.

Rekursif bisa digunakan dalam teknik pemrograman. Subrutin rekursif adalah subrutin yang memanggil dirinya sendiri, baik langsung maupun tak langsung. Subrutin tersebut memanggil dirinya sendiri secara tidak langsung yaitu jika ia memanggil subrutin lain yang akhirnya memanggil subrutin pertama (baik langsung maupun tak langsung).

Ada algoritma sederhana yang bisa digunakan untuk mencari suatu item pada array : Lihat setiap array, dan cek apakah isinya sama dengan item yang kita cari. Jika ketemu, maka pencarian selesai. Jika kita sudah melihat semua item dan tidak ada item yang sama, maka kita yakin bahwa item yang kita cari tidak ada dalam array.

Subrutin untuk mengimplementasikan algoritma tersebut mudah kita tulis. Misalnya array yang kita cari bertipe int[]. Berikut ini adalah metode untuk mencari integer tertentu dalam array. Jika integer ditemukan, maka metode ini akan mengembalikan indeks dalam array di mana item tersebut ditemukan. Jika integer tersebut tidak ada dalam array, maka metode tersebut akan mengembalikan nilai -1, yang artinya integer tersebut tidak ditemukan.

static int cari(int[] A, int N) {
    for (int indeks = 0; indeks < A.length; indeks++) {
        if ( A[indeks] == N )
            return indeks;
    }
    return -1;
}

Metode seperti ini dimana pencarian dilakukan dengan menguji setiap item disebut pencarian linier (linear search). Jika kita tidak mengetahui apa-apa tentang isi dan urutan item pada array, maka tidak ada lagi algoritma alternatif yang lebih baik dari ini. Akan tetapi jika kita tahu bahwa elemen di dalam array diurut dalam urutan menaik atau urutan menurun, maka kita bisa menggunakan algoritma lain yang lebih cepat. Tentu saja, waktu yang dibutuhkan untuk mengurutkan array tidak sebentar, akan tetapi jika array ini akan dicari berulang kali, maka waktu pengurutan array akan terbayarkan dengan cepat.

Caranya adalah dengan mengecek elemen di tengah list tersebut. Jika elemen tersebut sama dengan nilai yang dicari, maka pencarian tersebut selesai. Jika nilai yang dicari lebih kecil daripada nilai elemen di tengah list tersebut, maka kita harus mencari di separuh awal dari list tersebut. Jika lebih besar, kita harus mencari di separuh akhir list tersebut. Kemudian, pada separuh list yang kita pilih tersebut, kita akan mengecek kembali elemen tengahnya. Kita akan melihat kembali apakah nilainya sama dengan nilai yang kita cari, lebih besar atau lebih kecil, yang dari sini kita tahu paruh mana yang akan kita cari berikutnya. Dan begitu seterusnya, hingga besar list yang akan dicari berkurang menjadi 0.

Ini adalah definisi rekursif, dan kita bisa membuat subrutin rekursif untuk mengimplementasikannya.

Source : Belajar Java

Categories: Algorithm Tags:

Selection Sort

January 8, 2010 1 comment

Selection sort merupakan kombinasi dari searching dan sorting. Sebuah algoritma pengurutan yang secara berulang mencari item yang belum terurut dan mencari paling sedikit satu untuk dimasukkan ke dalam lokasi akhir. Metode ini memiliki konsep memilih data yang maksimum/minimum dari suatu kumpulan data larik L, lalu menempatkan data tersebut ke elemen paling akhir atau paling awal sesuai pengurutan yang diinginkan. Data maksimum/minimum yang diperoleh, diasingkan ke tempat lain, dan tidak diikutsertakan pada proses pencarian data maksimum/minimum berikutnya.

Algoritma pengurutan selection sort ini termasuk algoritma sulit dibagi/ mudah digabung (hard split/easy join).  Dari proses pengurutannya, Selection sort ini memiliki dua buah varian yaitu :

1. Maximum Sort

memilih data yang maksimum dari suatu kumpulan data larik, lalu menempatkan data tersebut ke elemen paling akhir atau paling awal sesuai pengurutan yang diinginkan. Data maksimum/minimum yang diperoleh, “diisolasi” dan tidak diikutsertakan pada proses pencarian data maksimum berikutnya.

2. Minimum Sort

memilih data yang minimum dari suatu kumpulan data larik , lalu menempatkan data tersebut ke elemen paling akhir atau paling awal sesuai pengurutan yang diinginkan. Data minimum yang diperoleh, “diisolasi” dan tidak diikutsertakan pada proses pencarian data minimum berikutnya.

Dalam pemecahan masalah algoritma selection sort , kita dapat memilih dua metode alternatif algoritma antara lain pemecahan dengan metode Brute Force dan pemecahan dengan metode devide and conquer.

Metode Pemecahan Brute Force

Kekuatan algoritma brute force terletak pada kemampuannya untuk menemukan semua pemecahan masalah yang mungkin, akan tetapi langkah yang dibutuhkan sangat banyak sehingga tidak baik jika digunakan untuk memecahkan masalah yang memiliki masukan yang cukup besar. Mengurutkan secara ascending dengan metode brute force

procedure SelectionSort(input/output L[1..N]: array of integer)
{Mengurutkan larik L[1..N] sehingga terurut menaik dengan metode selection sort. Asumsi : nilai N (jumlah elemen array) diketahui dan elemen larik L sudah terdefinisi nilainya }

Kamus
   i,j : integer
   temp : integer {temporary}
   Imaks : integer {indeks yang berisi nilai maks sementara}

Algoritma
   for i = n downto 2 do</p>
      Imaks ← i
      {elemen terakhir diasumsikan sebagai elemen maksimum sementara}
      for j = 1 to (i-1)
         if L[j] > L[Imaks] then
            Imaks ← j
         endif
      endfor
      {pertukaran L[i] dengan L[Imaks]</p>
      If L[i] <> L[Imaks] then
         temp ← L[i]
         L[i] ← L[Imaks]
         L[Imaks]  ← temp
      endif
   endfor

Run dari Procedure selection sort ascending :

Misalkan diberikan contoh Larik seperti berikut , perintah dari soal adalah mengurutkan larik berisi elemen-elemen acak berikut sehingga menjadi terurut menaik (ascending) menggunakan metode brute force dengan algoritma selection sort :

Cari elemen maksimum dari larik dengan perulangan. Lalu didapat hasilnya maks = 9 pada elemen ke-3 dari larik , tukarkan elemen maksimum dengan elemen terakhir pada larik yaitu ke-6 .  Selanjutnya lakukan perulangan mencari nilai maksimum, namun elemen terakhir tidak perlu di cek kembali. Cukup larik 1 – 5 saja yang dicek . akan didapat nilai maksimum 8, karena ia telah berada diposisi no 2 terakhir, jadi ia tidak perlu dipindah lagi sampai akhirnya semua elemen maksimum telah ditukar posisinya dan semuanya terurut secara ascending.

Simulasi :

Masalah

5

7

9

1

8

2

Iterasi 1

5

7

2

1

8

9

Iterasi 2

5

7

2

1

8

9

Iterasi 3

5

1

2

7

8

9

Iterasi 4

2

1

5

7

8

9

Iterasi 5

1

2

5

7

8

9

Terurut

procedure SelectionSort (input/output L[1..N]: array of integer)

{Mengurutkan larik L[1..N] sehingga terurut menaik dengan metode selection sort.

Asumsi : nilai N (jumlah elemen array) diketahui dan elemen larik L sudah terdefinisi nilainya }

Kamus

i,j : integer

temp : integer {temporary}

Imaks : integer {indeks yang berisi nilai maks sementara}

Algoritma

for i = n downto 2 do

Imaks ← i {elemen terakhir diasumsikan sebagai elemen maksimum sementara}

for j = 1 to (i-1) do

if L[j] > L[Imaks]then

Imaks ← j

endif

endfor

{pertukaran L[i] dengan L[Imaks]

If L[i] <> L[Imaks] then

temp ← L[i]

L[i] ← L[Imaks]

L[Imaks] ← temp

endif

endfor

Categories: Algorithm Tags: