09. Flowchart dan pseudocode — Pembahasan PR

Soal 1 dan 2 dikerjakan di kertas. Berkas .cpp untuk soal 3 sampai tantangan ada di exercises/09/homework/solutions/.

Halaman ini dibuka sesudah mencoba sendiri. Untuk soal kertas, tulis dulu jawabanmu, baru bandingkan — membaca jawaban orang lain terasa jelas padahal belum tentu bisa diulang sendiri. Bagian Uji berisi masukan dan keluaran yang sudah diperiksa untuk soal berkode.

Menjalankan salah satu jawabannya:

g++ -std=c++17 -O2 -o jawab exercises/09/homework/solutions/03-dari-flowchart.cpp
./jawab

Soal 1 — Gambar flowchart

Soal. Baca n, baca n bilangan, cetak berapa banyak yang negatif.

Cara berpikir. Dua hal yang harus ada sebelum perulangan: pencacah posisi (i) dan penampung jawaban (negatif). Belah ketupat pertama mengurus "masih ada data?", belah ketupat kedua mengurus "data ini negatif?". Cabang tidak dari belah ketupat kedua tetap harus digambar — ia langsung menuju langkah penambahan i.

Jawaban.

Kesalahan umum.

• Belah ketupat x < 0? hanya diberi satu panah keluar.
• Panah balik menuju baca x, bukan ke belah ketupat i <= n?. Akibatnya pemeriksaan batas dilewati dan perulangannya tidak pernah berhenti.
• Lupa menaikkan i.

Soal 2 — Tulis pseudocode

Soal. Cetak semua pembagi n, lalu jumlahnya.

Cara berpikir. Satu perulangan dari 1 sampai n, satu pemeriksaan n habis dibagi i, dan satu penampung. Dua pekerjaan (mencetak dan menjumlahkan) terjadi di dalam pemeriksaan yang sama, jadi cukup satu perulangan.

Jawaban.

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

Kesalahan umum.

• Menulis dua perulangan terpisah — satu untuk mencetak, satu untuk menjumlahkan. Jawabannya benar, tetapi pekerjaannya dua kali lipat.
• Memulai perulangan dari 2, sehingga pembagi 1 hilang.

Soal 3 — Baca flowchart, tulis kodenya

Soal. Terjemahkan flowchart menjadi kode.

Cara berpikir. Kenali dulu apa yang dikerjakan flowchart itu sebelum menerjemahkan: hasil dimulai dari 1 dan dikalikan i untuk setiap i dari 1 sampai n. Itu faktorial.

Bentuk < i <= n? > dengan panah balik adalah while; boleh juga ditulis sebagai for, dan keduanya diterima.

Pembahasan.

long long hasil = 1;
int i = 1;
while (i <= n) {
    hasil = hasil * i;
    i = i + 1;
}
cout << hasil << "\n";

Uji.

Baris terakhir adalah kasus tepi yang langsung terlihat pada flowchart: belah ketupat i <= n bernilai salah sejak pemeriksaan pertama, sehingga isi perulangannya dilewati dan hasil tetap bernilai awalnya, yaitu 1.

Kesalahan umum.

• Memulai hasil dari 0. Semua perkalian berikutnya menjadi nol.
• Memakai int untuk hasil. Sudah meluap di 13!.

Soal 4 — Baca pseudocode, ramalkan keluarannya

Jawaban.

A → 3 5. Tiga baris itu menukar isi dua variabel tanpa variabel bantu. Telusuri: x = 8, lalu y = 8 − 3 = 5, lalu x = 8 − 5 = 3.

B → 15. Perulangan dalam berjalan sebanyak i kali untuk setiap i, jadi totalnya 1 + 2 + 3 + 4 + 5. Bentuk ini muncul lagi di Bab 10 saat menghitung jumlah langkah perulangan bersarang.

C → 111. Ini barisan Collatz: bilangan genap dibagi dua, bilangan ganjil dikali tiga tambah satu. Dari 27 dibutuhkan 111 langkah untuk sampai di 1 — jauh lebih panjang daripada dugaan kebanyakan orang, dan itulah gunanya menjalankan program untuk memeriksa tebakan.

Uji. Program jawabannya mencetak ketiga hasilnya sekaligus:

3 5
15
111

Potongan C adalah yang paling mudah salah ditebak: barisan Collatz untuk 27 memerlukan 111 langkah, dan nilainya sempat naik sampai di atas 9.000 sebelum akhirnya turun ke 1. Menebaknya tanpa menjalankan hampir mustahil — dan itu pelajarannya: untuk pseudocode dengan perulangan bersyarat, tabel penelusuran (Bab 10) lebih bisa diandalkan daripada firasat.

Kesalahan umum.

• Pada A, menjawab 5 3 karena mengira penukarannya gagal.
• Pada C, mencoba menelusuri 111 langkah dengan tangan. Cukup telusuri lima langkah pertama untuk memastikan kodenya benar, lalu biarkan program menyelesaikan sisanya.

Tantangan — Perbaiki flowchart yang salah

Jawaban.

1. Cabang dari < d * d <= x? > menuju [ cetak x jika prima ] adalah cabang tidak dan harus diberi label. Belah ketupat tanpa label membuat pembaca menebak arah, dan di lembar jawaban OSN dianggap salah.
2. Langkah [ d = d + 1 ] hilang. Tanpa itu, d tidak pernah berubah dan perulangan dalam berputar selamanya.
3. Panah balik dari [ cetak x jika prima ] harus menuju [ x = x + 1 ] lalu ke < x <= n? >. Pada gambar aslinya ia kembali ke [ d = 2, prima = benar ], yang mengulang pemeriksaan bilangan yang sama tanpa henti.

Setelah diperbaiki, bentuk benarnya:

Pembahasan (kode).

for (int x = 2; x <= n; x++) {
    bool prima = true;
    for (int d = 2; d * d <= x; d++) {
        if (x % d == 0) prima = false;
    }
    if (prima) cout << x << " ";
}
cout << "\n";

Uji.

Kalau flowchart-nya diperbaiki dengan benar, keluarannya persis daftar itu. Dua gejala kalau salah satu perbaikan terlewat: program menggantung (langkah d = d + 1 masih hilang) atau mencetak bilangan bukan prima seperti 4 dan 9 (panah baliknya masih menuju kotak yang keliru).

Kesalahan umum.

• Menaruh bool prima = true; di luar perulangan luar. Sekali satu bilangan tersusun ditemukan, semua bilangan sesudahnya ikut dianggap bukan prima.
• Memakai d < x sebagai batas perulangan dalam. Jawabannya benar, tetapi jauh lebih lambat — persis persoalan yang dibahas di Bab 05.

Latihan bergaya OSN — pembahasan

Berkas jawabannya ada di exercises/09/osn/solutions/.

Soal 1 — Telusuri Pseudocode

Cara berpikir. Setiap putaran memasuki tepat satu cabang: kalau i kelipatan 3 maka a bertambah, kalau bukan maka b berlipat dua. Jadi kedua variabel tidak pernah berubah bersamaan, dan penelusurannya cukup mencatat satu perubahan per baris.

Penelusuran untuk n = 10:

Jawaban.

a. n = 10 mencetak dua baris: 18 lalu 128. b. n = 1 mencetak 0 lalu 2. Perulangannya berjalan sekali, dan 1 bukan kelipatan 3, jadi a tidak pernah tersentuh. c. a adalah jumlah semua kelipatan 3 dari 1 sampai n. b adalah 2 dipangkatkan banyaknya bilangan dari 1 sampai n yang bukan kelipatan 3, yaitu n − ⌊n/3⌋. d. b melewati batas int mulai n = 46. Pada n = 45 ada 30 bilangan bukan kelipatan 3, sehingga b = 2³⁰ = 1.073.741.824, masih muat. Pada n = 46 jumlahnya 31, sehingga b = 2³¹ = 2.147.483.648 — satu lebih besar daripada nilai int terbesar.

Jawaban (d) adalah inti soalnya: perulangan sesederhana ini pun sudah meluap pada n yang sangat kecil, karena pertumbuhannya berlipat, bukan bertambah.

Kesalahan umum.

• Menghitung b sebagai 2 pangkat n, lupa bahwa kelipatan 3 tidak melipatgandakan.
• Menjawab (a) dengan satu baris. CETAK muncul dua kali dan keduanya di luar perulangan.
• Menganggap b bermula dari 0. Baris b <- 1 menentukan seluruh hasilnya.

Soal 2 — Baca Flowchart

Cara berpikir. Kotak keputusan p * 2 <= n? dengan panah "ya" yang kembali ke atas adalah bentuk baku sebuah while. Isi perulangannya satu baris: p dilipatduakan. Begitu p * 2 melewati n, alurnya keluar dan mencetak p.

Karena p bermula dari 1 dan hanya dikalikan 2, nilainya selalu berupa pangkat dua. Perulangan berhenti tepat saat melipatduakan sekali lagi akan melewati n.

Jawaban.

a. N = 100 mencetak 64. Urutannya 1, 2, 4, 8, 16, 32, 64; lipat dua berikutnya 128 sudah melebihi 100. b. N = 1 mencetak 1. Perulangannya tidak pernah dimasuki karena 1 × 2 = 2 sudah melebihi 1. c. Flowchart ini mencetak pangkat dua terbesar yang tidak melebihi N. d. N = 10¹⁸ mencetak 576460752303423488, yaitu 2⁵⁹.

Pembahasan.

long long n;
cin >> n;

long long p = 1;
while (p * 2 <= n) {
    p = p * 2;
}

cout << p << "\n";

Perhatikan bahwa jumlah putarannya hanya sekitar 60 untuk N sebesar 10¹⁸ — setiap putaran melipatduakan, jadi banyaknya putaran sebanding dengan logaritma N, bukan N. Ini bentuk perulangan yang tetap cepat pada batasan sebesar apa pun.

Kesalahan umum.

• Menulis syaratnya p <= n, bukan p * 2 <= n. Hasilnya p melompat satu kali terlalu jauh, dan untuk N = 100 tercetak 128.
• Memakai int untuk p, sehingga perkalian meluap untuk N besar.
• Mengira panah "ya" yang kembali ke atas berarti do ... while. Syaratnya diperiksa sebelum badan perulangan, jadi terjemahannya while.

Soal 3 — Deret Gunung

Pseudocode.

BACA n
BACA a[1..n]
i <- 1
SELAMA i < n DAN a[i] < a[i+1]
    i <- i + 1
JIKA i = 1 ATAU i = n
    CETAK "TIDAK"
    SELESAI
SELAMA i < n DAN a[i] > a[i+1]
    i <- i + 1
JIKA i = n
    CETAK "YA"
SELAIN ITU
    CETAK "TIDAK"

Cara berpikir. Godaannya adalah memeriksa "di mana puncaknya" dengan mencari nilai terbesar lebih dulu. Cara itu bisa benar, tetapi menjadi berbelit kalau nilai terbesarnya muncul lebih dari sekali.

Cara yang lebih rapi: jalankan satu penunjuk i ke depan selama barisannya masih naik. Saat perulangan pertama berhenti, i berada tepat di puncak. Dua pemeriksaan langsung menjatuhkan barisan yang salah bentuk:

• i masih di awal berarti tidak pernah naik;
• i sudah di ujung berarti tidak sempat turun.

Sesudah itu, penunjuk yang sama diteruskan selama barisannya turun. Kalau akhirnya sampai di ujung, seluruh barisan memang naik lalu turun. Kalau berhenti di tengah, berarti ada bagian yang tidak naik dan tidak turun — yaitu dua angka yang sama, atau naik lagi setelah turun.

Perhatikan bahwa penunjuknya berjalan maju terus dan tidak pernah mundur. Jadi seluruh pemeriksaan memerlukan paling banyak N langkah, bukan N².

Pembahasan.

int i = 0;
while (i + 1 < n && a[i] < a[i + 1]) i++;

if (i == 0 || i == n - 1) {
    cout << "TIDAK\n";
    return 0;
}

while (i + 1 < n && a[i] > a[i + 1]) i++;

if (i == n - 1) cout << "YA\n";
else cout << "TIDAK\n";

Kode ini memakai indeks mulai 0, sehingga "puncak di ujung" ditulis i == n - 1, bukan i == n. Inilah pergeseran indeks yang dibahas di bagian Dari pseudocode ke C++ — pilih satu cara dan pakai terus.

Uji.

Kesalahan umum.

• Lupa memeriksa i + 1 < n di dalam syarat while, sehingga a[i + 1] dibaca di luar batas array pada barisan yang naik terus.
• Memakai <= pada perulangan naik, sehingga dua angka yang sama dianggap masih naik.
• Lupa memeriksa bahwa puncaknya tidak di ujung, sehingga barisan menaik seperti 1 2 3 4 dijawab YA.

Kalau masih tersendat

• Perulangan pada gambar tidak pernah berhenti → Bab 09, tabel susunan tetap sebuah perulangan.
• Pseudocode terbaca ambigu → Bab 09, bagian tentang indentasi dan contoh dua pseudocode yang hanya berbeda satu tingkat.
• Terjemahan ke C++ meleset satu langkah → Bab 09, bagian Dari pseudocode ke C++ dan dua cara menangani pergeseran indeks.

Sebelum lanjut ke Bab 10, pastikan kamu bisa membaca pseudocode orang lain dan meramalkan keluarannya tanpa menjalankannya.