Rabu, Maret 31

algoritma membalik string (string reverse)

Pada artikel ini kita akan membahas mengenai algoritma “string reverse”. Misalkan diberikan suatu string ‘KOMPUTER’, dan kita ingin membalik string tersebut sehingga menjadi ‘RETUPMOK’, bagaimana algoritmanya?

Ya… secara logika untuk membalik suatu string dengan panjang karakter sejumlah n, cukup menukar posisi karakter ke – 1 dengan karakter ke-n, dan karakter ke-2 ditukar posisi dengan karakter ke n-1, dst. Sekarang yang menjadi masalah adalah… sampai berapa kali proses penukaran ini dilakukan, apakah n kali? Coba kita cek proses ini bila diterapkan pada string ‘KOMPUTER’ tsb, dalam hal ini n = 8 (panjang string 8 karakter).

Penukaran ke-1, tukar posisi karakter ke-1 dg ke-8, hasilnya ‘ROMPUTEK‘
Penukaran ke-2, tukar posisi karakter ke-2 dg ke-7, hasilnya ‘REMPUTOK’
Penukaran ke-3, tukar posisi karakter ke-3 dg ke-6, hasilnya ‘RETPUMOK’
Penukaran ke-4, tukar posisi karakter ke-4 dg ke-5, hasilnya ‘RETUPMOK’
Penukaran ke-5, tukar posisi karakter ke-5 dg ke-4, hasilnya ‘RETPUMOK’
Penukaran ke-6, tukar posisi karakter ke-6 dg ke-3, hasilnya ‘REMPUTOK’
Penukaran ke-7, tukar posisi karakter ke-7 dg ke-2, hasilnya ‘ROMPUTEK’
Penukaran ke-8, tukar posisi karakter ke-8 dg ke-1, hasilnya ‘KOMPUTER‘

Bila proses penukaran dilakukan n kali, ternyata hasil akhir string tetap kembali ke string semula. So… salah donk. Dengan demikian, kita tidak bisa menulis algoritmanya sbb:

{ x adalah string yang akan ditukar }
n := length(x); { n = panjang string }
for i = 1 to n do
begin
    //
tukar antara karakter ke-i dengan karakter ke- (n+1-i)
    temp := x[i];
    x[i] := x[n+1-i];
    x[n+1-1] := x[i];
end;

Jadi… sampai berapa kali proses penukarannya? Anda perhatikan pada proses penukaran tahap demi tahap di atas. Pada langkah berapakah stringnya menjadi ‘RETUPMOK’? Ya tepat sekali, yaitu pada langkah ke-4.

OK… dari contoh ini bisa kita catat, bahwa untuk n = 8, kita butuh 4 kali langkah penukaran. Sekarang bagaimana bila n = 10? Coba selidiki… dan ternyata butuh 5 kali penukaran. Nah… dari sini bisa kita simpulkan bahwa untuk n genap, proses penukaran yang dibutuhkan ada n/2 kali.

Sekarang bagaimana dengan n ganjil? Kita ambil contoh misal n = 7. Berapakah jumlah proses penukarannya? Coba selidiki… dan ternyata butuh 3 kali. Lho apa tidak 4 kali? Mmmm… untuk yang ke-4 boleh kita tidak lakukan karena karakter ke-4 adalah karakter yang berada di tengah string, so… gak perlu ditukar. Untuk n = 9, akan butuh 4 kali penukaran. dan seterusnya… Dengan demikian untuk n ganjil, proses penukaran yang dilakukan juga sejumlah n/2 kali, tapi n/2 di sini dibulatkan ke bawah.

Untuk n genap pun, jumlah proses penukaran karakter juga dapat diterapkan pembulatan ke bawah dari n/2, karena misal n= 8, dan hasil n/2 kalau dibulatkan ke bawah juga menghasilkan 4.

So… algoritma yang benar untuk membalik string adalah:

{ x adalah string yang akan ditukar }
n := length(x); { n = panjang string }
for i = 1 to floor(n/2) do {maksud floor adalah pembulatan ke bawah}
begin
// tukar antara karakter ke-i dengan karakter ke- (n+1-i)
temp := x[i];
x[i] := x[n+1-i];
x[n+1-1] := x[i];
end;


Nah… sekarang kita implementasikan algoritma di atas ke PHP. Bagaimana bentuk script untuk membalik string? O… iya… ingat bahwa dalam PHP, karakter pertama dari suatu string itu dimulai dari nomor indeks ke-0, sehingga harap hati-hati. Ini dia scriptnya:



<?php
$x = 'KOMPUTER';
$n = strlen($x);
for ($i = 0; $i<=floor(($n-1)/2); $i++)
{
$temp = $x[$i];
$x[$i] = $x[$n-1-$i];
$x[$n-1-$i] = $temp;
}
echo $x;
?>


dan ini dia implementasi ke dalam program Pascal:



program balikstring;

var x : string; i, n : integer; temp : char;

begin


    x := 'KOMPUTER';


    n := length(x);


    for i:=1 to trunc(n/2) do


    begin


        temp := x[i];


        x[i] := x[n+1-i];


        x[n+1-1] := x[i];


    end;


    write(x);


end.



Mmmm…. secara sekilas sih ‘kayaknya’ bisa. Tapi kalau Anda yakin jawabannya ‘bisa’, silakan buat ke dalam program algoritma tersebut dan lihatlah hasilnya. Tentu hasilnya di luar dugaan dan Anda akan dibuat tercengang dibuatnya. Kok bisa ya? :-)



Oya, satu lagi, khusus di PHP, Anda tidak perlu repot-repot membuat script untuk membalik string karena telah disediakan function khusus untuk melakukan hal itu. Function yang dimaksud adalah strrev(). Berikut ini contoh penggunaannya:



<?php
echo strrev("Hello world!"); // outputnya "!dlrow olleH"
?>


OK, met membolak balik string yaa….



Source: http://blog.rosihanari.net/algoritma-membalik-string-string-reverse

1 comments:

Anonim mengatakan...

bro maaf. saya ganti kata katanya jadi mabuk malah hasilnya kubuu? gimana ?
komputer juga jadi retuuteu. . . mohon pencerahannya gan . thx

Posting Komentar

Twitter Delicious Facebook Digg Stumbleupon Favorites More