Array algorithms: max, count, search, average · Algoritma array: maksimum, hitung, cari, rata-rata
Four classic array jobs
- Most array work is one of four scans: find the maximum, count matches, search for a value, or take an average.
- Each one is a single
forloop over the array, with a variable that remembers something. - Once you know these four, most array problems are a small change to one of them.
Empat pekerjaan array klasik
- Sebagian besar pekerjaan array adalah salah satu dari empat pemindaian: cari maksimum, hitung kecocokan, cari nilai, atau ambil rata-rata.
- Masing-masing adalah satu loop
foratas array, dengan variabel yang mengingat sesuatu. - Setelah Anda tahu keempat ini, sebagian besar masalah array hanyalah perubahan kecil dari salah satu dari mereka.
Finding the maximum
- Start by assuming the first item is the biggest:
int best = a[0];. - Then look at the rest. If an item is bigger than
best, it becomes the newbest. - This works for negative numbers too, because you start from a real item, not
0.
Mencari maksimum
- Mulailah dengan mengasumsikan item pertama adalah terbesar:
int best = a[0];. - Kemudian lihat sisanya. Jika sebuah item lebih besar dari
best, itu menjadibestbaru. - Ini bekerja untuk angka negatif juga, karena Anda mulai dari item nyata, bukan
0.
Counting with a condition
- A counter starts at
0and adds1each time an item passes a test. - For example, count even numbers by testing
a[i] % 2 == 0inside the loop. - The counter's final value is your answer.
Menghitung dengan kondisi
- Counter dimulai dari
0dan menambahkan1setiap kali item melewati uji. - Sebagai contoh, hitung angka genap dengan menguji
a[i] % 2 == 0di dalam loop. - Nilai akhir counter adalah jawaban Anda.
Linear search
- To search, walk the array and compare each item to the target.
- Return the index as soon as you find a match. If the loop ends with no match, return
-1. -1is a common "not found" signal because it is never a valid index.
Pencarian linear
- Untuk mencari, jelajahi array dan bandingkan setiap item dengan target.
- Kembalikan index segera setelah Anda menemukan kecocokan. Jika loop berakhir tanpa kecocokan, kembalikan
-1. -1adalah sinyal "tidak ditemukan" umum karena tidak pernah merupakan index yang valid.
Average without integer-division bugs
- Add all the items into an
inttotal, then divide byn. - Dividing two
ints drops the fraction, so cast:(double)total / n. - Return a
doubleso the caller gets the exact average.
Rata-rata tanpa bug pembagian bilangan bulat
- Jumlahkan semua item ke dalam total
int, lalu bagi dengann. - Membagi dua
intakan membuang pecahan, jadi cast:(double)total / n. - Kembalikan
doubleagar pemanggil mendapatkan rata-rata yang tepat.
Common mistakes
- Start a max or min from the first element, then compare the rest.
- Do not read past the end of the array.
Kesalahan umum
- Mulai max atau min dari elemen pertama, lalu bandingkan sisanya.
- Jangan baca melebihi akhir array.
Now you try
- Pass the array and its length
n, and pick the right "remember" variable for each job. - Do not write a
main— the checker provides one.
Sekarang Anda coba
- Teruskan array dan panjangnya
n, dan pilih variabel "remember" yang tepat untuk setiap pekerjaan. - Jangan tulis
main— checker menyediakannya.
Scanning an array · Mescan array
One pass keeps a running result (max, sum, count) across the array. · Satu kali lintasan mempertahankan hasil berjalan (maksimum, jumlah, hitungan) melintasi seluruh array.
Complete int max(const int a[], int n) so it returns the largest item (assume n >= 1). Start from a[0] so negatives work. Do not write a main. · Lengkapi int max(const int a[], int n) agar mengembalikan item terbesar (asumsikan n >= 1). Mulai dari a[0] agar nilai negatif dapat diproses. Jangan tulis main.
Click Run to see the output here. · Klik Jalankan untuk melihat output di sini.
Complete int count_even(const int a[], int n) so it returns how many items are even. Use % 2. Do not write a main. · Lengkapi int count_even(const int a[], int n) agar mengembalikan jumlah item genap. Gunakan % 2. Jangan tulis main.
Click Run to see the output here. · Klik Jalankan untuk melihat output di sini.
Complete int index_of(const int a[], int n, int target) so it returns the index of the first target, or -1 if it is not there. Do not write a main. · Lengkapi int index_of(const int a[], int n, int target) agar mengembalikan indeks pertama dari target, atau -1 jika item tersebut tidak ditemukan. Jangan tulis main.
Click Run to see the output here. · Klik Jalankan untuk melihat output di sini.
Complete double average(const int a[], int n) so it returns the average of the items (assume n >= 1). Cast to avoid integer division. Do not write a main. · Lengkapi double average(const int a[], int n) agar mengembalikan rata-rata dari semua item (asumsikan n >= 1). Lakukan cast untuk menghindari pembagian bilangan bulat. Jangan tulis main.
Click Run to see the output here. · Klik Jalankan untuk melihat output di sini.