ALGORITMA PENCARIAN. c. Hasil pencarian berupa nilai Boolean yang menyatakan status hasil pencarian

ALGORITMA PENCARIAN

MINGGU KE: 9 TUJUAN:      

Mahasiswa dapat memahami masalah pencarian. Mahasiswa dapat memahami algoritma pencarian beruntun. Mahasiswa dapat memahami algoritma pencarian beruntun Versi 1 dengan hasil pencarian boolean Mahasiswa dapat memahami algoritma pencarian beruntun Versi 1 dengan hasil pencarian indeks Mahasiswa dapat memahami algoritma pencarian beruntun Versi 2 dengan hasil pencarian boolean Mahasiswa dapat memahami algoritma pencarian beruntun Versi 2 dengan hasil pencarian indeks

TEORI PENGANTAR: Bentuk pencarian berupa: a. Pencarian untuk memeriksa keberadaan x. b. Hasil pencarian adalah indeks elemen larik. c. Hasil pencarian berupa nilai Boolean yang menyatakan status hasil pencarian. Definisikan tipe larik di bagian deklarasi global. {kamus data global} DEKLARASI const Nmaks = 100 type LarikInt = array [1..Nmaks] of string Algoritma Pencarian Beruntun Algoritma pencarian beruntun adalah proses membandingkan setiap elemen larik satu per satu secara beruntun, mulai dari elemen pertama sampai elemen yang dicari ditemukan. Versi 1 (Pembandingan elemen dilakukan sebagai kondisi pengulangan) Hasil Pencarian: sebuah peubah boolen yang bernilai true bila x ditemukan atau bernilai false bila x tidak ditemukan procedure SeqSearch1(input L:ArrStr, input n:integer, input x: string, output ketemu: Boolean) {Mencari keberadaan nilai x di dalam larik L[1..n].} {K.Awal: x dan larik L[1..n] sudah terdefinisi nilainya.} Pemrograman Modular – Versi 2015 Rini Marwati – Matematika UPI

Page 1

{K.Akhir: ketemu bernilai true jika x ditemukan. Jika x tidak ditemukan, ketemu bernilai false.} DEKLARASI i: integer ALGORITMA: i1 while (i < n) and (L[i] ≠ x) do i  I +1 endwhile if L[i] = x then ketemu  true else ketemu  false endif Program utama: PROGRAM Pencarian {Program untuk mencari nilai tertentu di dalam larik} DEKLARASI const Nmaks = 100 type ArrStr : array[1..Nmaks] of string L : ArrStr x : integer ketemu : boolean n : integer procedure BacaLarik(output L: ArrStr, input n: integer) procedure SeqSearch1(input L : ArrStr, input n : integer, input x : string, output ketemu : Boolean) ALGORITMA : read(n) BacaLarik(L, n) read(x) SeqSearch1(L, n, x, ketemu) {i = n or L[i] = x} If ketemu then write(x, ‘ ditemukan’) else write(x, ‘ tidak ditemukan’) endif Hasil pencarian: indeks elemen larik yang mengandung nilai x. Setiap elemen larik L dibandingkan dengan x mulai dari elemen pertama L[1]. Aksi pembandingan dilakukan selama indeks larik i belum melebihi n dan L[i] tidak sama dengan x. Aksi pembandingan dihentikan bila L[i] = x atau i = n. Elemen terakhir, L[n] diperiksa secara khusus. Keluaran yang dihasilkan oleh prosedur pencarian adalah peubah idx yang berisi indeks larik tempat x ditemukan. Jika x tidak ditemukan, idx diisi dengan nilai -1. procedure SeqSearch2(input L: ArrStr, input n: integer, input x: string, output idx: integer) {Mencari keberadaan nilai x di dalam larik L[1..n].} Pemrograman Modular – Versi 2015 Rini Marwati – Matematika UPI

Page 2

{K. Awal: x dan elemen-elemen larik L[1..n] sudah terdefinisi.} {K.Akhir: idx berisi indeks larik L yang berisi nilai x. Jika x tidak ditemukan, maka idx diisi dengan nilai -1.} DEKLARASI i: integer ALGORITMA: i1 while (i < n) and (L[i] ≠ x) do i  i+1 endwhile {i = n or L[i] = x} if L[i] = x then idx  i else idx  -1 endif Misalkan program pemanggil prosedur SeqSearch2 bertujuan untuk menambahkan nilai x ke dalam larik, namun sebelum penambahan itu harus ditentukan apakah x sudah terdapat di dalam larik. Jika x belum terdapat di dalam larik, maka x ditambahkan pada elemen ke n+1. PROGRAM TambahElemenLarik {Program untuk menambahkan elemen baru ke dalam larik. Elemen baru dibaca dari piranti masukan, lalu dicari apakah sudah terdapat di dalam larik. Jika belum ada, tambahkan elemen baru setelah elemen terakhir.} DEKLARASI const Nmaks = 100 type ArrStr : array[1..Nmaks] of string L : ArrStr n : integer x : string idx : integer procedure BacaLarik(output L: ArrStr, input n: integer) procedure TulisLarik(output L: ArrStr, input n: integer) procedure SeqSearch2(input L: ArrStr, input n: integer, input x: string, output idx: integer) ALGORITMA: read(n) BacaLarik(L,n) read(x) SeqSearch2(L,n,x,idx) if idx ≠ -1 then write (x, ‘ sudah terdapat di dalam larik’) else nn+1 L[n]x TulisLarik(L,n+1) endif Versi 2 (Pembandingan elemen dilakukan di dalam badan pengulangan)

Pemrograman Modular – Versi 2015 Rini Marwati – Matematika UPI

Page 3

Aksi pembandingan dilakukan di dalam badan pengulangan, bukan di awal pengulangan seperti pada Versi 1. Maka diperlukan peubah Boolean yang akan berfungsi untuk menyatakan apakah x sudah ditemukan. Misalkan peubah tersebut adalah ketemu yang pada mulanya diisi dengan nilai false. Bila x ditemukan pada elemen ke-i, maka ketemu diisi dengan nilai true. Hasil pencarian: sebuah peubah Boolean yang bernilai true bila x ditemukan atau bernilai false bila x tidak ditemukan. Procedure SeqSearch3(input L: ArrStr, input n: integer, input x: string, output ketemu: Boolean) {Mencari keberadaan nilai x di dalam larik L[1..n].} {K.Awal: nilai x, n, dan elemen larik L[1..n] sudah terdefinisi.} {K.Akhir: ketemu bernilai true jika x ditemukan. Jika x tidak ditemukan, ketemu bernilai false.} DEKLARASI i:  1 ketemu  false while (i ≤ n) and (not ketemu) do if L[i] = x then ketemu  true else i  i+1 endif endwhile

Pemrograman Modular – Versi 2015 Rini Marwati – Matematika UPI

procedure SeqSearch1(input L: ArrStr, input n:integer, input x: string, output ketemu: Boolean) {Mencari keberadaan nilai x di dalam larik L[1..n].} {K.Awal: x dan larik L[1..n] sudah terdefinisi nilainya.} {K.Akhir: ketemu bernilai true jika x ditemukan. Jika x tidak ditemukan, ketemu bernilai false.} DEKLARASI i: integer ALGORITMA: i1 while (i < n) and (L[i] ≠ x) do i  I +1 endwhile {i = n or L[i] = x} if L[i] = x then ketemu  true else ketemu  false endif

Page 4

Hasil pencarian: indeks elemen larik yang mengandung nilai x procedure SeqSearch4(input L: ArrStr, input n: integer, input x: string, output idx: integer) {Mencari keberadaan nilai x di dalam larik L[1..n].} {K.Awal: x dan elemen-elemen larik L[1..N] sudah terdefinisi.} {K.Akhir: idx berisi indeks larik L tempat x berada. Jika x tidak ditemukan, maka idx diisi nilai -1.} DEKLARASI i: integer ketemu: Boolean ALGORITMA: i1 ketemu  false while (i ≤ n) and (not ketemu) do if L[i] = x then ketemu  true else ii+1 endif endwhile if ketemu then idx  i else idx  -1 endif

procedure SeqSearch2(input L: ArrStr, input n: integer, input x: string, output idx: integer) {Mencari keberadaan nilai x di dalam larik L[1..].} {K. Awal: x dan elemen-elemen larik L[1..n] sudah terdefinisi.} {K.Akhir: idx berisi indeks larik L yang berisi nilai x. Jika x tidak ditemukan, maka idx diisi dengan nilai -1.} DEKLARASI i: integer ALGORITMA: i1 while (i < n) and (L[i] ≠ x) do i  i+1 endwhile {i = n or L[i] = x} if L[i] = x then idx  i else idx  -1 endif

PRAKTIKUM: 1. Program dalam Delphi untuk pencarian elemen larik, gunakan procedure pencarian beruntun Versi 1 dengan hasil pencarian Boolean. Form

Pemrograman Modular – Versi 2015 Rini Marwati – Matematika UPI

Page 5

Komponen Tipe Komponen

Properti

Edit

Name = EditInput; Text = blank

Button

Name = ButtonInput; Text = >>

ListBox1

Name = ListBox1

Edit

Name = EditCari; Text = blank

Button

Name = ButtonCari; Text = blank

Edit

Name = EditHasilCari; Text = blank

Coding unit Unit1; interface uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls; type TForm1 = class(TForm) EditInput: TEdit; ButtonInput: TButton; ListBox1: TListBox; Label1: TLabel; EditCari: TEdit; ButtonCari: TButton; EditHasilCari: TEdit; procedure ButtonCariClick(Sender: TObject); procedure ButtonInputClick(Sender: TObject); private { Private declarations } public { Public declarations } end; var Form1: TForm1; implementation {$R *.dfm} Pemrograman Modular – Versi 2015 Rini Marwati – Matematika UPI

Page 6

procedure TForm1.ButtonInputClick(Sender: TObject); begin ListBox1.Items.Add(EditInput.Text); EditInput.Text:=''; end; procedure TForm1.ButtonCariClick(Sender: TObject); const NMax=100; type ArrStr=array[1..100] of string; var N: integer; x: string; A: ArrStr; ketemu: boolean; procedure BacaData(N:integer;var A:ArrStr); var i:integer; begin for i:=0 to N do begin A[i]:=ListBox1.Items[i]; end; end; procedure SeqSearch1(A:ArrStr; n:integer; x: string; var ketemu: boolean); var i: integer; begin i:=1; while (i < n) and (A[i]<>x) do i:=I +1; if A[i] = x then ketemu:=true else ketemu:=false; end; begin N:=ListBox1.Count-1; BacaData(N,A); x:=EditCari.Text; SeqSearch1(A,n,x,ketemu); if ketemu then EditHasilCari.Text:='ketemu' else EditHasilCari.Text:='Tidak ketemu'; end; end. Pemrograman Modular – Versi 2015 Rini Marwati – Matematika UPI

Page 7

2. Buat algoritma dan program dalam Delphi untuk penambahan elemen larik, gunakan procedure pencarian beruntun Versi 1 dengan hasil pencarian indeks. 3. Buat algoritma dan program dalam Delphi untuk pencarian elemen larik, gunakan procedure pencarian beruntun Versi 2 dengan hasil pencarian Boolean. 4. Buat algoritma dan program dalam Delphi untuk penambahan elemen larik, gunakan procedure pencarian beruntun Versi 2 dengan hasil pencarian indeks.

TUGAS: Misalkan diberikan daftar nama. Buat program dalam Pascal untuk menambahkan elemen larik bila nama tersebut belum ada.

Pemrograman Modular – Versi 2015 Rini Marwati – Matematika UPI

Page 8