MODUL PRAKTIKUM “ALGORITMA DAN PEMROGRAMAN II”
LABORATORIUM KOMPUTER FAKULTAS ILMU KOMPUTER UNIVERSITAS SRIWIJAYA 2011
Universitas Sriwijaya
LEMBAR PENGESAHAN
SISTEM MANAJEMEN MUTU
MODUL PRAKTIKUM
ISO 9001:2008
Fakultas Ilmu Komputer Laboratorium
No. Dokumen
…….
Tanggal
4 AGUSTUS 2011
Revisi
0
Halaman
2 DARI 33
MODUL PRAKTIKUM
Mata Kuliah Praktikum
: Algoritma dan Pemrograman II
Kode Mata Kuliah Praktikum
: FIK18411
SKS
:1
Program Studi
: Teknik Informatika
Semester
: 2 (Genap)
DIBUAT OLEH
DISAHKAN OLEH
DIKETAHUI OLEH
TIM LABORAN LABORATORIUM FASILKOM UNSRI
TIM DOSEN TEKNIK INFORMATIKA FASILKOM UNSRI
KEPALA LABORATORIUM
2
Daftar Isi
Cover ......................................................................................................
1
Lembar Pengesahan ...............................................................................
2
Daftar Isi .................................................................................................
3
Perkenalan ...............................................................................................
4
Penerapan konsep tipe data bentukan .....................................................
7
Penerapan konsep pengurutan bubble.....................................................
11
Quis .........................................................................................................
15
Penerapan konsep pengurutan selection .................................................
16
Penerapan konsep pengurutan sekuensial...............................................
20
Penerapan konsep pencarian biner..........................................................
23
UTS .........................................................................................................
28
Penerapan konsep pointer (Lanjutan Algoritma dan Pemrograman I) ...
29
Latihan kasus...........................................................................................
31
Latihan kasus...........................................................................................
32
Review materi ........................................................................................
33
3
1. PERKENALAN
1.1. Review Larik Larik merupakan sekumpulan data yang mempunyai nama dan tipe yang sama.Larik sering disebut juga variabel berindeks. Nilai suatu data dalam larik ditentukan oleh nama dan indeks. Larik banyak digunakan pada operasi yang melibatkan indeks seperti pada statistik dan matriks. Tipe data larik dapat berupa larik satu demensi, dua demensi, tiga demensi atau banyak dimensi. Bentuk Umum Larik Satu Dimensi : tipe_larik nama_larik [ukuran] Bentuk Umum Larik Dua Dimensi : tipe_larik nama_larik [ukuran1][ukuran2] Perhatikan : o Tanda kurung [ ] digunakan untuk menunjukkan elemen larik o Perhitungan elemen larik dimulai dari 0, bukan 1
C++ tidak mengecek larik. Bila anda menyatakan int x[10], ini artinya 10 elemen yang dimulai dari 0. Karena itu elemen terakhir larik adalah x[9]. Bila anda salah mereferensikannya dengan x[10], anda akan mendapatkan harga yang tidak terpakai. Akan lebih buruk lagi jika anda memberikan harga ke x[10], yang tidak dapat diterima.
1.2. REPRESENTASI LARIK Misalkan kita memiliki sekumpulan data ujian seorang siswa, ujian pertama bernilai 90, kemudian 95,78,85. Sekarang kita ingin menyusunnya sebagai suatu data kumpulan ujian seorang siswa. Dalam array kita menyusunnya sebagai berikut ujian[0] = 90; ujian[1] = 95; ujian[2] = 78; ujian[3] = 85;
4
Empat pernyataan diatas memberikan nilai kepada array ujian. Tetapi sebelum kita memberikan nilai kepada array, kita harus mendeklarasikannya terlebih dahulu, yaitu : intujian[4]; Perhatikan bahwa nilai 4 yang berada didalam tanda kurung menujukkan jumlahelemen larik, bukan menunjukkan elemen larik yang ke-4.Jadi elemen larik ujian dimulai dari angka 0 sampai 3. Pemrogram juga dapat menginisialisasi larik sekaligus mendeklarasikannya, sebagai contoh : int ujian[4] = {90,95,78,85}; Elemen terakhir dari larik diisi dengan karakter ‘\0’.Karakter ini memberitahu kompiler bahwa akhir dari elemen larik telah dicapai.Walaupun pemrogram tidak dapat melihat karakter ini secara eksplisit, namun kompiler mengetahui dan membutuhkannya. Sekarang kita akan membuat daftar beberapa nama pahlawan di Indonesia char pahlawan[3][15] ; char pahlawan[0][15] = “Soekarno”; char pahlawan[1][15] = “Diponegoro”; char pahlawan[2][15] = “Soedirman”; Larik diatas terlihat berbeda denga contoh larik pertama kita. Perhatikan bahwa pada larik pahlawan memilih dua buah tanda kurung [ ][ ]. Larik seperti itu disebut larik dua dimensi. Tanda kurung pertama menyatakan total elemen yang dapt dimiliki oleh larik pahlawan dan tanda kurung kedua menyatakan total elemen yang dapat dimiliki setiap elemen larik pahlawan. Dalam contoh diatas, tanda kurung kedua menyatakan karakter yang menyatakan nama pahlawan.
MENGHITUNG JUMLAH ELEMEN ARRAY Karena fungsi sizeof() mengembalikan jumlah byte yang sesuai dengan argumennya, maka operator tersebut dapat digunakan untuk menemukan jumlah elemen array, misalnya int array[ ] = {26,7,82,166}; cout<<sizeof(array)/sizeof(int); akan mengembalikan nilai 4, yaitu sama dengan jumlah elemen yang dimiliki larik.
MELEWATKAN ARRAY SEBAGAI ARGUMEN FUNGSI Larik dapat dikirim dan dikembalikan oleh fungsi. Pada saat larik dikirim ke dalam fungsi, nilai aktualnya dapat dimanipulasi 5
Contoh-contoh soal yang mengandung larik beserta analisis nya antara lain: Contoh 1 (larik 1 dimensi) #include
void input(int x[5]); void output(int x[5]); void main() { int x[5]; x[0]=1; x[1]=2; x[2]=3; x[3]=4; x[4]=5; cout<<"Isi cout<<"Isi cout<<"Isi cout<<"Isi cout<<"Isi
x x x x x
// // // // // //
adalah adalah adalah adalah adalah
banyak larik yang dibutuhkan nilai yang terdapat dalam larik nilai yang terdapat dalam larik nilai yang terdapat dalam larik nilai yang terdapat dalam larik nilai yang terdapat dalam larik "<<x[0]<<endl; "<<x[1]<<endl; "<<x[2]<<endl; "<<x[3]<<endl; "<<x[4]<<endl;
// // // // //
keluaran keluaran keluaran keluaran keluaran
x[0] x[1] x[2] x[3] x[4]
x[0] x[1] x[2] x[3] x[4]
}
Contoh 2 (larik 2 dimensi) #include void input(int x[5]); void output(int x[5]); void main() { int x[2][2]={{1,2,3},{4,5,6}}; for(int i=0 ;i<2 ;i++) { for(int j=0 ;j<2 ;j++) { cout<<x[i][j<<]<<" "; } cout<<endl ; } }
6
2. PENERAPAN KONSEP TIPE DATA BENTUKAN
Struktur bermanfaat untuk mengelompokkan sejumlah data dengan tipe yang berlainan. Sebuah contoh pendeklarasian struktur dapat dilihat dibawah ini : struct data_tanggal { int tahun; int bulan; int tanggal; }; Pada contoh ini, dideklarasikan sebuah struktur bernama data_tanggal yang terdiri dari tiga buah anggota berupa : tahun bulan tanggal
MENDEFINISIKAN VARIABEL STRUKTUR Apabila suatu struktur telah dideklarasikan, struktur ini dapat digunakan untuk mendefinisikan suatu variabel. Misalnya, data_tanggal tanggal_lahir; Merupakan pendefinisian variabel struktur bertipe struktur tanggal lahir. Dengan adanya pendefinisian ini, tanggal_lahir memiliki tiga buah anggota yaitu : tahun bulan tanggal
STRUKTUR DI DALAM STRUKTUR Suatu struktur juga bisa mengandung struktur yang lain. Sebagai gambaran ditunjukkan di bawah ini.
struct data_pegawai { int nip; 7
char nama[25]; data_tanggal tanggal_lahir; }
rec_peg;
MENGAKSES ANGGOTA STRUKTUR Anggota struktur diakses dengan menggunakan bentuk : variabel_struktur.nama_anggota Tanda titik diberikan diantara nama variabel struktur dan nama anggota. Misalnya : tanggal_lahir.tanggal = 1; merupakan pernyataan penugasan untuk memberikan nilai1 ke anggota tanggal pada variabel struktur tanggal_lahir. Bagaimana halnya untuk mengakses anggota bernama bulan pada variabel struktur rec_peg seperti pada contoh di depan ? Misalnya rec_peg.tanggal_lahir.bulan = 9; Merupakan contoh untuk memberikan nilai terhadap anggota bulan pada variabel struktur rec_peg.
PENUGASAN STRUKTUR Pemberian nilai terhadap suatu struktur dapat dilakukan dengan bentuk : var1 = var2; Sepanjang kedua variabel adalah variabel struktur bertipe sama. Misalnya terdapat pendefinisian : data_tanggal tgl1 tgl2; Penugasan seperti berikut : tgl2 = tgl1; Diperkenankan.Dalam hal ini, seluruh anggota pada variabel tgl2 diisi dengan anggota terkait yang ada pada tgl1. Pernyataan di atas merupakan penyederhanaan dari tiga pernyataan berikut : tgl2.bulan = tgl1.bulan; tgl2.tahun = tgl1.tahun; tgl2.tanggal = tgl1.tanggal; Contoh Program : 8
#include typedef struct lingkaran{ float r; float keliling; float luas; }; void kllluas(lingkaran &L); voidmain() { lingkaran L; cout<<"masukkan jari-jari :"; cin>>L.r; kllluas (L); cout<<" keliling "<
Contoh Program 2 : #include #include<malloc.h> typedef struct lingkaran{ float r; float keliling; float luas; }; lingkaran *L; void kllluas(lingkaran *L); void main() { L=(lingkaran *)malloc(sizeof(lingkaran)); cout<<"masukkan jari-jari :"; cin>>L->r; kllluas (L); cout<<" keliling "<keliling<<endl; cout<<" luas "<luas; } voidkllluas(lingkaran *L) { L->keliling = 2*3.14*L->r; L->luas =3.14*L->r*L->r; }
Contoh program 3 : #include<stdio.h> #include typedef int angka; //pendefinisian type bentukan angka=int typedeffloat pecahan; typedefchar huruf;
9
void main() { clrscr(); angka umur; //umur (nama variabel),angka (tipe bentukan yang sama dengan integer) pecahan pecah; huruf h; huruf nama[10]; printf ("Masukkan umur anda :" ) ;scanf ("%d",&umur); printf ("umur anda adalah %d",umur); printf ("\nMasukkan bilangan pecahan :" );scanf("%f",&pecah); printf ("Bilangan pecahan %f",pecah); printf ("\nMasukkan huruf : ");h=getche(); printf ("\nHuruf anda %c",h); printf ("\nMasukkan nama : ");scanf ("%s",nama); printf ("Nama anda %s",nama); getch(); }
10
3. PENERAPAN KONSEPPENGURUTAN BUBBLE Pengurutan (sorting) adalah proses mengatur sekumpulan obyek menurut urutan atau susunan tertentu. Urutan tersebut dapat menaik (ascending) atau menurun (descending). Jika diberikan n buah elemen disimpan di dalam larik L, maka : -
pengurutan menaik adalah L[0] < L[1] < L[2] < … < L[n-1]
-
pengurutan menaik adalah L[0] > L[1] > L[2] > … > L[n-1]
Pengurutan berdasarkan jenisnya, dibagi dua kategori, yaitu : 1. Pengurutan Internal, yaitu pengurutan terhadap sekumpulan data disimpan di dalam memori utama komputer. 2. Pengurutan Eksternal, yaitu pengurutan data yang disimpan di dalam memori sekunder, biasanya data bervolume besar sehingga tidak mampu dimuat semuanya dalam memori computer, disebut juga pengurutan arsip (file), karena struktur eksternal yang dipakai adalah arsip.
Karena pengaksesan memori utama lebih cepat daripada memori sekunder, maka pengurutan internal lebih cepat daripada pengurutan eksternal.
Bermacam-macam metode yang dipakai untuk melakukan pengurutan, antara lain : -
Bubble Sort
-
Selection Sort
-
Insertion Sort
-
Heap Sort
-
Shell Sort
-
Quick Sort
-
Merge Sort
-
Radix Sort
-
Tree Sort
Pada bagian ini hanya akan dibahas mengenai tiga buah metode sederhana yang mendasar, yaitu : 1. Metode Pengurutan Gelembung (Bubble Sort) 11
2. Metode Pengurutan Pilih (Selection Sort) 3. Metode Pengurutan Sisip (Insertion Sort)
Metode Pengurutan Gelembung (Bubble Sort)
Metode ini diinspirasi oleh gelembung sabun yang berada di permukaan air. Karena berat jenis gelembung sabun lebih ringan dibandingkan dengan berat jenis air, sehingga gelembung sabun selalu terapung di permukaan air. Prinsip pengapungan inilah yang diterapkan ke metode ini, dimana nilai yang paling rendah berada di posisi paling atas, melalui proses pertukaran.
Konsep dasar dari metode ini adalah setiap data yang ada di kumpulan, dibandingkan dengan data-data lainnya, artinya jika jumlah data sebnayak 5, maka akan terjadi perbandingan sebanyak (5-1)2 = 16 kali. Untuk satu data, akan dibandingkan sebanyak 4 kali terhadap data yang lainnya.
Atau secara umum dapat ditarik rumus, untuk jumlah data sebanyak n buah, maka : Jumlah iterasi pembandingan = (n-1)2 Jika data-data tersebut disimpan di dalam larik L, maka : 1. Untuk pengurutan menaik, pembandingnya sebagai berikut : L[n] L[n-1] Jika kondisi diatas terpenuhi, maka nilai data yang ada di indeks n-1 akan ditukar dengan nilai data yang ada di indeks n. Contoh : #include void input(int x[10]); void proses(int x[10], int&temp); void output1(int x[10]); void output2(int x[10]); void main() { int x[10], temp; input(x); output1(x); proses(x,temp); output2(x);
12
} void input(int x[10]) { int i; for (i=0; i<10; i++) { cout<<"Masukkan bilangan : "; cin>>x[i]; } } void proses(int x[10], int&temp) { int i,j; for(i=1;i<10;i++) { for(j=10;j>=1;j--) { if(x[j]<x[j-1]) { temp=x[j]; x[j]=x[j-1]; x[j-1]=temp; } } } } void output1(int x[10]) { int i; cout<<"Bilangan yang dimasukkan adalah : "<<endl; for (i=0; i<10; i++) { cout<<x[i]<<" "; } cout<<endl; } void output2(int x[10]) { int i; cout<<"Data setelah diurutkan :"<<endl; for (i=0;i<10;i++) { cout<<x[i]<<" "; } }
Analisis : Pengurutan bubble ini merupakan pengurutan dimana data input 10 buah.Berdasarkan iterasi yang ada jika ada 10 buah data maka dibandingkan sebanyak (10-1)2 jadi 92 berarti terjadi perbandingan sebanyak 81 kali.Pada prosedur input menggunakan pengulangan untuk memasukkan data yang ada yaitu for (i=0;i<10;i++).Setealh data dimasukkan
maka
akan
diurutkan
melalui
prosedur
proses.Pada
prosedur
proses,terjadi 2 kali pengulangan dimana pengulangan pertama menunjukkan perngulangan untuk banyak data(i) dan pengulangan kedua merupakan pengulangan 13
untuk masing-masing data (j).Pada pengulangan pertama yaitu for (i=1;i<10;i++) banyak data akan dibandingkan satu persatu sampai 10 data dibandingkan semuaya.Lalu pada pengulangan ke dua for (j=10;j<1;j--).Jika pada pengulangan pertama dimulai dengan i=0.Maka nilai x[0] akan dibandingkan pula sebanyak 9 kali pada pengulangan ke dua .Didalam pengulangan kedua terdapat pemilihan untuk menyusun agar dapat terurut menaik atau menurun.Pemilihan itu if (x[j]<x[j-1])maka akan ditukarkan ini berarti nilai apakah nilai x[10] <x[9] jika syarat terpenuhi maka akan terjadi pertukaran>jika tidak maka akan dilanjutkan ke pengulangan selanjutnya terjadi
lagi
pengulangan
untuk
x[9]<x[8],x[8]<x[7],x[7]<x[6],x[6]<x[5],x
[5]<x[4],x[4]<x[3], x[3]<x[2] x[2]<x[1] dan x[1]<x[0].perbandingan itu merupana perbandingan untuk i=0. Jika pengulangan telah selesai.Maka akan keluar dari pengulangan kedua dan kembali ke pengulangan pertama untuk i=1 dan begitu seterusnya sampai syarat untuk pengulangan pertama habis atau semua data telah di bandingkan satu-persatu.Setelah selesai di bandingkan maka data akan dikirim ke prosedur output .Pada prosedur output untuk mengelurakan hasil menngunakan pengulangan.Dan hasil yang telah terurut akan di keluarkan.
Output :
14
4. QUIS
Soal : Buatlah program untuk mengurutkan nilai mahasiswa dengan menggunakan metode pengurutan bubble
15
5. PENERAPAN KONSEP PENGURUTAN SELECTION 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. Perhatikan ilustrasi berikut :
Misalkan ada sekumpulan data acak berjumlah n elemen yang disimpan di dalam larik L, akan diurut menaik, maka langkah-langkah yang harus dilakukan adalah : 1. Menentukan jumlah iterasi, yaitu pass = n-2 2. Untuk setiap pass ke-I = 0,1,2, … , pass, lakukan a. Cari elemen terbesar (maks) dari elemen ke-i sampai ke-(n-1) b. Pertukaran maks dengan elemen ke-i c. Kurangin n sayu (n = n -1) Rincian tiap-tiap pas adalah sebagai berikut : -
pass 0 Cari elemen maksimum di dalam L[0 … (n-1)]. Pertukarkan elemen maksimum dengan elemen L[n-1]
-
pass 1 Cari elemen maksimum di dalam L[0 .. (n-2)] Pertukarkan elemen maksimum dengan elemen L[n-2]
-
pass 2 Cari elemen maksimum di dalam L[0 .. (n-3)] Pertukarkan elemen maksimum dengan elemen L[n-3]
. . . -
pass 3 Cari elemen maksimum di dalam L[0 .. 1] Pertukarkan elemen maksimum dengan elemen L[1]
16
Contoh Program : #include void input(int a[100], int&n); void selection(int a[100], int n); void output (int a[100], int n); void tukar (int a[100], int pos, int i); void main() { int a[100], n; input (a,n); selection (a,n); output (a, n); } voidinput (int a[20], int&n) { int i; cout<<"Masukan banyak data= "; cin>>n; for (i=0; i
Analisisnya : Program ini merupakan program untuk mengurutkan dengan Cara memilih nilai yang terbesar antara nilai yang lain.pada prosedur input merupakan untuk memasukkan 17
nilai data.Memasukkan banyak data dan banyak nilai dengan menggunkaan pengulangan for (i=0;i
18
Output :
19
6. PENERAPAN KONSEP PENCARIAN SEKUENSIAL Penerapan dari konsep pemrograman sebelumnya, dapat digunakan untuk berbagai macam permasalahan. Pada bagian ini akan dibahas penerapan ke dalam bentuk pencarian.
Konsep Pencarian merupakan proses yang fundamental dalam pemrograman, guna menemukan data (nilai) tertentu di dalam sekumpulan data yang bertipe sama. Fungsi pencarian itu sendiri adalah memvalidasi (mencocokan) data.Sebagai contoh, untuk menghapus atau mengubah sebuah data di dalam sekumpulan nilai, langkah pertama yang harus ditempuh adalah mencari data tersebut, lalu menghapus atau mengubahnya. Contoh lain adalah penyisipan data ke dalam kumpulan data, jika data telah ada, maka data tersebut tidak akan disisipkan, selainnya akan disisipkan ke dalam kumpulan data tersebut. Ada sebuah kasus sederhana, misalkan terdapat 10 data yang bertpe integer, terangkum di dalam variabel larik L. Terdapat data X di dalam larik L tersebut. Bagaimana proses pencarian data X tersebut ? Jika ketemu maka akan mengeluarkan pesan teks “ Data ditemukan ! “ atau jika tidak ditemukan akan mengeluarkan pesan teks “ Data tidak ditemukan “. Serta menampilkan di elemen ke beberapa elemen tersebut ditemukan, dan berapa jumlah data X di larik L.
Ada beberapa metode mencari data di dalam sekumpulan data yang bertipe sama yaitu : 1. Metode Pencarian Beruntun (Sequential Search) 2. Metode Pencarian Bagi Dua (Binary Search)
Metode Pencarian Beruntun
Konsep yang digunakan dalam metode ini adalah membandingkan data-data yang ada dalam kumpulan tersebut, mulai dari elemen pertama sampai elemen ditemukan, atau sampai elemen terakhir. Contoh program : #include void input(int data[10],int&cari); void hitung (int data[10],int cari,int&j,int indeks[10]); void output(int data[10],int cari,int j,int indeks[10]); void main()
20
{ int data [10],indeks[10]; int j,cari; input(data,cari) ; hitung (data,cari,j,indeks); output(data,cari,j,indeks); } void input(int data[10],int&cari) { int i; cout<<"Masukkan data 10 buah data"<<endl; for ( i=0;i<10;i++) { cout<<"data ke "<<(i+1)<<" : "; cin>>data[i]; } cout<<"Masukkan data yang akan dicari :"; cin>>cari; } void hitung (int data[10],int cari,int&j,int indeks[10]) { int i; j=0; for (i=0;i<10;i++) { if (data[i] ==cari) { indeks[j]=i; j++ ; } } } void output(int data[10],int cari,int j,int indeks[10]) { int i; if (j >0) { cout<<"data "<< cari<< " yang dicari "<<j<<endl; cout<<"data tersebut terdapat dalam "<<endl; for ( i =0;i<j;i++) { cout<
Analisis : Program ini merupakan program untuk melakukan pencarian yang ada didalam array apabila data yang dicari ditemukan maka akan ditampilkan terdapat pada indeks ke berapa dan berapa jumlahnya.Pada prosedur input menggunkan penggulangan untuk memasukkan data dengan banyak deta telah ditentukan yaitu 10 buah.Jadi terjadi pengulangan
sebanyak
10
kali
yang
di
awali
dengan
indeks
0
for 21
(i=0;i<10;i++).Setealh memasukkan banyak data maka akan dimasukkan data yang akan dicari.Pada prosedur hitung merupakan prosedur pencarian.Pada prosedur ini menggunkan pengulangan dan pemilihan pengulangan digunakan untuk memasukkan nilai/data yang telah dimasukkan pada prosedur input.Lalu didalam pegulangan terdapat pemilihan.jika pad pengulangan i=0 dan dimasukkan data x[0]=1 dan data yang akan dicari adalah 1.Berarti indeks x[0] akan masukk ke dalam pemilihan dan indeks akan diinisialisasikan menjadi indeks [j] untuk mempermudah membaca nilai yang sama dengan data yang dicari.Lalu data nilai akan disimpan dalam array indeks dan banyaknya data disimpan dalam j.Setelah semua nilai/data diperiksa
maka
hasilnya akan dikeluarkan melalui prosedur output terdapat pemilihna jika (j<0)beratri data yang dicari ada didalam array.Dengan menggunakan pengulangan untuk menunjukkan berapa banyak data yang didapatkan dan dimana letaknya.Maka pengulangannya menjadi for ( i=0;i<j;i++).i<j karena j menunjukkan banyak data yang sama maka pengulangan akan berhenti sesuia dengan banyak data yang didapatkan dan juga dan didalam pengulangan terdapat indeks dimana data yang ingin di cari diletakkan.Jika j=0 berarti data yang dicari tidak ada didalam array.
Output :
22
7. PENERAPAN KONSEP PENCARIAN BINER Metode ini diterapkan pada sekumpulan data yang sudah terurut (menaik atau menurun).Metode ini lebih cepat dibandingkan metode pencarian beruntun.Data yang sudah terurut menjadi syarat mutlak untuk menggunakan metode ini.
Konsep dasar metode ini adalah membagi 2 jumlah elemennya, dan menentukan apakah data yang berada pada elemen paling tengah bernilai sama, maka langsung data tengah dicari ditemukan. Jika data di elemen terurut naik, maka jika data yang berada di tengah kurang dari data yang dicari, maka pencarian selanjutnya berkisar di elemen tengah ke kanan, dan begitu seterusnya sampai ketemu atau tidak sama sekali. Dan sebaliknya untuk nilai data yang berada di tengah lebih dari data yang dicari, maka pencarian selanjutnya berkisar di elemen tengah ke kiri, dan begitu seterusnya sampai ketemu atau tidak sama sekali. Dan demikian sebaliknya untuk data yang terurut menurun.Dalam hal ini tentukan indeks paling awal dan indeks paling akhir, untuk membagi 2 elemen tersebut.
Indeks awal = i, dimana nilai i, pada awalnya bernilai 0; Indeks akhir =j, dimana nilai j, pada awalnya bernilai sama dengan jumlah elemen.
Langkah-langkah untuk metode pencarian bagi dua. 1. Asumsikan data terurut secara horizontal dari indeks 0 samapi n-1, untuk menggunkan istilah kanan dan kiri. 2. Misalkan kumpulan data yang berjumlah n adalah larik L, dan data yang akan dicari adalah X. 3. Tentukan nilai indeks awal i=0 dan indeks akhir j = n-1. 4. Tentukan
apakah
data
terurut
menurun
atau
meniak
dengan
menggunakan
membandingkan apakah elemen paling kiri L[0] lebih dari atau kurang dari eleemn paling kanan L[n-1].
Jika data di elemen paling kiri L[0] > data di elemen paling kanan L[n-1], maka data terurut menurun.
Jika data elemen paling kiri L[0] < data di elemen paling kanan L[n-1], maka data terurut menaik.
5. Asumsikan bahwa data terurut menaik (tergantung hasil nomor 3). 23
6. Misalkan variabel k adalah indeks paling tengah, diperoleh dengan rumus : K = (I + j) div 2 7. Periksa, jika L[k] = x, maka data dicari langsung ketemu di elemen k. 8. Jika nomor 7 tidak terpenuhi, periksa jika L[k]<X, maka pencarian berikutnya dilakukan di sisi kanan indeks k, lakukan proses seperti pada nomor 6, dimana nilai indeks I sekarang sama dengan nilai indeks sebelumnya. I=k K=(i+j)div2 Dan seterusnya sampai nilai X dicari ketemu atau tidak sama sekali. 9. Jika nomor 8 tidak terpenuhi, maka tidak pasti nilai Lk]>X, maka pencarian berikutnya dilakukan di sisi kiri indeks k, lakukan proses seperti pada nomor 6, dimana nilai indeks j sekarang sama dengan nilai indeks k sebelumnya. J=k K=(i+j)div2 Dan seterusnya sampai nilai X dicari ketemu atu tidak sama sekali. 10. Jika data terurut menurun, maka tukar kondisi yang ada di nomor 8 dan 9.
Contoh : Diberikan 10 data terurut L[10] = {15,17,20,25,29,30,45,50,58,60}. Cari nilai X = 20 di elemen tersebut. Solusi : 1. Menentukan apakah data terurut menaik atau menurun. L[0] = 15 L[9] = 60 Karena L[0] < L[9], maka data tersebut terurut menaik. 2. Misal indeks paling kiri adlah I = 0 dan indeks paling kanan adalah j = 9, maka indeks tengahnya adalah : K = (i+j) div 2 = (0+9) div 2 = 4. Elemen tengah sekarang adalah 4 dengan L[4] = 29. 3. Karena data di indeks tengah lebih dari nilai data yang dicari (L[4] > X), maka pencarian berikutnya dilakukan pada sisi kiri indeks k, maka nilai j sekarang sama dengan k, lalu lakukan proses sama seperti nomor 2. 24
J=k =4 K= (i+j) div 2 = (0 +4) div 2 =2 Elemen tengah sekarang adalah 2 dengan L[2] = 20. 4. Karena nilai data di elemen tengah sama dengan nilai data yang dicari X, maka pencarian berakhir. Data X ditemukan di iNdeks ke-1. Pada
contoh
diatas
mengunakan
data
masukan
yang
sudah
diurutkan
terlebih
dahulu.Bagaimana jika data yang di masukkan merupakan data acak sehingga belum dapat diketahui data tersebut menaik atau menurun.Jika kondisinya seperti ini maka hasus menggunakakn pengurutan terlebih dahulu untuk mengurutkan data menjadi terurut menaik atau menurun. Contoh program berikut ini merupakan contoh program yang datanya diinputkan acak #include #include<stdio.h> void input (int A[10],int&k); void urut (int A[10]) ; void cari(int A[10],int&tm,int k); void output(int tm,int k) ; void main() { int A[10], i, j, k, tkr, top, bottom, middle, tm; input (A,k); urut (A) ; cari(A,tm,k); output(tm,k); } void input (int A[10],int&k) { int i,j; for (i=0; i<10; i++) { printf("Data ke-%d : ", i+1); scanf("%d",&A[i]); } printf("Masukkan data yang akan dicari : "); scanf("%d",&k); } void urut (intA[10]) { int i,j,tkr; for(i=0; i<10; i++) { for(j=i+1; j<10; j++) { if (A[i]>A[j]) { tkr=A[i]; A[i]=A[j];
25
A[j]=tkr; } } } } void cari(int A[10],int &tm,int k) { int top,middle,bottom; tm=0; top=9; bottom=0; while(top>=bottom) { middle=(top+bottom)/2; if(A[middle]==k) { tm++; } if(A[middle]0) { printf("Data %d yang dicari ada dalam array\n",k); } else { printf("Data tidak ditemukan dalam array\n"); } }
Analisis : Program ini merupakan program untuk melakukan pencarian.Dimana pencarian dilakukan dengan cara membagi dua data masukan.Data dimasukkan pada prosedur input dengan menggunkaan pengulangan for ( i=0;i<10;i++) sehingga data akan diulang sebanyak 10 kali.Namun data yang dimasukkan harus terurut terlebih dahulu.Pada kasus ini data yang dimasukkan merupakan data acak sehingga program harus
mengurutkan
data
tersebut
terlebih
dahulu
dengan
menggunakan
pengurutan.Pada prosedur urut Terjadi dua kali pengulangan perngulangan pertama for ( i=0;i<10;i++) uang kedua yaitu pengulangan for ( j=i+1;j<10;j++).pada pengulangan pertama jika i=0 maka nilai j =1.Penurutan akan dimulai dengan membandingkan nilai yang satu dengan nilai selanjutnya.niali A[0] akan 26
dibandingkan dengan nilai A[1].Didalam pengulangan terdapat pula pemilihan jika A[i]>A[j].jika syarat tersebut terpenuhi maka akan ditukarkan tempat dengan menggunakan tkr.Setelah pengulangan telah selesai and data telah teurut maka data yang telah terurut dikirim ke prosedur cari.Dimisalkan banyak data 10 data,data yang dimasukkan 3,4,2,1,6,5,7,4,8,9.Maka data tersebut akan diurutkan terlebih dahulu menjadi 1,2,3,4,4,5,6,7,8,9.Lalu diinisialisasi awal nilai top = 0 bottom = 9,dan tm menunjukkan banyak data yang sama dengan nilai yang dicari.Lalu masuk kedalam akan berakhir jika nilai top>=bottom.Untuk mencari nilai tengah maka nilai atas ditambah dengan nilai bawah lalu di bagi dua.Dan akan didapatkan nilai tengah dari data tersebut.Lalu nilai tengah itu akan dilihat apakah sama dengan nilai yang dicari.Jika sama maka tm akan bertambah.Lalu apabila nilai tengah lebih kecil dari nilai yang dicari maka batas bawah akan berubah menjadi batas tengah +1.Dan jika nilai tengah lebih besar dari nilai yang dicari maka batas atas akan berubah menjadi batas tengah -1.Apabila pengulangan telah mencapai top>=bottom maka pengulangan akan berhenti.Dan akan di lanjutkan ke prosedur output.Jika nilai tm yang didapatkan lebih dari 0 maka akan ditampilkan bahwa nilai yang dicari ada didalam data.Dan jika nilai tm =0.Maka akan ditampilkan bahwa data yang dicari tidak ada didalam data.Setelah syarat tidak terpenuhi lagi maka hasil akan dikelurkan ke prosedur output.Pada prosedur output hanya dilihat nilai tm jika nilai tm >0 berati data yang dicari ada di dalam larik .Jika tm =0 maka data yang di cari tidak ada di dalam data masukkan. Output :
27
8. UTS
Soal : Buatlah program pencarian nama mahasiswa dari sekumpulan data mahasiswa (mahasiswa merupakan tipe data bentukan yang terdiri dari nama, nim dan nilai).
28
9. PENERAPAN KONSEP POINTER (Lanjutan Algoritma dan Pemrograman I )
Pointer Pointer (variabel penunjuk) adalah suatu variabel yang berisi alamat memori dari suatu variabel lain. Lokasi memori tersebut mungkin diwakili oleh sebuah variabel atau mungkin juga lokasi bebas dalam memori. Sedangkan pointer sendiri yang berupa nilai ditampung dalam sebuah variabel yang disebut variabel pointer.Jadi variable pointer atau pointer berisi suatu nilai yang menyatakan alamat suatu lokasi. Suatu variable pointer didefinisikan dengan bentuk : TipeData *NamaVariabel Contoh : a
*c
b
*d
var
2
*
3
*
value
A
*
B
*
address
Step : 1.
d=&a *d = 2 ; d = A
2.
c=&b *c = 3 ; c = B
3.
b=*d b = 2 ; &b = B
4.
*d=*c *d = 2 ; d = A
Dari contoh di atas terlihat bahwa addres pada variabel pointer dapat berubah – ubah, apabila addres suatu variabel pointer berubah maka valuenya akan berubah sesuai addres yang ditunjuk oleh pointer tersebut. Apabila pada address yang ditunjuk oleh pointer tersebut mengalami perubahan value, maka value pada pointer juga akan berubah.
Pemberian Memori Alokasi Pada Pointer Sebuah pointer itu tidak memiliki alamat, sehingga pointer harus menumpang pada variabel lain. Namun sekarang kita memberikan alamat kepada variabel pointer sehingga pointer
29
tidak lagi menumpang pada variabel lain.Untuk membuat alamat menggunakan malloc yang disesuaikan dengan panjang data. VariabelPointer = (TipeData *) malloc(sizeof(TipeData)); Contoh I: 1: #include 2: #include 3: voidmain() 4: { 5: int x; 6: float y; 7: long z; 8: 9: x = 3; 10: y = 3.7; 11: z = 1000; 12: 13: cout<<"isi variabel x = "<<x<<endl; 14: cout<<"isi variabel y = "<
30
10. LATIHAN KASUS
Buatlah program untuk menghitung frekuensi kemunculan nilai dari sebuah matriks dengan ordo 8 x 8 dengan nilai dari 0 – 15. Nilai matriksnya sebagai berikut : 3 7 7 ⎡2 0 0 ⎢ ⎢14 6 5 ⎢12 2 1 ⎢0 2 3 ⎢4 5 0 ⎢5 3 1 ⎣2 1 0
8 0 9 8 4 0 1 1
1 1 8 8 5 1 9 1
1 8 10 10 13 0 13 1
14 15 9 11 10 2 8 13
Sehingga didapatkan frekuensi kemunculan nilai seperti berikut :
10 15⎤ ⎥ 12⎥ 1⎥ 14⎥ 2⎥ 7⎥ 12⎦
Output : Data : Frekuensi 0: 8 1: 12 2: 6 3: 3 4: 2 5: 4 6: 1 7: 3 8: 6 9: 2 10: 4 11: 1 12: 3 13: 3 14: 3 15: 2
31
11. LATIHAN KASUS Buatlah program untuk melihat nilai terbesar dan nilai terkecil dari sekumpulan nilai mahasiswa (Dibuat dalam bentuk menu). Menu 1. Pengguna dapat melihat nilai yang paling kecil Menu 2. Pengguna dapat melihat nilai yang paling besar
32
12. REVIEW MATERI 1. Buatlah program mencari nilai dari array berikut ini dengan metode binary 4
13
21
28
35
42
47
48
57
2. Misalkan kita memiliki array dengan elemen seperti berikut ini : 1
5
2
7
6
3
9
4
0
8
Buatlah program dengan fungsi rekursif untuk menghitung jumlah total bilangan genap dalam array
33
