Barisan Bilangan Fibonacci – Implementasi Fungsi Rekursif Dalam Bahasa Pascal dan C

Anda pernah melihat barisan bilangan fibonacci? Jika belum, coba lihat dibawah ini.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

Dalam tulisan kali ini, saya ingin membahas bagaimana untuk menampilkan barisan bilangan fibonacci untuk memahami salah satu ‘fitur’ dalam pemrograman yang disebut rekursi. Seperti artikel sebelumnya, saya akan membahasnya dalam bahasa Pascal dan C.

Pengertian rekursi dikutip dari wikipedia adalah sebagai berikut

“…is a method of defining functions in which the function being defined is applied within its own definition”

Implementasi fungsi rekursif biasanya diletakkan dalam suatu prosedur atau fungsi. Kali ini saya akan membahasnya dengan menuangkannya dalam sebuah fungsi. Fungsi ini didefinisikan sebagai berikut:

Nama fungsi ini adalah fib, yang menggunakan 1 parameter berupa angka dari 0 dan seterusnya.
Nilai dari fib(0) adalah 0
Nilai dari fib(1) adalah 1
Nilai dari fib(n) adalah sama dengan fib(n-1) + fib(n-2), untuk n >= 2

Bingung? Misalnya ditanyakan berapa fib(4)?

fib(n) = fib(n-1) + fib(n-2)
fib(4) = fib(3) + fib(2)
fib(3) = fib(2) + fib(1)
fib(2) = fib(1) + fib(0)

Karena fib(1) = 1 dan fib(0) = 0 (lihat definisi) maka:

fib(2) = 1 + 0 = 1
fib(3) = 1 + 1 = 2
fib(4) = 2 + 1 = 3

Bagaimana? Jadi nilai dari fib(4) adalah 3. Kini, mari kita definisikan dalam bahasa pascal.

function fib(n : integer) : integer
begin
  if (n = 0) then
    fib := 0
  else if (n = 1) then
    fib := 1
  else
    fib := fib(n-1) + fib(n-2);
end;

Untuk menguji apakah fungsi ini bisa dipakai atau belum, mari kita mulai blok utama untuk menampilkan nilai dari fungsi fib(0) sampai fib(10)

var i : integer;

{letakkan deklarasi fungsi disini}

begin
  for i := 0 to 10 do
    write(fib(i), ' ');
end.

Silakan uji outputnya. Kurang lebih akan seperti ini outputnya.

0 1 1 2 3 5 8 13 21 34 55

Nah, ini salinan program lengkapnya dalam bahasa Pascal

var
  i : integer;

function fib(n : integer) : integer;
begin
  if (n = 0) then
    fib := 0
  else if (n = 1) then
    fib := 1
  else
    fib := fib(n-1) + fib(n-2);
end;

begin
  for i := 0 to 10 do
    write(fib(i), ' ');
end.

Juga, ini salinan program lengkapnya dalam bahasa C

#include <stdio.h>;

int fib(int n);

int main() {
  int i = 0;

  while (i <= 10) {
    printf("%i ", fib(i));
    i++;
  }
}

int fib(int n) {
  if (n == 0) {
    return 0;
  } else  if (n == 1) {
    return 1;
  } else {
    return fib(n-1) + fib(n-2);
  }
}

Semoga bermanfaat.

Advertisements

Sieve of Eratosthenes – Metode untuk Mengidentifikasi Bilangan Prima

Dalam kompetisi informatika, seperti Olimpiade Komputer di Indonesia, kasus problem solving yang melibatkan bilangan prima sering muncul, dari yang sederhana, hingga kasus yang kompleks. Tulisan ini membahas algoritma Sieve of Eratosthenes untuk mengidentifikasi bilangan prima, yang nantinya dapat diimplementasikan untuk kasus problem solving yang lebih kompleks. Untuk hal itu, saya akan mengimplementasikan algoritma ini dalam bahasa Pascal dan C.

Ini adalah kutipan wikipedia.org untuk algoritma Sieve of Erathosthenes (lihat http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes)

A prime number is a natural number which has exactly two distinct natural number divisors: 1 and itself.
To find all the prime numbers less than or equal to a given integer n by Eratosthenes’ method:

  1. Create a list of consecutive integers from two to n: (2, 3, 4, …, n).
  2. Initially, let p equal 2, the first prime number.
  3. Strike from the list all multiples of p less than or equal to n. (2p, 3p, 4p, etc.)
  4. Find the first number remaining on the list after p (this number is the next prime); replace p with this number.
  5. Repeat steps 3 and 4 until p2 is greater than n.
  6. All the remaining numbers in the list are prime.

Oke, mari kita langsung ke implementasi program dalam bahasa Pascal (saya merekomendasikan Anda untuk men-download Free Pascal dari http://www.freepascal.org/ yang saat saya menggunakannya, sudah memasuki versi 2.4)

const
    N = 1024;

Pertama, kita siapkan dulu larik (array) 1 dimensi. Untuk kasus ini, saya hanya memberikan contoh untuk bilangan prima dalam rentang 1..1024.

var sieve: array[1..N] of integer;

Siapkan juga 2 buah variabel untuk iterator

    i, p : integer;

Nah, kita mulai implementasinya. Pertama, kita ikuti langkah yang didefinisikan di atas. Siapkan isi variabel p dengan 2, kemudian siapkan variabel n yang menampung nilai 2, 3, 4, …, n. Dalam kasus ini, saya akan menggunakan variabel i sebagai penggantinya.

begin
    p := 2;

Langkah ke-3, kita hilangkan semua hasil kali p dengan setiap nilai i. Dalam kasus ini, saya batasi N = 1024, yang berarti i = {2, 3, …, 1024)

    while (p * p <= N) do begin
        i := 2;

        while (p * i <= N) do begin
            sieve[p * i] := -1;
            inc(i);
        end;

Langkah ke-4, isikan nilai p dengan angka prima selanjutnya, implementasinya:

        inc(p);
        while (sieve[p] = -1) do
            inc(p);
    end;

Untuk tambahan, karena dalam operasi larik (array) ini kita tidak menyenggol bilangan ke-1 (ingat bahwa 1 bukan bilangan prima) sekalipun, tambahkan kode ini untuk melengkapi.

    sieve[1] := -1;

Nah, secara otomatis, karena kita sudah menggunakan blok while, langkah ke 5 dan 6 telah ter-cover dengan baik. Jadi, apa hasil yang kita dapatkan? Kita memiliki suatu array bernama sieve, yang telah disaring, sedemikian sehingga jika suatu elemen (misalnya elemen ke-i) adalah bilangan prima, maka nilai dari elemen ke-i tersebut adalah 0. Jika bukan merupakan bilangan prima, maka isi elemen tersebut adalah -1. Untuk menguji, kita bisa tampilkan seluruh bilangan prima yang telah tertampung di dalam larik (array) tersebut.

    for i := 1 to N do
        if (sieve[i] = 0) then writeln(i);

Dengan demikian, selesailah teknik Sieve of Eratosthenes. Implementasi dari algoritma di atas dapat diterapkan untuk pemecahan masalah pemrograman yang lain.

Ini salinan program lengkapnya dalam Bahasa Pascal.

const
    N = 1024;

var
    sieve : array[1..N] of integer;
    i, p  : integer;

begin
    p := 2;

    while (p * p <= N) do begin
        i := 2;

        while (p * i <= N) do begin
            sieve[p * i] := -1;
            inc(i);
        end;

        inc(p);
        while (sieve[p] = -1) do
            inc(p);
    end;

    for i := 1 to N do
        if (sieve[i] = 0) then writeln(i);

end.

Untuk bahasa C, berikut implementasinya (mohon diperhatikan, karena implementasi array dalam bahasa C, indeks pertama dimulai dari 0, bukan dari 1 seperti pada bahasa Pascal)

#include <stdio.h>

const int N = 1024;

int main() {
    int sieve[1024] = {0};

    int p = 2;

    while (p * p <= N) {
        int i = 2;

        while (p * i <= N) {
            sieve[p * i -1] = -1;
            i++;
        }

        p++;
        while (sieve[p-1] == -1) {
            p++;
        }
    }

    sieve[0] = -1;

    int i;

    for (i = 0; i < N; i++) {
        if (sieve[i] == 0)
            printf("%i\n", i+1);
    }

    return 0;
}

Semoga bermanfaat.

Catatan:
Karena saya masih pemula, barangkali, kode-kode di atas ada yang salah. Mohon segera comment artikel ini jika ada yang keliru agar saya bisa memperbaikinya. Kontribusi Anda akan sangat membantu. Terima kasih.

Penulis bisa ditanya-tanyai di imam.hidayat92@gmail.com

Jogjakarta – Sebuah Rekaman Perjalanan

Asal Anda tahu pembaca yang saya hormati, saya menulis ini dengan kaki yang rasanya seperti remuk!! Saya pulang dari Taman Pintar sekitar pukul 16.00, dan baru sampai rumah sekitar pukul 19.30. Trans Jogja telah berhasil menghilangkan tenaga saya. Dengan transit 4 kali akibat ditutupnya jalan karena event Muktamar Muhammadiyah, saya dianugerahi duduk 2 kali dalam waktu singkat dan sisanya berdiri.

Maaf-maaf. Ini melenceng. Tentu bukan ini yang hendak saya bagikan. 😀

Malioboro

Pukul 11.00 hari ini, saya berangkat ke Malioboro, sebuah tempat yang saya rasa tidak ada orang yang tidak tahu dengan nama ini.

Saat saya berjalan mengelilingi hot spot bagi turis ini, saya menemukan beberapa fenomena yang (menurut saya) menarik. Ini yang saya temukan di sana:

Fenomena Emansipasi

Anda tahu tukang ojek? Ya, keliling mengantarkan orang dengan motor. Siapa yang biasanya jadi tukang ojek? Laki-laki. Oke. Silakan lihat gambar di bawah ini.

Emansipasi

Emansipasi, hidup sekali ternyata. Tukang ojek, perempuan. Saya baru pertama kali melihatnya langsung, dan saya sangat tertarik.

Kalau saya perhatikan, usia dari perempuan-perempuan hebat ini masih muda. Barangkali masih mahasiswa. Andai saya punya keberanian untuk bertanya kepada mereka, tentang motivasi mereka. Sayangnya, saya tidak berani. 🙂

Tuna Netra, Kreatif

Kebutaan, mungkin adalah sebuah skak mat (mungkin) bagi beberapa dari kita. Tapi, tidak untuk mereka.

Duet romantis 🙂

Salah satu dari tuna netra yang saya temui, berduet dipinggiran mall, dengan percaya diri. Mereka berdua sama, tidak bisa melihat. Tapi, mereka berani, demi mendapatkan nafkah. Aksi mereka cukup menarik perhatian. Mereka berbakat, itu pasti.

Instrumen merdu, dari maestro yang tak melihat.

Satu lagi, tuna netra yang bermain angklung dipinggiran hotel. Suaranya sungguh merdu. Andai saya punya perekam. Saya akan bagikan untuk Anda.

Mereka memberi saya pelajaran yang sangat berharga: TIDAK ADA KATA MENYERAH! SEMUA RINTANGAN, PASTI BISA DIATASI!

Globalisasi di Pasar Tradisional

Salah satu pengaruh globalisasi, adalah merambahnya bahasa non-nasional yang diakui internasional. Bahasa apa? Jelas: Bahasa Inggris. Penguasaan bahasa ini sekarang bukan hal baru, bahkan mutlak perlu.

Apakah Anda cukup percaya diri untuk berbicara dengan foreign people? Jujur, saya sendiri belum berani. Tapi, bapak ini tidak.

Saya terkesima, dengan kehebatan bapak ini. Bapak ini adalah seorang penjual pakaian biasa. Namun, fasih sekali ber-Bahasa Inggris. Orang asing itupun tidak terlihat kesulitan memahami bahasa bapak ini. Sungguh menarik.

Pedagang pasar tradisional, berbicara bahasa asing.

Usia, bukan masalah

Di atas tadi, ada duet romantis. Hal yang satu inipun tidak jauh berbeda.

Usia, ataupun kendala lainnya, bukan penghalang untuk tetap 'berjalan'

Sepasang ini (mudah-mudahan tidak salah) cukup menarik. Kendati sang ibu harus berjalan di atas kursi roda, namun tetap sang ayah setia menemaninya belanja. Sebuah bentuk kesetiaan yang mengharukan.

Untuk Pariwisata Bengkulu

Saya berkesempatan juga untuk mengunjungi salah satu situs sejarah, Benteng Vrederburg. Orang Jogja, tidak hanya mengandalkan peninggalan sejarah ini saja. Mereka menambahinya dengan kreasi mereka. Salah satunya, di sana digelar FKY (Festival Kesenian Yogyakarta), yang menampilkan seluruh kekayaan budaya yang mereka miliki dalam bentuk stan-stan kecil.

Berbeda sekali dengan Benteng Marlborough di Bengkulu. Saya rasa, sudah sewajarnya Pemerintah Bengkulu belajar dari Jogja. Toh, istilah kota pelajar juga asal mulanya telah dimiliki terlebih dahulu di kota tersebut. Semoga, lewat pilkada tahun ini, ada perbaikan untuk hal ini. 🙂

Saya memang penggemar hal-hal sepele. Mudah-mudahan catatan ini tidak terlalu norak. Silakan berkomentar 🙂