Jawaban dan Penjelasan:

Persoalan:
Ipin, Upin, Ikhsan, Memei, Jarjit, Susanti, Mail, dan Fizi berlomba memetik buah rambutan. Yang mendapatkan buah rambutan terbanyak itu pemenangnya. Sang pemenang akan memberikan semua buah rambutannya kepada kak Ros.

• Buatlah algoritma untuk menentukan berapa buah rambutan yang diterima oleh kak Ros!
• Tentukan jumlah langkah tiap baris algoritma!
• Tentukan G(n)!

Identifikasi Permasalahan

Persoalan ini adalah persoalan menentukan nilai bilangan terbesar dari sebuah koleksi data nilai bilangan. Kita dapat menggunakan struktur data array, atau dengan pembandingan langsung setelah input setiap nilai. Nilai bilangan merepresentasikan banyak buah rambutan yang berhasil dipetik oleh Ipin, Upin, Ikhsan, Memei, Jarjit, Susanti, Mail, dan Fizi. Sehingga, terdapat 8 elemen data banyak buah rambutan, dengan tipe elemen bilangan bulat (integer).

________________________

Alternatif 1

Kita dapat menggunakan algoritma secara iteratifataurekursif. Untuk membedakan dengan algoritma max(a, b) yang berfungsi untuk menentukan nilai terbesar dari dua bilangan a dan b, algoritma menentukan nilai terbesar pada array kita namakan maxi(A, n) untuk jenis iteratif, dan maxr(A, n) untuk jenis rekursif.
Agar sepadan, variabel n yang merupakan banyak elemen pada array A, ditentukan di luar fungsi.

Asumsi: kita sudah memiliki algoritma max(a, b), yaitu:
function max(a: integer, b: integer) → integer
   if a > b then
       → a
   else
       → b

Algoritma Iteratif
function maxi(A: array of integer, n: integer) → integer
   m ← A[1]
   for i = 2 to n do
        m ← max(m, A[i])
   end for
   → m

Algoritma Rekursif
function maxr(A: array of integer, n: integer) → integer
   if n = 1 then
       → A[1]
   else
       → max(A[n], maxr(A, n–1))

ALGORITMA PROGRAM UTAMA (Alternatif 1)

Program BuahRambutanKakRos1
Kamus:
   A: array[8] of integer
   m: integer
Algoritma:
   { input }
   for i ← 1 to 8 do
       input(A[i])
   end for
   { mencari nilai terbesar }
   m = maxr(A, 8)
   output(m)

Catatan: dapat juga menggunakan maxi(A, 8).

Banyak Langkah

Untuk fungsi maxi(A, n) dan maxr(A, n), banyak langkahnya sama, yaitu n – 1. Dengan n = 8, banyak langkah untuk setiap fungsi tersebut adalah:
7 langkah.

Untuk program utama, terdapat n langkah pada proses input, dengan n = 8. Pada proses output, terdapat 2 langkah.

Jadi, banyak langkah pada algoritma program utama dengan n = 8 adalah:
8 + 7 + 1 = 17 langkah.

Catatan: 2 baris terakhir pada algoritma program utama dapat digabungkan menjadi 1 baris yaitu output(maxr(A, 8))atauoutput(maxi(A, 8))sehinggatotal banyak langkahmenjadi16 langkah.

Menentukan G(n)

Dalam praktik perhitungan kompleksitas algoritma, kita hanya menghitung jumlah operasi khas/tipikal yang mendasari suatu algoritma. Pada algoritma program utama, operasi khasnya adalah maxi(A, n) atau maxr(A, n). Jadi G(n) ditentukan oleh G(n) kedua fungsi tersebut.

Pada kedua fungsi, operasi khasnya max(a, b), yang membutuhkan 1 langkah. Di atas telah dinyatakan pula bahwa banyak langkah masing-masing fungsi tersebut adalah n – 1.

Maka:

________________________

Alternatif 2

Kita juga dapat menyusun algoritma penyelesaian masalah ini tanpa menggunakan array. Di bawah ini diberikan algoritma program utama tanpa array, yang memanfaatkan algoritma fungsi max(a, b).

ALGORITMA PROGRAM UTAMA (Alternatif 1)

Program BuahRambutanKakRos2
Kamus:
   x, m: integer
   { x = banyak buah rambutan }
   { m = nilai maksimum }
Algoritma:
   input(m)  { nilai pertama yang dimasukkan dianggap maksimum }
   for i ← 2 to 8 do
       input(x)
       m = max(m, x)
   end for
   output(m)

Banyak Langkah

Untuk algoritma alternatif 2 ini, banyak langkah setiap baris adalah:

• baris 1: 1 langkah
• baris 2–5 (looping for): 7 × 2 = 14 langkah
• baris 6: 1 langkah

Total = 16 langkah

Menentukan G(n)

Sama dengan pembahasan di atas, kita hanya menghitung jumlah operasi khas/tipikal.

Pada algoritma ini, operasi khasnya terletak pada fungsi max(a, b), atau menentukan nilai terbesar dari 2 variabel, yang dilakukan sebanyak 7 kali. Dengan n = 8, maka 7 = n – 1.

Sehingga: