Untuk mencari maksimum sesuatu senarai, simpan satu pemboleh ubah yang memegang nilai terbesar yang dilihat setakat ini dan bandingkan setiap item lain dengannya. Setiap kali satu item lebih besar, ia menggantikan nilai yang disimpan.
Pelajaran ini menggunakan gelung daripada menjejak gelung terkawal bilangan pada tatasusunan. Ia berada dalam pengulangan dan tatasusunan, dan corak yang sama menghasilkan minimum, kiraan dan jumlah.
Apakah langkahnya?
- Tetapkan
Maxkepada item pertama dalam senarai. - Gelung melalui item yang tinggal, dari kedudukan 2 hingga kedudukan terakhir.
- Jika item semasa lebih besar daripada
Max, salin ke dalamMax. - Selepas gelung,
Maxmemegang nilai terbesar.
Contoh penyelesaian
Tatasusunan Scores[1:6] menyimpan 35, 48, 22, 48, 51, 40.
Max ← Scores[1]
FOR i ← 2 TO 6
IF Scores[i] > Max
THEN
Max ← Scores[i]
ENDIF
NEXT i
OUTPUT MaxMax bermula sebagai 35.
| i | Scores[i] | Scores[i] > Max? | Max selepas |
|---|---|---|---|
| 2 | 48 | 48 > 35 benar | 48 |
| 3 | 22 | 22 > 48 palsu | 48 |
| 4 | 48 | 48 > 48 palsu | 48 |
| 5 | 51 | 51 > 48 benar | 51 |
| 6 | 40 | 40 > 51 palsu | 51 |
Outputnya ialah 51. Kedudukan 4 menyimpan nilai yang sama, 48, dan tidak menggantikan Max kerana 48 > 48 palsu.
Untuk turut melaporkan di mana maksimum itu, simpan kedudukan juga:
Max ← Scores[1]
MaxPos ← 1
FOR i ← 2 TO 6
IF Scores[i] > Max
THEN
Max ← Scores[i]
MaxPos ← i
ENDIF
NEXT i
OUTPUT MaxPos, MaxBagi data yang sama, MaxPos berubah pada i = 2 dan i = 5. Outputnya ialah 5, 51.
Kesilapan yang perlu diawasi
Kesilapan biasa ialah memulakan dengan Max ← 0.
Algoritma yang salah:
Max ← 0, kemudian bandingkan setiap item termasuk yang pertama.Dengan suhu -5, -2 dan -9, tiada nilai lebih besar daripada 0, jadi algoritma mengeluarkan 0. Nilai itu tiada dalam senarai.
Pembetulannya ialah Max ← Temps[1], kemudian gelung dari kedudukan 2. Jejaknya: Max ialah -5, kemudian -2 > -5 benar jadi Max menjadi -2, kemudian -9 > -2 palsu. Outputnya -2, yang betul.
Semak sendiri
1. Jejak algoritma pada data 8, 3, 12, 12, 5. Apakah Max selepas setiap item?
Lihat jawapan
Mulakan dengan 8. Kemudian 3 > 8 palsu (8), 12 > 8 benar (12), 12 > 12 palsu (12), 5 > 12 palsu (12). Nilai akhir ialah 12.
2. Simbol tunggal yang manakah berubah untuk mencari minimum bagi data yang sama, dan apakah keputusannya?
Lihat jawapan
Tukar > kepada <. Mulakan dengan 8, kemudian 3 < 8 benar (3), kemudian 12, 12 dan 5 tidak kurang daripada 3. Minimumnya 3.
3. Bagi data 6, 9, 9, 2 dalam Data[1:4], apakah kedudukan yang diberi versi kedudukan, dan apa yang berubah dengan >=?
Lihat jawapan
Dengan >, 9 pada kedudukan 2 disimpan dahulu, dan 9 yang kedua tidak menggantikannya, jadi kedudukannya 2. Dengan >=, 9 yang kedua menggantikannya, jadi kedudukannya 3. Nilainya 9 dalam kedua-dua kes.
Seterusnya
Seterusnya, perhatikan dengan teliti apa maksud pemboleh ubah gelung i berbanding item yang ditunjuknya dalam menggunakan indeks tatasusunan tanpa mengelirukannya dengan nilai. Untuk mencuba senarai anda sendiri, gunakan kotak pasir penaakulan Python dan bandingkan keputusannya dengan jadual jejak anda.
Seorang guru dalam tuisyen Computer Science dalam talian secara satu dengan satu boleh memberi senarai yang janggal, seperti nilai negatif atau nilai berulang, supaya anda belajar meramal di mana algoritma gagal.