Desain algoritma dan pemecahan masalah

Siklus hidup pengembangan program adalah serangkaian tahap yang digunakan untuk membuat sebuah program. Ada empat tahap.

*Perangkat lunak ditulis oleh para pemrogram, yang mengikuti siklus pengembangan

*Empat tahap pengembangan program; pengujian memberikan umpan balik untuk memperbaiki dan menyempurnakan desain

*Diagram alir program menggambarkan langkah-langkah dan keputusan program selama tahap desain

Analisis

Dalam analisis, Anda memahami masalah. Dua keterampilan kunci membantu:

• abstraksi — pertahankan hanya detail penting dan abaikan sisanya;
• dekomposisi — pecahkan masalah besar menjadi bagian-bagian yang lebih kecil dan mudah.

Desain

Dalam desain, Anda merencanakan solusi, sering menggunakan dekomposisi. Anda dapat menampilkan bagian-bagian sebagai sub-sistem dalam diagram struktur (grafik yang memecah sistem menjadi kotak-kotak yang lebih kecil).

Pengkodean dan pengujian

Dalam pengkodean, Anda menulis kode program. Anda menggunakan pengujian iteratif — menguji bagian-bagian kecil berkali-kali saat Anda membangunnya. Dalam pengujian, Anda menjalankan seluruh program dengan data uji untuk memastikan program berfungsi.

Anda dapat merencanakan solusi dengan tiga cara utama.

• diagram struktur — menunjukkan bagian-bagian sistem dan bagaimana mereka saling terkait;
• diagram alir — diagram menggunakan kotak dan panah untuk menunjukkan langkah-langkah secara berurutan;
• pseudokode — langkah-langkah yang ditulis dalam bahasa Inggris sederhana yang menyerupai kode (bukan bahasa nyata).

Sebuah algoritma adalah serangkaian langkah, dalam urutan yang benar, yang memecahkan masalah. Setiap algoritma dapat dibagi menjadi tiga bagian:

• input — data yang masuk;
• pemrosesan — pekerjaan yang dilakukan pada data;
• output — hasil yang keluar.

Ini disebut dekomposisi menjadi input, proses, dan output. Misalnya, untuk "temukan rata-rata dari tiga nilai ujian": inputnya adalah tiga nilai ujian; pemrosesannya adalah menjumlahkannya dan membagi dengan 3; outputnya adalah rata-ratanya.

*Setiap algoritma terurai menjadi input, pemrosesan, dan output — di sini, menemukan rata-rata dari tiga nilai ujian

Ketika data dimasukkan, Anda memeriksanya untuk mengurangi kesalahan.

Validasi memeriksa apakah data masuk akal dan mematuhi aturan. Validasi tidak dapat memastikan data benar, hanya bahwa data tersebut diperbolehkan.

Verifikasi memeriksa apakah data telah disalin atau dimasukkan dengan benar (tanpa kesalahan saat mengetiknya). Dua metode:

• visual check — seseorang membandingkan data yang diketik dengan data asli;
• double entry — data dimasukkan dua kali dan kedua salibannya dibandingkan.

Sebuah tabel pelacakan mencatat nilai setiap variabel saat algoritma berjalan, langkah demi langkah. Ini membantu Anda:

• memeriksa apakah algoritma bekerja dengan benar;
• menentukan apa yang dilakukan algoritma dengan melacaknya menggunakan data yang diberikan.

Contoh: lacak algoritma ini dengan input 5.

INPUT N
Total ← 0
FOR I ← 1 TO N
    Total ← Total + I
NEXT I
OUTPUT Total

Pelacakan menunjukkan algoritma menjumlahkan 1 hingga n. Dengan input 5, output adalah 15.

Contoh terpecahkan. Lacak algoritma ini dan berikan output-nya.

X ← 20
Count ← 0
WHILE X > 1
    X ← DIV(X, 2)
    Count ← Count + 1
ENDWHILE
OUTPUT Count

DIV memberikan hanya bagian bilangan bulat dari sebuah pembagian. Ambil satu baris per putaran: x menjadi 10 (count 1), kemudian 5 (count 2), kemudian 2 (count 3), kemudian 1 (count 4). Sekarang x > 1 bernilai salah, sehingga loop berhenti dan outputnya adalah 4. Dua kebiasaan melindungi nilai ini: uji kondisi sebelum setiap putaran daripada setelah, dan tulis baris baru untuk setiap putaran - mencoba menyimpan nilai-nilai dalam ingatan adalah penyebab kesalahan pada pelacakan.

Data uji adalah data yang Anda gunakan untuk menguji sebuah program. Ada empat jenis yang harus Anda ketahui.

Anda harus mengetahui algoritma-algoritma umum ini.

Pencarian linear

Pencarian linear (linear search) memeriksa setiap item dalam daftar, satu per satu, hingga menemukan nilai yang diinginkan atau mencapai akhir.

Found ← FALSE
FOR I ← 0 TO 9
    IF List[I] = SearchValue
      THEN
        Found ← TRUE
    ENDIF
NEXT I
OUTPUT Found

Pengurutan gelembung

Sortir gelembung (bubble sort) menyusun daftar agar tersusun. Algoritma ini membandingkan setiap pasangan item yang berdampingan dan menukarnya jika urutannya salah. Algoritma ini mengulangi proses ini hingga tidak ada lagi penukaran yang diperlukan.

FOR I ← 0 TO 8
    IF List[I] > List[I + 1]
      THEN
        Temp ← List[I]
        List[I] ← List[I + 1]
        List[I + 1] ← Temp
    ENDIF
NEXT I

Penjumlahan dan Penghitungan

• penjumlahan — terus menambahkan nilai ke total kumulatif (Total ← Total + Value).
• penghitungan — tambahkan 1 ke penghitung setiap kali suatu hal terjadi (Count ← Count + 1).

Maksimum, Minimum, dan Rata-rata

• untuk menemukan maksimum: simpan nilai terbesar yang terlihat sejauh ini.
• untuk menemukan minimum: simpan nilai terkecil yang terlihat sejauh ini.
• untuk menemukan rata-rata: bagi total dengan berapa banyak nilai yang ada.

Total ← 0
FOR I ← 0 TO 9
    Total ← Total + List[I]
NEXT I
Average ← Total / 10
OUTPUT Average

• Pelajari empat tahap siklus hidup: analisis → desain → penulisan kode → pengujian. Abstraksi hanya mempertahankan detail penting; dekomposisi memecah masalah menjadi bagian-bagian yang lebih kecil.
• Validasi memeriksa data masuk akal (pemeriksaan range, panjang, tipe, kehadiran, format); verifikasi memeriksa data tersebut disalin dengan benar (pemeriksaan visual atau entri ganda).
• Pelajari empat jenis data uji: normal (diterima), abnormal (ditolak), ekstrem (nilai terbesar/terkecil yang masih diperbolehkan), batas (nilai di kedua sisi limit).
• Untuk menentukan apa yang dilakukan algoritma, isi tabel pelacakan — tuliskan nilai setiap variabel pada setiap langkah.
• Kenali algoritma standar: pencarian linear (periksa setiap item secara berurutan) dan sortir gelembung (tukar pasangan yang berdampingan hingga tidak ada lagi penukaran yang diperlukan).