Desain Algoritma dan Pemecahan Masalah

Berpikir komputasional adalah kumpulan alat mental untuk menganalisis masalah dan merancang solusi yang dapat dijalankan komputer. Dua hal penting adalah abstraksi dan dekomposisi.

Abstraksi

Abstraksi berarti menjaga fitur-fitur esensial dari masalah dan mengabaikan detail yang tidak relevan, memberikan model yang lebih sederhana.

Contoh-contoh:

• peta jaringan kereta api mempertahankan stasiun dan jalur tetapi menghilangkan geografisnya.
• kelas dalam pemrograman berorientasi objek hanya mempertahankan atribut dan metode yang dibutuhkan sistem.
• fungsi menyembunyikan sebagian pekerjaan di balik sebuah nama.

Model lengkap dari masalah nyata apa pun akan terlalu besar untuk dipikirkan, jadi abstraksi sangat penting.

Penguji meminta tujuan abstraksi dan manfaat-nya. Tujuan: untuk menghasilkan model yang lebih sederhana dari sebuah masalah yang hanya berisi detail yang diperlukan untuk menyelesaikannya. Manfaat: masalah menjadi lebih mudah dipahami dan diprogram; program lebih kecil dan lebih cepat ditulis serta diuji; model yang sama dapat digunakan kembali untuk masalah serupa. Ketika Anda diminta untuk membuat model abstrak dari suatu sistem, sebutkan hanya data dan tindakan yang dibutuhkan oleh tugas tersebut. Untuk jadwal sekolah, ini berarti kelas, ruang, guru, dan periode; bukan berarti warna ruangan atau usia guru.

Dekomposisi

Dekomposisi berarti memecah masalah besar menjadi sub-masalah yang lebih kecil, masing-masing lebih mudah diselesaikan dan ditangani satu per satu.

1. temukan bagian utama dari tugas.
2. pecahkan setiap bagian menjadi sub-tugas yang lebih kecil.
3. lanjutkan hingga setiap bagian cukup kecil untuk dirancang secara langsung.
4. selesaikan tugas-tugas kecil dan gabungkan hasilnya.

Untuk pengendalian stok: "kelola stok" → "catat penjualan", "catat pengiriman", "hasilkan laporan" → ("catat penjualan") "cari produk", "kurangi jumlah stok", "simpan transaksi". Dekomposisi membuat masalah besar dapat dikelola, memungkinkan tim membagi pekerjaan, dan memberikan kode modular — setiap modul menjadi prosedur atau fungsi.

"Jelaskan mengapa dekomposisi digunakan" adalah soal bernilai tiga dengan struktur tetap. Berikan tiga manfaat terpisah: setiap sub-masalah cukup kecil untuk dirancang, diprogram, dan diujinya sendiri; programmer berbeda dapat bekerja pada modul yang berbeda secara bersamaan; modul yang sudah ada (atau rutinitas perpustakaan) dapat digunakan kembali, dan kesalahan lebih mudah ditemukan karena terletak di dalam satu modul. Peta struktur (topik 12) adalah diagram dari dekomposisi: program di bagian atas, modul-modul di bawahnya, dan data yang dilewatkan di antaranya.

Sebuah algoritma adalah solusi yang dinyatakan sebagai serangkaian langkah terdefinisi. Setiap langkah tidak ambigu (satu makna), deterministik (input yang sama → output yang sama), finite (langkah-langkah berakhir), dan efektif (setiap langkah dapat dilakukan). Algoritma menyatakan apa yang harus dilakukan, terlepas dari bahasa pemrograman yang digunakan untuk mengimplementasikannya.

Ketika Anda memulai algoritma, daftarkan setiap komponen data dalam tabel pengenal — pengenal-nya (nama variabel), tipe data, dan deskripsi. Tabel ujian memiliki tepat tiga kolom ini:

Gunakan nama deskriptif (ItemCost, bukan x): pengenal dimulai dengan huruf, tidak mengandung spasi, dan ditulis sama setiap kali muncul. Tipe umum adalah INTEGER, REAL, STRING, CHAR, BOOLEAN, DATE, serta array. Tabel memaksa Anda untuk menamai setiap bagian data sebelum menulis kode, dan pertanyaan "lengkapi tabel pengenal" memberikan satu nilai untuk setiap tipe data atau deskripsi yang benar, jadi tulis tipe persis seperti panduan pseudocode.

*Tabel pengenal menamai setiap bagian data sebelum Anda menulis kode

Pseudocode adalah cara terstruktur dan netral bahasa untuk mendeskripsikan algoritma.

1. Urutan

Langkah-langkah berjalan satu setelah lainnya (urutan):

INPUT Name
INPUT Age
OUTPUT "Hello", Name

2. Seleksi

Pilihan langkah mana yang akan dijalankan, berdasarkan suatu kondisi (seleksi):

IF Age >= 18 THEN
    OUTPUT "Adult"
ELSE
    OUTPUT "Minor"
ENDIF

Untuk opsi tambahan, gunakan CASE OF ... ENDCASE.

3. Iterasi

Pengulangan sebuah blok (iterasi, sebuah perulangan):

FOR i ← 1 TO 10
    OUTPUT i
NEXT i

Perulangan WHILE menguji kondisi sebelum setiap putaran (mungkin berjalan nol kali); perulangan REPEAT...UNTIL menguji setelah setiap putaran (selalu berjalan setidaknya sekali).

WHILE Total < 100 DO
    INPUT Value
    Total ← Total + Value
ENDWHILE

REPEAT
    INPUT Mark
UNTIL Mark >= 0 AND Mark <= 100

Memilih jenis perulangan itu sendiri bernilai poin: FOR ketika Anda tahu berapa kali (perulangan yang dikendalikan hitung; count-controlled loop); WHILE ketika perulangan mungkin tidak berjalan sama sekali (perulangan pre-kondisi; pre-condition loop); REPEAT ... UNTIL ketika harus berjalan setidaknya sekali, seperti dalam validasi input (perulangan post-kondisi; post-condition loop). Jawaban "deskripsikan konstruk iterasi" menyebutkan nama konstruk, mengatakan di mana kondisi diuji, dan memberikan konsekuensinya (nol kali atau setidaknya sekali).

Operasi umum

• penugasan: x ← 5 (tanda panah; = untuk perbandingan).
• input/output: INPUT variable, OUTPUT expression.
• perbandingan =, <>, <, >, <=, >=; logika AND, OR, NOT.
• aritmatika + - * /, tambah DIV (pembagian bulat) dan MOD (sisa bagi).
• string: LENGTH, LEFT, RIGHT, MID, dan & untuk penggabungan (menyambungkan).

Pseudocode yang diharapkan dalam ujian

Setiap jawapan pseudocode dinilai mengikut panduan pseudocode yang diterbitkan oleh Cambridge. Tulis bentuk ini dengan tepat:

RAND(100) memberikan nombor nyata dari 0 hingga (tetapi tidak termasuk) 100. INT(RAND(100)) + 1 memberikan integer dari 1 hingga 100.

Dua tabiat mendapat markah dalam setiap soalan: nyatakan setiap pembolehubah yang anda gunakan, dengan jenis daripada jadual pengenal anda, dan inisialisasikan setiap pesaing dan jumlah (Count ← 0, Total ← 0) sebelum putaran yang mengubahnya.

Masukan → Proses → Keluaran

Setiap program mengikuti bentuk ini:

INPUT Length
INPUT Width
Area ← Length * Width
OUTPUT "Area = ", Area

Menyenaraikan masukan dan keluaran terlebih dahulu menjadikan algoritma lebih kemas.

Contoh kerja. Tulis pseudocode yang memasukkan 100 integer dan mengeluarkan berapa banyak darinya, serta jumlah mereka, yang terletak antara 10 dan 20 termasuk.

Jadual pengenal: Count : INTEGER (pesaing putaran), Value : INTEGER (integer baru-baru dimasukkan), InRange : INTEGER (berapa banyak yang berada dalam julat), Total : INTEGER (jumlah mereka).

DECLARE Count, Value, InRange, Total : INTEGER
InRange ← 0
Total ← 0
FOR Count ← 1 TO 100
    INPUT Value
    IF Value >= 10 AND Value <= 20 THEN
        InRange ← InRange + 1
        Total ← Total + Value
    ENDIF
NEXT Count
OUTPUT InRange, Total

Jika soalan kemudian meminta anda "kenal pasti dua konstruksi dan nyatakan bagaimana setiap satu digunakan", jawab dalam bentuk yang sama: putaran, putaran FOR, mengulangkan masukan sebanyak 100 kali; pemilihan, pernyataan IF, menambah nilai hanya apabila ia berada dalam julat.

Contoh kerja. Sebuah program memilih integer rahsia dari 1 hingga 100. Pengguna mengira sehingga mereka betul; selepas setiap tebak salah program mengatakan "Terlalu rendah" atau "Terlalu tinggi", dan pada akhirnya ia mengeluarkan berapa banyak tebak yang telah dibuat.

Jadual pengenal: Secret : INTEGER (nombor yang perlu ditebak), Guess : INTEGER (masukan pengguna), Tries : INTEGER (berapa banyak tebak sehingga kini).

DECLARE Secret, Guess, Tries : INTEGER
Secret ← INT(RAND(100)) + 1
Tries ← 0
REPEAT
    INPUT Guess
    Tries ← Tries + 1
    IF Guess < Secret THEN
        OUTPUT "Too low"
    ELSE
        IF Guess > Secret THEN
            OUTPUT "Too high"
        ENDIF
    ENDIF
UNTIL Guess = Secret
OUTPUT "You took ", Tries, " guesses"

Putaran REPEAT ... UNTIL adalah pilihan yang sesuai kerana pengguna mesti menebak sekurang-kurangnya sekali. Markah adalah untuk: nombor rawak dalam julat yang betul, putaran yang berakhir pada tebak yang betul, pesaing yang bermula daripada sifar dan meningkat di dalam putaran, dua mesej di bawah syarat yang betul, dan keluaran akhir.

Contoh kerja. Keluarkan dua integer rawak yang berbeza, masing-masing antara $-10$ dan $10$ termasuk.

Terdapat 21 nilai yang mungkin, jadi INT(RAND(21)) memberikan 0 hingga 20 dan menolak 10 memindahkan julatnya kepada $-10$ hingga $10$. Nombor kedua mesti dijana semula sehingga ia berbeza dari yang pertama:

DECLARE First, Second : INTEGER
First ← INT(RAND(21)) - 10
REPEAT
    Second ← INT(RAND(21)) - 10
UNTIL Second <> First
OUTPUT First, Second

Algoritma yang sama boleh ditulis dengan tiga cara.

• bahasa Inggeris terstruktur — bahasa semula jadi dengan perenggan dan kata kunci tetap; baik untuk penerangan tahap tinggi.
• peta alir — rajah dengan bentuk piawai:

• pseudocode — notasi kata kunci di atas; paling dekat dengan kod.

Anda sepatutnya dapat menukar antara mana-mana pasangan: setiap IF adalah berlian keputusan, setiap putaran adalah anak panah balik, dan urutan adalah segi empat tepat bertindih.

IF ... THEN ... ELSE ... ENDIF

*Peta alir untuk purata senarai nombor, menggunakan bentuk piawai

Penyempurnaan bertingkat bermula dengan garis besar tahap tinggi dan mengembangkan setiap langkah sehingga ia cukup kecil untuk dikod. Untuk purata $n$ nombor:

Tahap 1:

Read in the numbers
Compute the average
Output the average

Tahap 2:

INPUT n
total ← 0
FOR i ← 1 TO n
    INPUT value
    total ← total + value
NEXT i
average ← total / n
OUTPUT average

Setiap penyempurnaan mengekalkan struktur sebelumnya dan menambah butiran.

Soalan "terapkan penyempurnaan bertingkat" enam markah memberikan anda garis besar tahap tinggi dan mahukan setiap langkah dikembangkan kepada pernyataan konkret yang boleh dikod oleh seorang pengaturcaraan. Kekalkan langkah-langkah dalam urutan yang sama, beri nama data yang dibaca atau dihasilkan oleh setiap langkah, dan berhenti apabila setiap baris merupakan masukan tunggal, penugasan, keluaran, putaran atau syarat. Sebagai contoh, "sahkan kata laluan" menjadi: masukkan kata laluan; semak panjangnya sekurang-kurangnya 8; semak ia mengandungi sekurang-kurangnya satu digit; output "diterima" jika kedua-dua semakan berjaya, sebaliknya output "ditolak".

Sebuah pernyataan logik adalah syarat Boolean yang mengawal percabangan, dibina daripada perbandingan (x > 10), penyambung (AND, OR, NOT) dan kurung. Gunakan ia sebagai syarat bagi IF, WHILE atau REPEAT...UNTIL:

WHILE attempts < 3 AND NOT loggedIn DO
    INPUT password
    IF password = correctPassword THEN
        loggedIn ← TRUE
    ELSE
        attempts ← attempts + 1
    ENDIF
ENDWHILE

Kecutuhan (tertinggi ke terendah): NOT, kemudian AND, kemudian OR. Gunakan kurung jika tidak pasti. Kesilapan biasa:

• a = 1 OR 2 adalah salah — tulis a = 1 OR a = 2.
• NOT a > 5 bermaksud NOT (a > 5), iaitu a <= 5.
• NOT (A AND B) sama dengan (NOT A) OR (NOT B) (Hukum De Morgan) — berguna untuk mempermudahkan syarat.

Menukar ayat kepada pernyataan logik adalah kemahiran yang diuji secara langsung dalam kertas peperiksaan. "Tiket percuma untuk sesiapa di bawah 5 atau melebihi 65" menjadi Age < 5 OR Age > 65. "Markah sah jika ia merupakan nombor bulat dari 0 hingga 100" menjadi Mark >= 0 AND Mark <= 100. "Gelung berhenti apabila fail tamat atau sepuluh rekod telah dibaca" menjadi UNTIL EOF(File) OR Count = 10. Tulis setiap perbandingan secara penuh: Age > 65 dan Age < 5, jangan pernah Age > 65 OR < 5.

Contoh berkerja. Tulis jadual pengenal pasti dan pseudocode untuk membaca 10 nombor dan mengeluarkan nilai terbesar. Jadual pengenal pasti menamakan setiap pembolehubah dengan jenis data dan tujuannya: Count : INTEGER (pengira gelung), Num : REAL (nombor yang baru dibaca), Max : REAL (nilai terbesar sehingga kini).

Max ← -999999
FOR Count ← 1 TO 10
    INPUT Num
    IF Num > Max THEN
        Max ← Num
    ENDIF
NEXT Count
OUTPUT Max

Keputusan reka bentuk yang membawa markah ialah mewujudkan Max: ia mesti dimulakan lebih rendah daripada sebarang input yang mungkin - atau, lebih selamat lagi, tetapkan kepada nombor pertama yang dibaca. Inisialisasi ia kepada 0 dan algoritma akan kembali 0 untuk senarai nombor negatif, sebuah ralat yang jejak anda hanya mendedahkan jika data ujian termasuk nombor negatif.

Soal definisi dinilai berdasarkan frasa tetap. Hafalkan ini persis, dan berikan hanya satu jawaban.

• Takrifkan algoritma sebagai satu siri langkah yang jelas, terhingga, deterministik, dan bebas bahasa.
• Gunakan tiga binaan dengan betul — jujukan, pemilihan, pengiterasian — dan kekalkan jadual pengenal pasti dengan jenis data.
• Pecahkan masalah melalui penguraian dan abstraksi, kemudian penyempurnaan bertahap.
• Tulis pseudocode yang sebenarnya boleh berjalan: nyatakan pembolehubah dan ikuti gaya pseudocode peperiksaan.

Kesalahan umum

• Menggunakan = untuk menetapkan nilai. Penetapan ialah ←; = ialah perbandingan.
• Melupakan ENDIF, ENDWHILE, ENDCASE atau NEXT. Setiap binaan ditutup, dan kata penutup adalah tempat markah bagi binaan tersebut diperiksa.
• Tidak mewujudkan jumlah atau pengira sebelum gelung, jadi algoritma menambah kepada nilai yang tidak pernah wujud.
• Menggunakan gelung FOR apabila bilangan pengulangan tidak diketahui. Membaca sehingga nilai pengawal atau tekaan yang betul memerlukan WHILE atau REPEAT ... UNTIL.
• Menulis Age > 65 OR < 5. Setiap bahagian OR dan AND mesti merupakan perbandingan lengkap.
• Menjawab "jelaskan mengapa penguraian digunakan" dengan satu faedah ditulis tiga cara. Tiga markah memerlukan tiga faedah yang berbeza.