Algoritma
What this chapter coversMatlamat bab ini
- Murid boleh menulis pseudokod dan melukis carta alir menggunakan struktur kawalan pilihan bersarang dalam penyelesaian masalah (2.1.1 (i))
- Murid boleh menulis pseudokod dan melukis carta alir menggunakan struktur kawalan ulangan for dan while dalam penyelesaian masalah (2.1.1 (ii))
- Murid boleh mengesan dan membaiki ralat yang terdapat dalam pseudokod dan carta alir dalam penyelesaian masalah (2.1.2)
- Murid boleh menyelesaikan masalah menggunakan pseudokod dan carta alir dengan menggabungkan pelbagai struktur kawalan (2.1.3)
2.1Pembangunan algoritma
Dalam hidup harian, banyak perkara melibatkan pilihan dan ulangan: lampu isyarat yang sentiasa bertukar, pusingan kereta di litar F1, atau tarian sumazau. Semuanya boleh ditulis sebagai algoritma. Bab ini mengajar anda menulis algoritma dengan struktur kawalan dan menyemak sama ada algoritma itu betul.
Pengatur cara membangunkan algoritma sebelum menulis atur cara dalam bahasa pengaturcaraan. Pada peringkat ini, pengatur cara tidak perlu tahu bagaimana komputer akan melaksanakan arahan. Algoritma ialah salah satu teknik utama dalam pemikiran komputasional.
Contoh algoritma harian: peraturan menggunakan jalan raya, membakar kek dan menanam pokok (ms. 40).
Cara mewakili algoritma
Algoritma diwakili dalam dua bentuk (Peta Konsep, ms. 70):
| Bentuk | Maksud |
|---|---|
| Pseudokod | Algoritma ditulis dengan ayat pendek dan kata kunci seperti Mula, Jika, while. Tiada sintaks bahasa pengaturcaraan. |
| Carta alir | Algoritma dilukis dengan simbol dan anak panah. |
| Kata kunci | Maksud |
|---|---|
Mula, Tamat | Algoritma bermula dan berakhir. |
Isytihar pemboleh ubah | Menamakan pemboleh ubah yang akan digunakan. |
Setkan | Memberi nilai kepada pemboleh ubah (Setkan kira = 1). |
Masukkan, Baca | Menerima input daripada pengguna. |
Paparkan | Menunjukkan output. |
Kirakan | Melakukan pengiraan (Kirakan jum = jum + kira). |
Jika, Jika tidak, Tamat jika | Struktur kawalan pilihan. |
for, while | Struktur kawalan ulangan (gelung). |
Ulang langkah N | Kembali ke langkah N. |
<, <=, ==, != | Kurang daripada, kurang daripada atau sama dengan, sama dengan, tidak sama dengan. |
Tunjuk jawapanSembunyi jawapan
Struktur kawalan yang telah dipelajari
Di Tingkatan 1 anda telah belajar empat jenis struktur kawalan (Imbas kembali, ms. 41): pilihan tunggal, dwipilihan, pelbagai pilihan dan ulangan. Di Tingkatan 2 anda belajar pilihan bersarang serta dua jenis ulangan, iaitu for dan while.
2.1.1 (i) Struktur kawalan pilihan bersarang
Struktur kawalan pertama menyebabkan struktur kedua (yang terbenam) bermula. Struktur kedua dilaksanakan sehingga tamat dahulu, baharu struktur pertama tamat. Ia ibarat pintu dalam pintu: anda hanya sampai ke pintu kedua jika pintu pertama dibuka.
Contoh: mencari kek lapis Sarawak (Rajah 2.3 dan 2.4)
1Mula 2Cari kedai kek 3Masuk ke kedai kek 4Jika ada kek lapis Sarawak Semak corak kek Jika menarik Beli kek lapis Sarawak Jika Tidak Keluar dari kedai kek Jika Tidak Keluar dari kedai kek 5Tamat
Pseudokod mengikut Rajah 2.3, buku teks Asas Sains Komputer Tingkatan 2, ms. 41.
Contoh 2.1: integer positif, negatif atau sifar (ms. 43)
Integer x diuji. Jika x < 0, tandanya -. Jika x == 0, ia ialah 0. Jika tidak, tandanya +.
1Mula 2Isytihar pemboleh ubah x dan tanda 3Baca x Jika (x < 0) tanda = - Jika tidak Jika (x == 0) tanda = 0 Jika tidak tanda = + 4Tamat
Semakan meja dengan tiga nilai (dikira dengan Python). Ujian pertama ialah x < 0; ujian kedua ialah x == 0.
| x | Ujian pertama | Ujian kedua | tanda |
|---|---|---|---|
| -4 | Ya | tidak diuji | - |
| 0 | Tidak | Ya | 0 |
| 9 | Tidak | Tidak | + |
< dan <= yang tertukar.Menyelesaikan masalah: sistem kad bayaran elektronik (Rajah 2.5 hingga 2.7, ms. 44 hingga 46)
Sebuah sekolah menggunakan kad bayaran. Dua syarat disemak: tempoh sah laku kad dan nilai kad (sekurang-kurangnya RM5.00). Buku teks menunjukkan tiga langkah membangunkan algoritma:
| Langkah | Apa yang dilakukan |
|---|---|
| 1 Penyiasatan | Kenal pasti proses: semak sah laku, semak nilai minimum, laksanakan atau batalkan transaksi. |
| 2 Mendraf algoritma dan semakan semula | Tulis draf proses dan keputusan, kemudian periksa logiknya. |
| 3 Memurnikan langkah-langkah algoritma | Tulis langkah akhir yang tepat (Rajah 2.5). |
1Mula 2Baca kad 3Jika kad sah digunakan Periksa nilai minimum kad Jika nilai minimum mencukupi Paparkan "Jalankan urus niaga" Jika tidak Paparkan "Tambah nilai" Tamat jika Jika tidak Paparkan "Kad ditolak" 4Tamat jika 5Tamat
Pseudokod mengikut Rajah 2.6, buku teks Asas Sains Komputer Tingkatan 2, ms. 46.
Jika mesti diakhiri dengan Tamat jika di tempat yang betul. Kalau tidak, ralat akan timbul dalam skrip (Tip, ms. 46). Dalam pseudokod di atas ada dua Jika, maka ada dua Tamat jika.Aktiviti 2.1: komisen jurujual (ms. 44), cadangan jawapan nota ini
Komisen bergantung pada jumlah jualan sebulan: kurang daripada RM400 = 7.0%; RM400 hingga kurang daripada RM750 = 10.0%; RM750 hingga kurang daripada RM1000 = 12.5%; RM1000 ke atas = 16.0%. Pilihan bersarang menguji dari kecil ke besar:
Baca jualan
Jika (jualan < 400)
komisen = 7.0
Jika tidak
Jika (jualan < 750)
komisen = 10.0
Jika tidak
Jika (jualan < 1000)
komisen = 12.5
Jika tidak
komisen = 16.0
Paparkan komisen
Semakan: jualan RM350 memberi 7.0%; RM400 memberi 10.0% (bukan 7.0% kerana 400 tidak kurang daripada 400); RM820 memberi 12.5% iaitu RM102.50; RM1000 memberi 16.0% iaitu RM160.00.
tanda jika x = 0? Mengapa x == 0 tidak diuji apabila x = -4?
Tunjuk jawapanSembunyi jawapan
x < 0 benar, jadi struktur kedua (yang terbenam dalam Jika tidak) tidak dimulakan.2.1.1 (ii) Struktur kawalan ulangan
Tarian sumazau dan lampu isyarat ialah contoh ulangan. Dalam algoritma tarian sumazau (Rajah 2.8, ms. 48), langkah 6, 10 dan 12 memberitahu ulangan bagi jujukan langkah yang berlainan: "ulang langkah 2 hingga 5 sebanyak lima kali", "ulang langkah 7 hingga 9 sebanyak 10 kali" dan "ulang langkah 7 hingga 11 sehingga muzik tamat".
Lampu isyarat (Contoh 2.2, ms. 50): lampu hijau menyala 60 saat, kuning 10 saat, merah 40 saat, kemudian ulang semula selagi sistem berfungsi. Sistem ini diperiksa untuk kerosakan lampu; jika ada kerosakan, algoritma tamat.
Dalam pengaturcaraan, ulangan menjimatkan kerja: kod yang serupa tidak perlu ditulis berkali-kali, dan penambahbaikan hanya dibuat pada satu segmen kod. Dua struktur kawalan ulangan yang kerap digunakan ialah for dan while.
Struktur kawalan ulangan for
1Isytihar pembilang. 2Syarat diuji. Jika benar Pernyataan yang berulang dilaksanakan. Kemas kini pembilang for. Jika tidak benar Atur cara keluar dari struktur kawalan ulangan for. 3Ulangi langkah 2 sehingga syarat menjadi tidak benar.
Rangka umum mengikut Rajah 2.11, buku teks Asas Sains Komputer Tingkatan 2, ms. 52.
Contohnya, pembilang bermula 0 dan syarat "pembilang < 10" membuat pernyataan berulang 10 kali (Rajah 2.12 dan 2.13, ms. 52): nilai 0, 1, 2 hingga 9 lulus ujian, manakala 10 tidak.
Contoh 2.3: hasil tambah 1 hingga n (ms. 53 dan 54)
Pengguna memasukkan nombor n. Atur cara menjumlahkan 1 + 2 + 3 + ... + n. Tiga pemboleh ubah digunakan: nom (n), kira (pembilang) dan jum (hasil tambah).
1Mula 2Isytihar pemboleh ubah nom, kira, jum 3Setkan nilai kira kepada 1 4Setkan nilai jum kepada 0 5Masukkan satu nombor 6Setkan nilai nom kepada nombor yang dimasukkan 7for kira <= nom Kirakan jum = jum + kira Kirakan kira = kira + 1 8Paparkan nilai jum 9Tamat
Pseudokod mengikut Contoh 2.3, buku teks Asas Sains Komputer Tingkatan 2, ms. 54.
Semakan meja bagi nom = 5 (dikira dengan Python; buku menggunakan nom = 10). Ujian syarat ialah kira <= 5.
| Lelaran | kira sebelum | Ujian syarat | jum selepas | kira selepas |
|---|---|---|---|---|
| 1 | 1 | Ya | 1 | 2 |
| 2 | 2 | Ya | 3 | 3 |
| 3 | 3 | Ya | 6 | 4 |
| 4 | 4 | Ya | 10 | 5 |
| 5 | 5 | Ya | 15 | 6 |
| Ujian | 6 | Tidak | Gelung berhenti. Paparkan jum = 15. | |
Untuk nom = 10, jum bertambah 1, 3, 6, 10, 15, 21, 28, 36, 45, 55 dan gelung berhenti apabila kira = 11. Output ialah 55. Penerangan buku (ms. 55) berhenti apabila kira = 11, sama seperti di sini.
for kira <= nom berjalan nom kali apabila kira bermula 1. Selepas gelung tamat, pembilang sentiasa satu lebih besar daripada nilai terakhir yang lulus syarat.Tunjuk jawapanSembunyi jawapan
Struktur kawalan ulangan while
| for | while | |
|---|---|---|
| Bilangan ulangan | Ditetapkan (diketahui) | Tidak diketahui; bergantung sama ada syarat dipenuhi |
| Kawalan | Pembilang yang berubah setiap ulangan | Syarat yang diuji, contohnya input pengguna |
| Ujian syarat | Sebelum pernyataan berulang dilaksanakan (sama untuk kedua-duanya) | |
| Contoh | Cetak ayat 10 kali | Terima nama sehingga ruang kosong |
Struktur while digunakan dalam pelbagai bahasa pengaturcaraan seperti Scratch, C, C++, Java dan Python (Fakta segera, ms. 56). Rajah 2.15 dan 2.16 menunjukkan algoritma yang menerima dan mencetak nama yang ditaip selagi nama itu bukan ruang kosong.
Contoh 2.4: jumlah sehingga pengguna menaip 0 (ms. 57 hingga 59)
1Mula 2Isytihar pemboleh ubah jumlah dan nombor 3Setkan jumlah = 0 4Setkan nombor = 0 5Paparkan mesej "Masukkan nombor:" 6Setkan nombor = nombor yang dimasukkan 7while nombor != sifar Kirakan jumlah = jumlah + nombor Ulang langkah 5 8Paparkan jumlah 9Tamat
Pseudokod mengikut Contoh 2.4, buku teks Asas Sains Komputer Tingkatan 2, ms. 58.
!= bermaksud tidak sama dengan. Syarat nombor != sifar bermaksud selagi nombor tidak bersamaan dengan sifar, pernyataan dalam gelung while akan dilaksanakan (Tip, ms. 58).
Semakan meja jika pengguna menaip 4, 7, 2, 0 (dikira dengan Python). Ujian syarat ialah nombor != 0.
| Nombor dimasukkan | Ujian syarat | jumlah selepas |
|---|---|---|
| 4 | Ya | 4 |
| 7 | Ya | 11 |
| 2 | Ya | 13 |
| 0 | Tidak, gelung berhenti | 13 |
Output ialah 13. Nombor 0 ialah penanda untuk berhenti; ia tidak ditambah ke jumlah.
while, sesuatu mesti berubah di dalam gelung (di sini, nombor baharu dibaca semula). Jika tiada apa-apa yang mengubah syarat, gelung tidak akan berhenti.for atau while: (a) mencetak "Saya sihat" 6 kali; (b) membaca markah murid satu demi satu sehingga guru menaip -1.
Tunjuk jawapanSembunyi jawapan
2.1.2 Mengesan dan membaiki ralat dalam pseudokod dan carta alir
Atur cara ditulis untuk menghasilkan output yang dijangka. Kadang-kadang ia memberi output yang tidak dijangka, berhenti tiba-tiba atau berulang tanpa henti. Maka atur cara itu mempunyai ralat.
| Jenis ralat | Ciri |
|---|---|
| Ralat sintaks | Kesilapan dalam penggunaan bahasa pengaturcaraan, seperti kesilapan ejaan atau tatabahasa. Ada mesej ralat semasa atur cara dilaksanakan. |
| Ralat masa larian | Atur cara terhenti tiba-tiba semasa jalanan ujian (test run). Sebabnya boleh jadi memori tidak mencukupi, virus atau perisian hasad. |
| Ralat logik | Atur cara memberi output yang tidak dijangka, misalnya urutan tindakan salah atau syarat ditulis salah. Sebab utama ialah kecuaian. Tiada mesej ralat, maka sukar dikesan. |
Ralat logik dikesan dengan dua teknik manual, iaitu semakan meja (desk check) dan langkah demi langkah (step through). Kedua-duanya menggunakan kertas dan pensel, satu set sampel data input dan semakan terhadap output yang dijana (ms. 60).
Contoh 2.5 dan 2.6: senarai nombor menaik (ms. 61 hingga 63)
Murni menulis atur cara yang menyenaraikan nombor menaik bermula daripada nombor yang dimasukkan, naik 5 setiap kali. Dia mahu senarai berhenti pada 45 apabila nombor permulaan ialah 20.
1Mula 2Isytihar pemboleh ubah k = 0 3Paparkan mesej "Masukkan nombor yang bermula:" 4Setkan nilai k = nombor yang dimasukkan 5while k <= 50 Paparkan k k = k + 5 6Tamat
Dengan input 20, Murni menyemak dengan kertas dan pensel. Ujian syarat ialah k <= 50. Dia mendapati output memaparkan 50 yang tidak dikehendaki:
| Langkah | k dipaparkan | k selepas k = k + 5 | Ujian syarat |
|---|---|---|---|
| 1 | 20 | 25 | Ya |
| 2 | 25 | 30 | Ya |
| 3 | 30 | 35 | Ya |
| 4 | 35 | 40 | Ya |
| 5 | 40 | 45 | Ya |
| 6 | 45 | 50 | Ya (50 <= 50) |
| 7 | 50 | 55 | Tidak |
Ini ialah ralat logik: syarat ulangan k <= 50 tidak tepat. Syarat yang dibaiki ialah k <= 45. Semakan meja kali kedua memberi 20, 25, 30, 35, 40, 45 dan gelung berhenti kerana 50 tidak kurang daripada atau sama dengan 45.
Aktiviti 2.5: carta alir sifir (ms. 64), tafsiran nota ini
Buku tidak memberi jawapan bagi aktiviti ini. Bahagian di bawah ialah tafsiran nota ini, bukan jawapan buku teks.
Carta alir meminta nom (contoh 5), menyetkan bilang = 1, kemudian: selagi bilang < 12, lakukan nom = nom + bilang, bilang = bilang + 1, Paparkan nom. Buku berkata carta alir itu "menjana sifir" dan 12 nombor bermula daripada 5 akan dipaparkan.
Semakan meja (dikira dengan Python) dengan nom = 5 memberi output 6, 8, 11, 15, 20, 26, 33, 41, 50, 60, 71. Itu ialah 11 nombor, bukan 12, dan nombor itu bukan hasil darab 5 (sifir 5).
Tafsiran: jika "sifir" bermaksud sifir 5, output yang dikehendaki ialah 5, 10, 15, ..., 60. Dalam tafsiran itu ada dua ralat logik:
nom = nom + bilangmengubah nilai nom itu sendiri. Hasil darab ialahnom * bilangdan nom mesti kekal 5.bilang < 12berhenti pada 11, maka hanya 11 nombor dipaparkan. Syarat yang membolehkan 12 nombor ialahbilang <= 12.
Selepas dibaiki: bilang <= 12? Ya: Paparkan nom * bilang, bilang = bilang + 1. Output: 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60 (12 nombor). Guru anda mungkin menerima tafsiran lain; yang pasti ialah carta alir asal tidak memaparkan 12 nombor.
Tunjuk jawapanSembunyi jawapan
2.1.3 Menggabungkan pelbagai struktur kawalan
Masalah yang kompleks harus dileraikan kepada masalah yang lebih kecil dan mudah melalui pembentukan algoritma. Setiap penyelesaian bermula dengan rancangan, dan rancangan itu ialah algoritma (ms. 65).
Contoh: mesin membuat capati (Rajah 2.19 hingga 2.21, ms. 65 hingga 68)
Nadira menulis algoritma untuk mesin yang membuat capati. Pengguna memasukkan bahan dan menekan butang Mula; mesin mengadun bahan dan membuat capati selagi adunan masih ada. Tiga langkah digunakan:
| Langkah | Isi |
|---|---|
| 1 Penyiasatan | Input: bahan membuat adunan. Proses: mengadun bahan dan membuat capati. Output: capati. |
| 2 Mendraf algoritma | Mesin menyemak bahan; mengadun sehingga sebati; membuat capati selagi adunan ada; paparkan jumlah capati; pengguna menyemak sama ada jumlah mencukupi. |
| 3 Memurnikan langkah-langkah | Tulis tujuh langkah akhir (Rajah 2.19) dan wakilkan sebagai pseudokod (Rajah 2.20) dan carta alir (Rajah 2.21). |
1Mula 2Sediakan bahan. Jika ada, masukkan bahan ke dalam mesin. Hidupkan mesin. Jika tidak, sediakan bahan dahulu. Ulang Langkah 2. 3Semak bahan. Jika ada, mula mengadun bahan. Jika tidak, paparkan mesej "Sila masukkan bahan". Ulang Langkah 2. 4Semak mencapai masa tamat mengadun. Jika ya, mula membuat capati. Jika tidak, terus mengadun bahan. Ulang Langkah 4. 5Semak adunan habis. Jika ya, paparkan jumlah capati yang dihasilkan. Jika tidak, terus membuat capati. Ulang Langkah 5. 6Semak jumlah capati. Jika mencukupi, matikan mesin. Jika tidak mencukupi, ulang Langkah 2. 7Tamat
Pseudokod mengikut Rajah 2.20, buku teks Asas Sains Komputer Tingkatan 2, ms. 67.
Cari struktur kawalan dalam algoritma ini:
| Struktur | Di mana dalam algoritma |
|---|---|
| Pilihan (Jika ... Jika tidak) | Bahan tersedia? Semak bahan? |
Ulangan while | Terus mengadun sehingga masa tamat; terus membuat capati selagi adunan belum habis |
| Ulangan keseluruhan proses | Jika jumlah capati tidak cukup, ulang dari langkah 2 |
Aktiviti 2.6: lesen memandu Kelas D (ms. 68 dan 69)
Algoritma lesen memandu mempunyai syarat umur, ujian buta warna, ujian teori, 10 jam belajar memandu, ujian praktikal dan tempoh PDL selama dua tahun. Petunjuk daripada nota ini (bukan daripada buku): setiap "Jika lulus ... Jika tidak lulus, ulangi ujian" ialah satu ulangan while (ulang selagi belum lulus), manakala "Jika tidak lulus, tidak dibenarkan" ialah satu pilihan. Tulis pseudokod dahulu, kemudian lukis carta alir dan semak dengan sampel data (misalnya umur 16, 17 dan 18).
Tunjuk jawapanSembunyi jawapan
Ringkasan bab
| Konsep | Ingat |
|---|---|
| Algoritma | Langkah demi langkah yang tersusun; diwakili oleh pseudokod dan carta alir. |
| Pilihan bersarang | Struktur pilihan di dalam struktur pilihan; setiap Jika ada Tamat jika. |
| Ulangan for | Bilangan ulangan ditetapkan oleh pembilang. |
| Ulangan while | Berulang selagi syarat benar; bilangan ulangan tidak diketahui. |
| Ralat sintaks | Salah bahasa; ada mesej ralat. |
| Ralat masa larian | Atur cara terhenti tiba-tiba. |
| Ralat logik | Output salah; tiada mesej; dikesan dengan semakan meja atau langkah demi langkah. |
i sahaja atau pembilang sahaja.