Sunday, 2 June 2013

Algoritma Pengulangan


Ada kalanya untuk menyelesaikan suatu masalah, satu atau beberapa instruksi harus dikerjakan beberapa kali. Misalnya anda hendak menampilkan tulisan ”algoritma” sebanyak tiga kali, maka algoritmanya dapat ditulis 
1. Mulai 
2. Tulis ‘Algoritma’
3. Tulis ‘Algoritma’
4. Tulis ‘Algoritma’
5. Selesai
Sehingga diperoleh keluaran :
Algoritma
Algoritma
Algoritma
Contoh lain. Anda hendak menghitung suatu bilangan dipangkatkan tiga. Maka algoritmanya dapat dituliskan


1. Mulai
2. Masukkan bilangan X
3. Set nilai Y=1
4. Kalikan X dengan Y, simpan sebagai Y
5. Kalikan X dengan Y, simpan sebagai Y
6. Kalikan X dengan Y, simpan sebagai Y
7. Tulis (Y)
8. Selesai
Atau dalam algoritma teks standar deskripsinya dapat ditulis seperti berikut :

Deskripsi
Read(X)
Y1
YX*Y
YX*Y
YX*Y
Write(Y)




Jika input algoritma (X) adalah 2, maka perubahan nilai dalam variabel dapat dilihat pada tabel penyimpanan data berikut.

Perintah X Y Ouput
Read(X)
Y1
YX*Y
YX*Y
YX*Y
Write(Y)
2


1
4
8
16






16

Output yang dihasilkan adalah : 16

Cara ini memang dapat menyelesaikan permasalahan tersebut di atas, tapi sangat tidak efisien dalam penulisannya. Bayangkan kalau pengulangan yang harus dilakukan sebanyak 1000 kali, maka kita harus menulisnya sebanyak seribu kali pula. Tentunya hal ini sangat sangat merepotkan. Untuk itu kita perlu mengenal satu lagi algoritma dasar yaitu algoritma pengulangan. Dengan algoritma ini kita cukup menuliskan perintahnya sekali untuk pengulangan berapapun banyaknya.
Bila mengacu pada bahasa pemrograman Pascal, terdapat tiga ekspresi algoritma untuk pengulangan :
1. for-do
2. while-do
3. repeat-until
Pengulangan For-Do
Pengulangan for adalah pengulangan yang cocok digunakan untuk kasus-kasus yang jumlah pengulangannya telah jelas. Ada 2 macam pengulangan for-do, yaitu for-do menaik dan for-do menurun. Berikut ini adalah bentuk umumnya.
For-do menaik
For var  nilai_awal to nilai_akhir do
  Aksi
Contoh

for i  1 to 3 do
Write(‘Halo’)


Kondisi pengulangan for secara tersirat dapat dilihat pada ni (nilai_awal) dan nf (nilai_akhir); Nilai yang terkandung pada var mula-mula sama dengan nilai_awal, kemudian bertambah (berkurang) sebanyak satu, kemudian berhenti setelah var lebih besar (lebih kecil) nilai_akhir. 
Contoh
for i  3 downto 1 do
Write(‘Halo’)
Penjelasan
Pada perintah di atas, mula-mula i diberi nilai 1. Kemudian perintah write(‘Halo’) dikerjakan. Setelah itu i bertambah satu sehingga menjadi 2, dilanjutkan dengan perintah write(‘Halo’). Proses yang sama diulang lagi hingga i bernilai tiga, perintah write(’Halo’)  dikerjakan. Setelah itu proses pengulangan berhenti di situ. 
Dengan demikian outputnya dapat kita nyatakan seperti berikut
Halo
Halo
Halo

For-do menurun
For variabel  nilai_awal downto nilai_akhir do
  Aksi

Kita dapat membuat output yang sama seperti di atas dengan for-do menurun.

for i  3 downto 1 do
Write(‘Halo’)





Perbedaannya, pada for-do menaik i berubah dari 1 sebanyak +1 dan berhenti setelah lebih dari 3, sedangkan pada for-do menurun, i berubah dari 3 sebanyak –1 hingga akhirnya berhenti saat i kurang dari 1.
Studi Kasus
1. Buat algoritma menampilkan deret 1, 2, 3, …, N. N adalah masukan.
Input : -
Output : 1 2 3
Algoritma 2 8
Algoritma deret

Deklarasi
   var
N,x : integer

Deskripsi
read(N)
for x  1 to N do
write(x)
Mula-mula masukkan nilai N, misalnya 3. Setelah itu masuk ke dalam loop dengan x mula-mula 1. Pengulangan dilakukan selama kondisi bernilai true, yaitu selama nilai x dalam rentang 1..N. Kemudian  write (x) menghasilkan keluaran 1. Proses diulang lagi dengan x (=2) Kemudian  write (x) menghasilkan keluaran 2. Demikian seterusnya. Aksi tidak lagi dikerjakan saat x>N.
Tabel Penyimpanan Data Algoritma 2 8
Perintah N x=1..N x Output
Read(N) 3
x=1 : write(x)
x=2 : write(x)
x=3 : write(x)
x=4 : write(x)    

true
true
true
false 1
2
3
1
2
3
Latihan : coba anda  tuliskan bentuk flowchart dari algoritma di atas.
Studi Kasus
Buat algoritma yang menampilkan jumlah dari deret pada Algoritma 2 8.
Input : -
Output : jumlah deret
Algoritma 2 9
Algoritma jumlah_deret

Deskripsi
read(N)
jum0
for x  1 to N do
jumjum+x
write(jum)
Tabel Penyimpanan Data Algoritma 2 9
Perintah N x > N x jum Output
read(N) 4
jum0 0
x=1 : jumjum+x
X=2 : jumjum+x
x=3 : jumjum+x
x=4 : jumjum+x
x=5 : jumjum+x

true
true
true
true
false 1
2
3
4 1
3
6
10
write(jum) 10

Penjelasan
Mula-mula masukkan nilai N, misalnya 4, kemudian inisialisasi jum=0. Setelah itu masuk ke dalam loop dengan x mula-mula 1. Kemudian jum = 0 ditambah dengan x = 1 sehingga diperoleh jum (baru) = 1. Proses diulang lagi dengan x = 2. Kemudian jum = 1 ditambah dengan x = 2 sehingga diperoleh jum = 3. Demikian seterusnya. Aksi tidak lagi dikerjakan saat x>N.
Dengan demikian keluaran dari algoritma di atas adalah : 10.

Latihan 
Coba masukkan input N yang lain, misalnya 7, kemudian isi tabel penyimpanan data dan tuliskan nilai keluarannya.

Pengulangan While-Do
Secara umum algoritma pengulangan while adalah

while <kondisi> do
aksi





Teks algoritma dan flowchart di atas menunjukkan bahwa ada pengecekan kondisi dulu sebelum aksi berikutnya dilakukan. Aksi di bawah kondisi dikerjakan jika kondisinya atau lebih tepatnya nilai boolean kondisi bernilai benar. Jika kondisi bernilai salah, maka proses akan ‘melompat’ atau mengerjakan aksi yang berada di luar loop.
Studi Kasus
Buat algoritma menampilkan deret 2, 4, 6, …, N. N adalah masukan berupa bilangan genap.
Deskripsi masalah
Input : -
Output : 2 4 6
Algoritma 2 10
Algoritma deret

Deskripsi
read(N)
x  2
while x <= N do
write(x)
x  x + 2  
Tabel Penyimpanan Data Algoritma 2 10
Perintah x<=N N x Output
Read(N) 8
x2 2
x=2  : Write(x)
          xx+2

x=4  : Write(x)
         xx+2

x=6  : Write(x)
          xx+2

x=8  : Write(x)
          xx+2

x=10 : Write(x)
           xx+2 true


true


true


true


false

4


6


8


10 2


4


6


8
Mula-mula inputkan nilai N dalam hal ini adalah 8. Kemudian x diberi nilai 2 (proses inisialisasi). Setelah itu x dibandingkan dengan N. Jika aksi (x<=N) bernilai benar maka x ditampilkan. Lalu x ditambah 2 dan menghasilkan x baru. 
Setelah itu arus data kembali ke atas untuk menguji apakah aksi x<=N bernilai benar. Jika iya, maka proses yang sama dengan sebelumnya dilakukan kembali. 
Demikian seterusnya hingga kondisi x<=N bernilai salah.
Jika N adalah 10 maka output algoritma deret : 2 4 6 8
Pertanyaan
Untuk N=10
- Bagaimana output algoritma jika x tidak diinisialisasi (perintah x  2 dihilangkan)?
Jawab : keluaran program menjadi 0  2  4  6  8
- Bagaimana output jika kondisi pengulangan diubah menjadi  while x > 10 ?
Jawab : Tidak ada output yang dihasilkan, karena kondisi sejak awal sudah tidak terpenuhi, sehingga aksi dalam loop while tidak ada yang dikerjakan
- Bagaimana output algoritma  jika aksi (xx+2) dihilangkan.?
Jawab : aksi (xx+2) memastikan bahwa kondisi pada suatu saat akan bernilai salah, sehingga pengulangan berhenti. Jika aksi ini dihilangkan, maka kondisi akan selalu bernilai benar, sehingga pengulangan tidak akan pernah berhenti.
- Bagaimana output algoritma jika aksi (xx+2) dan (write(x)) saling bertukar tempat (urutannya ditukar)?
Jawab : keluaran algoritma menjadi : 4   6   8   10
- Bagaimana output algoritma jika aksi (xx+2) diganti dengan (xx*2)?
Jawab : keluaran algoritma menjadi : 2   4   8


Flowchart Algoritma 2 10
Pengulangan Repeat-Until

Secara umum algoritma repeat-until adalah
repeat 
aksi
until <kondisi>

sedangkan bentuk flowchartnya      



Algoritma while-do dengan repeat-until sebenarnya hampir sama, perbedaannya hanya terletak pada penempatan kondisinya. Pada while-do pengecekan kondisi diletakkan di awal loop, sedangkan pada repeat-until pengecekan kondisi dilakukan di akhir loop. Itu sebabnya pada algoritma while-do aksi bisa jadi tidak dilakukan sama sekali jika sejak awal kondisinya sudah bernilai salah. Sedangkan pada pada repeat-until aksi sekurang-kurangnya dilakukan sebanyak satu kali. (Perhatikan flowchart). 
Studi Kasus
Pada Algoritma 2 10 kita telah mendemonstrasikan cara menampilkan deret 2, 4, 6, …, N. N adalah masukan berupa bilangan genap menggunakan pengulangan while-do. Berikut ini kita akan menggunakan algoritma repeat until untuk menyelesaikan persoalan tersebut.
Deskripsi masalah
Input : banyak deret (N)
Output : 2 4 6

Algoritma deret

Deskripsi
read(N)
x  2
repeat
write(x)
x  x + 2
until x>N



Perbandingan antara Algoritma For-Do, While-Do, dan Repeat-Until
Dari ketiga algoritma pengulangan yang sudah dibahas, for-do adalah jenis pengulangan yang sudah jelas banyaknya pengulangan. Itu sebabnya pengulangan for-do cocok digunakan untuk kasus dimana jumlah pengulangannya sudah jelas. Misalnya, kita ingin membuat algoritma menampilkan 10 suku pertama yang positif dari sebuah deret hitung dengan beda merupakan masukan. Jika deret hitung yang diinginkan memiliki beda sama dengan tiga, maka keluaran yang diharapkan adalah
3 6 9 12 15 18 21 24 27 30
Algoritma penyelesaian masalah ini adalah sebagai berikut.

Algoritma 2 11
Algoritma DeretHitung1

Deskripsi
Read(Beda)
Suku  0
For i  1 to 10 do
Suku  Suku + Beda
Write(Suku)
 
Berbeda dengan pengulangan for-do, tidak ada jaminan berhenti pada pengulangan while-do dan repeat-until kecuali dibuat suatu kondisi yang membuat algoritma tersebut berhenti pada suatu saat. Oleh karena itu di dalam pengulangan repeat dan while harus ada kondisi yang membatasi sampai kapan pengulangan tersebut berlangsung. Itu sebabnya pengulangan while dan repeat lebih cocok digunakan untuk kasus pengulangan yang belum jelas banyaknya pengulangan yang diinginkan, namun diketahui kondisi berhentinya.
Contoh.
x  0
while x < 20 do
xx+2
write(‘Halo’)
Perhatikan pengulangan while di atas. Banyaknya pengulangan tidak eksplisit dinyatakan oleh perintah while, tetapi kondisi berhentinya jelas, yaitu bila x>=20 (atau dengan kata lain terus melakukan pengulangan selama x<20). Keadaan yang sama juga bisa kita temukan pada pengulangan repeat until berikut :
x  0
repeat
xx+2
write(‘Halo’)
until x>=20
Pemrogram perlu berhati-hati menggunakan pengulangan while dan repeat karena ada kalanya kondisi berhentinya tidak akan pernah dicapai.
Lihat contoh program berikut
x  0
repeat
write(‘Halo’)
x = x + 3
until x = 10
Pengulangan ini tidak akan pernah berhenti karena nilai x tidak akan pernah memenuhi kondisi until x = 10. 
Demikian juga program berikut ini
x  0
while x < 20 do
write(‘Halo’)
tidak pernah berhenti karena kondisi while x < 20 selalu terpenuhi, sehingga pengulangan tidak akan berhenti.
Oleh karena itu, pemrogram harus lebih jeli dalam menggunakan pengulangan while-do atau repeat until untuk menghindari pengulangan tanpa batas.

Contoh lain. 
Misalkan kita ingin menampilkan suatu deret hitung dengan beda tertentu (input) yang deret tersebut berhenti sebelum jumlah deret tersebut mencapai suatu nilai batas. Suku pertama dari deret sama dengan beda. Beda dan batas merupakan masukan.  
Di sini kita tidak bisa memastikan berapa kali pengulangan (disebut juga iterasi) yang harus dilakukan. Karena input yang berbeda membutuhkan jumlah pengulangan yang berbeda pula. Misalnya, jika kita ingin menampilkan deret positif dengan beda 3 dan berhenti sebelum jumlah deret tersebut mencapai 50 maka deret dimaksud adalah
3 6 9 12 15
Jumlah deret di atas adalah 45, belum mencapai batas 50. Dalam hal ini pengulangan while-do merupakan pilihan yang lebih memudahkan.
Algoritma 2 12
Algoritma DeretHitung2

Deklarasi
Beda, Suku, Batas, Jum : integer

Deskripsi
Read(Beda, Batas)
Jum  0
Suku  0
While Jum < Batas
Suku  Suku + Beda
Jum  Jum+Suku
Write(Suku)
Lain halnya jika kondisi berhenti yang diinginkan adalah setelah jumlah deret tersebut melewati suatu nilai batas. Dengan input beda = 3 dan batas = 50 maka deret yang dimaksud adalah 
3 6 9 12 15 18
Dalam hal ini pengulangan repeat-until lebih memudahkan.
Algoritma 2 13
Algoritma DeretHitung3

Deklarasi
Beda, Suku, Jum, Batas : integer

Deskripsi
Read(Beda, Batas)
Jum  0
Suku  0
Repeat 
Suku  Suku + Beda
Jum  Jum+Suku
    Write(Suku)
Until Jum > Batas
Contoh lain. Dalam kasus tertentu bisa jadi semua cara ini bisa digunakan. Misalnya, algoritma menghitung perpangkatan XN, dengan X merupakan bilangan real dan N merupakan bilangan bulat positif. X dan N merupakan input. Kasus ini dapat diselesaikan dengan pengulangan for.
Algoritma 2 14
Algoritma XPangkatNFor

Deklarasi
N,i : integer 
X, Pangkat : real

Deskripsi
Read(X, N)
Pangkat  1
For i  1 to N do
Pangkat  Pangkat * X
Write (Pangkat)
Atau juga pengulangan while
Algoritma 2 15
Algoritma XPangkatNWhile

Deklarasi
N,i : integer 
X, Pangkat : real

Deskripsi
Read(X, N)
Pangkat  1
i  0
While i <= N
i  i + 1
Pangkat  Pangkat * X
Write (Pangkat)
Dan juga pengulangan repeat.
Algoritma 2 16
Algoritma XPangkatNRepeat

Deklarasi
N,i : integer 
X, Pangkat : real

Deskripsi
Read(X, N)
Pangkat  1
i  0
Repeat
i  i + 1
Pangkat  Pangkat * X
Until i > N
Jadi, sebenarnya agak sulit menentukan batasan yang tegas mengenai kasus mana yang cocok dikerjakan dengan for-do, atau while-do atau repeat-until. Pengalamanlah dan kebiasaan serta selera pemrogram yang lebih pandai  menjawab hal ini. 
Soal Latihan 
Soal Runtunan
1. Diketahui algoritma berikut ini
Algoritma UtakAtik1

Deskripsi
Read(A)
B  0.5 * A + 15
C  A * A -3
D  B + C
Write(B,C,D)
Tentukan keluaran algoritma jika 
a. A = 4 b.  A = 6 c. A = -3


2. Terjemahkan algoritma soal no 1 ke dalam bentuk flowchart
3. Diketahui algoritma berikut ini
Algoritma UtakAtik1

Deskripsi
Read(A,B)
C  0.5 * (A + B)
D  A * C - 3
E  C + D
Write(C,D,E)
Tentukan keluaran algoritma jika masukan A dan B masing-masing :
a. 5 dan 4 b. -2 dan 9 c. 3 dan 6
4. Terjemahkan algoritma no 3 ke dalam bentuk flowchart.
5. Buatlah algoritma teks dan flowchart yang menampilkan tulisan “Halo” sebanyak tiga kali
6. Setiap pegawai dalam perusahaan X mendapat penghasilan dari gaji pokok dan tunjangan. Besar tunjangan adalah 20% dari gaji pokok. Selain itu penghasilan tersebut terkena pajak yang besarnya 5% dari penghasilan. Buatlah algoritma menghitung penghasilan bersih pegawai dengan masukan gaji pokok.
7. Buatlah algoritma untuk menghitung luas segitiga sama sisi yang panjang sisi terpanjangnya sama dengan diameter sebuah lingkaran. Input : jari-jari lingkaran yang dimaksud.
8. Andi 8 tahun lebih tua dari Ali. Ali lebih muda 5 tahun dari Ahmad. Usia Amir adalah setengah dari jumlah usia Andi dan Ahmad. Buatlah algoritma menghitung usia Andi, Ali dan Amir, dengan masukan usia Ahmad.
9. Berkaitan dengan soal no, 8. Tuliskan keluaran algoritma tersebut jika masukannya : 
a. 45 b. 28 c. 36 
10. Buatlah algoritma teks untuk menghitung besar hambatan pengganti untuk tiga buah hambatan yang dipasang secara paralel. Input : ketiga hambatan R1, R2, R3.
11. Buatlah algoritma untuk mengkonversi waktu dari satuan jam, menit, dan detik ke dalam satuan detik.
12. Berkebalikan dengan soal no 11, buatlah algoritma yang mengkonversi waktu dari satuan detik ke dalam satuan jam, menit, dan detik.  
13. PT Telkom memberlakukan ketentuan tarif percakapan lokal sebesar Rp 50/menit sedangkan interlokal Rp 100/menit. Selain itu pelanggan juga dikenai biaya abonemen sebesar Rp 500 dan pajak sebesar 10% dari total tagihan. Buatlah algoritma menghitung biaya rekening telpon dengan masukan lama percakapan lokal dan interlokal (dalam menit).

Soal Percabangan
1. Tentukan keluaran dari algoritma teks berikut ini
Algoritma UtakAtik3

Deskripsi
Read(A,B)
      If A>B then 
    C  A*B
else
  C  A+B
D  C*C
Write(C,D)
Diketahui masukan A dan B masing-masing adalah :
a. 4 dan 6 b. 3 dan 5 c. 9 dan 6

2. Tentukan keluaran dari algoritma teks berikut ini
Algoritma UtakAtik3

Deskripsi
Read(A,B)
if A+B < 10 then 
    C  A-B
else
  C  A+B
D  2*C+B
Write(C,D)
Diketahui masukan A dan B masing-masing adalah :
b. 4 dan 6 b. 3 dan 5 c. 9 dan 6

3. Buatlah algoritma teks dan flowchart untuk menyelesaikan masalah berikut ini
a. Menginput sebuah bilangan kemudian menentukan apakah sebuah data masukan merupakan bilangan kelipatan tiga atau bukan.
b. Menginput dua bilangan kemudian menentukan manakah yang merupakan bilangan terbesar.
c. Menginput dua buah bilangan kemudian menentukan apakah bilangan yang satu merupakan kelipatan dari bilangan yang lainnya atau tidak. 
d. Menginput sebuah bilangan dan menentukan apakah ia bilangan positif atau bukan

4. Buatlah algoritma teks dan flowchart yang menentukan apakah sebuah persamaan kuadrat memiliki akar-akar yang real atau tidak.

5. Sebuah warnet memberlakukan ketentuan tarif sebagai berikut. Untuk penyewaan selama 3 jam pertama dikenai tarif Rp 5000 per jam. Sedangkan untuk jam berikutnya dikenai biaya Rp 4000 per jam. Buatlah algoritma yang menghitung biaya penyewaan warnet dengan masukan lama pemakaian.


6. PLN memberikan ketentuan tarif per kwh berdasarkan golongan konsumen sebagai berikut
Gol A : tarif per kwh = Rp 20, abonemen = 5000
Gol B : tarif per kwh = Rp 30, abonemen = 7500

Buatlah algoritma teks standar untuk menentukan total tagihan yang dibayar oleh pelanggan PLN. Input algoritma : jumlah pemakaian (kwh) dan golongan. Output : total tagihan.
7. Sebuah provider internet memberikan penawaran tarif langganan sebagai berikut. Untuk pemakaian hingga 50 jam pertama dikenai biaya Rp 5000. Untuk pemakaian lebih dari itu, setiap jam kelebihannya dikenai biaya tambahan Rp 5. Tuliskan algoritma menghitung biaya internet itu dengan masukan lama pemakaian.

8. Seorang salesman sebuah produk mendapat gaji dari perusahaannya terdiri dari gaji pokok dan bonus. Besar gaji pokok adalah 5000. Jika produk yang terjual lebih dari 100, salesman tersebut mendapat bonus sebesar 20% omset penjualan, sedangkan jika kurang mendapat 10% dari omset. Buatlah program menghitung gaji salesmen dengan masukan banyaknya produk yang terjual dan harga satuan produk.


Soal Pengulangan
1. Perhatikan algoritma berikut ini
Algoritma UtakAtik5

Deskripsi
Read(N)
      y0
z0 
For x  1 to N do 
    y  y +
z  z + y
  write(x,y,z)
a. Tuliskan keluaran algoritma untuk N=5
b. Tuliskan algoritma di atas menggunakan pengulangan while dan repeat

2. Perhatikan algoritma berikut ini

Algoritma UtakAtik6

Deskripsi
Read(N,k)
      i0
j0 
while i <= N do 
    i  i + 1
j  j + k
  write(j)
a. Tentukan keluaran algoritma untuk (N,k) =(5,2)
b. Nyatakan algoritma tersebut dalam pengulangan repeat dan while

3. Perhatikan algoritma berikut ini

Algoritma UtakAtik6

Deskripsi
Read(M,N)
      repeat 
  if i<5 then
  jj+M
    else
  jj+N
  i  i + 1
  write(j)
until i>8
a. Tentukan keluaran algoritma jika M,N = 2,1
b. Nyatakan algoritma tersebut dalam pengulangan for dan while

4. Buatlah algoritma dan flowchart persoalan berikut. Gunakan pengulangan for, while, dan repeat.
a. Menampilkan deret bilangan kelipatan tiga positif hingga lima suku pertama
b. Menghitung jumlah deret pada soal (a)

5. Buatlah algoritma dan flowchart yang menampilkan deret kelipatan X hingga N suku. X dan N masukan.

6. Buatlah algoritma yang menampilkan deret fibonaci (1  1  2  3  5  8  …) hingga N suku. Input N.


Untuk Mendownload Materi ini, klik Disini

0 comment:

Post a Comment

 
×
ISUZU ELF NMR