Arsip

Archive for the ‘Olimpiade Komputer’ Category

ROSEDUR dan FUNGSI REKURSIF

April 12, 2010 2 komentar

di copy dari http://www.khabib.staff.ugm.ac.id

Prosedur dan fungsi merupakan sub program yang sangat bermanfaat dalam pemrograman, terutama untuk program atau proyek yang besar. Manfaat penggunaan sub program antara lain adalah :
Prosedur dan fungsi merupakan sub program yang sangat bermanfaat dalam pemrograman, terutama untuk program atau proyek yang besar. Manfaat penggunaan sub program antara lain adalah :

  1. meningkatkan readibility, yaitu mempermudah pembacaan program
  2. meningkatkan modularity, yaitu memecah sesuatu yang besar menjadi modul-modul atau bagian-bagian yang lebih kecil sesuai dengan fungsinya, sehingga mempermudah pengecekan, testing dan lokalisasi kesalahan.
  3. meningkatkan reusability, yaitu suatu sub program dapat dipakai berulang kali dengan hanya memanggil sub program tersebut tanpa menuliskan perintah-perintah yang semestinya diulang-ulang.

adalah Dengan melihat sifat sub program rekursif di atas maka sub program rekursif harus memiliki :

  1. kondisi yang menyebabkan pemanggilan dirinya berhenti (disebut kondisi khusus atau special condition)
  2. pemanggilan diri sub program (yaitu bila kondisi khusus tidak dipenuhi)

Secara umum bentuk dari sub program rekursif memiliki statemen kondisional :

if kondisi khusus tak dipenuhi
then panggil diri-sendiri dengan parameter yang sesuai
else lakukan instruksi yang akan dieksekusi bila kondisi khusus dipenuhi

Sub program rekursif umumnya dipakai untuk permasalahan yang memiliki langkah penyelesaian yang terpola atau langkah-langkah yang teratur. Bila kita memiliki suatu permasalahan dan kita mengetahui algoritma penyelesaiannya, kadang-kadang sub program rekursif menjadi pilihan kita bila memang memungkinkan untuk dipergunakan. Secara algoritmis (dari segi algoritma, yaitu bila kita mempertimbangkan penggunaan memori, waktu eksekusi sub program) sub program rekursif sering bersifat tidak efisien .
Dengan demikian sub program rekursif umumnya memiliki efisiensi dalam penulisan perintah, tetapi kadang tidak efisien secara algoritmis. Meskipun demikian banyak pula permasalahan-permasalahan yang lebih sesuai diselesaikan dengan cara rekursif (misalnya dalam pencarian / searching, yang akan dibahas pada pertemuan-pertemuan yang akan datang).

Contoh sub program rekursif dalam bahasa Pascal.

  1. Contoh sederhana

  2. PROCEDURE TULIS_1(banyak : integer;kata : string);
    begin
    if banyak > 1 then TULIS_1(banyak-1,kata);
    writeln(kata, banyak:5);
    end;

    OUTPUT (misal dipanggil dengan TULIS_1(5,”Cetakan ke “))

    Cetakan ke 1
    Cetakan ke 2
    Cetakan ke 3
    Cetakan ke 4
    Cetakan ke 5

    Bandingkan prosedur dan outputnya di atas dengan prosedur di bawah ini!PROCEDURE TULIS_2(banyak :

    integer;kata : string);
    begin
    writeln(kata, banyak:5);
    if banyak > 1 then TULIS_1(banyak-1,kata);
    end;

    OUTPUT (misal dipanggil dengan TULIS_2(5,”Cetakan ke “))Cetakan ke 5
    Cetakan ke 4
    Cetakan ke 3
    Cetakan ke 2
    Cetakan ke 1

    Mengapa hasilnya jauh berbeda?

  3. Contoh terapan

Secara matematis, perkalian dua bilangan bulat positif a dengan b (ditulis ab atau a x b) pada hakekatnya merupakan penjumlahan dari a sebanyak b suku, yaitu a + a + a + …. + a sebanyak b suku. Misalnya 2 x 3 dapat diartikan sebagai 2 + 2 + 2 = 6 , yaitu penjumlahan 2 sebanyak 3 suku   Dengan mengingat bahwa suatu bilangan bila dikalikan dengan angka 1 (satu) akan menghasilkan bilangan itu sendiri, maka permasalahan perkalian dengan menyatakannya dalam bentuk penjumlahan di atas dapat diselesaikan dengan komputer secara mudah.

Dengan non rekursif

  1. Dengan prosedur
      Procedure KALI_BIASA_P(a,b : integer; var hasil : longint);
      var i : integer;
      begin
      hasil := 0;
      for i:= 1 to b do hasil := hasil + a;
      end;
  2. Dengan fungsi
    Function KALI_BIASA_F(a,b:integer):longint;
    var hasil : longint; i: integer;
    begin
    hasil := 0;
    for i:= 1 to b do hasil := hasil + a;
    KALI_BIASA_F := hasil;

    end;

Dengan Rekursif

  1. Dengan Prosedur
      Procedure KALI_REK_P(a,b:integer;var hasil:longint)
      begin
      if b>1 then KALI_REK_P(a,b-1,hasil);
      hasil:= hasil+a;
      end;
  2. Dengan Fungsi
    Function KALI_REK_F(a,b:integer):longint;
    begin
    if b>1 then
    KALI_REK_F := KALI_REK_F(a,b-1)+a
    else
    KALI_REK_F := a;
    end;

Untuk lebih memahami materi bisa di download disini

Iklan

Soal Olimpiade Komputer Function 1

April 11, 2010 3 komentar

Perhatikan algoritma berikut:
function ABC (a, b : integer) : integer;
var
hasil : integer;
begin
if (a mod b = 0) then ABC := b
else ABC := ABC(a, b-1);
end;
Berapakah hasil ABC(12, 4)?

Pembahasan

Fungsi ABC mengembalikan nilai b jika a merupakan kelipatan b (a mod b = 0). Jika b bukan faktor dari a, maka fungsi ini akan memanggil dirinya kembali dengan parameter ABC(a,b‐1). Tampak bahwa fungsi ABC akan mengembaikan nilai faktor terbesar dari a yang kurang dari atau sama dengan b. Maka hasil ABC(12,4) adalah 4.

Untuk lebih memahami silahkan download disini

Soal Olimpiade Komputer Procedure 2

April 11, 2010 1 komentar

Perhatikan algoritma berikut:

Procedure geser(i: integer);
begin
i := (((i shl 4) shr 6) shl 2);
writeln(i);
end;
Apakah output dari pemanggilan geser(9) di atas?

Pembahasan

i = 910 = 10012
i shl 4 = 100100002
(i shl 4)shr 6 = 102
((i shl 4)shr 6)shl 2 = 10002 = 810

Jadi output program diatas adalah 8

Untuk lebih mengerti silahkan download disini

Contoh Soal Olimpiade Komputer Pascal

April 11, 2010 11 komentar

Diberikan penggalan program berikut :

procedure jalan(n: integer);
begin
if n > 0 then begin
jalan(n div 5);
write(n mod 5 + 1);
end;
end;

Pada pemanggilan jalan(49) pada procedure di atas ini apa yang akan dicetaknya kemudian?

Pembahasan

perhatian dengan baik program tersebut, jika nilai n tersebut lebih besar dari nol maka statmen dibawahnya akan di jalankan. karena terdapat begin … end  di bawahnya jadi 2 statmen di antara begin .. end akan di jalankan.

begin
jalan(n div 5);
write(n mod 5 + 1);
end;

jalan(49) :
– jalan(9)
‐ jalan(1)
‐ jalan(0)
‐ write(2)
‐ write(5)
– write(5)

Jadi, yang akan tercetak adalah 255

untuk lebih memahami silahkan download disini

Penentuan Bilangan Awal Pangkat Banyak

untuk mampu dalam memecahakan masalah untuk soal mengetahui digit awal atau akhir, tentunya kita harus terbiasa dengan sifat-sifat bilangan pangkat!

berikut beberapa sifat pangkat :

a p x a q = a p+q

(a x b)p = a p x b p

a p : a q = a p-q

a 0 = 1

(a p) q = a pxq

a –p = 1 / a p

Contoh soal sebagai berikut

Jumlah dua digit pertama dari bilangan hasil perkalian

5 30003 x 8 10004 Adalah…

Pembahasan

Untuk memecahkan soal seperti diatas mencari digit pertama, kita harus sederhanakan bentuk pangkat tersebut agar menjadi bilangan tertentu di kaliakan 10 pangkat banyak.

lebih jelasnya mari kita sederhanakan :

5 30003 x 8 10004 =  5 30003 x (23) 10004

= 5 30003 x 23×10004

= 5 30003 x 230012

= 5 30003 x 230003 +9

= 5 30003 x 230003 x 29

= (5 x 2)30003 x 29

= 1030003 x 29

= 29 x 1030003

= 512 x 1030003

perlu di ingat berapapun 10 dipangkatkan dari 1 sampai n hasilnya nol ke n dibelakangnya

ex :

103 = 1000

jadi jumlah dua digit pertama adalah 5 + 1 = 6.

bisa di download disini

Jumlah dua digit pertama dari bilangan hasil perkalian 5 30003 x 8 10004 Adalah…

Struktur Dan Komponen Dasar Program Pascal.

April 28, 2008 14 komentar

            Struktur program Pascal terdiri dari sebuah judul program dan  badan program. Badan program dibagi lagi menjadi dua bagian, bagian deklarasi dan bagian pernyataan (statement).

 

Struktur program :

 

Judul Program                          PROGRAM nama-program;

Blok Program  

Bagian deklarasi

deklarasi label                           LABEL nama-label;

deklarasi konstanta                   CONST…………..;

deklarasi tipe                            TYPE …………….;

deklarasi variabel                      VAR ………………;

deklarasi prosedur                    PROCEDURE nama-prosedur;

                                                ……………………………….;

deklarasi fungsi                         FUNCTION nama-fungsi;

                                                ………………………….;

Bagian Pernyataan                   

Begin

      (statement)                        

      …………;

      …………;

end.

 

 

Contoh :  Menghitung perkalian dua bilangan bulat

 

PROGRAM Perkalian;                                     {Judul}

VAR A,B,Hasil            : Integer;                       {Deklarasi variabel}

BEGIN

            A := 2;                                                 {Statemant}

            B := 3;                                                  {Statemant}

            Hasil := A*B;                                       {Statement}

            Writeln (A,B,Hasil);                              {Statement}

END.

 

 

Judul program sifatnya adalah optional, dan bila ditulis, harus terletak pada awal dari program dan diakhiri dengan titik koma.

Bagian deklarasi digunakan bila di dalam program digunakan pengenal ( identifier). Identifier dapat berupa label, konstanta, tipe, variabel, prosedur dan fungsi. Kalau suatu program menggunakan identifier, Pascal menuntut supaya identifier tersebut diperkenalkan terlebih dahulu sebelum digunakan, yaitu dideklarasikan terlebih dahulu pada bagian ini.

Beberapa aturan dalam program Pascal :

 

·        Akhir sebuah program Pascal ditandai dengan tanda baca titik ‘ . ‘ setelah END yang  paling akhir.

·        Tanda titik koma ‘ ; ‘ merupakan pemisah antar instruksi satu dengan lainnya.

·        Beberapa statement boleh ditulis menjadi satu baris dipisahkan dengan tanda baca titk koma ‘ ; ‘

·        Baris komentar diletakkan diantara tanda ‘(*’ dan   ‘*)’ atau diantara tanda ‘{‘ dan ‘}’

Contoh :     Var      a   : real;                (*nilai bilangan pertama*)

                              b : real;                {nilai bilangan kedua}      

 

Statement  (pernyataan)

            Adalah instruksi atau gabungan instruksi, yang menyebabkan komputer melakukan aksi.

 

Type statement dalam Pascal terdiri atas :

 

1.      Sederhana :

– menandai sebuah item data ke sebuah variabel (assigment statement)

            contoh : c := b * 4

         pemanggilan procedure dan goto statement

 

2.      Terstruktur:

– Compound Statement

            contoh : Begin

                                    read (x) ;

                                    y := x * 2;

                                    write (y)

                          End.

      – Repetitive Statement

            contoh :            For j := 1 to 10 do

                                    write (count);

     – Conditional Statement

            contoh :            If x > 10 then write (a)

                                                else write (b) ;

 

 

Komponen Dasar Program Pascal

 

Pola susun bahasa Pascal dibentuk dengan menggunakan komponen bahasa pemrograman yang umum, yaitu :

1.      Simbol Dasar

2.      Reserved Word (kata pasti)

3.      Identifier (penyebut)

      1.      Simbol Dasar.

Simbol dasar terdiri atas :

1.      Simbol huruf, yaitu huruf A sampai dengan Z atau a sampai dengan z.

(huruf besar dan kecil).

2.      Simbol angka atau digit yaitu : 0,1,2,3,4,5,6,7,8,9.

3.      Simbol khusus, yaitu

{  }   ( )   [   ]+      *   /   ;   :=   ,      =   <   >   <=   >=   <>   :  

 

      2.      Reserved Word (kata pasti)

Reserved Word adalah suatu kata yang secara mutlak tidak boleh diartikan lain dan harus digunakan sebagaimana yang telah didefinisikan atau ditentukan kegunaanya oleh bahasa Pascal. Reserved word tidak dapat dipergunakan sebagai pengenal (identifier)

 

 

3.      Identifier (sebutan/pengenal)

Identifier merupakan sebuah kata yang digunakan sebagai nama atau sebutan terhadap sesuatu didalam program. Pemakai dapat mendefinisikan sendiri suatu nama sebagai identifier.

 

Identifier ini terdiri atas :

 

1.      Identifier Standar, yaitu identifier yang telah didefinisikan oleh bahasa pascal.

Contoh dari Identifier standar ini antara lain:

ABS                             LN

ARCTAN                    ODB

BOOLEAN                 PRED

CHAR                         ROUND

CHR                            READ

COS                            READLN

EOF                             SQR

EOLN                          SQRT

EXP                             SUCC

            Dan masih banyak lagi.

 

2.      Identifier Non Standar; yaitu identifier yang didefinisikan oleh pemakai bahasa pascal; misalnya;

      3.   Nama suatu program

      4.   Nama suatu konstanta

      5.   Nama suatu variabel

      6.   Nama suatu procedure

Identifier ini bebas, tetapi dengan ketentuan-ketentuan sebagai berikut :

7.   terdiri dari gabungan huruf dan angka dengan karakter pertama harus berupa huruf. Huruf besar dan huruf kecil dianggap sama.

8.      Tidak boleh mengandung blank.

9.      Tidak boleh mengandung simbol-simbol khusus, kecuali garis bawah.

10.  Panjangnya bebas, tetapi hanya 63 karakter pertama yang dianggap signifikan.

 

Contoh :

 

Identifier

Keterangan

NasiBungkus

Benar

Belajar_Pascal

Benar

NO2

Benar

1_dua

Salah, karakter pertama harus huruf

Andi&tono

Salah, tidak boleh mengandung simbol khusus

Penjuanglan bar

Salah, tidak boleh mengandung spasi

 

Contoh Soal Olimpiade Komputer materi WHILE DO

April 9, 2008 30 komentar

potongan prgram dibawah untuk soal 1 -2

c := 0
d := 0
while (a>b) do
begin
a := a – b;
c := c + 1;
d := d + b;
end;
write(c,’,’,d);

1. jika nilai  a = 15, b = 4 maka keluaran dari program diatas adalah..
a. 3 , 12
b. 1 , 4
c. 0 , 0
d. 6 , 23
e. 2 , 8

Pembahasan
nilai awal a = 15, b = 4, c = 0, d = 0
kondisi a > b
—–>> 15 > 4 (True), maka
a = 15 – 4
= 11
c = 0 + 1
= 1
d = 0 + 4
= 4
—–>> 11 > 4 (True), maka
a = 11 – 4
= 7
c = 1 + 1
= 2
d = 4 + 4
= 8
—–>> 7 > 4 (True), maka
a = 7 – 4
= 3
c = 2 + 1
= 3
d = 8 + 4
= 12
—–>> 3 > 4 (False), maka perulangan dihentikan.
Jadi nilai c = 3, d = 12
2. jika nilai  a = 34, b = 11 maka keluaran dari program diatas adalah..
a. 3 , 12
b. 1 , 4
c. 0 , 0
d. 6 , 23
e. 2 , 8

Pembahasan
nilai awal a = 34, b = 11, c = 0, d = 0
kondisi a > b
—–>> 34 > 11 (True), maka
a = 34 – 11
= 23
c = 0 + 1
= 1
d = 0 + 11
= 11
—–>> 23 > 11 (True), maka
a = 23 – 11
= 12
c = 1 + 1
= 2
d = 11 + 11
= 22
—–>> 12 > 11 (True), maka
a = 12 – 11
= 1
c = 2 + 1
= 3
d = 22 + 11
= 33
—–>> 1 > 11 (False), maka perulangan dihentikan.
Jadi nilai c = 3, d = 33

klik disini untuk download