Minggu IV : Teori dan Workshop

PERULANGAN (LOOP/Iterasi/Repetisi)

Motivasin Sangat banyak kegiatan sehari-hari yang

sering diulang.n Contoh : n Makan sepiring akan dilakukan sesendok

demi sesendok (berulang).n Kondisi awal : sepiring nasin Yang diulang : makan sesendok nasin Kondisi berikutnya : sepiring – sesendok nasin Kondisi akhir : nasi habis

Aritmetika

n Untuk menghitung 2 x 3 dilakukan dengan menjumlah 2 sebanyak 3 kali (2ditambah 2 ditambah 2)n Kondisi awal ?n Yang diulang ?n Kondisi berikutnya ?n Kondisi akhir ?

Ada yang berkurang vs ada yangbertambah

n Kondisi awal : berada di rumahn Kondisi akhir : sampai di kampusn Yang diulang : jalan kaki selangkah

demi selangkahn Yang berkurang : jarak rumah à

kampusn Yang bertambah : banyaknya langkah

yang telah dilakukan

n Komputer mempunyai kemampuan untuk menghitung perulangan dengan sangat cepat dan tidak mengenal lelah.

n Kadang diperlukan suatu kondisi untuk menghitung dengan perulangan sampai presisi tertentu.

Konsep Countern Perhatikan penugasan berikut ini :

i ß i + 1n C++ :

i++;Atau

++i;

Operator Increment dan Decrement

Operator increment dan decrement digunakan dalam ekspresi aritmetika

int hasil, bilangan = 10;hasil = 2 * bilangan++;cout << hasil << endl;cout << bilangan << endl;

int hasil, bilangan = 10;hasil = 2 * ++bilangan;cout << hasil << endl;cout << bilangan << endl;

Output:2011

Output:2211

Postfix Prefix

Konsep Totaln Misalnya kita diminta untuk menghitung

jumlah deret :1 + 2 + 3 + … + n =

n Harga awal : i dimulai dengan 0 (unsur identitas penjumlahan)

1=∑

n

ii

Konsep Total (lanjutan)n Algoritmik :

jumlah ß 0for i ß 1 to n do

jumlah ß jumlah + in C++ :

jumlah = 0;for (i = 1; i<=n; i++)

jumlah += i;

Konsep Total Perkaliann Misalkan kita diminta menghitung :n n! = 1 . 2 . 3 . … n =

n Harga awal : 1 (unsur identitas perkalian)

1=∏

n

ii

n Algoritmikfaktorial ß 1for i ß 1 to n do

faktorial ß faktorial * in C++

faktorial = 1;for (i = 1; i<=n; i++)

faktorial *= i;

PemrogramanAlgoritmik C++

for i ß awal to akhir do aksi

end for

for (i = awal; i <= akhir; i++) aksi;

for i ß awal downto akhir do aksi

end for

for (i = awal; i <= akhir; i--) aksi;

while (kondisi) do aksi end while

while (kondisi) aksi;

repeat aksi

until (kondisi)

do { aksi;

} while (kondisi);

n Tidak sah:

for (j = 0, j < n, j = j + 3) // semicolon diperlukan

for (j = 0; j < n) // bagian ketiga diperlukan

Contoh pernyataan for

for – Ekspresi Null

nContoh 1: j = 1;sum = 0;for ( ; j <= 10; j = j + 1)

sum = sum + j;

• Contoh 2: j = 1;sum = 0;for ( ; j <= 10; )

sum = sum + j;

Contoh 3: j = 1;sum = 0;for ( ; ; ){ sum = sum + j; j++;

cout << "\n" << sum;}

Menghentikan Loop

terminating loopOutput bilangan genap < 12

x = 2;while ( x != 12 ){

cout << x << “ “;x = x + 2;

}

Example: infinite loopOutputs odd bilangans < 12

x = 1;while ( x != 12 ){

cout << x << “ “;x = x + 2;

}

2 4 6 8 10

Program Output:

1 3 5 7 9 11 13 15 . . .

Program Output:

x tidak pernah berharga12, sehingga ekspresiselalu true

Ketika x berharga 12, evaluasi ekspresimenjadi false

Loop akan terusberulang !

Perulangan while dan do-whilePerbedaan antara keduanya : saat pengecekan ekspresi !

while ( Expression ){

Statement_1;Statement_2;. . . .Statement_Last;

}

while loop: do-while loop:do{

Statement_1;Statement_2;. . . .Statement_Last;

} while ( Expression );Ekspresi dievaluasi sebelumbadan loop dieksekusi.

Badan loop bisa saja tidak dieksekusi.

Ekspresi dievaluasi sesudahbadan loop dieksekusi.

Badan loop setidakna diekseskusisekali.

Badanloop

Badanloop

for Loop

Format:Badan loop adalah sebuah blok

for (initialisasi; tes; update ){

Statement_1;Statement_2;. . .

}

Badan loop adalah pernyataan tunggal

for (initialisasi; tes; update )Statement;

for loop adalah pre-test loop – ekspresi dites beforesetiap iterasi

1. Eksekusi ekspresi inisialisasi dilakukan hanya sekali

2. Evaluasi ekspresi tesIf true, go to 3.If false, loop berakhir.

3. Eksekusi badan loop

4. Eksekusi ekspresi updateKembali ke 2.

for LoopUntuk menambah 1 sampai 10 lakukan pernyataan berikut 10 kali

sum = sum + n;

Menggunakan while :sum = 0;n = 1;while ( n <= 10 ){

sum = sum + n;n++;

}

Menggunakan for :sum = 0;for ( n = 1; n <= 10 ; n++ )

sum = sum + n;n diinitialisasi1

loop berlanjutsepanjang bernilai true

increment setiap kali badan loop dieksekusi

for ( Inisialisasi; Ekspresi_Tes; Ekspresi_Update)

Cek untuk akhir loop

for Loop

Mendeklarasikan variabel saat inisialisasifor ( int n = 1; n <= 10; n++ ){

sum = sum + n;cout << sum << endl;

}

Variabel n lokalterhadap badanloop

Variabel update yang berbedafor ( n = 0; n >= -100; n = n – 7 )

cout << “n is now equal to “ << n << endl;

Lebih dari 1 pernyataan dalam inisialisasifor ( int ct = 1, total = 0.0; ct <= 5; ct ++ ){

cout << “Enter the sales for day “ << ct << endl;cin >> sales;total += sales;

}

ct dan total diinisialisasi

multiple inisialisasi dipisahdengan koma

Variabel n didecrement 7 setiap kali iterasi

Skopevariabel n

Loop Bersarang

loop bersarang : loop yang berada di dalam loop yang lain

for ( int hours = 0; hours < 24; hours++ ){

}

for ( int minutes = 0; minutes < 60; minutes++ ){

}

3 levels of nesting

Indentasikan setiap level sub pernyataan bersarang

for ( int seconds = 0; seconds < 60; seconds++ ){

cout << setw(2) << hours << “:”;cout << setw(2) << minutes << “:”cout << setw(2) << seconds << endl;

}

Inner loop akan menjalani iterasi untuk setiap iterasi outer loop

int y,z;for (y = 5; y > 0; y--){ cout << "\nKuliah.";

for (z = 1; z < 3; z++)cout <<"\tAlgoritma.\t";

cout << “**“;}

Contoh loop bersarang

Eksekusi1 2 3 4 5

4 5 4 62 3 4 5

4 5 4 62 3 4 5

4 5 4 62 3 4 5

4 5 4 62 3 4 5

4 5 4 62 7

Pernyataan break dan continuebreak statement causes a loop to terminate early

while ( ++count <= 10 ){

cin >> bilangan;if ( bilangan >= 0 ){

cout << “Error: positive bilangan”;break;

}sum += bilangan;

}

When break is executed, the loop ends immediately and execution continues with statement following the loop

Reads in 10 negative bilangans, computes sum

continue statement causes loop to stop current iteration and begin next one while ( testVal++ < 7 )

{if ( testVal == 4 )

continue;cout << testVal << “ “;

}

Exit loop

Ketika testVal = 4, continue dieksekusi dan cout diloncati, lalu iterasi berikutnya mulai

1 2 3 5 6 7

Pernyataan break

int j =50;while (j < 80){

j += 10;if (j == 70)

break;cout << “Nilai j adalah “ << j<< ‘\n’;

}cout << “Keluar dari loop.\n”;

n OutputNilai j adalah 60Keluar dari loop.n Deretan eksekusi :n 1 2 3 4 6 7 1 2 3 4 5 8

Pernyataan continue

int j =50;while (j < 80) {

j += 10;if (j == 70) continuecontinue;cout << “Nilai j adalah “ << j<< ‘\n’;

}cout << “Keluar dari loop.\n”; nOutput

Nilai j adalah 60Nilai j adalah 80Keluar dari loop.nSequence of execution:n 1 2 3 4 6 7 1 2 3 4 5n 1 2 3 4 6 7 1 8

break dan continue

while ( - - - ){

statement-1;if( - - - )

continuecontinuestatement-2;

}statement-3;

while ( - - - ){

statement-1;if( - - - )

breakbreakstatement-2;

}statement-3;

Designing Loops

Loop body repeats a predetermined bilangan of times

int product =1;for ( int ct = 1; ct <= this_many; ct++){

cin >> next;product = product * next;

}

Compute the product of a list of bilangans

pseudocode:sum = 0repeat this_many times

read value into nextsum = sum + next

end of loop

implemented as a for loop:int sum = 0;for ( int ct = 1; ct <= this_many; ct++ ){

cin >> next;sum = sum + next;

}

Not initialized to 0

First time through loop product * next should = next

Initialize to 0

1 – the body of the loop2 – the initializing statements3 – the conditions for ending the loop

Loop design consists of three parts

Loop terminates when this is false

Kasus 4.1.Cetaklah bilangan 1 sampai 4

Algoritma Cetak_Angka {Mencetak angka 1, .., 4 ke piranti keluaran}

Deklarasi i : integer

for loop while loop repeat until loop Deskripsi

for i ß 1 to 4 do write (i) endfor

Deskripsi i ß 1 while (i <= 4) do write (i) i ß i + 1 endwhile

Deskripsi i ß 1 repeat write (i) i ß i + 1 until (i > 4)

Perhatikan perbedaan ketiga flowchart berikut :

Mulai

for i = 1 to 4 do

i

Selesai

Selesai

Mulai

i =1

i = i+1

i <= 4F

T

Mulai

i =1

Selesai

i = i+1

i

i > 4F

T

i

Struktur for Struktur while Struktur repeat - until

for loop while loop do while loop #include <iostream.h> main() { int i; for (i=1; i<=4; i++) cout << “ “ << i; return 0; }

#include <iostream.h> main() { int i=1; while (i <= 4) { cout << “ “ << i; i++; } return 0; }

#include <iostream.h> main() { int i=1; do { cout << “ “ << i; i++; } while (i <= 4); return 0; }

Kasus 4.2.Cetaklah bilangan ganjil dari 0 sampai 10

Ide : n Bilangan ganjil dari 0 sampai 10 diawali

dengan 1, kemudian bertambah dengan 2 atau bilangan ganjil adalah bilangan yang bila dibagi 2 bersisa 1.

Algoritma Cetak Ganjil {Mencetak bilangan ganjil dari 0 sampai 10 ke piranti keluaran} Deklarasi i : integer Deskripsi

for i ß 0 to 10 do if (i mod 2 = 1) then write (i) endif endfor

Deskripsi i ß 1 while (i <= 10) do write (i) i ß i + 2 endwhile

Deskripsi i ß 1 repeat write (i) i ß i + 2 until (i > 10)

Beberapa cara :Alternatif for Alternatif while Alternatif do while

#include <iostream.h> main() { for (int i=0; i<=10; i++) { if (i % 2 == 1)

cout << i << endl; } return 0; }

#include <iostream.h> main() { int i=1; while (i<=10) { if (i % 2 == 1)

cout << i << endl; i++; } return 0; }

#include <iostream.h> main() { int i=1; do { if (i % 2 == 1)

cout << i << endl; i++; } while (i<=10); return 0; }

Aplikasin Perulangan kerap digunakan untuk

menghitung jumlah deret.Contoh :n Hitung jumlah dari :

1+2+3+… + n =n Kuncinya : buat pola untuk rumus di sebelah

kanan ! n Untuk operasi perkalian menggunakan tanda

∏

1

n

ii

=∑

Algoritma menjumlah deret Deklarasi

i, n, jumlah : integer Deskripsi

read(n) {menjumlah sampai suku ke-n} jumlah ß 0 { nilai awal/unsur identitas penjumlahan adalah 0} for i ß 1 to n do jumlah ß jumlah + i write(jumlah)

Bahasa C++ #include <iostream.h> main() { int n, jumlah = 0; cout << "Sampai berapa suku ? "; cin >> n; for (int i=0; i<=n; i++) jumlah += i; cout << "Jumlah deret sampai : " << n << " suku = " << jumlah; return 0; }

Cocok menggunakan perulangan for karena digunakan untuk kalkulasi bilanganerik dengan jumlah perulangan tertentu (fix)

Bilangan Fibonacci

n Bilangan Fibonacci dapat disajikan sebagai berikut :

0, 1, 1, 2, 3, 5, 8, …n Dimulai dari suku pertama = 0 dan

kedua = 1, suku ketiga adalah jumlah 2 suku pertama. Dalam rumus :

F(n) = F(n-1) + F(n-2)

Analisis :n Ketika kita menghitung suku ke-3 (F(3))

maka suku ke-1 sebenarnya sudah tidak digunakan. Untuk itu kita bisa “menggeser tempat” :

f1 ß f2f2 ß f3

n Lalu berulang kita hitung suku berikutnya : f3 ß f2 + f1

Buat algoritma fibonacci dan flowchartnya !

Bahasa C++ #include <iostream.h> #define true 1 int main() { long batas; cout << "Masukkan integer positif : "; cin >> batas; cout << "Bilangan Fibonacci < " << batas << ":\n0, 1"; long f1=0, f2=1; while (true) { long f3 = f2 + f1; if (f3 > batas) break; // menghentikan loop cout << ", " << f3; f1 = f2; f2 = f3; } return 0; }

Buat class Fibonacci dan methodnya !

n Perulangan while cocok untuk situasi di mana badan loop tidak semuanya dieksekusi

n Perulangan do - while cocok untuksituasi di mana badan loop sekurang-kurangnya dieksekusi satu kali

Kasus 4.3.Carilah rata-rata dari n bilangan bulat positif.

Analisis :n Rumus rata-rata adalah :

n yaitu jumlah data dibagi dengan banyaknya data, dengan xi adalah data ke-i.

1=∑

n

ii

x

n

Algoritma mencari rata-rata {Diberikan n data kemudian dicari rata-ratanya} Deklarasi

i, n, jumlah, x : integer rata : real

Deskripsi

read(n) jumlah ß 0 for i ß 1 to n do

read(x) jumlah ß jumlah + x

endfor rata ß jumlah/n write(rata)

Bahasa C++

#include <iostream.h> main() { int i, n, jumlah, x; float rata; cout << "Banyak data : "; cin >> n; jumlah = 0; for (i = 1; i<=n; i++) { cout << "Data ke- : " << i; cin >> x; jumlah += x; } rata = (float) jumlah/n; cout << "Rata-rata = " << rata; return 0; }

Buat class Rata dan methodnya !

Sentineln Digunakan bila banyaknya masukan tidak

diketahui, tetapi sifat datanya diketahui. n Untuk menghentikan masukan, digunakan

harga lain.n Contoh :

Bila masukan harga selalu positif (misalkan nilai mahasiswa), sentinel bisa nol atau harga negatif.

Kasus 4.4.Hitunglah rata-rata dari integer positif (banyak data ditentukan dari data yang dimasukkan)

Algoritma mencari rata-rata {Diberikan data bilangan bulat positif kemudian dicari rata-ratanya} Deklarasi

n, jumlah, x : integer rata : real

Deskripsi

jumlah ß 0 read(x) n ß 1 while (x>0) do

jumlah ß jumlah + x read(x) n ß n+1

endfor rata ß jumlah/(n-1) write(rata)

Bahasa C++

#include <iostream.h> main() { int n = 1, jumlah = 0, x; float rata; cout << "Data ke-1 : "; cin >> x; while (x>0) { jumlah += x; cout << "Data ke- : " << n+1; cin >> x; n++; } rata = (float)jumlah/(n-1); cout << "Rata-rata = " << rata; return 0; }

Buat class Rata dan methodnya !

Kasus 4.7.Hitunglah nilai dari dengan x bilangan real dan y bilangan bulat.

n Analisis := x . x . x . … x (sebanyak y kali) =

n Input : x dan yn Output : hasil x pangkat y

yx

yx 1=∏

y

i

x

Algoritma Pangkat {Diberikan masukan x dan y, dihitung

nilai dari x pangkat y}

Deklarasi x, y, i : integer { input }

pangkat : integer { output }

Deskripsi

read (x,y) pangkat ß 1 for i ß 1 to y do

pangkat ß pangkat * x enfor write (pangkat)

Buat class Pangkat dan methodnya !

Bahasa C++

#include <iostream.h> main() { int x, y, i; int pangkat = 1; cout << "Menghitung hasil perpangkatan\n"; cout << "Tulis sebuah bilangan : "; cin >> x; cout << "Mau dipangkat berapa : "; cin >> y; for (i = 1; i<=y; i++) pangkat *= x; cout << x << " pangkat “ << y << “ = “ << pangkat; return 0; }

n Hanya saja, algoritma ini khusus untuk y ≥ 0.

Latihan :n Sempurnakan algoritma tersebut agar

dapat menghitung pangkat y negatif.

Kasus 4.8.Hitunglah axb dengan metode penjumlahan

Analisis :axb = a + a + … + a (sebanyak b kali)

= n Ini berlaku untuk a positif maupun

negatifn Bagaimana bila b negatif ?

1

b

ia

=∑

n Karena loop “tidak pernah negatif” maka harus dimanipulasi perulangan yang “selalu” positif.

n Untuk itu nilai b menjadi abs(b)n Kemudian khusus untuk b < 0, jumlah

yang sudah diperoleh dinegatifkann Ingat : ax(-b) = ax(-1)xb = -axb

Bahasa C++ #include <iostream.h> #include <math.h> main() { int a, b, jumlah=0; cout << "Program menghitung perkalian dengan cara penjumlahan\n"; cout << "Masukkan nilai a : "; cin >> a; cout << "Masukkan nilai b : "; cin >> b; for (int i=1; i<=abs(b); i++) jumlah += a; if (b < 0) jumlah = -jumlah; cout << a << "x" << b << " = " << jumlah; return 0; }

Loop Invariant

n Loop invariant digunakan untuk membuktikan bahwa loop for adalah benar

n Karakteristik :n Benar pada suatu titik (pernyataan) pada

setiap iterasi loopn Benar bila loop berhenti membuktikan

loop bekerja secara benar.

Contoh :program untuk mencari nilai minimum dari sederetan input

Bahasa C++

#include <iostream.h> int main() { // mencari maksimum dari sederetan bilangan

int n, min; cout << "Masukkan bilangan positif(0 untuk selesai): "; cin >> n; for (min = n; n > 0; ) {

if (n < min) min = n; // INVARIANT: min <= n untuk semua n,

// dan min adalah 1 dari n bilangan cin >> n;

} cout << "min = " << min << endl; return 0;

}

n Kondisi : min <= n selalu benar sebab sebelum pernyataan if mengubah harga min jika harga input terakhir dari n kurang dari harga min sebelumnya.

n Kondisi : min satu dari n harga selalu benar sebab min diawali dengan harga pertama dan min berubah harganya hanya bila harga input n yang baru lebih kecil dari min.

n Akhirnya : kondisi benar ketika loop berakhir diperoleh nilai minimum dari semua input

Rangkuman

n Minggu Depan : SUBPROGRAM

Mengakhiri perulangann Secara umum, perulangan dapat diakhiri

dengan cara :n Dikontrol counter : banyaknya iterasi ditentukan

sebelum perulangan dimulain Ditanyakan lebih dulu sebelum iterasi : pengguna

ditanya setiap kali iterasi apakah dilanjutkan atau tidak

n Keluar dengan “tanda” (flag) : harga variabel berubah pada saat perulangan. Bila sudah berubah sesuai dengan kondisi keluar, maka perulangan berhenti

n Buat contoh dari masing-masing kasus di atas !

Menunggu respon pengguna

char jawab;do {

// pernyataan lain …cout << “Mau melanjutkan ? (y/t): ";cin >> jawab;

} while (jawab != ‘t');

bilangan = 0;while ( bilangan != 999bilangan != 999 ){

total = total + bilangan;cout “\nTotal saat ini“ << total;cout << “Masukkan bilangan: “;cin >> bilangan;

}

Contoh Flag

flag = 1;flag = 1;while ( flagflag ){

total = total + bilangan;cout “\nTotal saat ini “ << total;cout << “Masukkan bilangan: “;cin >> bilangan;if( bilangan > 999)

flag = 0;flag = 0;}

Contoh Flag

Melakukan debugging pada perulangan

n Bisa terjadi loop terjadi tak berhingga banyak. Agar loop dapat dikendalikan, dapat dilakukan trace (pelacakan) dengan cara :

Debuglah kode berikut :int next = 2;int prod = 1;while ( next < 5 ){

next++;prod = prod * next;

}

Variabel trace diletakkan pada coutdalam badan loop :

int next = 2;int prod = 1;while ( next < 5 ){

next++;prod = prod * next;cout << “next = “ << next

<< “prod = “ << prod << endl;}

Variabel Trace

Kesalahan umum !

while (balance != 0.0);{

balance = balance - amount;}n ini akan mengarah ke infinite loop!

for (n=1; n <= count; n++);{

cout << "hello" << endl;}n "hello" hanya dicetak sekali!

while (balance != 0.0) {balance = balance - amount;

}n balance may not become equal zero due to

bilangan inaccuracieswhile (power <= 1000) {

cout << "Next power of N is " << power << endl;power *= n;

}n pastikan variabel sudah diinisialisasi. Untuk

penjumlahan 0 dan untuk perkalian 1

Kesalahan umum !

Latihan n Buatlah algoritma dan program untuk

mencetak bilangan yang habis dibagi 3 dan 5 antara 1 sampai dengan 100.

n Hitunglah nilai dari :

n [Sentinel] Buatlah algoritma untuk menentukan nilai terkecil, terbesar, dan jumlah semua bilangan positif yang dimasukkan.

n Buatlah algoritma untuk menentukan nilai terbesar t sedemikian sehingga :

12 + 22 + … + t2 < 2000

1 1 1 112 3 4

− + − + +Ln

Bahan Diskusi

Buat simulasi membeli tiket masuk kebun binatangdengan spesifikasi :

n Input berupa :n Pilihan perorangan/ rombongann Perorangan, berapa orangtua, berapa anak-anak

(50% orangtua)n Rombongan, banyak orang tua+ anak, diskon 25%

n Input akan terus dimasukkan sampai tidak ada lagi pengunjung yang membeli tiket

n Output menyatakan :n Banyak tiket orang tua, dan tiket anakn Banyak rombongan beserta jumlah tiketnya

Ketentuan program

n Dibuat menggunakan classn Input dan output menggunakan

operator overloading dan dibuat cukup informatif untuk pengguna

n Tidak menggunakan ARRAYn Tidak diperkenankan menggunakan

SATU FILE untuk seluruh program

Laporan (selain listing program)

n Deskripsi masalahn Analisis permasalahann Algoritman Print out uji coba berupa :

n Masukann Keluaran

Bacaan

n [S5] n 6.5 while Statement : Fibonaccin 6.6 break Statement n 8.1 for Statement n 8.2 switch Statement

n Tunjukkan catatan pinggir saat masuk kelas