05. Perulangan

Komputer unggul pada pekerjaan yang diulang ribuan kali tanpa bosan. Perulangan adalah alat untuk menyuruhnya melakukan itu — dan hampir semua soal OSN membutuhkannya.

for

Bentuk for dipakai ketika banyaknya pengulangan sudah diketahui:

for (int i = 1; i <= 5; i++) {
    cout << i << " ";
}
cout << "\n";

1 2 3 4 5

Tiga bagian di dalam kurung, dipisahkan titik koma:

Urutan pengerjaannya bukan dari kiri ke kanan begitu saja, melainkan seperti ini: awal dijalankan sekali, lalu syarat diperiksa, lalu isi dijalankan, lalu perubahan, lalu kembali memeriksa syarat, dan seterusnya. Telusuri contoh di atas:

Perhatikan dua hal yang sering mengejutkan pemula: syarat diperiksa sebelum isi dijalankan (jadi isi bisa tidak pernah dijalankan sama sekali), dan sesudah perulangan selesai nilai i sudah melewati batasnya.

Variabel i yang dibuat di dalam for (int i = ...) hanya hidup selama perulangan itu. Sesudahnya ia tidak ada lagi, dan memakainya menghasilkan 'i' was not declared in this scope.

Variasi yang sering dipakai:

for (int i = 0; i < n; i++)        // 0 sampai n-1, paling umum untuk array
for (int i = n; i >= 1; i--)       // mundur
for (int i = 0; i < n; i += 2)     // melompat dua

Banyaknya putaran bisa dihitung tanpa menjalankan programnya, dan ini yang perlu dibiasakan sejak sekarang karena Bab 10 memakainya terus-menerus:

Baris ketiga adalah kesalahan satu langkah (off-by-one) yang paling sering: mengganti < menjadi <= menambah satu putaran, dan pada array putaran tambahan itu menyentuh kotak yang tidak ada.

while

while dipakai ketika banyaknya pengulangan tidak diketahui sejak awal, hanya syarat berhentinya yang diketahui:

int n = 1234;
int banyak_digit = 0;

while (n > 0) {
    n /= 10;
    banyak_digit++;
}
cout << banyak_digit << "\n";   // 4

Menelusuri contoh di atas untuk n = 1234:

Memilih for atau while

Keduanya sama kuat — apa pun yang bisa ditulis dengan for bisa ditulis dengan while, dan sebaliknya. Yang dipilih adalah yang membuat maksudnya paling jelas terbaca.

do ... while

Sama seperti while, tetapi isinya dijalankan minimal sekali karena syaratnya diperiksa di akhir:

int pilihan;
do {
    cin >> pilihan;
} while (pilihan < 1 || pilihan > 3);

Bentuk ini jarang dipakai untuk soal penilai daring, tetapi berguna untuk program interaktif.

break dan continue

• break keluar dari perulangan seketika.
• continue melompat ke putaran berikutnya.

for (int i = 1; i <= 100; i++) {
    if (i % 3 != 0) continue;   // lewati yang bukan kelipatan 3
    if (i > 20) break;          // berhenti begitu melewati 20
    cout << i << " ";
}

3 6 9 12 15 18

Pola akumulasi

Pola paling sering di seluruh buku ini: siapkan sebuah penampung sebelum perulangan, ubah isinya di setiap putaran, pakai hasilnya sesudah perulangan.

long long total = 0;            // penampung
for (int i = 1; i <= n; i++) {
    total += i;                 // diubah tiap putaran
}
cout << total << "\n";          // dipakai sesudahnya

Tiga bagian itu — siapkan, ubah, pakai — selalu ada. Yang paling sering salah adalah bagian "siapkan", karena nilai awalnya berbeda untuk setiap jenis akumulasi:

Nilai awal 0 untuk hasil kali membuat jawabannya selalu nol; nilai awal 0 untuk "terbesar" membuat jawabannya salah bila semua data negatif. Keduanya kesalahan klasik yang lolos dari contoh kasus di soal dan baru ketahuan saat dinilai.

Variasi yang perlu kamu hafal bentuknya:

// menghitung berapa banyak yang memenuhi syarat
int banyak = 0;
for (int i = 1; i <= n; i++) if (i % 7 == 0) banyak++;

// mencari yang terbesar
int besar = -1000000000;
for (int i = 0; i < n; i++) { cin >> x; if (x > besar) besar = x; }

// perkalian beruntun (faktorial)
long long hasil = 1;
for (int i = 2; i <= n; i++) hasil *= i;

Memproses digit

Gabungan % 10 dan / 10 dari Bab 03 di dalam while memberi cara membaca sebuah bilangan digit demi digit, dari belakang:

long long n = 4071;
int jumlah = 0;

while (n > 0) {
    int digit = n % 10;   // ambil digit terakhir
    jumlah += digit;
    n /= 10;              // buang digit terakhir
}
cout << jumlah << "\n";   // 12

Perulangan bersarang

Perulangan boleh berada di dalam perulangan. Yang dalam berputar penuh untuk setiap putaran yang luar.

for (int baris = 1; baris <= 4; baris++) {
    for (int kolom = 1; kolom <= baris; kolom++) {
        cout << "*";
    }
    cout << "\n";
}

*
**
***
****

Cara membacanya: perulangan luar menentukan berapa baris, perulangan dalam menentukan isi satu baris. Untuk contoh di atas:

Seluruhnya 1 + 2 + 3 + 4 = 10 bintang. Perhatikan juga letak cout << "\n": ia berada di dalam perulangan luar tetapi di luar perulangan dalam. Memindahkannya satu tingkat ke dalam membuat setiap bintang berpindah baris; memindahkannya ke luar membuat semuanya menjadi satu baris panjang.

Jumlah pekerjaan ikut berlipat: dua perulangan bersarang yang masing-masing sampai n mengerjakan sekitar n² langkah. Untuk n = 1000 itu sejuta langkah (cepat), untuk n = 100000 itu sepuluh miliar (jauh terlalu lambat). Bab 10 membahas cara memperkirakannya sebelum menulis kode.

Pola banyak kasus uji

Banyak soal lomba memberi jumlah kasus uji di baris pertama. Bentuk bakunya:

int t;
cin >> t;
while (t--) {
    int a, b;
    cin >> a >> b;
    cout << a + b << "\n";
}

t-- memberikan nilai t sekarang kepada while, lalu menguranginya satu. Saat t mencapai 0, perulangan berhenti.

Kalau perulangan tidak mau berhenti

Program yang menggantung tanpa mencetak apa-apa hampir selalu berarti satu dari tiga hal:

1. Nilai yang diperiksa tidak pernah berubah. Periksa apakah ada baris di dalam perulangan yang benar-benar mengubahnya.
2. Perubahannya menjauhi syarat berhenti. Misalnya i-- pada perulangan yang menunggu i mencapai n.
3. Programnya menunggu masukan. Bukan perulangan tak berujung, melainkan cin >> yang menanti angka yang tidak pernah kamu ketik.

Hentikan program yang menggantung dengan Ctrl + C. Untuk melihat apa yang sebenarnya terjadi, sisipkan sementara cerr << i << " " << n << "\n"; di dalam perulangan — cerr dipakai, bukan cout, supaya tidak mengotori keluaran yang dinilai (Bab 10).

Pekerjaan rumah

1
12
123
1234

Kesalahan yang paling sering

Tips OSN

Pola banyak kasus uji harus otomatis. Sebagian soal OSN membungkus satu soal kecil ke dalam T kasus uji. Bentuknya selalu sama, dan sebaiknya sudah hafal:

int t;
cin >> t;
while (t--) {
    // baca satu kasus, cetak satu jawaban
}

Dua kesalahan yang sering muncul di pola ini: variabel penampung yang lupa dikembalikan ke nol di awal setiap kasus, dan jawaban yang dikumpulkan dulu lalu dicetak di akhir padahal soal meminta satu baris per kasus.

Perkirakan banyaknya langkah sebelum menulis kode. Aturan kasar yang dipakai sepanjang buku ini: mesin penilai menyelesaikan sekitar 10⁸ operasi sederhana per detik. Dari situ, batasan pada soal langsung memberi tahu bentuk penyelesaian yang muat:

Batasan 10¹⁸ adalah isyarat yang jelas: yang diminta rumus atau pengulangan atas digit-nya, bukan atas nilainya.

Nilai antara bisa jauh lebih besar daripada masukan. Soal yang menyatakan N ≤ 10⁶ tidak menjamin semua angka di dalam programmu tetap kecil. Deret Collatz di bawah adalah contohnya: mulai dari 704.511, deretnya sempat mencapai 56.991.483.520 — melewati int lebih dari dua puluh kali lipat.

Perulangan yang tidak berhenti dinilai Time Limit Exceeded, bukan error. Kalau jawabanmu benar di komputer sendiri tetapi kena TLE di semua berkas uji, curigai syarat berhenti yang tidak pernah tercapai — misalnya while (n != 1) untuk n yang bisa bernilai 0.

Keluaran banyak baris lebih baik dikumpulkan. Untuk soal yang mencetak ratusan ribu baris, mencetak dengan endl di setiap perulangan membuat program berkali-kali lipat lebih lambat. Pakai "\n".

Ringkasan

• for dipakai saat banyaknya putaran diketahui, while saat hanya syarat berhentinya yang diketahui.
• Tiga bagian for: awal (sekali), syarat (sebelum tiap putaran), perubahan (sesudah tiap putaran).
• for (int i = 0; i < n; i++) berputar n kali dan cocok dengan indeks array; mengganti < menjadi <= menambah satu putaran.
• Pola akumulasi: siapkan penampung, ubah tiap putaran, pakai sesudahnya. Nilai awalnya berbeda untuk jumlah, hasil kali, dan nilai terbesar.
• while (n > 0) { n % 10; n /= 10; } membaca sebuah bilangan digit demi digit dari belakang.
• Perulangan bersarang mengerjakan sekitar n² langkah — cukup untuk n ribuan, tidak untuk n ratusan ribu.
• Penampung pada soal banyak kasus uji harus disiapkan ulang di setiap kasus.

Latihan bergaya OSN

Ketiga soal berikut dikerjakan dengan perulangan saja — belum perlu array. Soal ketiga memakai pola banyak kasus uji yang akan sering kamu temui di OSN.

Kerangka ketiganya ada di exercises/05/osn/.

Soal 1 — Deret Collatz

Ambil sebuah bilangan bulat positif N. Selama angkanya belum sama dengan 1, terapkan aturan berikut berulang-ulang:

• kalau angkanya genap, bagi dua;
• kalau angkanya ganjil, kalikan tiga lalu tambah satu.

Satu kali penerapan aturan dihitung sebagai satu langkah. Hitung berapa langkah yang diperlukan sampai angkanya menjadi 1.

Format masukan. Satu baris berisi satu bilangan bulat N.

Format keluaran. Satu baris berisi banyaknya langkah.

Batasan. 1 ≤ N ≤ 10⁶. Untuk semua N pada batasan ini, deretnya dijamin mencapai 1.

Contoh masukan

6

Contoh keluaran

8

Penjelasan. Deretnya 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1, yaitu delapan langkah. Untuk N = 1, jawabannya 0 karena angkanya sudah 1 sejak awal.

Kerangkanya: exercises/05/osn/01-collatz.cpp

Soal 2 — Palindrom Angka

Sebuah bilangan disebut palindrom kalau urutan digitnya dibaca dari depan sama dengan dibaca dari belakang. Misalnya 12321 dan 7 adalah palindrom, sedangkan 12345 dan 10 bukan.

Format masukan. Satu baris berisi satu bilangan bulat N.

Format keluaran. Satu baris berisi YA kalau N palindrom, atau TIDAK kalau bukan.

Batasan. 1 ≤ N ≤ 10¹⁸. Bilangan tidak boleh dibaca sebagai teks.

Contoh masukan

12321

Contoh keluaran

YA

Penjelasan. Digit 12321 dibaca dari belakang tetap 12321. Perhatikan batasan 10¹⁸: bilangan sebesar itu tidak muat di int, dan perulangan sebanyak N kali jelas tidak mungkin — yang diulang adalah digitnya, dan digitnya paling banyak 19.

Kerangkanya: exercises/05/osn/02-palindrom-angka.cpp

Soal 3 — Banyak Faktor

Untuk setiap bilangan yang diberikan, hitung ada berapa bilangan bulat positif yang membaginya habis.

Format masukan. Baris pertama berisi satu bilangan bulat T, banyaknya kasus uji. T baris berikutnya masing-masing berisi satu bilangan bulat N.

Format keluaran. T baris. Baris ke-i berisi banyaknya faktor positif dari N pada kasus uji ke-i.

Batasan.

• 1 ≤ T ≤ 50
• 1 ≤ N ≤ 100.000

Contoh masukan

3
12
1
97

Contoh keluaran

6
1
2

Penjelasan. Faktor 12 adalah 1, 2, 3, 4, 6, dan 12 — ada enam. Bilangan 1 hanya punya satu faktor, yaitu dirinya sendiri. Bilangan 97 adalah bilangan prima, jadi faktornya hanya 1 dan 97.

Kerangkanya: exercises/05/osn/03-banyak-faktor.cpp

Bingung atau sudah selesai? Buka halaman pembahasan PR.