05. Perulangan — Pembahasan PR

Berkas .cpp jawabannya ada di exercises/05/homework/solutions/.

Halaman ini dibuka sesudah mencoba sendiri. Bandingkan jalan pikiranmu dengan bagian Cara berpikir, bukan kodenya baris per baris: dua kode yang berbeda bentuk bisa sama-sama benar, dan yang perlu ditiru adalah cara sampai ke sana. Bagian Uji di tiap soal berisi masukan dan keluaran yang sudah diperiksa — jalankan jawabanmu sendiri dengan masukan itu sebelum merasa selesai.

Menjalankan salah satu jawabannya:

g++ -std=c++17 -O2 -o jawab exercises/05/homework/solutions/01-jumlah-n.cpp
./jawab

Soal 1 — Jumlah 1 sampai N

Soal. Baca n sampai 1.000.000, cetak jumlah 1 sampai n.

Cara berpikir. Pola akumulasi biasa. Yang diuji di sini adalah pemilihan tipe: untuk n = 1.000.000, hasilnya 500.000.500.000 — sekitar 5 × 10¹¹, jauh melewati batas int. Penampungnya harus long long.

Pembahasan.

int n;
cin >> n;

long long total = 0;
for (int i = 1; i <= n; i++) total += i;

cout << total << "\n";

Rumus n × (n + 1) / 2 memberi jawaban yang sama tanpa perulangan:

long long total = (long long)n * (n + 1) / 2;

Bentuk (long long)n penting: tanpa itu, n * (n + 1) dihitung sebagai int dan meluap sebelum sempat disimpan.

Uji.

Baris ketiga adalah pemeriksaan tipe data: dengan penampung int, program mencetak 1784293664 — angka yang sama sekali tidak menyerupai jawaban yang benar, dan tidak disertai pesan error apa pun.

Kesalahan umum.

• Memakai int total. Hasilnya angka negatif tanpa pesan error.
• Memakai rumus tetapi lupa cast, sehingga hasilnya tetap salah.

Soal 2 — Jumlah digit

Soal. Jumlahkan digit sebuah bilangan sampai 10¹⁸.

Cara berpikir. Ambil digit terakhir dengan % 10, tambahkan ke penampung, buang digit itu dengan / 10, ulangi selama bilangannya masih lebih dari nol. Karena batasnya 10¹⁸, bilangan yang dibaca harus long long; penampung jumlahnya boleh int karena maksimalnya hanya 19 × 9 = 171.

Pembahasan.

long long n;
cin >> n;

int jumlah = 0;
while (n > 0) {
    jumlah += n % 10;
    n /= 10;
}

cout << jumlah << "\n";

Uji.

Baris terakhir menguji dua hal sekaligus: bilangan 18 digit hanya muat di long long, dan jumlah digitnya (18 × 9 = 162) memastikan seluruh digit terbaca, bukan sebagian.

Kesalahan umum.

• Membaca ke int untuk masukan 10¹⁸. cin akan gagal dan n berisi nilai tak terduga.
• Menulis while (n >= 0), yang tidak pernah berhenti karena 0 / 10 tetap 0.

Soal 3 — Tabel perkalian

Soal. Cetak tabel n × n, angka dipisahkan spasi, tanpa spasi di akhir baris.

Cara berpikir. Dua perulangan bersarang: yang luar mengurus baris, yang dalam mengurus kolom. Bagian yang menjebak adalah spasi. Kalau ditulis cout << i * j << " ", setiap baris berakhir dengan spasi tambahan. Sebagian penilai memaafkannya, sebagian tidak — biasakan cara yang aman: cetak spasi sebelum angka, kecuali angka pertama.

Pembahasan.

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        if (j > 1) cout << " ";
        cout << i * j;
    }
    cout << "\n";
}

Uji. Masukan 3 menghasilkan:

1 2 3
2 4 6
3 6 9

Periksa tidak ada spasi di akhir baris. Cara termudah: cetak spasi sebelum angka kecuali untuk kolom pertama, atau cetak angka lalu spasi kecuali untuk kolom terakhir.

Kesalahan umum.

• Menaruh cout << "\n" di dalam perulangan dalam, sehingga setiap angka jatuh ke baris sendiri.
• Memakai endl di dalam perulangan besar. Untuk keluaran ribuan baris, "\n" jauh lebih cepat.

Soal 4 — Segitiga angka

Soal. Cetak pola segitiga berisi angka 1 sampai nomor barisnya.

Cara berpikir. Perhatikan hubungan antara nomor baris dan isinya: baris ke-b berisi angka 1 sampai b. Jadi batas perulangan dalam adalah variabel perulangan luar. Ini pola yang sama dengan segitiga bintang di bab, hanya yang dicetak berganti dari * menjadi nomor kolom.

Pembahasan.

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

Uji. Masukan 4 menghasilkan:

1
12
123
1234

Perhatikan hubungan baris dan isinya: baris ke-i berisi angka 1 sampai i. Itu berarti batas perulangan dalam bergantung pada perulangan luar — bentuk yang sama dengan segitiga bintang di Bab 05.

Kesalahan umum.

• Menulis kolom <= n pada perulangan dalam, sehingga semua baris sama panjang.
• Mencetak baris alih-alih kolom, sehingga keluarannya 1 / 22 / 333.

Tantangan — Uji bilangan prima

Soal. Tentukan n sampai 10¹² prima atau bukan.

Cara berpikir. Memeriksa setiap bilangan dari 2 sampai n − 1 berarti 10¹² langkah — butuh waktu berjam-jam. Kuncinya: kalau n = a × b dengan a ≤ b, maka a ≤ √n. Artinya, kalau tidak ada faktor sampai akar n, tidak akan ada faktor sama sekali. Jumlah langkahnya turun menjadi 10⁶, selesai dalam sepersekian detik.

Tulis syaratnya sebagai i * i <= n, bukan i <= sqrt(n): sqrt bekerja dengan double dan bisa meleset satu di bilangan besar.

Jangan lupa dua kasus tepi: n = 0 dan n = 1 bukan prima, sedangkan n = 2 prima.

Pembahasan.

long long n;
cin >> n;

if (n < 2) {
    cout << "BUKAN\n";
    return 0;
}

bool prima = true;
for (long long i = 2; i * i <= n; i++) {
    if (n % i == 0) {
        prima = false;
        break;
    }
}

cout << (prima ? "PRIMA" : "BUKAN") << "\n";

Uji.

Baris pertama adalah kasus tepi yang paling sering terlewat: 1 bukan bilangan prima, tetapi perulangan i * i <= n tidak pernah berjalan untuk n = 1, sehingga program menjawab PRIMA kalau tidak diberi pemeriksaan khusus. Baris terakhir menguji kecepatan: dengan cara akar hanya sekitar 31.623 putaran, sedangkan memeriksa sampai n - 1 memerlukan hampir satu miliar putaran.

Kesalahan umum.

• Menulis int i pada perulangan. Untuk n mendekati 10¹², i * i meluap sebagai int.
• Lupa break. Programnya tetap benar, tetapi mengerjakan sisa perulangan tanpa guna.
• Menjawab PRIMA untuk n = 1, karena perulangannya tidak pernah berjalan dan prima tetap true.

Latihan bergaya OSN — pembahasan

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

Soal 1 — Deret Collatz

Cara berpikir. Banyaknya langkah tidak diketahui sebelum dijalankan, jadi bentuknya while, bukan for. Syarat berhentinya diambil langsung dari kalimat soal: "selama angkanya belum sama dengan 1".

Bagian yang menentukan benar-salahnya jawaban bukan perulangannya, melainkan tipe datanya. Batasan N ≤ 10⁶ menggoda untuk memakai int, tetapi nilai yang muncul di tengah deret jauh lebih besar daripada N.

Pembahasan.

long long n;
cin >> n;

long long langkah = 0;
while (n != 1) {
    if (n % 2 == 0) n /= 2;
    else n = 3 * n + 1;
    langkah++;
}

cout << langkah << "\n";

Uji.

Baris terakhir adalah pemeriksaan tipe. Mulai dari 704.511, deretnya sempat mencapai 56.991.483.520 — nilai terbesar yang muncul untuk semua N sampai 10⁶. Dengan penampung int, nilai itu meluap, deretnya berbelok ke jalur yang salah, dan program mencetak 211 alih-alih 242. Tidak ada pesan error apa pun.

Kesalahan umum.

• Memakai int. Program tetap berjalan dan tetap mencetak angka.
• Menghitung langkah sebelum aturan diterapkan, sehingga N = 1 menghasilkan 1, bukan 0.
• Menulis while (n > 1) lalu menambah cabang untuk n genap saja. Untuk soal ini while (n > 1) juga benar, tetapi hanya karena deretnya dijamin turun sampai 1; kebiasaan yang lebih aman adalah menyalin syarat berhenti dari kalimat soal apa adanya.

Soal 2 — Palindrom Angka

Cara berpikir. Membalik bilangan memakai pasangan % 10 dan / 10 yang sama seperti bagian Memproses digit di Bab 05, tetapi arahnya dibalik: setiap digit yang diambil dari belakang didorong ke depan penampung dengan balik = balik * 10 + digit.

Satu jebakan: perulangan menghabiskan n, jadi nilai aslinya harus disalin dulu sebelum perulangan dimulai. Kalau tidak, di akhir tidak ada lagi yang bisa dibandingkan.

Banyaknya putaran adalah banyaknya digit — paling banyak 19 untuk batasan ini — bukan N kali.

Pembahasan.

long long n;
cin >> n;

long long asli = n;
long long balik = 0;
while (n > 0) {
    balik = balik * 10 + n % 10;
    n /= 10;
}

if (balik == asli) cout << "YA\n";
else cout << "TIDAK\n";

Uji.

Baris 10 layak diperhatikan: balikannya adalah 01, yang sebagai bilangan bernilai 1, jadi jawabannya TIDAK. Ini benar — dan sekaligus alasan kenapa menyimpan digit ke dalam teks tidak diperlukan.

Kesalahan umum.

• Lupa menyalin n ke asli, sehingga di akhir n sudah bernilai 0.
• Memakai int, sehingga bilangan pada batas atas tidak bisa dibaca sama sekali.
• Menulis balik = balik + n % 10 * 10. Urutannya salah: penampung yang lama harus digeser satu digit ke kiri lebih dulu.

Soal 3 — Banyak Faktor

Cara berpikir. Cara paling langsung adalah memeriksa setiap i dari 1 sampai N dan menghitung yang membagi habis. Untuk N ≤ 100.000 dan T ≤ 50, itu sekitar 5 × 10⁶ pemeriksaan — masih muat.

Tetapi ada cara yang jauh lebih baik, dan sebaiknya dibiasakan sejak sekarang: faktor selalu datang berpasangan. Kalau i membagi habis N, maka N / i juga. Salah satu dari pasangan itu pasti tidak lebih besar daripada akar N, jadi cukup memeriksa i sampai i × i ≤ N dan menghitung dua faktor sekaligus. Perkecualiannya adalah bilangan kuadrat, saat i dan N / i bernilai sama dan hanya boleh dihitung sekali.

Pembahasan.

int t;
cin >> t;

for (int kasus = 0; kasus < t; kasus++) {
    int n;
    cin >> n;

    int banyak = 0;
    for (int i = 1; (long long)i * i <= n; i++) {
        if (n % i == 0) {
            banyak++;                      // faktor i
            if (i != n / i) banyak++;      // pasangannya n/i
        }
    }

    cout << banyak << "\n";
}

Perhatikan banyak dikembalikan ke nol di dalam perulangan kasus uji. Ini kesalahan paling sering pada soal banyak kasus: penampung yang dideklarasikan di luar akan membawa sisa perhitungan kasus sebelumnya.

Uji.

Uji juga bilangan kuadrat seperti 36, yang jawabannya 9: kalau pemeriksaan i != n / i dihilangkan, angka 6 terhitung dua kali dan jawabannya menjadi 10.

Kesalahan umum.

• Menaruh int banyak = 0; di luar perulangan kasus uji.
• Lupa i != n / i, sehingga semua bilangan kuadrat kelebihan satu faktor.
• Memulai perulangan dari i = 0, yang langsung menyebabkan pembagian dengan nol dan Runtime Error.

Kalau masih tersendat

• Perulangan berjalan satu kali terlalu banyak atau kurang → Bab 05, tabel banyak putaran.
• Penampung bernilai aneh → Bab 05, tabel nilai awal pada bagian Pola akumulasi.
• Program menggantung → Bab 05, bagian Kalau perulangan tidak mau berhenti.

Sebelum lanjut ke Bab 06, pastikan kamu bisa menulis dari ingatan: pola menjumlahkan n bilangan, pola mencari nilai terbesar, dan pola memproses digit dengan % 10 dan / 10.