09. Flowchart dan pseudocode

Algoritma perlu ditulis sebelum menjadi kode. Ada dua cara menuliskannya: flowchart (gambar) dan pseudocode (tulisan). Keduanya muncul di soal OSN tingkat kabupaten, dan keduanya memaksa kamu memikirkan urutan langkah tanpa direpotkan titik koma.

Menulis algoritma lebih dulu terasa seperti pekerjaan tambahan, padahal ia menghemat waktu. Alasannya: memperbaiki langkah yang salah di kertas memerlukan satu coretan, sedangkan memperbaikinya setelah menjadi enam puluh baris C++ memerlukan membaca ulang seluruh kode sambil menebak di mana letak salahnya. Di lomba, peserta yang langsung mengetik biasanya kalah oleh peserta yang menghabiskan lima menit pertama di kertas.

Simbol flowchart

Empat aturan yang membuat flowchart bisa dibaca orang lain — dan tiga di antaranya adalah kesalahan yang paling sering di lembar jawaban:

1. Belah ketupat selalu punya tepat dua panah keluar, diberi label ya dan tidak. Cabang yang tidak diberi label membuat pembaca menebak.
2. Satu oval Mulai dan satu oval Selesai. Semua jalur akhirnya bermuara ke oval Selesai yang sama.
3. Setiap kotak punya tepat satu panah keluar. Kalau sebuah kotak perlu dua kemungkinan, ia harus diganti belah ketupat.
4. Tidak ada panah yang menggantung. Panah yang tidak menuju ke mana-mana berarti ada langkah yang belum dipikirkan.

Tiga pola dasar

Setiap algoritma, sepanjang apa pun, tersusun dari tiga pola ini.

Urutan

Percabangan

Perulangan

Panah dari i = i + 1 kembali ke belah ketupat itulah perulangannya. Tanpa panah balik, tidak ada pengulangan.

Perhatikan susunan tetap sebuah perulangan pada flowchart, karena bentuk ini selalu sama untuk perulangan apa pun:

Percabangan di dalam perulangan

Gabungan kedua pola itu adalah bentuk yang paling sering muncul di soal: telusuri seluruh data, dan pada setiap elemen ambil keputusan. Berikut algoritma mencari nilai terbesar.

Ada dua belah ketupat dengan tugas yang berbeda: yang atas mengatur berapa kali perulangan berjalan, yang bawah mengatur apa yang dikerjakan pada satu elemen. Perhatikan juga bahwa kedua cabang belah ketupat bawah bertemu kembali di kotak i = i + 1 — langkah itu harus dijalankan apa pun keputusannya, kalau tidak perulangannya tidak pernah berhenti.

Pseudocode

Pseudocode adalah algoritma yang ditulis sebagai kalimat pendek, satu langkah per baris, dengan indentasi untuk menunjukkan bagian dalam. Tidak ada aturan baku, tetapi bentuk yang dipakai buku ini:

BACA n
jumlah <- 0
UNTUK i DARI 1 SAMPAI n
    jumlah <- jumlah + i
CETAK jumlah

Kata kunci yang cukup dikuasai:

Dua aturan bentuknya: satu langkah per baris, dan indentasi menunjukkan isi. Baris yang menjorok ke dalam berarti berada di dalam perulangan atau percabangan tepat di atasnya. Karena tidak ada kurung kurawal, indentasi itulah satu-satunya penanda — jadi menuliskannya dengan rapi bukan soal keindahan.

Bandingkan dua pseudocode yang hanya berbeda indentasinya:

jumlah <- 0
UNTUK i DARI 1 SAMPAI n
    jumlah <- jumlah + i
    CETAK jumlah

jumlah <- 0
UNTUK i DARI 1 SAMPAI n
    jumlah <- jumlah + i
CETAK jumlah

Yang pertama mencetak n baris, yang kedua mencetak satu baris. Soal OSN tingkat kabupaten memang gemar menguji perbedaan sehalus ini.

Contoh yang lebih panjang — mencari nilai terbesar:

BACA n
BACA a[1..n]
besar <- a[1]
UNTUK i DARI 2 SAMPAI n
    JIKA a[i] > besar
        besar <- a[i]
CETAK besar

Dari pseudocode ke C++

Terjemahannya nyaris baris per baris:

Perhatikan pergeseran indeks: pseudocode di buku ini menulis array mulai dari 1 (seperti soal OSN), sedangkan C++ mulai dari 0. Salah satu sumber kesalahan paling sering saat menerjemahkan.

Ada dua cara menanganinya, dan keduanya sah asal dipakai konsisten:

• Geser semuanya: a[1] pada pseudocode menjadi a[0] pada kode, dan UNTUK i DARI 1 SAMPAI n menjadi for (int i = 0; i < n; i++).
• Biarkan indeks 0 kosong: baca data ke a[1] sampai a[n], dan tulis for (int i = 1; i <= n; i++). Arraynya cukup dibuat satu kotak lebih besar.

Cara kedua sering dipilih di lomba justru karena menghilangkan pergeseran itu: kode dan soal memakai penomoran yang sama, sehingga rumus seperti "elemen ke-i dan ke-i+1" bisa disalin apa adanya.

Membaca pseudocode orang lain

Latihan yang dipakai OSN tingkat kabupaten berbentuk terbalik: pseudocode diberikan, keluarannya yang ditanyakan. Coba potongan ini sebelum membaca lanjutannya:

n <- 5
hasil <- 1
SELAMA n > 1
    hasil <- hasil * n
    n <- n - 1
CETAK hasil

Telusuri dengan tangan: hasil berturut-turut menjadi 5, lalu 20, lalu 60, lalu 120, dan n berhenti di 1. Keluarannya 120, yaitu 5!. Bab 10 mengajarkan cara membuat tabel penelusuran seperti ini secara sistematis supaya tidak ada langkah yang terlewat.

Kapan memakai yang mana

• Flowchart untuk algoritma pendek dengan percabangan rumit. Bentuk gambarnya memperlihatkan cabang yang terlewat.
• Pseudocode untuk algoritma dengan perulangan bersarang atau banyak langkah. Menggambar tiga perulangan bersarang menjadi gambar yang tidak terbaca; menuliskannya cukup enam baris.

Di lembar jawaban OSN tingkat kabupaten, soal sering menyajikan pseudocode lalu bertanya "apa keluarannya?". Kemampuan membaca pseudocode orang lain sama pentingnya dengan menulisnya — dan itu latihan Bab 10.

Pekerjaan rumah

Kesalahan yang paling sering

Tips OSN

Soal "ramalkan keluaran" adalah soal gratis kalau ditelusuri dengan tabel. Jangan membacanya dalam kepala. Buat tabel di kertas coretan: satu kolom per variabel, satu baris per putaran. Cara ini memakan waktu setengah menit dan hampir tidak pernah salah, sedangkan menebak dari membaca hampir selalu salah di putaran terakhir.

Periksa dua tempat yang paling sering menjebak: nilai variabel sesudah perulangan berakhir, dan apakah CETAK berada di dalam atau di luar perulangan. Perbedaan indentasi satu tingkat mengubah jawaban dari satu baris menjadi n baris.

Perhatikan batas perulangan. UNTUK i DARI 1 SAMPAI n mencakup n, sedangkan for (int i = 1; i < n; i++) tidak. Kesalahan satu putaran ini adalah penyebab Wrong Answer yang paling sering pada soal terjemahan.

Pseudocode pada soal memakai indeks mulai 1. Soal OSN hampir selalu menomori data dari 1, sedangkan array C++ mulai dari 0. Tentukan cara penanganannya sekali di awal — geser semuanya, atau biarkan indeks 0 kosong — lalu pakai satu cara itu saja sampai selesai. Mencampur keduanya di satu program adalah sumber kesalahan yang sangat sulit ditemukan.

Rancangan di kertas bukan pemborosan waktu. Lima menit menulis pseudocode menghemat setengah jam mengejar kesalahan logika, karena kesalahan rancangan terlihat sebagai kalimat yang janggal, bukan sebagai angka yang salah pada kasus uji ke-37. Yang perlu digambar bukan seluruh program, melainkan bagian yang belum jelas.

Flowchart berguna untuk memeriksa alur, bukan untuk menulis kode. Di lomba, gambar flowchart lengkap tidak sepadan dengan waktunya. Yang dipakai adalah bentuk ringkasnya: tiga sampai lima kotak untuk memastikan setiap cabang punya jalan keluar dan setiap perulangan punya syarat berhenti.

Ringkasan

• Flowchart memakai oval untuk mulai/selesai, persegi untuk tindakan, belah ketupat untuk keputusan, dan panah untuk urutan.
• Belah ketupat punya tepat dua panah keluar berlabel ya dan tidak; perulangan ditandai panah balik menuju belah ketupatnya.
• Pseudocode menulis satu langkah per baris dan memakai indentasi untuk menunjukkan isi perulangan atau percabangan.
• Kata kunci yang dipakai buku ini: BACA, CETAK, <-, JIKA, SELAIN ITU, UNTUK ... DARI ... SAMPAI ..., SELAMA.
• Flowchart cocok untuk percabangan rumit, pseudocode untuk perulangan bersarang dan algoritma panjang.
• Terjemahannya ke C++ nyaris baris per baris; yang perlu diawasi adalah pergeseran indeks array dari 1 menjadi 0.

Latihan bergaya OSN

Dua soal pertama dikerjakan di kertas lebih dulu, seperti soal analitik yang muncul di seleksi tingkat awal: yang diuji bukan kecepatan mengetik, melainkan ketelitian menelusuri. Soal ketiga baru dikerjakan di komputer, tetapi tulis pseudocode-nya lebih dulu.

Kerangkanya ada di exercises/09/osn/.

Soal 1 — Telusuri Pseudocode

Perhatikan pseudocode berikut:

BACA n
a <- 0
b <- 1
UNTUK i DARI 1 SAMPAI n
    JIKA i habis dibagi 3
        a <- a + i
    SELAIN ITU
        b <- b * 2
CETAK a
CETAK b

Jawab tanpa menjalankan program:

a. Apa yang dicetak untuk n = 10? b. Apa yang dicetak untuk n = 1? c. Dengan kalimat sendiri, apa arti nilai a dan nilai b secara umum? d. Mulai dari n berapa nilai b melewati batas int?

Cara mengerjakannya. Buat tabel dengan kolom i, a, dan b, lalu isi satu baris per putaran. Untuk bagian (c), perhatikan berapa kali masing- masing cabang dimasuki, bukan nilainya satu per satu.

Sesudah menjawab di kertas, periksa dengan exercises/09/osn/solutions/01-telusuri.cpp.

Soal 2 — Baca Flowchart

Flowchart berikut membaca satu bilangan bulat N dan mencetak satu bilangan.

a. Apa yang dicetak untuk N = 100? b. Apa yang dicetak untuk N = 1? c. Dengan satu kalimat, apa yang dihitung flowchart ini? d. Tulis kodenya dalam C++, lalu jalankan untuk N = 10¹⁸.

Format masukan. Satu baris berisi bilangan bulat N.

Format keluaran. Satu baris berisi satu bilangan bulat.

Batasan. 1 ≤ N ≤ 10¹⁸.

Kerangkanya: exercises/09/osn/02-pangkat-dua.cpp

Soal 3 — Deret Gunung

Sebuah barisan disebut barisan gunung kalau ia naik tegas sampai satu puncak, lalu turun tegas sampai akhir. Naik tegas berarti setiap angka lebih besar daripada angka sebelumnya; turun tegas berarti setiap angka lebih kecil daripada angka sebelumnya. Puncaknya tidak boleh berada di ujung: harus ada bagian yang naik dan bagian yang turun.

Format masukan. Baris pertama berisi bilangan bulat N. Baris kedua berisi N bilangan bulat A₁ A₂ … A_N.

Format keluaran. Satu baris berisi YA kalau barisannya barisan gunung, atau TIDAK kalau bukan.

Batasan.

• 3 ≤ N ≤ 200.000
• 1 ≤ Aᵢ ≤ 10⁹

Contoh masukan

5
1 3 7 4 2

Contoh keluaran

YA

Penjelasan. Barisan naik dari 1 ke 3 ke 7, lalu turun ke 4 dan 2. Barisan 1 2 3 4 bukan barisan gunung karena tidak pernah turun, dan barisan 3 3 4 2 1 bukan karena dua angka pertamanya sama — naiknya tidak tegas.

Tulis pseudocode-nya lebih dulu di kertas. Petunjuk: hanya perlu dua perulangan yang berjalan berurutan pada penunjuk yang sama, bukan dua perulangan bersarang.

Kerangkanya: exercises/09/osn/03-deret-gunung.cpp

Bingung atau sudah selesai? Buka halaman pembahasan PR.