HUBUNGAN BERULANG

Bagian ini menyajikan contoh-contoh dan pola pemakaian skema pengulangan untuk 

persoalan deret yang rumusnya dapat dinyatakan dalam suatu hubungan berulang 

(reccurence relation). Bagian ini sekaligus menunjukkan keterbatasan analisis dan 

penulisan algoritma, yaitu yang menyangkut masalah ketelitian representasi bilangan 

riil pada komputer. Untuk melihat efek tersebut, harus dilakukan eksekusi pada mesin. 

Contoh 1: 

Hitunglah S = 1 - 1/2 + 1/3 - 1/4 + ... + 1/999 - 1/1000 Ide pertama yang muncul adalah menyatakan suku ke-i sebagai: 

                            Si = (-1)i+1/i 

Berikut ini adalah beberapa versi solusi, dengan penjelasannya: 

Penjelasan : 

1. Pengontrol pengulangan adalah sebuah bilangan integer i, i adalah next element. 

2. Perhatikan inisialisasi. Invarian dari i dan S. 

3. Program menghasilkan nilai jumlah deret nol, jika konstanta N bernilai negatif, N ≤ 0, dengan                 tambahan spesifikasi: Jumlah deret adalah 0 untuk N ≤ 0. 

4. Jika diimplementasikan dalam salah satu bahasa pemrograman, harus diperhatikan konversi type            sebab misalnya 1/2 adalah ekspresi integer, yang hasilnya adalah integer. 

 

Penjelasan: 

1. Pengontrol pengulangan adalah sebuah bilangan integer i, i adalah next element. 

2. Perhatikan inisialisasi. Invarian dari i dan S. Program benar dengan tambahan spesifikasi : N ≥ 1.  

Penjelasan: 

1. Merupakan modifikasi dari versi 2. Tampaknya, algoritma versi 1 sederhana, tetapi sebenarnya tidak     efisien karena mengandung proses pemangkatan yaitu perhitungan (-1)^(i + 1). Karena proses               pemangkatan ini gunanya hanya untuk mengubah tanda dari satu suku ke suku berikutnya, maka            harus dipikirkan cara lain yang lebih bagus untuk mengatur perubahan tanda ini. Pada algoritma            versi-2 ini, dipakai sebuah variabel tambahan TANDA yang harganya berubah-ubah, yaitu +1 atau        -1. 

2. Sebuah loop “while” di atas, merupakan penggabungan dari dua loop yang dijalankan secara                    bersamaan, yaitu loop dengan elemen pengontrol i dan tanda. 

Penjelasan: 

1. Pengontrol pengulangan adalah sebuah bilangan integer i, i adalah current element. 

2. Perhatikan inisialisasi: Invarian dari i dan S. 

3. Program benar dengan tambahan spesifikasi N ≥ 2.  

Contoh 2: FAKTORIAL 

Hitunglah n! 

Dari definisi:     0! = 1 

                          1! = 1 

                          2! = 2 x 1! = 2 x 1 = 2 

                          3! = 3 x 2! = 3 x 2 = 6 

                          4! = 4 x 3! = 4 x 6 = 24 

                          ... 

                          n! = n x (n-1)! = n x (n-1) x ... x 3 x 2 x 1 

Hubungan berulang: 

                                       Fo = 1 

                                    Fi = i * Fi-1 

Solusi 1: