06. Fungsi — Pembahasan PR

Berkas .cpp jawabannya ada di exercises/06/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/06/homework/solutions/01-maksimum.cpp
./jawab

Soal 1 — Fungsi maksimum

Soal. Tulis maksimum(a, b) lalu maksimum3(a, b, c) yang memakainya.

Cara berpikir. Inti soal ini: fungsi boleh memanggil fungsi lain. Setelah maksimum untuk dua bilangan ada, bandingkan hasilnya dengan bilangan ketiga — tidak perlu menulis ulang logikanya.

Pembahasan.

int maksimum(int a, int b) {
    return (a > b) ? a : b;
}

int maksimum3(int a, int b, int c) {
    return maksimum(maksimum(a, b), c);
}

Uji.

Nilai soal ini bukan pada jawabannya, melainkan pada bentuknya: maksimum3 memanggil maksimum dua kali, bukan menulis ulang perbandingannya. Pola "fungsi kecil dipakai fungsi yang lebih besar" inilah yang membuat soal panjang tetap terkendali.

Kesalahan umum.

• Menyalin logika perbandingan ke dalam maksimum3 alih-alih memanggil maksimum. Jawaban tetap benar, tetapi kesempatan belajarnya hilang.
• Lupa return di salah satu cabang. Compiler hanya memberi peringatan (dengan -Wall), dan nilai kembalinya menjadi sampah.

Soal 2 — Cacah bilangan prima

Soal. Hitung banyaknya bilangan prima dari 1 sampai n.

Cara berpikir. Pisahkan dua pekerjaan: satu fungsi menjawab "apakah satu bilangan prima", main mengurus perulangan dan pencacahan. Fungsi prima sama persis dengan tantangan Bab 05, kini dibungkus agar bisa dipakai ulang.

Pola return false di tengah perulangan menggantikan variabel penanda dan break — begitu satu faktor ditemukan, jawabannya sudah pasti.

Pembahasan.

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

int banyak = 0;
for (int i = 2; i <= n; i++) if (prima(i)) banyak++;
cout << banyak << "\n";

Perlu diingat batasnya: cara ini memeriksa setiap bilangan satu per satu, dengan biaya sekitar n √n langkah. Untuk n = 1.000.000 masih jalan beberapa detik; di atas itu dibutuhkan saringan Eratosthenes, yang memakai array dan dibahas di Bab 07.

Uji.

Baris pertama adalah kasus tepi yang wajib: fungsi prima(1) harus mengembalikan false. Kalau pemeriksaannya hanya berupa perulangan i * i <= n, perulangan itu tidak pernah berjalan untuk n = 1 dan fungsinya salah menjawab true.

Kesalahan umum.

• Memulai perulangan dari 1, lalu ikut menghitung 1 sebagai prima. Penjaga if (n < 2) return false; mencegahnya.
• Menghitung 2 sebagai bukan prima karena perulangan i * i <= n ditulis i < n.

Soal 3 — Pangkat rekursif

Soal. pangkat(a, b) secara rekursif.

Cara berpikir. Rumusnya langsung menjadi kode: aᵇ = a × aᵇ⁻¹, dan a⁰ = 1. Kasus dasar b == 0 harus diperiksa lebih dulu, jika tidak rekursinya turun ke b negatif dan tidak pernah berhenti.

Pembahasan.

long long pangkat(long long a, int b) {
    if (b == 0) return 1;
    return a * pangkat(a, b - 1);
}

Cara ini memerlukan b pemanggilan. Ada cara yang jauh lebih cepat dengan membelah pangkatnya menjadi dua (a⁸ = a⁴ × a⁴), hanya butuh sekitar log₂ b langkah. Itulah pangkat modulo cepat di Bab 14.

Uji.

Baris kedua menguji kasus dasarnya: apa pun a, pangkat nol bernilai 1. Baris ketiga menguji batas yang disebut soal — 2⁶⁰ masih muat di long long, sedangkan 2⁶⁴ sudah tidak.

Kesalahan umum.

• Menulis kasus dasar b == 1, sehingga pangkat(a, 0) tidak pernah berhenti.
• Memakai int untuk hasil. 2⁴⁰ sudah melewati batas int.

Soal 4 — Membalik bilangan

Soal. Balik urutan digit, lalu periksa palindrom.

Cara berpikir. Membangun bilangan terbalik memakai satu baris yang perlu dihafal:

hasil = hasil * 10 + n % 10;

Setiap putaran menggeser hasil satu digit ke kiri (dikali 10) lalu menempelkan digit terakhir n di posisi satuan. Contoh untuk 4071:

Setelah fungsinya ada, pemeriksaan palindrom cukup satu baris: balik(n) == n.

Pembahasan.

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

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

Uji.

Baris terakhir memperlihatkan kenapa membalik bilangan bukan operasi yang bisa dibalik lagi: 1200 dibalik menjadi 0021, dan nol di depan hilang sendirinya sehingga tersisa 21. Untuk memeriksa palindrom hal itu tidak masalah, tetapi kalau soal meminta bilangan terbalik dicetak apa adanya, kasus angka nol di belakang perlu diperhatikan.

Kesalahan umum.

• Menulis hasil = hasil + n % 10 tanpa mengalikan 10, sehingga yang dihasilkan jumlah digit, bukan bilangan terbalik.
• Mengubah n di main dengan memanggil fungsi, lalu membandingkan dengan n yang sudah berubah. Karena parameternya salinan, n di main aman — ini contoh gunanya pengiriman salinan.

Tantangan — Fibonacci dengan ingatan

Soal. Percepat fib rekursif dengan menyimpan hasil yang sudah dihitung.

Cara berpikir. Versi lambat menghitung fib(40) dengan lebih dari 300 juta pemanggilan, padahal jawaban yang berbeda hanya ada 41 buah. Semuanya terhitung ulang berkali-kali.

Perbaikannya tiga baris: sediakan array ingat berisi -1 sebagai tanda "belum pernah dihitung", periksa array itu di awal fungsi, dan isi array itu sebelum mengembalikan hasil.

Pembahasan.

long long ingat[100];

long long fib(int n) {
    if (n <= 1) return n;
    if (ingat[n] != -1) return ingat[n];
    ingat[n] = fib(n - 1) + fib(n - 2);
    return ingat[n];
}

int main() {
    for (int i = 0; i < 100; i++) ingat[i] = -1;
    ...
}

Sesudah perubahan, setiap nilai dihitung tepat sekali: fib(45) selesai seketika, dan fib(90) pun masih muat di long long (2.880.067.194.370.816.120).

Uji.

Bandingkan waktunya: fib(45) tanpa ingatan memerlukan 3.672.623.805 pemanggilan, dengan ingatan hanya 46 keadaan yang masing-masing dihitung sekali — jawabannya muncul seketika. Baris terakhir adalah batas praktis tipe long long: fib(93) sudah melewatinya.

Kesalahan umum.

• Lupa mengisi ingat dengan -1. Array global berisi nol, dan nol adalah jawaban sah untuk fib(0) — akibatnya semua jawaban menjadi nol.
• Memakai 0 sebagai tanda "belum dihitung" pada soal yang jawabannya bisa bernilai nol. Pilih tanda yang mustahil menjadi jawaban.
• Menyimpan hasil tetapi tidak memeriksanya di awal fungsi, sehingga tidak ada yang lebih cepat.

Latihan bergaya OSN — pembahasan

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

Soal 1 — Akar Digit

Cara berpikir. Soal ini punya dua tingkat perulangan yang berbeda sifatnya: satu menjumlahkan digit, satu lagi mengulangi penjumlahan itu sampai hasilnya tinggal satu digit. Memisahkan yang pertama menjadi fungsi membuat yang kedua tinggal satu baris.

Perulangan luarnya berhenti saat n < 10. Jangan memakai "ulangi dua kali" atau jumlah putaran tetap: untuk N sampai 10¹⁸, jumlah digitnya paling besar 19 × 9 = 171, lalu 1 + 7 + 1 = 9 — jadi paling banyak tiga putaran, tetapi menuliskannya sebagai syarat jauh lebih aman daripada menghitungnya sendiri.

Pembahasan.

long long jumlahDigit(long long n) {
    long long total = 0;
    while (n > 0) {
        total += n % 10;
        n /= 10;
    }
    return total;
}

int main() {
    int t;
    cin >> t;

    while (t--) {
        long long n;
        cin >> n;

        while (n >= 10) n = jumlahDigit(n);

        cout << n << "\n";
    }
    return 0;
}

Ada jalan pintas yang tidak memerlukan perulangan sama sekali: akar digit sebuah bilangan positif selalu sama dengan 1 + (n - 1) % 9. Sifat itu berasal dari kenyataan bahwa jumlah digit dan bilangan aslinya selalu bersisa sama saat dibagi 9 — alasannya dibahas di Bab 14. Kirim versi perulangan lebih dulu, lalu bandingkan keduanya untuk semua n dari 1 sampai 100000 sebagai latihan.

Uji.

Kesalahan umum.

• Memakai int untuk n, sehingga batas atas tidak terbaca.
• Menulis while (n > 10), sehingga n yang bernilai tepat 10 tidak pernah disederhanakan dan jawabannya tercetak 10 — dua digit.
• Menjumlahkan digit hanya satu kali, sehingga 9875 menjawab 29.

Soal 2 — Menara Hanoi

Cara berpikir. Ini soal rekursi yang paling murni: penyelesaiannya didefinisikan dengan penyelesaian soal yang sama berukuran lebih kecil.

Untuk memindahkan n cakram dari asal ke tujuan, cakram terbesar baru bisa bergerak kalau n − 1 cakram di atasnya sudah menyingkir ke tiang ketiga. Jadi urutannya selalu tiga langkah:

1. pindahkan n − 1 cakram dari asal ke bantu, memakai tujuan sebagai tiang bantu;
2. pindahkan satu cakram terbesar dari asal ke tujuan;
3. pindahkan n − 1 cakram dari bantu ke tujuan, memakai asal sebagai tiang bantu.

Kasus dasarnya n == 0: tidak ada yang perlu dipindahkan.

Perhatikan bahwa peran ketiga tiang bertukar di setiap pemanggilan. Itulah sebabnya ketiganya dikirim sebagai parameter, bukan ditulis tetap.

Pembahasan.

void pindah(int n, char asal, char bantu, char tujuan) {
    if (n == 0) return;
    pindah(n - 1, asal, tujuan, bantu);
    cout << asal << " " << tujuan << "\n";
    pindah(n - 1, bantu, asal, tujuan);
}

int main() {
    int n;
    cin >> n;

    long long banyak = (1LL << n) - 1;
    cout << banyak << "\n";

    pindah(n, 'A', 'B', 'C');
    return 0;
}

1LL << n adalah cara cepat menulis 2^n. Untuk n ≤ 15 sebenarnya int sudah cukup, tetapi kebiasaan memakai 1LL menghindarkan luapan saat batasannya dinaikkan.

Uji. Untuk N = 3, keluarannya:

7
A C
A B
C B
A C
B A
B C
A C

Periksa dua hal: banyaknya baris perpindahan harus tepat 2^N − 1, dan cakram terbesar hanya boleh bergerak satu kali, tepat di tengah daftar. Untuk N = 15, keluarannya 32.768 baris — satu baris jumlah ditambah 32.767 perpindahan.

echo 15 | ./hanoi | wc -l

Kesalahan umum.

• Menukar urutan parameter pada salah satu pemanggilan rekursif. Programnya tetap jalan dan tetap mencetak 2^N − 1 baris, tetapi urutannya melanggar aturan cakram.
• Memakai endl di dalam rekursi. Untuk N = 15 itu 32.767 kali flush yang tidak perlu.
• Menulis kasus dasar if (n == 1) lalu lupa mencetak perpindahannya.

Soal 3 — Bilangan Sempurna

Cara berpikir. Bagian yang diulang tiga kali — menjumlahkan faktor — diangkat menjadi fungsi, sehingga main tinggal membandingkan. Cara mencari faktornya sama seperti soal Bab 05: berpasangan, sampai akar N.

Dua hal yang berbeda dari soal Bab 05. Pertama, yang dijumlahkan adalah faktor sejati, jadi N sendiri tidak ikut. Karena itu pencacahan dimulai dari total = 1 dan perulangannya dari i = 2. Kedua, N bisa mencapai 10⁹, sehingga jumlah faktornya bisa melewati batas int — penampungnya long long.

Bilangan 1 perlu ditangani terpisah: ia tidak punya faktor sejati sama sekali, sedangkan rumus total = 1 akan menjawab 1.

Pembahasan.

long long jumlahFaktorSejati(int n) {
    if (n == 1) return 0;

    long long total = 1;                    // 1 selalu faktor sejati
    for (int i = 2; (long long)i * i <= n; i++) {
        if (n % i == 0) {
            total += i;
            int pasangan = n / i;
            if (pasangan != i) total += pasangan;
        }
    }
    return total;
}

Uji.

Kesalahan umum.

• Memulai perulangan dari i = 1 dan menambahkan pasangannya, sehingga N sendiri ikut terjumlah dan semua bilangan menjadi BERLEBIH.
• Lupa memisahkan N = 1, sehingga jawabannya SEMPURNA.
• Memeriksa i sampai N, bukan sampai akar N. Untuk T = 100 dan N = 10⁹ itu 10¹¹ putaran — jauh melewati batas waktu.
• Lupa pemeriksaan pasangan != i pada bilangan kuadrat.

Kalau masih tersendat

• Fungsi tidak dikenali saat dipanggil → Bab 06, bagian Bentuk sebuah fungsi (tulis di atas pemanggilnya, atau deklarasikan lebih dulu).
• Perubahan di dalam fungsi tidak terbawa keluar → Bab 06, tabel pada bagian Nilai salinan dan referensi.
• Rekursi berhenti mendadak atau tidak berhenti → Bab 06, bagian Rekursi dan gambar tumpukan pemanggilannya.

Sebelum lanjut ke Bab 07, pastikan kamu bisa menjelaskan dalam satu kalimat kenapa fib rekursif polos lambat — jawabannya adalah setengah dari isi Bab 13.