Array algorithms: max, count, search, average
Common array jobs
- Some array tasks come up again and again: find the sum, the biggest, the smallest, or count items.
- Each one uses the same idea: start with a guess, then loop and update it.
- These patterns appear all the time on the AP CSA exam.
งาน Array ที่พบบ่อย
- บางงาน Array มาซ้ำๆ: หา ผลรวม, ค่ามากที่สุด, ค่าน้อยที่สุด, หรือ นับ รายการ
- ทุกอย่างใช้แนวคิดเดียวกัน: เริ่มต้นด้วยการเดา, แล้วลูปและอัปเดต
- รูปแบบเหล่านี้ปรากฏตลอดเวลาในการสอบ AP CSA
Sum and count
- Keep a running total that starts at 0, and add each value.
- To count items that pass a test, start a counter at 0 and add 1 when the test is true.
- Below we count how many values are even (
v % 2 == 0).
ผลรวมและนับ
- เก็บ ผลรวมสะสม ที่เริ่มที่ 0, และเพิ่ม every value
- เพื่อ นับ รายการที่ผ่าน test, เริ่มต้น counter ที่ 0 และเพิ่ม 1 เมื่อ test เป็นจริง
- ด้านล่างนี้ เรานับ有多少 values เป็นคู่ (
v % 2 == 0)
public class Main {
public static void main(String[] args) {
int[] a = {3, 4, 7, 10};
int evens = 0;
for (int v : a) {
if (v % 2 == 0) {
evens = evens + 1;
}
}
System.out.println(evens); // 2
}
}
Find the maximum
- Start by guessing the first value is the biggest:
int max = a[0];. - Loop through the rest. If a value is bigger than
max, make it the newmax. - This works for negative numbers too, because the guess comes from the array itself.
หาค่าสูงสุด
- เริ่มต้นด้วยการเดาว่า ค่าแรก คือค่าที่ใหญ่ที่สุด:
int max = a[0];. - ลูปผ่านส่วนที่เหลือ ถ้ามีค่าไหนใหญ่กว่า
maxให้เปลี่ยนเป็นmaxใหม่ - วิธีนี้ใช้กับเลขติดลบได้ด้วย เพราะค่าเริ่มต้นมาจากตัว-array เอง
public class Main {
public static void main(String[] args) {
int[] a = {3, 9, 2, 7};
int max = a[0];
for (int i = 1; i < a.length; i++) {
if (a[i] > max) {
max = a[i];
}
}
System.out.println(max); // 9
}
}
Find the minimum
- The minimum uses the same shape — just flip the test to
<. - Start with
int min = a[0];and keep the smallest value you see. - Never start
minat 0; a real value from the array is a safe first guess.
หาค่าต่ำสุด
- สิ่งต่ำสุดจะใช้รูปทรงเดียวกัน เพียงแค่เปลี่ยนการทดสอบเป็น
< - เริ่มต้นด้วย
int min = a[0];และเก็บค่าที่น้อยที่สุดที่เราพบไว้ - ห้ามเริ่ม
minที่ 0; ควรใช้ค่าจริงจาก array เพื่อเป็นการเดาเริ่มต้นที่ปลอดภัย
public class Main {
public static void main(String[] args) {
int[] a = {3, 9, 2, 7};
int min = a[0];
for (int i = 1; i < a.length; i++) {
if (a[i] < min) {
min = a[i];
}
}
System.out.println(min); // 2
}
}
Search for a value
- To find where a value is, loop the index and compare each element.
- Return the index as soon as you find it.
- If the loop finishes with no match, return
-1to mean "not found".
ค้นหาค่า在某处
- เพื่อหาว่า ตำแหน่ง ของค่าคือที่ไหน ให้ลูปตามดัชนีและเปรียบเทียบแต่ละองค์ประกอบ
- ดัชนีทันทีที่พบค่าที่ต้องการ
- หากลูปจบลงโดยไม่พบค่าให้คืน
-1เพื่อสื่อว่า "ไม่พบ"
public class Main {
public static void main(String[] args) {
int[] a = {5, 8, 13, 21};
int target = 13;
int found = -1;
for (int i = 0; i < a.length; i++) {
if (a[i] == target) {
found = i;
break; // stop at the first match
}
}
System.out.println(found); // 2
}
}
Average
- Average = sum divided by count. The count is
a.length. - To get a decimal, divide by
(double) a.length, so the math is not integer division. (double)turns the length into a decimal before the division.
ค่าเฉลี่ย
- ค่าเฉลี่ย = ผลรวมหารด้วยจำนวน ตัวเลขของจำนวนคือ
a.length - เพื่อให้ได้ผลลัพธ์ทศนิยม ให้หารด้วย
(double) a.lengthเพื่อไม่ให้เป็นการหารจำนวนเต็ม (integer division) (double)จะแปลงความยาวให้เป็นทศนิยมก่อนทำการหาร
public class Main {
public static void main(String[] args) {
int[] a = {2, 3, 10};
int total = 0;
for (int v : a) {
total = total + v;
}
double avg = total / (double) a.length;
System.out.println(avg); // 5.0
}
}
Common mistakes
- Start a max or min from the first element, then compare the rest.
- Do not read past
a.length - 1.
ข้อผิดพลาดที่พบบ่อย
- เริ่มหาค่าสูงสุดหรือต่ำสุดจากองค์ประกอบแรก แล้วจึงเปรียบเทียบส่วนที่เหลือ
- อย่าอ่านข้อมูลเกิน
a.length - 1
Now you try
- Each task completes a method the Harness calls with several arrays.
- Reuse the patterns above: a running total, a "best so far", or a counter.
- Press Run to compile, then Check answer.
ลองดูเลย
- แต่ละงานจะสมบูรณ์เมื่อเรียกใช้ method ที่ Harness เรียกด้วย array หลายชุด
- นำรูปแบบข้างต้นกลับมาใช้ใหม่: ผลรวมสะสม, ค่าที่ดีที่สุดเท่าที่เห็น, หรือตัวนับ
- กด Run เพื่อคอมไพล์ แล้วกด Check answer
Scanning an array for the max · การ scan array เพื่อหาค่า max
One pass keeps a running max, updating it when a bigger value appears. · การทำรอบเดียวเก็บค่า running max, อัปเดตเมื่อเจอค่าที่ใหญ่กว่า.
Complete max(int[] a) so it returns the largest value in the array. You may assume the array has at least one value. It must work with negative numbers too. · เติม max(int[] a) ให้สมบูรณ์เพื่อให้กลับคืนค่าที่ใหญ่ที่สุดใน array. คุณสามารถสันนิษฐานได้ว่า array มีอย่างน้อยหนึ่งค่า. มันต้องทำงานได้กับตัวเลขติดลบด้วย.
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่
Complete countEven(int[] a) so it returns how many values are even. A value is even when v % 2 == 0. An empty array returns 0. · เติม countEven(int[] a) ให้สมบูรณ์เพื่อให้กลับคืนว่ามีค่าคู่กี่ตัว. ค่าเป็น偶数เมื่อ v % 2 == 0. Arrayว่างกลับคืน 0.
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่
Complete indexOf(int[] a, int target). Return the index of the first time target appears. If it is not in the array, return -1. · เติม indexOf(int[] a, int target) ให้สมบูรณ์. กลับคืน index ของครั้งแรกที่ target ปรากฏ. หากมันไม่อยู่ใน array, กลับคืน -1.
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่
Complete average(int[] a). Return the average of the values as a double. Divide by (double) a.length so you get a decimal, not integer division. You may assume the array is not empty. · เติม average(int[] a) ให้สมบูรณ์. กลับคืนค่าเฉลี่ยของค่าต่างๆ เป็น double. หารด้วย (double) a.length เพื่อให้ได้เลขทศนิยม ไม่ใช่ integer division. สามารถสันนิษฐานได้ว่า array ไม่ว่าง.
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่