Python/JavaPersoalan: Menemukan indeks awal dan akhir dari subarray (tidak boleh

Berikut ini adalah pertanyaan dari qed pada mata pelajaran TI untuk jenjang Sekolah Dasar

Python/JavaPersoalan: Menemukan indeks awal dan akhir dari subarray (tidak boleh diubah urutannya), yang memiliki jumlah elemen (bukan banyak elemen) yang sama dengan kriteria. Jika terdapat beberapa kemungkinan, hasilnya adalah subarray dengan indeks awal dan akhir terkecil.

Contoh kasus:
Array = [2, 3, 4, 5, 7]
Kriteria jumlah = 12
3 + 4 + 5 = 12, sedangkan 5 + 7 = 12 juga.
Maka hasilnya adalah 2, 4.
(artinya jumlah = 12 ditemukan pada subarray dari indeks ke-2 hingga ke-4).

Jawaban dan Penjelasan

Berikut ini adalah pilihan jawaban terbaik dari pertanyaan diatas.

Kode Program (Python)

# jumlah-subarray.py
# oleh: hy

def jumlah_subarray_1(arr, jum):
   n = len(arr)
   for i in range(n):
       for j in range(i+1, n+1):
           if sum(arr[i:j]) > jum:
               break
           if sum(arr[i:j]) == jum:
               return [i+1, j]
   return [-1]

def jumlah_subarray_2(arr, jum):
   n = len(arr)
   for i in range(n):
       total = arr[i]
       j = i+1
       while j <= n:
           if total == jum:
               return [i+1, j]
           if total > jum or j == n:
               break
           total += arr[j]
           j += 1
   return [-1]

def info(arr, hasil, jum):
   print(', '.join([str(i) for i in hasil]))
   if len(hasil) == 2:
       print(f'=> Jumlah = {jum} ditemukan pada elemen ke-{hasil[0]} sampai elemen ke-{hasil[1]} dari array\n{arr}.')
   else:
       print(f'=> Jumlah = {jum} tidak ditemukan pada array\n{arr}.')
   print()

import random

def main():
   print()

   jum = 12
   arr = [2, 3, 4, 5, 7]
   hasil = jumlah_subarray_1(arr, jum)
   info(arr, hasil, jum)
   hasil = jumlah_subarray_2(arr, jum)
   info(arr, hasil, jum)
   jum = 9
   arr = [1,2,3,4,5,6,7,8,9,10]
   hasil = jumlah_subarray_1(arr, jum)
   info(arr, hasil, jum)
   hasil = jumlah_subarray_2(arr, jum)
   info(arr, hasil, jum)

   jum = 40
   arr = [1,2,3,4,5,6,7,8,9,10]
   hasil = jumlah_subarray_1(arr, jum)
   info(arr, hasil, jum)
   hasil = jumlah_subarray_2(arr, jum)
   info(arr, hasil, jum)

   jum = 468
   arr = [135,101,170,125,79,159,163,65,106,146,\
       82,28,162,92,196,143,28,37,192,5,103,154,\
       93,183,22,117,119,96,48,127,172,139,70,113,\
       68,100,36,95,104,12,123,134]
   hasil = jumlah_subarray_1(arr, jum)
   info(arr, hasil, jum)
   hasil = jumlah_subarray_2(arr, jum)
   info(arr, hasil, jum)

if __name__ == '__main__':
   main()
______________

Pembahasan

Pada program di atas, diberikan dua fungsi yang melakukan hal yang sama, yaitu menemukan indeks awal dan akhir subarray, yang memiliki jumlah elemen sama dengan kriteria yang diinginkan.

Fungsi jumlah_subarray_1(arr, jum)mengandalkan fungsi built-insum() pada Python. Sedangkan fungsi jumlah_subarray_2(arr, jum) menggunakan cara "manual".

Karena dalam fungsi sum() secara internal sudah mengandung iterasi, maka pada fungsi jumlah_subarray_1(arr, jum), "level" iterasinya akan bertambah dalam, sehingga jika kita ukur waktu eksekusinya, kemungkinan besar fungsi jumlah_subarray_2(arr, jum) membutuhkan waktu yang lebih singkat, karena penjumlahan nilai elemen dilakukan pada iterasi utama.

Untuk array berukuran kecil, mungkin selisih waktunya sangat kecil. Namun, untuk array dengan ukuran yang besar, pasti selisih waktunya akan bertambah besar.
______________

Contoh Hasil Eksekusi

2, 4
=> Jumlah = 12 ditemukan pada elemen ke-2 sampai elemen ke-4 dari array
[2, 3, 4, 5, 7].

2, 4
=> Jumlah = 12 ditemukan pada elemen ke-2 sampai elemen ke-4 dari array
[2, 3, 4, 5, 7].

2, 4
=> Jumlah = 9 ditemukan pada elemen ke-2 sampai elemen ke-4 dari array
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10].

2, 4
=> Jumlah = 9 ditemukan pada elemen ke-2 sampai elemen ke-4 dari array
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10].

6, 10
=> Jumlah = 40 ditemukan pada elemen ke-6 sampai elemen ke-10 dari array
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10].

6, 10
=> Jumlah = 40 ditemukan pada elemen ke-6 sampai elemen ke-10 dari array
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10].

38, 42
=> Jumlah = 468 ditemukan pada elemen ke-38 sampai elemen ke-42 dari array
[135, 101, 170, 125, 79, 159, 163, 65, 106, 146, 82, 28, 162, 92, 196, 143, 28, 37, 192, 5, 103, 154, 93, 183, 22, 117, 119, 96, 48, 127, 172, 139, 70, 113, 68, 100, 36, 95, 104, 12, 123, 134].

38, 42
=> Jumlah = 468 ditemukan pada elemen ke-38 sampai elemen ke-42 dari array
[135, 101, 170, 125, 79, 159, 163, 65, 106, 146, 82, 28, 162, 92, 196, 143, 28, 37, 192, 5, 103, 154, 93, 183, 22, 117, 119, 96, 48, 127, 172, 139, 70, 113, 68, 100, 36, 95, 104, 12, 123, 134].

Kode Program (Python)# jumlah-subarray.py# oleh: hydef jumlah_subarray_1(arr, jum):    n = len(arr)    for i in range(n):        for j in range(i+1, n+1):            if sum(arr[i:j]) > jum:                break            if sum(arr[i:j]) == jum:                return [i+1, j]    return [-1]def jumlah_subarray_2(arr, jum):    n = len(arr)    for i in range(n):        total = arr[i]        j = i+1        while j <= n:            if total == jum:                return [i+1, j]            if total > jum or j == n:                break            total += arr[j]            j += 1    return [-1]def info(arr, hasil, jum):    print(', '.join([str(i) for i in hasil]))    if len(hasil) == 2:        print(f'=> Jumlah = {jum} ditemukan pada elemen ke-{hasil[0]} sampai elemen ke-{hasil[1]} dari array\n{arr}.')    else:        print(f'=> Jumlah = {jum} tidak ditemukan pada array\n{arr}.')    print()import randomdef main():    print()    jum = 12    arr = [2, 3, 4, 5, 7]    hasil = jumlah_subarray_1(arr, jum)    info(arr, hasil, jum)    hasil = jumlah_subarray_2(arr, jum)    info(arr, hasil, jum)    jum = 9    arr = [1,2,3,4,5,6,7,8,9,10]    hasil = jumlah_subarray_1(arr, jum)    info(arr, hasil, jum)    hasil = jumlah_subarray_2(arr, jum)    info(arr, hasil, jum)    jum = 40    arr = [1,2,3,4,5,6,7,8,9,10]    hasil = jumlah_subarray_1(arr, jum)    info(arr, hasil, jum)    hasil = jumlah_subarray_2(arr, jum)    info(arr, hasil, jum)    jum = 468    arr = [135,101,170,125,79,159,163,65,106,146,\        82,28,162,92,196,143,28,37,192,5,103,154,\        93,183,22,117,119,96,48,127,172,139,70,113,\        68,100,36,95,104,12,123,134]    hasil = jumlah_subarray_1(arr, jum)    info(arr, hasil, jum)    hasil = jumlah_subarray_2(arr, jum)    info(arr, hasil, jum)if __name__ == '__main__':    main()______________PembahasanPada program di atas, diberikan dua fungsi yang melakukan hal yang sama, yaitu menemukan indeks awal dan akhir subarray, yang memiliki jumlah elemen sama dengan kriteria yang diinginkan.Fungsi jumlah_subarray_1(arr, jum) mengandalkan fungsi built-in sum() pada Python. Sedangkan fungsi jumlah_subarray_2(arr, jum) menggunakan cara

Semoga dengan pertanyaan yang sudah terjawab oleh henriyulianto dapat membantu memudahkan mengerjakan soal, tugas dan PR sekolah kalian.

Apabila terdapat kesalahan dalam mengerjakan soal, silahkan koreksi jawaban dengan mengirimkan email ke yomemimo.com melalui halaman Contact

Last Update: Thu, 17 Nov 22