Repetisi)

Minggu IV : Teori dan Workshop

PERULANGAN (LOOP/Iterasi/Repetisi)

Motivasi n

n n

Sangat banyak kegiatan sehari-hari yang sering diulang. Contoh : Makan sepiring akan dilakukan sesendok demi sesendok (berulang). n n n n

Kondisi awal : sepiring nasi Yang diulang : makan sesendok nasi Kondisi berikutnya : sepiring – sesendok nasi Kondisi akhir : nasi habis

Aritmetika n

Untuk menghitung 2 x 3 dilakukan dengan menjumlah 2 sebanyak 3 kali (2 ditambah 2 ditambah 2) n n n n

Kondisi awal ? Yang diulang ? Kondisi berikutnya ? Kondisi akhir ?

Ada yang berkurang vs ada yang bertambah n n n

n

n

Kondisi awal : berada di rumah Kondisi akhir : sampai di kampus Yang diulang : jalan kaki selangkah demi selangkah Yang berkurang : jarak rumah à kampus Yang bertambah : banyaknya langkah yang telah dilakukan

n

n

Komputer mempunyai kemampuan untuk menghitung perulangan dengan sangat cepat dan tidak mengenal lelah. Kadang diperlukan suatu kondisi untuk menghitung dengan perulangan sampai presisi tertentu.

Konsep Counter n

n

Perhatikan penugasan berikut ini : ißi+1 C++ : i++; Atau ++i;

Operator Increment dan Decrement Operator increment dan decrement digunakan dalam ekspresi aritmetika Postfix int hasil, bilangan = 10; hasil = 2 * bilangan++; cout << hasil << endl; cout << bilangan << endl;

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

Output: 20 11

22 11

Konsep Total n

Misalnya kita diminta untuk menghitung jumlah deret : n 1 + 2 + 3 + … + n = ∑i i =1

n

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

Konsep Total (lanjutan) n

Algoritmik : jumlah ß 0 for i ß 1 to n do jumlah ß jumlah + i

n

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

Konsep Total Perkalian n n

n

Misalkan kita diminta menghitung : n i n! = 1 . 2 . 3 . … n = ∏ i =1 Harga awal : 1 (unsur identitas perkalian)

n

Algoritmik faktorial ß 1 for i ß 1 to n do faktorial ß faktorial * i

n

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

Pemrograman Algoritmik for i ß awal to akhir do aksi end for for i ß awal downto akhir do aksi end for while (kondisi) do aksi end while repeat aksi until (kondisi)

C++ for (i = awal; i <= akhir; i++) aksi; for (i = awal; i <= akhir; i--) aksi; while (kondisi) aksi; do { aksi; } while (kondisi);

Contoh pernyataan for n

Tidak sah:

for (j = 0, j < n, j = j + 3) for (j = 0; j < n)

// semicolon diperlukan

// bagian ketiga diperlukan

for – Ekspresi Null Contoh 1:

n

• Contoh 2:

j = 1; sum = 0; for ( ; j <= 10; j = j + 1) sum = sum + j; 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 loop Output bilangan genap < 12 Ketika x berharga 12, evaluasi ekspresi menjadi false

x = 2; while ( x != 12 ) { cout << x << “ “; x = x + 2; } Program Output: 2 4 6 8 10

Example: infinite loop Outputs odd bilangans < 12 x tidak pernah berharga 12, sehingga ekspresi selalu true

x = 1; while ( x != 12 ) { cout << x << “ “; x = x + 2; Loop akan } Program Output:

terus berulang !

1 3 5 7 9 11 13 15 . . .

Perulangan while dan do-while Perbedaan antara keduanya : saat pengecekan ekspresi ! while loop: while ( Expression ) { Statement_1; Statement_2; . . . . Statement_Last; }

do-while loop: do { Badan loop

Ekspresi dievaluasi sebelum badan loop dieksekusi. Badan loop bisa saja tidak dieksekusi.

Statement_1; Statement_2;

Badan loop

. . . . Statement_Last; } while ( Expression ); Ekspresi dievaluasi sesudah badan loop dieksekusi. Badan loop setidakna diekseskusi sekali.

for Loop for loop adalah pre-test loop – ekspresi dites before setiap iterasi Format: Badan loop adalah sebuah blok for (initialisasi; tes; update ) { Statement_1; Statement_2; . . . }

Badan loop adalah pernyataan tunggal for (initialisasi; tes; update ) Statement;

1. Eksekusi ekspresi inisialisasi dilakukan hanya sekali 2. Evaluasi ekspresi tes If true, go to 3. If false, loop berakhir. 3. Eksekusi badan loop 4. Eksekusi ekspresi update Kembali ke 2.

for Loop Untuk 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 berlanjut sepanjang bernilai true

for ( Inisialisasi; Ekspresi_Tes; Ekspresi_Update) Cek untuk akhir loop

increment setiap kali badan loop dieksekusi

for Loop Variabel update yang berbeda

Variabel n didecrement 7 setiap kali iterasi

for ( n = 0; n >= -100; n = n – 7 ) cout << “n is now equal to “ << n << endl;

Mendeklarasikan variabel saat inisialisasi Variabel n lokal terhadap badan loop

for ( int n = 1; n <= 10; n++ ) { Skope sum = sum + n; cout << sum << endl; variabel n }

Lebih dari 1 pernyataan dalam inisialisasi for ( int ct = 1, total = 0.0; ct <= 5; ct ++ ) ct dan total { diinisialisasi cout << “Enter the sales for day “ << ct << endl; cin >> sales; multiple inisialisasi dipisah total += sales; dengan koma }

Loop Bersarang loop bersarang : loop yang berada di dalam loop yang lain for ( int hours = 0; hours < 24; hours++ ) 3 levels of nesting { for ( int minutes = 0; minutes < 60; minutes++ ) { for ( int seconds = 0; seconds < 60; seconds++ ) { cout << setw(2) << hours << “:”; cout << setw(2) << minutes << “:” cout << setw(2) << seconds << endl; } } }

Indentasikan setiap level sub pernyataan bersarang

Inner loop akan menjalani iterasi untuk setiap iterasi outer loop

Contoh loop bersarang int y,z; for (y = 5; y > 0; y--) { cout << "\nKuliah."; for (z = 1; z < 3; z++) cout <<"\tAlgoritma.\t"; cout << “**“; }

Eksekusi 1 2 3 4 4 2 3 4 4 2 3 4 4 2 3 4 4 2 3 4 4 2 7

5 546 5 546 5 546 5 546 5 546

Pernyataan break dan continue break statement causes a loop to terminate early while ( ++count <= 10 ) { Reads in 10 negative cin >> bilangan; bilangans, computes When break is executed, the loop ends if ( bilangan >= 0 ) sum { immediately and cout << “Error: positive bilangan”; execution continues break; with statement following the loop } sum += bilangan; Exit loop }

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

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

}

1 2 3 5 6 7

if ( testVal == 4 ) continue; cout << testVal << “ “;

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”; Output Nilai j adalah 60 Keluar dari loop. n Deretan eksekusi : n 1 2 3 4 6 7 n

1 2 3 4 5 8

Pernyataan continue int j =50; while (j < 80) { j += 10; if (j == 70) continue; continue cout << “Nilai j adalah “ << j<< ‘\n’; } cout << “Keluar dari loop.\n”; nOutput

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

break dan continue while ( - - - ) { statement-1; if( - - - ) continue statement-2; } statement-3;

while ( - - - ) { statement-1; if( - - - ) break statement-2; } statement-3;

Designing Loops Loop design consists of three parts

1 – the body of the loop 2 – the initializing statements 3 – the conditions for ending the loop

Loop body repeats a predetermined bilangan of pseudocode: implemented as a for loop: times sum = 0 repeat this_many times read value into next sum = sum + next end of loop

int sum = 0; Initialize to 0 for ( int ct = 1; ct <= this_many; ct++ ) { Loop terminates cin >> next; when this is false sum = sum + next; }

Compute the product of a list of bilangans Not initialized to 0 int product =1; for ( int ct = 1; ct <= this_many; ct++) { First time through loop cin >> next; product * next should = next product = product * next; }

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 Deskripsi Deskripsi for i ß 1 to 4 do iß1 iß1 write (i) while (i <= 4) do repeat endfor write (i) write (i) ißi+1 ißi+1 endwhile until (i > 4)

Perhatikan perbedaan ketiga flowchart berikut : Mulai

for i = 1 to 4 do

Mulai

Mulai

i =1

i =1

F i

i <= 4

i

T Selesai

i = i+1

i F i>4 i = i+1 T

Struktur for

Selesai

Selesai

Struktur while

Struktur repeat - until

for loop

while loop

do while loop

#include main() { int i; for (i=1; i<=4; i++) cout << “ “ << i; return 0; }

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

#include 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 Deskripsi Deskripsi for i ß 0 to 10 do iß1 iß1 if (i mod 2 = 1) while (i <= 10) do repeat then write (i) write (i) write (i) ißi+2 ißi+2 endif endwhile until (i > 10) endfor

Beberapa cara : Alternatif for #include

Alternatif while #include

Alternatif do while #include

main() { main() { main() { for (int i=0; i<=10; i++) int i=1; int i=1; { while (i<=10) do { if (i % 2 == 1) { if (i % 2 == 1) cout << i << endl; if (i % 2 == 1) cout << i << endl; } cout << i << endl; i++; return 0; i++; } while (i<=10); } } return 0; return 0; } }

Aplikasi Perulangan kerap digunakan untuk menghitung jumlah deret. Contoh : n Hitung jumlah dari : n i 1+2+3+… + n = ∑ i =1 n Kuncinya : buat pola untuk rumus di sebelah kanan ! n Untuk operasi perkalian menggunakan tanda ∏ n

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 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

n

Bilangan Fibonacci dapat disajikan sebagai berikut : 0, 1, 1, 2, 3, 5, 8, … 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

n

Ketika kita menghitung suku ke-3 (F(3)) maka suku ke-1 sebenarnya sudah tidak digunakan. Untuk itu kita bisa “menggeser tempat” : f1 ß f2 f2 ß f3 Lalu berulang kita hitung suku berikutnya : f3 ß f2 + f1 Buat algoritma fibonacci dan flowchartnya !

Bahasa C++

#include #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

n

Perulangan while cocok untuk situasi di mana badan loop tidak semuanya dieksekusi Perulangan do - while cocok untuk situasi di mana badan loop sekurangkurangnya dieksekusi satu kali

Kasus 4.3.

Carilah rata-rata dari n bilangan bulat positif.

Analisis : n Rumus rata-rata adalah : n

∑x i =1

i

n n

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

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 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 !

Sentinel n

n

n

Digunakan bila banyaknya masukan tidak diketahui, tetapi sifat datanya diketahui. Untuk menghentikan masukan, digunakan harga lain. 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 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. y x Hitunglah nilai dari dengan x bilangan real dan y bilangan bulat. n

n n

y Analisis : x y ∏ x = x . x . x . … x (sebanyak y kali) = i =1 Input : x dan y Output : hasil x pangkat y

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 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; }

Hanya saja, algoritma ini khusus untuk y ≥ 0. Latihan : n Sempurnakan algoritma tersebut agar dapat menghitung pangkat y negatif. n

Kasus 4.8.

Hitunglah axb dengan metode penjumlahan

Analisis : axb = a + a + … + a (sebanyak b kali) b = ∑a i =1 n Ini berlaku untuk a positif maupun negatif n Bagaimana bila b negatif ?

n

n n

n

Karena loop “tidak pernah negatif” maka harus dimanipulasi perulangan yang “selalu” positif. Untuk itu nilai b menjadi abs(b) Kemudian khusus untuk b < 0, jumlah yang sudah diperoleh dinegatifkan Ingat : ax(-b) = ax(-1)xb = -axb

Bahasa C++ #include #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

n

Loop invariant digunakan untuk membuktikan bahwa loop for adalah benar Karakteristik : n

n

Benar pada suatu titik (pernyataan) pada setiap iterasi loop Benar bila loop berhenti membuktikan loop bekerja secara benar.

Contoh :

program untuk mencari nilai minimum dari sederetan input Bahasa C++ #include 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

n

n

Kondisi : min <= n selalu benar sebab sebelum pernyataan if mengubah harga min jika harga input terakhir dari n kurang dari harga min sebelumnya. 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. Akhirnya : kondisi benar ketika loop berakhir diperoleh nilai minimum dari semua input

Rangkuman n

Minggu Depan : SUBPROGRAM

Mengakhiri perulangan n

Secara umum, perulangan dapat diakhiri dengan cara : n

n

n

n

Dikontrol counter : banyaknya iterasi ditentukan sebelum perulangan dimulai Ditanyakan lebih dulu sebelum iterasi : pengguna ditanya setiap kali iterasi apakah dilanjutkan atau tidak Keluar dengan “tanda” (flag) : harga variabel berubah pada saat perulangan. Bila sudah berubah sesuai dengan kondisi keluar, maka perulangan berhenti

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');

Contoh Flag bilangan = 0; while ( bilangan != 999 ) { total = total + bilangan; cout “\nTotal saat ini“ << total; cout << “Masukkan bilangan: “; cin >> bilangan; }

Contoh Flag flag = 1; while ( flag ) { total = total + bilangan; cout “\nTotal saat ini “ << total; cout << “Masukkan bilangan: “; cin >> bilangan; if( bilangan > 999) flag = 0; }

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 cout dalam badan loop : int next = 2; int prod = 1; while ( next < 5 ) Variabel { Trace next++; prod = prod * next; cout << “next = “ << next << “prod = “ << prod << endl; }

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!

Kesalahan umum ! while (balance != 0.0) { balance = balance - amount; } n balance may not become equal zero due to bilangan inaccuracies while (power <= 1000) { cout << "Next power of N is " << power << endl; power *= n; } n

pastikan variabel sudah diinisialisasi. Untuk penjumlahan 0 dan untuk perkalian 1

Latihan n

n

n

n

Buatlah algoritma dan program untuk mencetak bilangan yang habis dibagi 3 dan 5 antara 1 sampai dengan 100. Hitunglah nilai dari : 1 1 1 1 1− + − +L + 2 3 4 n

[Sentinel] Buatlah algoritma untuk menentukan nilai terkecil, terbesar, dan jumlah semua bilangan positif yang dimasukkan. Buatlah algoritma untuk menentukan nilai terbesar t sedemikian sehingga : 12 + 22 + … + t2 < 2000

Bahan Diskusi Buat simulasi membeli tiket masuk kebun binatang dengan spesifikasi : n Input berupa : n n

n

n n

Pilihan perorangan/ rombongan Perorangan, berapa orangtua, berapa anak-anak (50% orangtua) Rombongan, banyak orang tua+ anak, diskon 25%

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

Banyak tiket orang tua, dan tiket anak Banyak rombongan beserta jumlah tiketnya

Ketentuan program n n

n n

Dibuat menggunakan class Input dan output menggunakan operator overloading dan dibuat cukup informatif untuk pengguna Tidak menggunakan ARRAY Tidak diperkenankan menggunakan SATU FILE untuk seluruh program

Laporan (selain listing program) n n n n

Deskripsi masalah Analisis permasalahan Algoritma Print out uji coba berupa : n n

Masukan Keluaran

Bacaan n

[S5] n n n n

n

6.5 while Statement : Fibonacci 6.6 break Statement 8.1 for Statement 8.2 switch Statement

Tunjukkan catatan pinggir saat masuk kelas