Array algorithms: max, count, search, average
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.
งานคลาสสิกของอาร์เรย์สี่อย่าง
- งานกับอาร์เรย์ส่วนใหญ่เป็นหนึ่งในการสแกนสี่แบบ: หา ค่าสูงสุด, นับ จำนวนตรงกัน, ค้นหา ค่า หรือหา ค่าเฉลี่ย
- แต่ละอย่างเป็นการวนลูป
forเดียวบนอาร์เรย์ พร้อมตัวแปรที่จดจำสิ่งบางอย่างไว้ - เมื่อคุณรู้เรื่องสี่อย่างนี้แล้ว ปัญหาส่วนใหญ่เกี่ยวกับอาร์เรย์ก็เพียงการปรับเล็กน้อยจากหนึ่งในสี่สิ่งนี้
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.
การหาค่าสูงสุด
- เริ่มต้นด้วยการสันนิษฐานว่า รายการแรก เป็นargest:
int best = a[0]; - จากนั้นดูรายการที่เหลือ ถ้ารายการไหนมีค่ามากกว่า
bestมันจะกลายเป็นbestใหม่ - วิธีนี้ใช้ได้กับเลขลบด้วย เพราะเราเริ่มจากรายการจริง ไม่ใช่
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.
Counting with a condition
- เคาน์เตอร์ เริ่มที่
0และเพิ่ม1ทุกครั้งที่รายการผ่านเงื่อนไข - เช่นตัวอย่าง นับเลขคู่โดยการทดสอบ
a[i] % 2 == 0ภายในวนลูป - ค่าสุดท้ายของเคาน์เตอร์คือคำตอบของคุณ
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.
การค้นหาแบบเชิงเส้น
- เพื่อ ค้นหา ให้เดินผ่านอาร์เรย์และเปรียบเทียบแต่ละรายการกับเป้าหมาย
- คืนค่า ดัชนี ทันทีที่พบการจับคู่ ถ้าวนลูปจบโดยไม่พบ ให้คืนค่า
-1 -1เป็นสัญญาณ "ไม่พบ" ที่นิยมใช้เพราะมันไม่เคยเป็นดัชนีที่ถูกต้อง
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.
ค่าเฉลี่ยโดยไม่เกิดข้อผิดพลาดจากการหารจำนวนเต็ม
- รวมรายการทั้งหมดลงในผลรวม
intแล้วหารด้วยn - การหาร
intสองตัวจะทำให้ทศนิยมหายไป ดังนั้นต้อง cast:(double)total / n - คืนค่า
doubleเพื่อให้ผู้เรียกได้รับค่าเฉลี่ยที่แม่นยำ
Common mistakes
- Start a max or min from the first element, then compare the rest.
- Do not read past the end of the 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.
ลองดูเลย
- ส่งอาร์เรย์และความยาว
n之给它，并为每项工作选择正确的“remember”变量 - อย่า เขียน
main— ตัวตรวจสอบจะจัดเตรียมให้
Scanning an array
One pass keeps a running result (max, sum, count) across the array. · การวนซ้ำครั้งเดียวเก็บ ผลสะสม (max, sum, count) Across 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. · เติม int max(const int a[], int n) เพื่อให้ส่งค่าสูงสุด (สมมติว่า n >= 1) เริ่มจาก a[0] เพื่อรองรับค่าลบ ห้าม เขียน main
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่
Complete int count_even(const int a[], int n) so it returns how many items are even. Use % 2. Do not write a main. · เติม int count_even(const int a[], int n) นับจำนวนอู่ Even ใช้ % 2 ห้าม เขียน main
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่
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. · เติม int index_of(const int a[], int n, int target) ส่งค่า index ของ target ตัวแรก หรือ -1 ถ้าไม่มี ห้าม เขียน main
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่
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. · เติม double average(const int a[], int n) ส่งค่าเฉลี่ยของรายการ (สมมติว่า n >= 1) Cast เป็น float เพื่อหลีกเลี่ยงการหารจำนวนเต็ม ห้าม เขียน main
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่